Режа: Формулаларнинг нормал шакллари. Дизъюнктив нормал шакл

Мисоллар. 1.


;

Шундай қилиб, формуланинг КНШ биттагина дизъюнктив ҳаддан иборат экан.
2.






формуласи тавтология эканлигини чинлик жадвалига мурожаат қилмай туриб аниқлаш мумкинми деган саволга қуйидаги чинлик аломати деб аталган теорема ижобий жавоб беради.
2-теорема. формула доимо чин бўлиши учун унинг КНШ даги ҳар бир элементар дизъюнктив ҳадида камида битта элементар мулоҳаза билан бирга бу мулоҳазанинг инкори ҳам мавжуд бўлиши зарур ва етарли.
Исбот: а) формуланинг
(5)
КНШ даги ҳар бир ҳадида камида битта элементар мулоҳаза билан бирга бу мулоҳазанинг инкори ҳам мавжуд бўлсин, яъни шаклида бўлсин, у ҳолда ва ларга асосан бўлади. Демак, бўлади, яъни айнан чин формула бўлади.
б) Энди - тавтология бўлсин ва унинг КНШ даги шундай элементар дизъюнктив ҳади бўлсинки, унда бирорта элементар мулоҳаза билан бирга унинг инкори қатнашмаган бўлсин. Масалан, шаклида бўлсин. Энди, элементар мулоҳазаларнинг шундай қийматлар сатрини олайликки, бу сатрда нинг қиймати ё, нинг қиймати ч, нинг қиймати ё,......, нинг қиймати ё бўлсин. У вақтда
ё ч ё = ё ё = ё.
Демак, нинг қиймати ҳам ёлғон бўлади. Аммо, теореманинг шартига асосан нинг қиймати айнан чиндир. Натижада қарама-қаршиликка келдик. Демак, элементар дизъюнкцияларнинг ҳар бир ҳадида бирорта мулоҳаза ўзи ва ўзининг инкори билан қатнашиши шарт.
Мисол. 1. .
- айнан чиндир.
2. - айнан чин формуладир.
2. Дизъюнктив нормал шакл

Эслатиб ўтамизки, элементар конъюнкцияларнинг дизъюнкциясига формуланинг дизъюнктив нормал шакли (ДНШ) деб айтилади.