16- mukammal diz`yunktiv va kon`yunktiv normal shakllar

Nazorat uchun savollar:

1. 
   Mantiq formulasi ko‘rinishi 0 ga teng qiymatlari bo‘yicha qanday tiklanadi?
   
2. 
   Mantiq formulasi ko‘rinishi 1 ga teng qiymatlari bo‘yicha qanday tiklanadi?
   
3. 
   Tavtologiya va ziddiyat formulalari uchun MKNSh va MDNSh haqidagi teoremalarni ayting.
   

Mustaqil yechish uchun masalalar:
Quyidagi rostlik jadvali berilgan mantiq funksiyalarining formulasini tiklang:

A	B	C	α1	α2	α3	α4	α5	α6	α7	α8	α9	α10	α11	α12	α13	α14	α15
0	0	0	1	1	1	0	0	1	1	0	0	0	1	0	0	0	0
0	0	1	1	0	0	1	0	1	1	1	1	1	1	1	1	1	0
0	1	0	0	1	0	0	1	1	0	1	0	0	0	1	1	1	1
0	1	1	0	0	1	1	1	0	0	0	1	0	0	0	1	1	1
1	0	0	0	0	1	1	1	0	0	1	0	1	1	0	0	0	1
1	0	1	0	1	0	0	1	0	1	0	0	1	1	1	0	0	0
1	1	0	1	0	0	1	0	0	0	1	1	1	0	1	0	1	0
1	1	1	1	1	1	0	0	1	1	0	1	0	0	0	1	0	1

Jegalkin polinomi.

Ta’rif 1. Mantiqiy formulaning kon’yunktsiya va simmetrik ayirma amallari bilan ifodalangan shakliga Jegalkin polinomi (ko’phadi) deyiladi.

Mantiqiy formulani Bul ifodasidan Jegalkin polinomi ko’rinishiga keltirish uchun 4 ta bosqich amalga oshiriladi:

1-bosqich: Berilgan formulani DNSh ga keltirish;

2-bosqich: Quyidagi formuladan foydalanib, diz’yunktsiya amalidan qutilish kerak:

;

3-bosqich: Inkor amalini simmetrik ayirma amali bilan almashtirish:



4-bosqich: Hosil bo’lgan ifodani soddalashtirish, bunda

tenglikdan foydalaniladi.

Misol.

.

Ta’rif 2. O’zgaruvchilarida inkor qatnashmagan kon’yunktsiyaga monoton kon’yunktsiya deyiladi.

Ko’yunktsiya amali bilan birlashtirilgan o’zgaruvchilar soniga polinom rangi deyiladi.

Ta’rif 3. Polinomda qatnashgan hadlarning eng katta rangi Jegalkin ko’phadi darajasi deyiladi.

Nazorat uchun savollar:

1. 
   Jegalkin polinomi ta’rifini ayting. Misol keltiring.
   
2. 
   Jegalkin ko’phadi darajasi deganda nimani tushunasiz?
   
3. 
   Bul ko’phadlari bilan Jegalkin ko’phadining farqi nimada?
   

Mustaqil yechish uchun masalalar:
Quyidagi Bul formulalarini Jegalkin polinomiga o’tkazing:

1. 
   α(A,B,C)= AB(AC)
   
2. 
   α (A,B,C)=C→(AB)
   
3. 
   α (A,B,C)=A&B→(AB)
   
4. 
   α (A,B,C)=(A&B&C)(A B)
   
5. 
   α (A,B,C)=(AC)B
   
6. 
   α (A,B,C)=(A→B)→C
   
7. 
   α (A,B,C)=(A→B)(B→C)
   
8. 
   α (A,B,C)=A(B→C)B
   
9. 
   α (A,B,C)=(A&BC)
   
10. 
    α(A,B,C)=(AB)(BC)
    
11. 
    α(A,B,C)=(A→C)B
    
12. 
    α (A,B,C)=A→(BC)
    
13. 
    α(A,B,C)=(A→B)(B→A)C
    
14. 
    α(A,B,C)=CAB
    
15. 
    α(A,B,C)=A(ABC)(AC)
    
16. 
    α(A,B,C)=(AB)(BAC)
    
17. 
    α(A,B,C)=A(BA)(AC)
    
18. 
    α(A,B,C)=(A→B)&A&C
    
19. 
    α(A,B,C)=(A&B)→(C&A)
    
20. 
    α(A,B,C)=(A&BC)&A&C
    
21. 
    α(A,B,C)=(A&BA&B)&(C→B)
    
22. 
    α(A,B,C)=(AB CABC)AB
    
23. 
    α(A,B,C)=(A→B)&(C→A)
    
24. 
    α(A,B,C)=(AB&CA&C)&B
    
25. 
    α(A,B,C)=(ABC)→AC