2-bob mulohazalar algebrasi 1-§. Mulohazalar va ular ustida amallar

6.3-ta’rif. Elementar konyuksiyasiga har bir propozitsional o’zgaruvchi (inkor belgisi qatnashganini ham e’tiborga olsak) bir martadan ortiq kirmagan bo’lsa, bunday elementar konyuksiya to’g’ri elementar konyuksiya deyiladi.
6.3-misol. formulalar to’g’ri elementar konyuksiyalardir. 6.2-misolda keltirilgan formulaning dastlabki ikkita hadi to’g’ri elementar konyuksiyadir.
6.4-ta’rif. propozitsional o’zgaruvchilardan tuzilgan to’g’ri elementar konyuksiyadagi har bir propozitsional o’zgaruvchi bu konyuksiyaga faqat bir marta kirgan bo’lsa, bunday elementar konyuksiyaga faqat bir marta kirgan bo’lsa, bunday elementar konyuksiya o’zgaruvchilarga nisbatan to’liq elementar konyuksiya deyiladi.
6.4-misol. Elementar konyuksiyalar o’zgaruvchilardan tuzilgan bo’lsin. U holda formulalar to’liq elementar konyuksiyalardir.
6.5-ta’rif. Tarkibida bir xil elementar konyuksiyalar bo’lmagan hamda barcha elementar konyuksiyalar o’zgaruvchilarga nisbatan to’g’ri va to’liq bo’lgan DNF o’zgaruvchilarga nisbatan mukammal dizyunktiv normal forma (MDNF) deyiladi.
6.5-misol. formula o’zgaruvchilarga nisbatan MDNF dir. DNF va MDNF larning ta’rifidan ko’rinadiki, bunday formulalar keltirilgan formulalardir.
6.1-teorema. Mulohazalar algebrasining AYO formula bo’lmagan ixtiyoriy formulasi yagona MDNF ga teng kuchlidir.
Isbot. mulohazalar algebrasining ixtiyoriy AYo formula bo’lmagan formulasi bo’lsin. Demak, bajariluvchi formula bo’lib, u propozitsional o’zgaruvchilar qiymatlarining hech bo’lmaganida bitta tanlanmaida 1 qiymat qabul qiladi. formulani rostga aylantiruvchi tanlanmalar to’plami bo’lsin:

bunda Quyidagi DNF ni qaraylik:
(2)
Mazkur DNF MDNF ekanligi ravshandir, chunki ning elementlari har xil tanlanmalaridir. ekanligini ko’rsatamiz. bo’lsin. U holda bo’ladi. ( to’plamning tanlanishiga asosan). formulaning tanlanmadagi qiymatini hisoblaylik. (2) dagi MDNF tarkibida to’liq elementar konyuksiya qatnashgan bo’lib, ning tanlanmadagi qiymatini hisoblashda had hosil qiladi. (1) ga asosan hamda dir, chunki Demak, qanday bo’lishidan qat’iy nazar hamda

ga asosan bo’ladi. Shunday qilib, ga tegishli tanlanmalarda berilgan formula ham, formula ham 1 qiymat qabul qilar ekan.
bo’lgan ixtiyoriy tanlanma bo’lsin. U holda bu tanlanma ga kiruvchi ixtiyoriy tanlanmadan hech bo’lmaganda bitta elementi bilan farq qiladi. ( bu tanlanmalar tartiblangan tanlanmalar ekanligini eslatib o’tamiz ) ning tanlanmadagi qiymatini hisoblashda hosil bo’ladigan ifodada qatnashgan ixtiyoriy

