Mulohazalar algebrasi. Mulohazalar ustida amallar

4-§. TENG KUCHLI FORMULALAR VA ASOSIY TENG KUCHLILIKLAR
4.1-ta’rif. Mulohazalar algebrasining va formulalari propozitsional o’zgaruvchilar qiymatlarining barcha tanlanmalarida bir xil qiymat qabul qilsalar, bu formulalar teng kuchli formulalar deyiladi va bu ko’rinishida yoziladi.
4.1-misol. va formulalar teng kuchli formulalar ekanligini ko’rsatamiz:

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	1 1 0 0 1 1 1 1	1 1 0 0 1 1 1 1	1 0 0 0 1 0 1 0	1 0 0 0 1 0 1 0

Agar va formulalar teng kuchli bo’lsalar, u holda va lar AR formulalar bo’lishi ravshandir. Aksincha, qandaydir va (bir xil propozitsional o’zgaruvchilarga ega bo’lgan) formulalar uchun va lar AR formulalar bo’lsa, u holda bo’ladi.
va formulalar teng kuchli formulalar ekanligini ko’rsataylik:

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

Shunday qilib, bu tebgkuchliliklardan ko’rinadiki, bo’lishi uchun formula AR formula bo’lishi zarur va yetarlidir. Teng kuchli bo’lish munosabati ekanligi binary munosabat ekanligi ravshandir, ya’ni bu munosabat

1. 
   - refleksivlik
   
2. 
   Agar bo’lsa, u holda bo’ladi- simmetriklik
   
3. 
   Agar va bo’lsa, u holda bo’ladi- tranzitivlik xossalariga egadir.
   

4.1-teorema. - jumlalar algebrasining ixtiyoriy formulasi, uning qism formulasi bo’lsin. Agar bo’lsa, u holda bo’ladi.
Isbot. bo’lgani uchun va formulalar ularda qatnashgan proporsional o’zgaruvchilar qiymatlarining barcha tanlanmalarida bir xil qiymatlarga erishadilar. va formulalarining qiymatlarning qiymatlari 1 yoki 0 bo’lgani uchun yo yoki, hosil bo’ladi. Bu esa ekanini ko’rsatadi.
4.2-teorema. lar va formulalarning har birida qatnashgan barcha propozitsional o’zgaruvchilar, lar esa ixtiyoriy formulalar bo’lsin. U holda bo’ladi; bunda har bir propozitsional o’zgaruvchi berilgan tengkuchlilikda necha joyda qatnashgan bo’lsa, shuncha joyda mos formula bilan almashtiriladi.
Isbot. tengkuchlilikda qatnashgan har bir propozitsional o’zgaruvchi 1 yoki 0 qiymat qabul qiladi. formula ham o’zi qatnashgan propozitsional o’zgaruvchilar qiymatlarining barcha tanlanmalarida 1 yoki 0 qiymat qabul qiladi. formula tarkibida qatnashgan propozitsional o’zgaruvchilar bo’lsin. bu propozitsional o’zgaruvchilar qiymatlari tanlanmalaridan biri va formulalarning tanlanmadagi qiymatlari tanlanmai bo’lsin. Uzunligi n bo’lgan tanlanma propozitsional o’zgaruvchilar qabul qiladigan qiymatlar tanlanmalari orasida mavjuddir. va formulalar ta tanlanmaning har birida bir xil qiymatga ega bo’lishi uchun tanlanmada ham bir hil qiymat qabul qiladilar.
Yuqorida isbotlangan teoremalardan bevosita quyidagi natijalar kelib chiqadi.
Agar va bo’lsa, u holda

1. 
   
   
2. 
   
   
3. 
   
   
4. 
   
   
5. 
   ( yoki )
   

4.2-ta’rif.Agar formulaning tarkibida faqat konyuksiya, dizyunksiya va inkor amallari qatnashgan bo’lib, inkor amalsi propozitsional o’zgaruvchilargagina tegishli bo’lsa, u holda bunday formula keltirilgan formula deyiladi.
4.2-misol. keltirilgan formuladir, ammo keltirilgan formula emas, chunki bu formulada implikatsiya amalsi qatnashishi bilan birgalikda inkor amalsi murakkab formula ga tegishlidir.
4.3-teorema. Mulohazalar algebrasining har bir formulasining yo o’zi keltirilgandir yoki uni teng kuchli keltirilgan formula bilan almashtirish mumkin.
Bu teoremani isbotlash uchun mulohazalar algebrasining asosiy tengkuchliliklari bilan tanishib chiqamiz. Mulohazalar algebrasining tengkuchliliklari quyidagilar:

