Buxoro davlat universiteti fizika-matematika fakulteti "matematika" kafedrasi

Dizyunktiv va konyunktiv normal formalar

Bundan keyin, yozuvni yanada soddalashtirish maqsadida, mulohazaning qiymati rostligini ifodalovchi R o’rniga 1 raqamidan, yolg’on qiymatini

ifodalovchi Yo o’rniga 0 raqamidan foydalanamiz. Ba’zi hollarda esa, A ^ B

formulani AB ko’rinishda yozamiz, hamda A,A formulalar uchun ushbu belgilashni kiritamiz:

_{ } A,



A <sub>

</sub>7A,

agar

agar

  1

  0

bыlsa bыlsa

ya’ni, A¹  A, A⁰  7A ^{deb hisoblaymiz.}

2. ta’ri f:

₁,₂ ,...,_n

o’zgar uv chilarning har biri 0 yoki 1

qiymatlarni qabul qilganlarida

_A₁

i₁

 A^2

i₂

 ... 

A^n ,

i_n

(i_n

 1)

formulaga elementar konyunksiya deyiladi.

3. ta’ri f:

₁,₂ ,...,_n

o’zgaruvchilarning har biri0 va 1

qiymatlarni qabul qilganlarida

_A₁

i₁

 A^2

i₂

 ... A^n ,

i_n

(i_n

 1)

formulaga elementar dizyunksiya deyiladi.

6. 
   ta’rif: Elementar dizyunksiyalarning har qanday konyunksiyasidan tashkil topgan formula konyunktiv normal forma (KNSH) yoki konyunktiv normal formadagi formula deyiladi.
   

Mukammal dizyunktiv va mukammal konyunktiv normal formalar.

6. 
   ta’rif: Щar bir propozi tsional o’zgar uv chining yo o’zi, yo inkori bir mar tadan or tiq qa tna shmagan elemen tar kon’yunk tsiya to’g’ri elemen tar kon’yunk tsiya deyiladi.
   

Misollar: Ta’ri fga ko’ra

A, A  B,

7A  B,

7A  B  C  D

formulalar

to’g’ri elementar konyunksiyalardir.

A  7A,

B  B  C  D  D

formulalar esa,

elementar konyunksiyalar bo’lgani holda, to’g’ri elementar konyunksiyalar

emas, chunki

A  7A

elementar konyunksiyada A o’zgaruvchi o’zining inkori

bilan, BBCDD formulada esa B, D propozitsional o’zgaruvchilar ikki martadan qatnashmoqda.

6. 
   ta’rif: Shar bir propozitsional o’zgaruvchining yo o’zi yo inkori bir martadan ortiq qatnashmagan elementar dizyunksiya to’g’ri elementar dizyunksiya deyiladi.
   

6. ta’rif:

A₁ , A₂ ,. ,A_n

Propozitsional o’zgaruvchilardan tashkil

topgan to’g’ri elementar konyunksiyada, har bir o’zgaruvchi rosa bir marta

qatnashgan bo’lsa, bu to’g’ri elementar konyunksiya, A₁ , A₂ ,. ,A_n

propozitsional o’zgaruvchilarga nisbatan to’liq elementar konyunksiya deyiladi.

6. ta’rif:

A₁,

A₂,. ,A_n

Propozitsional o’zgaruvchilarda tashkil

topgan to’g’ri elementar dizyunksiyada, har bir o’zgaruvchi rosa bir marta

qatnashgan bo’lsa, bu to’g’ri elementar dizyunksiya A₁, A₂,..,A_n

propozitsional o’zgaruvchilarga nisbatan to’liq elementar dizyunksiya deyiladi.

6. 
   ta’ri f: Mulohazalar algebrasining
   

A₁ , A₂ ,. ,A_n

propozi tsional

o’zgaruvchilardan tashkil topgan

F(A₁, A₂,. ,A_n )

formulasining mukammal

dizyunktiv normal forma (shakl) (MDNSH)si deb, shu formulaning tarkibida bir xil elementar konyunksiyalar bo’lmagan, hamda barcha elementar

konyunksiyalari

A₁ , A₂ ,. ,A_n

o’zgaruvchilarga nisbatan to’g’ri, to’liq bo’lgan

DNSH siga aytiladi.

Ta’rifga binoan, aynan yolg’on formula uchun MDNSH mavjud emas, chunki agar uning uchun MDNSH mavjud bo’ladigan bo’lsa, bunday MDNSH ning tarkibidagi har bir qo’shiluvchi elementar konyunksiya aynan yolg’on bo’lmog’i lozim. Buni bo’lishi MDNSH tarkibidagi elementar konyunksiyalarda propozitsional o’zgaruvchining ham o’zi, ham inkorini qatnashishini taqozo qiladi. Bu holat formula uchun MDNSH ta’rifidagi bir qismni bajarilmasligini bildiradi.

6. 
   ta’ri f. M ulo xazalar algebrasining
   

A₁ , A₂ ,. ,A_n

propozitsional

o’zgaruvchilardan tashkil topgan

F(A₁, A₂ , , A_n)

formulasining mukammal

konyunktiv normal forma(shakl) (MKNSH)si deb, shu formulaning tarkibida bir

xil elementar dizyunksiyalar bo’lmagan, hamda barcha elementar

dizyunksiyalari

A₁ , A₂ ,. ,A_n

o’zgaruvchilariga nisbatan to’g’ri va to’liq

bo’lgan KNSH siga aytiladi.