hadda hech bo’lmaganda bitta uchun dir. (1) ga asosan va bo’lgani uchun (3) ifodaning qiymati 0 ga tengdir. Bundan ekanligi kelib chiqadi. bo’lgani uchun demak ga kirmagan tanlanmalarda va formulalar 0 qiymatga ega ekan. Shunday qilib, ya’ni formula (2) MDNF ga teng kuchli ekanligi kelib chiqadi. formula yagona usulda MDNF ga yoyilishi ravshandir, chunki, formula formulaning qiymatini 1 ga aylantiruvchi barcha tanlanmalar yordamida yagona usulda hosil qilinadi.
Natija. Teng kuchli formulalar bir xil MDNF ga ega.
4.3-teoremaga asosan mulohazalar algebrasining ixtiyoriy formulasining o’zi keltirilgan formuladir yoki uni teng kuchli almashtirishlar yordamida keltirilgan formula shakliga olib kelish mumkin.
Biz quyida har qanday keltirilgan formulani MDNF ga yoyish algortmini keltiramiz.
ixtiyoriy formula bo’lsin.
1-qadam. Agar keltirilmagan formula bo’lsa, u holda unga 4.3-teoremani qo’llanib, undagi implikatsiya amallari yo’qotiladi; natijada hosil bo’lgan formulada faqat inkor, konyuksiya va dizyunksiya amallari qatnashgan bo’ladi.
2-qadam. Agar hosil bo’lgan formulada inkor murakkab formula oldida qatnashgan bo’lsa, u holda uni I, XII va XIII tengkuchliliklar yordamida shunday shakl almashtiriladiki, hosil bo’lgan formulada inkor faqat propozitsional o’zgaruvchilarga tegishli bo’ladi.
3-qadam. 2-qadamdan so’ng hosil bo’lgan formulani VI-VII tengkuchliliklar yordamida shunday shakl almashtirish kerakki, yangi hosil bo’lgan formulada konyuksiya dizyunksiyadan oldin bajarilsin, ya’ni natijadan DNF hosil bo’lsin.
4-qadam. Agar hosil bo’lgan DNF da bir necha bir xil elementar konyuksiyalar qatnashgan bo’lsa, ulardan bittasini qoldirib, qolganlarini tashlab yuboriladi (VIII tengkuchlilikka asosan).
5-qadam. 4-qadamdan keyin hosil bo’lgan DNF da qatnashgan biror elementar konyuksiyada propozitsional o’zgaruvchi va uning inkori qatnashgan bo’lsa, bunday elementar konyuksiya AYo formula bo’lib, XV va XVII tengkuchliliklarga asosan uni tashlab yuboriladi).
6-qadam. Elementar konyuksiyada biror propozitsional o’zgaruvchining o’zi yoki uning inkori bir necha marta qatnashgan bo’lsa, u holda undan faqat bittasini qoldirib, qolganlari tashlab yuboriladi. (IX tengkuchlikka asosan). Bu qadamdan keyin hosil bo’lgan DNF da barcha elementar konyuksiyalar to’g’ri elementar konyuksiyalardan iborat bo’ladi.
7-qadam. Agar hosil bo’lgan DNF da to’liqmas elementar konyuksiya qatnashgan bo’lsa, uni to’liq elementar konyuksiya qatnashgan bo’lsa, uni to’liq elementar konyuksiyaga aylantirish uchun quyidagi shakl almashtirish bajariladi:

to’liqmas elementar konyuksiya bo’lsin. (bu elementar konyuksiyada propozitsional o’zgaruvchi qatnashgan emas). U holda bu to’g’ri elementar konyuksiyani unga teng kuchli

formula bilan almashtirish mumkin. Agar yetishmaydigan propozitsional o’zgaruvchi bir nechta bo’lsa, u holda elementar konyuksiyani bir nechta ko’rinishdagi konyuktiv had bilan to’ldirish kerak.
7-qadamdan so’ng hosil bo’lgan DNF da yana bir xil elementar konyuksiyalar paydo bo’lishi mumkin. U holda unga yana 4-qadam qo’llaniladi. Mazkur algoritmni qo’llanilganda albatta kerakli joyda II-V tengkuchliliklardan foydalaniladi.
6.6-misol. formulaning MDNF ini yozing.
Berilgan formula keltirilmagan bo’lgani uchun undagi implikatsiyani dizyunksiya va inkor bilan almashtiramiz:

