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

3-теорема. Элементар мулоҳазаларнинг исталган формуласини ДНШга келтириш мумкин.
Исбот. Бунинг учун формулани КНШга келтирамиз:

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

Энди ёлғонлик аломати деб аталган теоремани исботлаймиз.

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