Navoiy davlat pedagogika instituti fizika matematika fakulteti

Asosiy teng kuchli formulalar.

1. 
   A Ù A º A (kon’yunksiyaning idempotentlik qonun).
   
2. 
   A Ú A º A (diz’yunksiyaning idempotentlik qonun).
   
3. 
   A Ù 1 º A .
   
4. 
   A Ú 1 º 1.
   
5. 
   A Ù 0 º 0 .
   
6. 
   A Ú 0 º A .
   
7. 
   A Ú ù A º 1 – uchinchisini inkor qilish qonun.
   
8. 
   A Ù ù A º 0 - ziddiyatga keltirish qonun.
   
9. 
   ù ( ù A ) º A - qo‘sh inkor qonun.
   
10. 
    A Ù ( B Ú A ) º A .
    
11. 
    A Ú ( B Ù A ) º A .
    
12. 
    A Û B º ( A Þ B ) Ù ( B Þ A ).
    
13. 
    A Þ B º ù A Ú B .
    
14. 
    ù ( A Ù B ) º ù A Ú ù B .
    
15. 
    ù ( A Ú B ) º ù A Ù ù B .
    
16. 
    A Ù B º ù ( ù A Ù ù B ).
    
17. 
    A Ú B º ù ( ù A Ù ù B ).
    
18. 
    A Ù B º B Ù A – kon’yunksiyaning kommutativlik qonun.
    
19. 
    A Ú B º B Ú A – diz’yunksiyaning kommutativlik qonun.
    
20. 
    A Ù ( B Ú C ) º ( A Ù B ) Ú ( A Ù C ) - Ù ning Ú ga nisbatan distributivlik qonun.
    
21. 
    A Ú ( B Ù C ) º ( A Ú B ) Ù ( A Ú C ) - Ú ning Ù ga nisbatan distributivlik qonun.
    
22. 
    A Ù ( B Ù C ) º ( A Ù B ) Ù C – kon’yunksiyaning assotsiativlik qonun.
    
23. 
    A Ú ( B Ú C ) º ( A Ú B ) Ú C – diz’yunksiyaning assotsiativlik qonun.
    

Bu tengkuchliliklar rostlik jadvallari yordamida isbotlanishi mumkin. Masalan, 20 - tengkuchlilikning isboti uchun rostlik jadvali tuzamiz :

A	B	C	A Ù B	A Ù C	B Ú C	A Ù (B Ú C)	(A Ù B) Ú (A Ù C)
1	1	1	1	1	1	1	1
1	1	0	1	0	1	1	1
1	0	1	0	1	1	1	1
1	0	0	0	0	0	0	0
0	1	1	0	0	1	0	0
0	1	0	0	0	1	0	0
0	0	1	0	0	1	0	0
0	0	0	0	0	0	0	0

Rostlik jadvalidagi oxirgi ikki ustunlar mos qatorlaridagi qiymatlar tengligidan ko‘rinadiki :

A Ù ( B Ú C ) º ( A Ù B ) Ú ( A Ù C ).

4 . Formulalarni teng kuchli almashtirish.

Agar Á º  bo‘lib, Á va  formulalar tarkibiga kirgan C qism formulani C ga teng kuchli bo‘lgan D formula bilan almashtirsak, yana teng kuchli formulalar hosil bo‘lishi ravshan. Buni qisqacha

Á ( C ) º Â ( C ) , C º D

Á ( D ) º Â ( D )

ko‘rinishda ¸zishni kelishib olamiz.

4.1 – misol. A Û B º A Ù B Ú A Ù B tengkuchlilikni isbotlang.

3.6 da keltirilgan tengkuchliliklardan foydalanib quyidagi teng kuchli formulalar ketma – ketligini hosil qilamiz :

A Û B º ( A Þ B ) Ù ( B Þ A ) º ( ù A Ú B ) Ù ( ù B Ú A ) º

º ( ( ù A Ú B ) Ù ù B ) Ú ( ù A Ú B ) Ù A ) º ( ù A Ù ù B ) Ú

Ú ( B Ù ù B ) Ú ( ù A Ù A ) Ú ( B Ù A ) º ( ù A Ù ù B ) Ú 0 Ú

Ú 0 Ú ( B Ù A ) º ( ù A Ù ù B ) Ú ( B Ù A ).

MAVZU. FUNKSIYALARNING TO’LIQ SISTEMALAR BUL FUNKSIYALAR

1 -ta’rif . Bo‘sh bo‘lmagan M to‘plam va unda aniqangan " + " - qo‘shish , " · " – ko‘paytirish, " ¯ " – inkor amallariga nisbatan quyidagi shartlar bajarilgan bo‘lsin :