1. 
   (qo’sh inkor tengkuchlilikgi )
   
2. 
   (konyuksiya va
   
3. 
   dizyunksiyaning kommutativligi )
   
4. 
   (konyuksiya va dizyunksiyaning
   
5. 
   assosiativligi )
   
6. 
   (dizyunksiyaning konyuksiyaga va
   
7. 
   konyuksiyaning dizyunksiyaga nisbatan distributivligi )
   
8. 
   (dizyunksiya va konyuksiyaning
   
9. 
   idempotentligi )
   
10. 
    (yutilish tengkuchliliklari )
    
11. 
    
    
12. 
    (de Morgan
    
13. 
    tengkuchliliklari )
    
14. 
    ( uchinchini inkor etish tengkuchliligi )
    
15. 
    (qarama-qarshilik tengkuchliligi )
    
16. 
    a) b) c) d)
    
17. 
    (kontropozitsiya tengkuchliligi )
    

Bu tengkuchliliklar o’rinli ekanligini rostlik jadvali yordamida bevosita tekshirib ko’rish mumkin. Masalan, XIII tengkuchlilik uchun rostlik jadvalini ko’raylik:

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

II-XI, XIV-XVI tengkuchliliklarni tashkil etuvchi formulalar keltirilgan formulalar ekanligi ravshandir. (propozitsional o’zgaruvchilar va mantiqiy konstantalar keltirilgan formula hisoblanadi).

Bundan tashqari,

tengkuchlilik o’rinli ekanligini rostlik jadvali tuzib ko’rsatish qiyin emas. Yuqorida ekanligi ko’rsatilgan edi. Implikatsiya inkor va dizyunksiya bilan almashtirish mumkin ekanligidan quyidagi tengkuchlilikni hosil qilamiz:
(2)
Demak, va formulalar keltirilgan formulalar bilan almashtirilishi mumkin ekan. I, XII, XIII tengkuchliliklar qo’sh inkor hamda dizyunksiya va konyuksiyalar inkorlarini qanday keltirilgan formulalar bilan almashtirilishi mumkin ekanini ko’rsatadi.
Endi 4.3- teoremaning isbotini keltiramiz. Agar formulaning o’zi keltirilgan formula bo’lsa, u holda teorema isbotlangan bo’ladi.
Agar formula tarkibida implikatsiya va ekvivalentsiya amallari qatnashgan bo’lsa, ularni (1) va (2) tengkuchliliklar yordamida almashtirish mumkin; formula tarkibida ko’rinishdagi qism formula qatnashgan bo’lsa, uni bilan, yoki ko’rinishidagi qism formula qatnashgan bo’lsa, ularni mos ravishda va formulalar bilan almashtirish mumkin. Bu jarayonni yetarli marta takrorlab, nihoyat, formulaga teng kuchli bo’lgan keltirilgan formulaga kelamiz.
Shunday qilib, 4. 3-teoremaga asosan mulohazalar algebrasining har bir formulasini asosiy va boshqa tengkuchliliklar yordamida almashtirib, unga teng kuchliliklar yordamida almashtirib, unga teng kuchli formulalar hosil qilish mumkin. Bu shakl almashtirishlar ba’zi bir masalalarni yechishda keng ko’lamda ishlatiladi. Bu yerda formulalarni shakl almashtirishga oid ba’zi namunalarni keltiramiz.
4.3-misol. formulaning shaklini almashtiring va soddalashtiring.

Demak, berilgan formula formula ekan.
Yuqorida aniqlangan ,, Sheffer shtrixi ” va ,,pers strelkasi’’ amallariga qaytamiz. Mantiqiy amallarning jadval formalarini taqqoslasak:

ekanligini ko’ramiz. Demak, ,,sheffer shtrixi’’ va ,,Pirs strelkasi’’ inkor mos ravishda konyuksiya va dizyunksiya orqali ifoda qilinar ekan.