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 AB ko’rinishda yozamiz, hamda A,A formulalar uchun ushbu belgilashni kiritamiz:
A,
A
7A,
agar
agar
1
0
bыlsa bыlsa
ya’ni, A1 A, A0 7A deb hisoblaymiz.
ta’ri f:
1, 2 ,..., n
o’zgar uv chilarning har biri 0 yoki 1
qiymatlarni qabul qilganlarida
A1
i1
A2
i2
...
An ,
in
(in
1)
formulaga elementar konyunksiya deyiladi.
ta’ri f:
1, 2 ,..., n
o’zgaruvchilarning har biri0 va 1
qiymatlarni qabul qilganlarida
A1
i1
A2
i2
... An ,
in
(in
1)
formulaga elementar dizyunksiya deyiladi.
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.
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 7 A
elementar konyunksiyada A o’zgaruvchi o’zining inkori
bilan, B B C D D formulada esa B, D propozitsional o’zgaruvchilar ikki martadan qatnashmoqda.
ta’rif: Shar bir propozitsional o’zgaruvchining yo o’zi yo inkori bir martadan ortiq qatnashmagan elementar dizyunksiya to’g’ri elementar dizyunksiya deyiladi.
ta’rif:
A1 , A2 ,. , An
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, A1 , A2 ,. ,An
propozitsional o’zgaruvchilarga nisbatan to’liq elementar konyunksiya deyiladi.
ta’rif:
A1,
A2,. , An
Propozitsional o’zgaruvchilarda tashkil
topgan to’g’ri elementar dizyunksiyada, har bir o’zgaruvchi rosa bir marta
propozitsional o’zgaruvchilarga nisbatan to’liq elementar dizyunksiya deyiladi.
ta’ri f: Mulohazalar algebrasining
A1 , A2 ,. , An
propozi tsional
dizyunktiv normal forma (shakl) (MDNSH)si deb, shu formulaning tarkibida bir xil elementar konyunksiyalar bo’lmagan, hamda barcha elementar
konyunksiyalari
A1 , A2 ,. ,An
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.
ta’ri f. M ulo xazalar algebrasining
A1 , A2 ,. , An
propozitsional
o’zgaruvchilardan tashkil topgan
F(A1, A2 , , An)
formulasining mukammal
konyunktiv normal forma(shakl) (MKNSH)si deb, shu formulaning tarkibida bir
Ta’rif. Agar B1 ,B2 ,...,Bn chekli formulalar ketma-ketligining har qanday hadi quyidagi:
1)H formulalar majmuasining birorta formulasi;
2) isbotlanuvchi formula;
3) B1 ,B2 ,...,B2ketma-ketlikning istalgan ikkita oldinma-keyin keladigan elementlaridan xulosa qoidasiga asosan hosil qilinadi degan uch shartning birortasini qanoatlantirsa, u holda bu ketma-ketlik H chekli formulalar majmuasidan keltirib chiqarilgan deb aytiladi.
H { A, B} dan quyidagi formulalar chekli ketma-ketligi keltirilib chiqariladi:
xil elementar dizyunksiyalar bo’lmagan, hamda barcha elementar
dizyunksiyalari
A1 , A2 ,. ,An
o’zgaruvchilariga nisbatan to’g’ri va to’liq
bo’lgan KNSH siga aytiladi.
Dostları ilə paylaş: |