1. 
   x + u = u + x - =ûshishga nisbatan kommutativlik qonun
   
2. 
   x · u = u · x - ko‘paytirishga nisbatan kommutativlik qonun.
   
3. 
   ( x + u ) + z = x + ( y + z ) -=ûshishga nisbatan assotsiativlik qonun..
   
4. 
   ( x · u ) · z = x · ( y · z ) – ko‘paytirishga nisbatan assotsiativlik qonun.
   
5. 
   x + x = x =ûshishga nisbatan idempotentlik qonun.
   
6. 
   x · x = x – ko‘paytirishga nisbatan idempotentlik qonun.
   
7. 
   х̿ = x - =ûsh inkor qonun.
   
8. 
   x + u = х̅ · у̅
   
9. 
   x · u = х̅ + у̅ - de – Morgan qonunilar
   
10. 
    x + ( u · x ) = x
    
11. 
    x · ( u + x ) = x - yutilish qonunilar
    
12. 
    ( x + u ) · z = ( x · z ) + ( y · z ) -=ûshishning ko‘paytirishga nisbatan distributivlik qonun.
    
13. 
    ( x · y ) + z = ( x + z ) · ( y + z ) –ko‘paytirishning =ûshishga nisbatan distributivlik qonun
    

u holda < M ; + , · , ¯ > - algebra Bul algebrasi deyilad

Misollar. 1. 3.6 dagi tengkuchliliklardan ko‘rinadiki, mulohazalar algebrasida kon’yunksiyani " · ", diz’yunksiyani " + " ga mos =ûysak, mulohazalar algebrasi Bul algebrasiga misol bo‘la olad

2 - ta’rif. X = { 0 , 1 } –ikki elementli to‘plam berilgan bo‘lsin. U holda f : Xⁿ® X ( n = 0, 1, 2, . . . ) - funksiya n – o‘zgaruvchili Bul funksiyasi yoki 2 - qiymatli funksiya deyilad

n=0, bo‘lganda, X to‘plamning ajratilgan elementlarini, ya’ni 0 yoki 1 ni hosil qilamiz. Mulohazalar algebrasining ihtiyoriy formulasi ikki qiymatli funksiyaga misol bo‘la olad Masalan, A Ú V –formulani qaraylik.

A	V	A Ú V
1	1	1
1	0	1
0	1	1
0	0	0

Demak , f ( x,u ) = x Ú u – Bul funksiyasi ekan. Umuman,

Á ( A ₁ , . . . , A _n ) – formula n – o‘zgaruvchili Bul funksiyasidir.

Endi teskari masalani kûraylik. Ixtiyoriy

F ( X₁, . . . , X_n ) – Bul funksiyasi berilgan bo‘lsin. Bu funksiyani mulohazalar algebrasining formulasi orqali ifodalash mumkinligini kûramiz :

Á º F ( 1, 1, . . . , 1 ) Ù X₁ Ù X₂ Ù . . . Ù X_n Ú

Ú F ( 1, . . . , 1,0 ) Ù X₁ Ù . . . Ù X_n-1 Ù ù X_n Ú . . . Ú

Ú F ( 0 , 0 , . . . ,0 ) Ù ù X₁ Ù . . . Ù ù X_n (1) –

formula mulohazalar algebrasining F ( X₁, . . . , X_n) – Bul funksiyasiga teng bo‘lgan formuladir. Bu tasdiqni

( X₁, . . . , X _n) – propozitsional o‘zgaruvchitizimiga

(1 , . . . , 1), ( 1, . . . , 1, 0 ) , . . . , ( 0, . . . , 0 ) qiymatlar tizimini qo‘yib tekshirib chiqish mumkin. ( 1, . . . , 1, 0 ) - qiymatlar tizimi uchun tenglikni tekshiraylik. 3.6 dagi tengkuchliliklarga asosan :

F ( 1, 1, . . . , 1 ) Ù 1 Ù. . . Ù 0 Ú F ( 1, . . . ,1, 0 ) Ù 1 Ù 1 Ù

Ù . . . Ùù 0 Ú . . . Ú F ( 0, . . . , 0 ) Ù ù 1 Ùù 1 Ù . . . Ù ù 0 º

º F ( 1, . . . , 1 ) Ù 0 Ú F ( 1, . . . ,1, 0 ) Ù 1 Ù 1 Ù . . . Ù 1 Ú

Ú . . . Ú F ( 0, . . . , 0 ) Ù 0 º 0 Ú F ( 1, . . . , 1, 0 ) Ú

Ú . . . Ú 0 º F ( 1, 1, . . . , 0 ) .