Hosil bo’lgan formulada amalsi murakkab formula oldida qatnashgan. Shuning uchun unga de Morgan tengkuchliliklari va qo’sh inkor tengkuchligini qo’llaymiz:
Bu keltirilgan formulada dizyunksiya konyuksiyadan oldin bajariladigan had mavjud; shuning uchun distributivlik tengkuchliligini qo’llasak, quyidagi DNF hosil bo’ladi:



Ushbu DNF da qatnashgan barcha elementar konyuksiyalar to’g’ri elementar konyuksiyalar bo’lsa-da, ammo to’liq elementar konyuksiyalar emas. Shuning uchun quyidagi shakl almashtirish bajariladi:
ni bilan,
ni bilan,
ni bilan,
ni esa bilan almashtiramiz.
Ravshanki, natijada teng kuchli formula hosil bo’ladi:

Ushbu formulaga yana distributivlikni qo’llasak:

tengkuchlilikka ega bo’lamiz. Bundagi bir xil elementar konyuksiyalarni tashlab yuborsak (faqat bittasini qoldirib) u holda quyidagi oxirgi natijaga kelamiz:

Tengkuchlilikning o’ng tomoni berilgan formulaning MDNF idir. Ushbu MDNF ni formulaning rostlik jadvali bilan taqqoslaylik:

1 1 1 1 0 0 0 0	1 1 0 0 1 1 0 0	1 0 1 0 1 0 1 0	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	1 1 1 1 0 0 1 1	1 1 0 0 1 1 1 1	1 0 0 0 1 0 1 0	1 1 0 1 1 1 1 1

Bu jadvaldan ko’rinadiki: berilgan formula propozitsional o’zgaruvchilar qiymatlarining (1,1,1), (1,1,0) , (1,0,0), (0,1,1), (0,1,0), (0,0,1) va (0,0,0) tanlanmalarida 1 (rost) qiymati qabul qiladi.

6.1-teoremaga asosan berilgan formula quyidagi MDNF fa teng kuchlidir:

1. 
   ga asosan esa bu ifoda quyidagi ifodadan iboratdir:
   

yoki

ya’ni natijada (4) ning o’ng tomoni hosil bo’ladi. Berilgan formula 7 ta tanlanmada 1 qiymatga, bitta tanlanmada esa 0 qiymatga egadir, demak, u AP formula emas. (4) dan ko’rinadiki, berilgan formulaning MDNF iga 7 ta bog’liq elementar konyuksiya kiradi. Demak, tekshirilayotgan formula AR formula bo’lsa, uning MDNF iga ta to’liq elementar konyuksiya kiradi. Shunday qilib, mulohazalar algebrasining formulasini AR formulami yoki yo’qmi ekanligini aniqlash uchun uni MDNF ga yoyib uni MDNF dagi to’liq elementar konyuksiyalar sonini sanash kerak: to’liq elementar konyuksiyalar soni ta bo’lsa, berilgan formula AR formula, bo’lganda- bajariluvchi formula bo’ladi. Agar bo’lsa, u holda berilgan formula AYo formula bo’lishi ravshandir.
Yuqoridagi 6.1-6.5- ta’riflarda ,,konyuksiya’’ so’zi ,,dizyunksiya’’ bilan,,,dizyunksiya’’ so’zini ,,konyuksiya’’ so’zi bilan almashtirsak, u holda ,,elementar dizyunksiya’’ ,,to’liq elementar dizyunksiya’’ ,,mukammal konyuktiv normal forma’’ (MKNF) tushunchalari hosil bo’ladi.
MKNF lar uchun quyidagi teorema o’rinli.
6.2-teorema. Mulohazalar algebrasining AP formula bo’lmagan ixtiyoriy formulasi yagona MKNF ga teng kuchlidir.