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

7-МАЪРУЗА. НОРМАЛ ШАКЛЛАР


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


Таянч иборалар. Элементар конъюнкция (дизъюнкция), КНШ, ДНШ, ёлғонлик аломати,
1. Формулаларнинг нормал шакллари
Тенгкучли алмаштиришлар бажариб, мулоҳазалар алгебрасининг формулаларини ҳар хил кўринишларда ёзиш мумкин. Масалан, ВС формулани ёки кўринишларда ёза оламиз.
Қуйидаги белгилашни киритамиз:

= ч эканлиги аниқ.
1-таъриф.
(1)
кўринишдаги формулага элементар конъюнкция деб айтамиз. Бу ерда ихтиёрий қийматлар сатри ва ўзгарувчилар орасида бир хиллари бўлиши мумкин.
2-таъриф.
(2)
кўринишдаги формулага элементар дизъюнкция деб айтамиз. Бу ерда ҳам ихтиёрий қийматлар сатри ва ўзгарувчилар орасида бир хиллари бўлиши мумкин.


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