Asosiy teng kuchli formulalar.
A Ù A º A (kon’yunksiyaning idempotentlik qonun).
A Ú A º A (diz’yunksiyaning idempotentlik qonun).
A Ù 1 º A .
A Ú 1 º 1.
A Ù 0 º 0 .
A Ú 0 º A .
A Ú ù A º 1 – uchinchisini inkor qilish qonun.
A Ù ù A º 0 - ziddiyatga keltirish qonun.
ù ( ù A ) º A - qo‘sh inkor qonun.
A Ù ( B Ú A ) º A .
A Ú ( B Ù A ) º A .
A Û B º ( A Þ B ) Ù ( B Þ A ).
A Þ B º ù A Ú B .
ù ( A Ù B ) º ù A Ú ù B .
ù ( A Ú B ) º ù A Ù ù B .
A Ù B º ù ( ù A Ù ù B ).
A Ú B º ù ( ù A Ù ù B ).
A Ù B º B Ù A – kon’yunksiyaning kommutativlik qonun.
A Ú B º B Ú A – diz’yunksiyaning kommutativlik qonun.
A Ù ( B Ú C ) º ( A Ù B ) Ú ( A Ù C ) - Ù ning Ú ga nisbatan distributivlik qonun.
A Ú ( B Ù C ) º ( A Ú B ) Ù ( A Ú C ) - Ú ning Ù ga nisbatan distributivlik qonun.
A Ù ( B Ù C ) º ( A Ù B ) Ù C – kon’yunksiyaning assotsiativlik qonun.
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 :
x + u = u + x - =ûshishga nisbatan kommutativlik qonun
x · u = u · x - ko‘paytirishga nisbatan kommutativlik qonun.
( x + u ) + z = x + ( y + z ) -=ûshishga nisbatan assotsiativlik qonun..
( x · u ) · z = x · ( y · z ) – ko‘paytirishga nisbatan assotsiativlik qonun.
x + x = x =ûshishga nisbatan idempotentlik qonun.
x · x = x – ko‘paytirishga nisbatan idempotentlik qonun.
х̿ = x - =ûsh inkor qonun.
x + u = х̅ · у̅
x · u = х̅ + у̅ - de – Morgan qonunilar
x + ( u · x ) = x
x · ( u + x ) = x - yutilish qonunilar
( x + u ) · z = ( x · z ) + ( y · z ) -=ûshishning ko‘paytirishga nisbatan distributivlik qonun.
( 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 : Xn® 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 1 , . . . , A n ) – formula n – o‘zgaruvchili Bul funksiyasidir.
Endi teskari masalani kûraylik. Ixtiyoriy
F ( X1, . . . , Xn ) – Bul funksiyasi berilgan bo‘lsin. Bu funksiyani mulohazalar algebrasining formulasi orqali ifodalash mumkinligini kûramiz :
Á º F ( 1, 1, . . . , 1 ) Ù X1 Ù X2 Ù . . . Ù Xn Ú
Ú F ( 1, . . . , 1,0 ) Ù X1 Ù . . . Ù Xn-1 Ù ù Xn Ú . . . Ú
Ú F ( 0 , 0 , . . . ,0 ) Ù ù X1 Ù . . . Ù ù Xn (1) –
formula mulohazalar algebrasining F ( X1, . . . , Xn) – Bul funksiyasiga teng bo‘lgan formuladir. Bu tasdiqni
( X1, . . . , 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 :
Formuladagi har bir qo‘shiluvchida F ( X1, . . . , Xn ) funksiyaga kirgan barcha X1, . . . , Xn o‘zgaruvchi qatnashad
Formulada bir hil qo‘shiluvchilar yo‘q.
3. Har bir qo‘shiluvchida X1, . . . , Xn o‘zgaruvchifaqat bir martagina qatnashad
Agar F ( X1, . . . , Xn ) funksiyaning rostlik jadvali berilgan bo‘lsa, uni mulohazalar algebrasining formulasi orqali ifoda qilish uchun X1, . . . , Xn o‘zgaruvchilarning
F ( X1, . . . , Xn ) funksiya 1 ga teng qiymat qabul qiladigan qiymattizimlarinigina ajratib olamiz. Bunday qiymatlar tizimi uchun Xk o‘zgaruvchi 1 ga teng qiymat qabul qilsa, Xk ni ûzini, aks holda Xk ning inkorini olib
X1, . . . , Xk o‘zgaruvchilardan kon’yunksiyalar tuzib olamiz. Hosil bo‘lgan barcha kon’yunksiyalarning yi\indisi
F ( X1, . . . , Xn ) formulaning ifodasi bo‘lad
misol. F ( X1, X2, X3 ) – ikki qiymatli fuksiya faqatgina ( 1, 1, 0 ) va ( 0, 1, 1 ) qiymatlar tizimlaridagina
1 ga teng qiymat qabul qilsin. F ( X1, . . . , Xn ) ni mulohazalar algebrasining formulasi orqali ifodalaylik.
Echim. X1, X2, X3 – o‘zgaruvchilarning ( 1, 1, 0 ) qiymattizimiga X1 Ù X2 Ù ù X3 – kon’yunksiya, ( 0, 1, 1 ) ga esa ù X1Ù X2 Ù X3 - kon’yunksiya mos kelad U holda,
F ( X1, X2, X3 ) = X1 Ù X2 Ù ù X3 Ú ù X1 Ù X2 Ù X3 .
natija . F ( X1, . . . ,Xn )– ikki qiymatli funksiya berilgan bo‘lsin. U holda,
F ( X1, . . . , Xn ) º ( F ( 1, . . . , 1 ) Ú
Ú ù X1 Ú, . . . , Ú ù Xn ) Ù F ( 1, . . . , 1, 0 ) Ú ù X1 Ú ,
, . . . , Ú Xn-1 Ù ù Xn ) Ù . . . Ù ( F ( 0, 0, . . . , 0 ) Ú
Ú X1 Ú . . . Ú Xn ).
Isbot. Haqiqatdan ham, YUqorida F ( X1, . . . , Xn ) funksiya uchun hosil qilingan ifodaga asosan :
ù F ( X1, . . . , Xn ) º ( ù F ( 1, . . . , 1 ) Ù X1 Ù . . . Ù Xn ) Ù
Ù ( ù F ( 1, . . . , 1, 0 ) Ù X1Ù . . . Ù Xn-1 Ù ù Xn ) Ù . . . Ù
Ù ( ù F ( 0, . . . , 0 ) Ù ù X1 Ù . . . Ù ù Xn ).
qo‘sh inkor va de-Morgan qonunilariga kûra
F ( X1, . . . , Xn ) º ù ( F ( X1, . . . ,Xn)) º ù ( ù F ( 1, . . . ,1 ) Ù
Ù X1 Ù . . . Ù Xn) Ú ( ù F ( 1, . . . , 1, 0 ) Ù X1 Ù . . . Ù Xn-1 Ù
Ù ù Xn ) Ú . . . Ú ( F ( 0, . . . , 0 ) Ù ù X1 Ù . . . Ù ù Xn ) º
º ( F ( 1, . . . , 1 ) Ú ù X1 Ú . . . Ú ù Xn ) Ù ( F ( 1, . . . ,1, 0 ) Ú
Ú ù X1 Ú . . . Ú ù Xn-1 Ú Xn ) Ù . . . Ù (F ( 0, . . . , 0 ) Ú
Ú X1 Ú . . . Ú Xn ).
Do'stlaringiz bilan baham: |