Agar (1) formulada 0 ga teng bo‘lgan qo‘shiluvchilarni, ya’ni birinchi o‘paytuvchisi 0 ga teng kon’yunksiyalarni va birinchi ko‘paytuvchisi 1 ga teng kon’yunksiyalarda 1 Ù A º A tengkuchlilikdan foydalanib 1 ni tashlab yozsak, (1) formulaning ko‘rinishi ancha soddalashad

SHunday qilib, (1) ni faqat propozitsional o‘zgaruvchilardan tuzilgan va quyidagi shartlarni qanoatlantiradigan formula shaklida yozish mumkin :

1. 
   Formuladagi har bir qo‘shiluvchida F ( X₁, . . . , X_n ) funksiyaga kirgan barcha X₁, . . . , X_n o‘zgaruvchi qatnashad
   
2. 
   Formulada bir hil qo‘shiluvchilar yo‘q.
   

3. Har bir qo‘shiluvchida X₁, . . . , X_n o‘zgaruvchifaqat bir martagina qatnashad

Agar F ( X₁, . . . , X_n ) funksiyaning rostlik jadvali berilgan bo‘lsa, uni mulohazalar algebrasining formulasi orqali ifoda qilish uchun X₁, . . . , X_n o‘zgaruvchilarning

F ( X₁, . . . , X_n ) funksiya 1 ga teng qiymat qabul qiladigan qiymattizimlarinigina ajratib olamiz. Bunday qiymatlar tizimi uchun X_k o‘zgaruvchi 1 ga teng qiymat qabul qilsa, X_k ni ûzini, aks holda X_k ning inkorini olib

X₁, . . . , X_k o‘zgaruvchilardan kon’yunksiyalar tuzib olamiz. Hosil bo‘lgan barcha kon’yunksiyalarning yi\indisi

F ( X₁, . . . , X_n ) formulaning ifodasi bo‘lad

misol. F ( X₁, X₂, X₃ ) – ikki qiymatli fuksiya faqatgina ( 1, 1, 0 ) va ( 0, 1, 1 ) qiymatlar tizimlaridagina

1 ga teng qiymat qabul qilsin. F ( X₁, . . . , X_n ) ni mulohazalar algebrasining formulasi orqali ifodalaylik.

Echim. X₁, X₂, X₃ – o‘zgaruvchilarning ( 1, 1, 0 ) qiymattizimiga X₁ Ù X₂ Ù ù X₃ – kon’yunksiya, ( 0, 1, 1 ) ga esa ù X₁Ù X₂ Ù X₃ - kon’yunksiya mos kelad U holda,

F ( X₁, X₂, X₃ ) = X₁ Ù X₂ Ù ù X₃ Ú ù X₁ Ù X₂ Ù X₃ .

natija . F ( X₁, . . . ,X_n )– ikki qiymatli funksiya berilgan bo‘lsin. U holda,

F ( X₁, . . . , X_n ) º ( F ( 1, . . . , 1 ) Ú

Ú ù X₁ Ú, . . . , Ú ù X_n ) Ù F ( 1, . . . , 1, 0 ) Ú ù X₁ Ú ,

, . . . , Ú X_n-1 Ù ù X_n ) Ù . . . Ù ( F ( 0, 0, . . . , 0 ) Ú

Ú X₁ Ú . . . Ú X_n ).

Isbot. Haqiqatdan ham, YUqorida F ( X₁, . . . , X_n ) funksiya uchun hosil qilingan ifodaga asosan :

ù F ( X₁, . . . , X_n ) º ( ù F ( 1, . . . , 1 ) Ù X₁ Ù . . . Ù X_n ) Ù

Ù ( ù F ( 1, . . . , 1, 0 ) Ù X₁Ù . . . Ù X_n-1 Ù ù X_n ) Ù . . . Ù

Ù ( ù F ( 0, . . . , 0 ) Ù ù X₁ Ù . . . Ù ù X_n ).

qo‘sh inkor va de-Morgan qonunilariga kûra

F ( X₁, . . . , X_n ) º ù ( F ( X₁, . . . ,X_n)) º ù ( ù F ( 1, . . . ,1 ) Ù

Ù X₁ Ù . . . Ù X_n) Ú ( ù F ( 1, . . . , 1, 0 ) Ù X₁ Ù . . . Ù X_n-1 Ù

Ù ù X_n ) Ú . . . Ú ( F ( 0, . . . , 0 ) Ù ù X₁ Ù . . . Ù ù X_n ) º

º ( F ( 1, . . . , 1 ) Ú ù X₁ Ú . . . Ú ù X_n ) Ù ( F ( 1, . . . ,1, 0 ) Ú

Ú ù X₁ Ú . . . Ú ù X_n-1 Ú X_n ) Ù . . . Ù (F ( 0, . . . , 0 ) Ú

Ú X₁ Ú . . . Ú X_n ).