Режа: кнш ва днш мкнш ва мднш. Реле – контактли схемалар

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

ва сўнгра нинг инкорини топганимизда формула ДНШ кўринишига келади:

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