|
I BOB. DISKRET MATEMATIKA VA MATEMATIK MANTIQ
1.1. Mantiq algebrasidagi ikkitaraflamalik qonuni. Mantiq algebrasidagi arifmetik amallar. Jegalkin ko‘phadi. Mantiq algebrasidagi monoton funksiyalar.
Mantiq algebrasidagi ikki taraflama qonun. Ikki taraflama funksiya. Endi ikki taraflama (qo‘shma) funksiya tushunchasini kiritamiz.
f (x1 ,x2 ,...,xn ) funksiyaga ikki taraflama bo‘lgan funksiyani topish uchun f funksiyaning chinlik jadvalida hamma o‘zgaruvchilarni ularning inkoriga almashtirish kerak, ya’ni hamma joyda 1ni 0ga va 0ni 1ga almashtirish kerak.
1- ta’ri f. Quyidagicha aniqlangan
f * (x1,x2 ,...,xn ) = f (x1,x2 ,...,xn )
1- jadval
Berilgan funksiya
|
Ikki taraflama funksiya
|
f1(x) = x
|
f1*(x) = x
|
f2(x) = x
|
f2* (x) = x
|
f 3 (x, y) = xy
|
f3* = x = y
|
f4(x, y) = x = y
|
f 4* = x y
|
f 5 (x, y) = x = y
|
f 5* = y = x
|
f 6 (x, y) = x = y
|
f 6* = x = y
|
f7 =1
|
f7* = 0
|
f8 = 0
|
f8* =1
|
funksiyaga f (x1 ,x2 ,...,xn ) funksiyaning ikki taraflama funksiyasi deb aytiladi. 2- ta’ri f. Agar
f (x1,x2,..., xn ) = f *(x1,x2,..., xn ) = f (x1, x2,..., xn )
munosabat bajarilsa, u holda f (x1 ,x2 ,...,xn ) o‘z-o‘ziga ikki taraflama funksiya deb ataladi.
Ta’rifga asosan, f (x1 ,x2 ,...,xn ) ikki taraflama funksiya (x1,...,xn ) va (x1,...,xn ) qiymatlar satrida qarama-qarshi qiymatlar qabul qiladi.
miso l. Mulohazalar algebrasining asosiy elementar funksiyalariga ikki taraflama bo‘lgan funksiyalarni topamiz (1- jadvalga qarang). Demak, ta’rifga asosan, f1(x) va f2(x) funksiyalar o‘zo‘ziga ikki taraflama funksiya bo‘ladi. ■
mi so l. f (x, y,z) = xy = yz = xz funksiyaning o‘z-o‘ziga ikki taraflama funksiya
ekanligini isbot qilamiz. Haqiqatdan ham
f *(x,y,z) = xy= yz=xz = xyyzxz =(x=y)(y=z)(x=z) =
=[(x=y)y=(x=y)z](x=z)=[y=yz=xz](x=z)=
= (y= xz)(x= z) = xy=yz=x(x=z)z = xy=yz=xz
Demak, f (x, y,z) = f *(x, y,z) ekanligi uchun f o‘z-o‘ziga ikki taraflama funksiyadir. ■
Te o re ma. Agar
Ф(x1,...,xn ) = f ( f1(x11,...,x1p1 ),..., fm(xm1,...,xmpm ))
bo‘lsa, u holda
Ф*(x1,..., xn ) = f *( f1*(x11,..., x1p1 ),..., fm*(xm1,..., xmpm ))
bo‘ladi.
Isboti. Ф*(x1,...,xn) =Ф (x ,...,x ) =
= f (f 1(x11,...,x1p1),...,f m(xm1,...,xmpm ))=
= f*( f1*(x11,...,x1p1),...,fm*(xm1,...,xmpm )). ■
Ikki taraflama qonun. 1- teoremaning isbotidan ikki taraflama qonun kelib chiqadi.
Ikki taraflama qonun. x1,x2 ,...,xm funksiyalarning superpozisiyasiga ikki taraflama bo‘lgan funksiya mos ravishda x1*,x2*,...,xm* ikki taraflama funksiyalar superpozisiyasiga teng kuchlidir, ya’ni agar A = C[x1,x2 ,...,xm ] formula f (x1 ,...,xn ) funksiyani realizasiya etsa, u
holda C[ x1*,x2*,...,xm* ] formula f * (x1,...,xn ) funksiyani realizasiya etadi.
Bu formula A formulaga ikki taraflama bo‘lgan formula deb aytiladi va u A* deb belgilanadi. Demak, A* = C[x1*,x2*,...,xm* ].
Ushbu qonundan o‘z-o‘ziga ikki taraflama bo‘lgan funksiyalarning superpozisiyasi yana o‘zo‘ziga ikki taraflama funksiya bo‘lishligi kelib chiqadi, ya’ni agar x1,x2 ,...,xm o‘z-o‘ziga ikki taraflama funksiya bo‘lsa, u holda Ф* =x* (x1*,...xm* ) funksiya ham o‘z-o‘ziga ikki taraflama bo‘ladi. Haqiqatan ham,
Ф* =x*(x1*,...xm* ) =x(x1,...xm ) =Ф .
Agar funksiya formula orqali ifodalangan va bu formula o‘z navbatida , =, mantiq amallari orqali ifodalangan bo‘lsa, u holda bu funksiyaga (formulaga) ikki taraflama bo‘lgan funksiyani (formulani) topish uchun = belgini belgiga, ni =ga, 1ni 0ga va 0ni 1ga almashtirish kifoya. Bu prinsipni teng kuchli formulalarga nisbatan ishlatganda, yana teng kuchli formulalar hosil qilamiz, ya’ni A(x1,...,xn) = B(x1,...,xn) bo‘lsa, u holda A*(x1,...,xn)=B*(x1,...,xn).
Ushbu prinsipga tayanib mantiq algebrasining bir formulasidan boshqa formulasini, bir teoremasidan boshqa teoremasini, bir ta’rifidan esa boshqa ta’rifini hosil qilish mumkin.
3- mi so l. Ushbu bobning 9- paragrafida keltirilgan (2), (3), (6), (8), (10), (12) teng kuchli formulalarga ushbu prinsipni qo‘llasak, (4), (5), (7), (9), (11), (13) teng kuchli formulalar kelib chiqadi. ■
Mantiq algebrasida elementlari n ta argumentli o‘z-o‘ziga ikki taraflama funksiyalardan iborat bo‘lgan to‘plamni S bilan belgilaymiz, uning elementlari soni 22n 1 ga tengdir.
Endi o‘z-o‘ziga ikki taraflama bo‘lmagan funksiyalar haqidagi lemmani ko‘rib chiqaylik.
Le mma. Agar x(x1 ,...,xn ) S bo‘lsa, u holda undan argumentlarining
o‘rniga x va x funksiyalarni qo‘yish usuli bilan bir argumentli o‘z-o‘ziga ikki taraflama bo‘lmagan funksiya, ya’ni konstantani hosil qilish mumkin.
Isboti. x(x1,...,xn )S bo‘lgani uchun, shunday (x1,...,xn) qiymatlar satri topiladiki, x(x1,...,xn ) =x(x1,...,xn ) bo‘ladi.
xi (x) = xxi (i =1,n) funksiyani kiritamiz va xi (x) =x(x1(x),...,xn (x)) deb belgilab olamiz. U holda quyidagi natijaga ega bo‘lamiz:
x(0) =x(x1(0),...,xn(0)) =x(0x1,...,0xn ) =x(x1,...,xn ) =
x(x1,...,xn ) =x(1x1 ,...,1xn ) =x(x1(1),...,xn (1)) =x(1). ■
Mantiq algebrasidagi arifmetik amallar. Jegalkin ko‘phadi
Mantiq algebrasidagi arifmetik amallar. {0,1} Bul algebrasidagi kon’yunksiya amali oddiy arifmetikadagi 0 va 1 sonlar ustidagi ko‘paytma amaliga mos keladi. Ammo 0 va 1 sonlarini qo‘shish natijasi {0,1} to‘plam doirasidan chetga chiqadi. Shuning uchun I.I.Jegalkin1 2 moduliga asosan qo‘shish amalini kiritdi. x va y mulohazalarni 2 moduli bo‘yicha qo‘shishni x = y deb belgilaymiz. 2 moduli bo‘yicha qo‘shish, odatda, chinlik jadvali bilan beriladi (1- jadvalga qarang).
x
|
y
|
x = y
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
Chinlik jadvalidan ko‘rinib turibdiki, x = y = x = y bo‘ladi. Mantiq 1- jadval algebrasidagi ko‘paytma va 2 moduli bo‘yicha qo‘shish mantiq amallari uchun kommutativlik, assotsiativlik va distributivlik qonunlari o‘z kuchini saqlaydi.
Bul algebrasidagi asosiy mantiqiy amallarni kiritilgan arifmetik amallar orqali quyidagicha ifodalash mumkin:
x = x =1; x y = xy ; x = y = xy = x = y ; x = y = xy = x =1; x = y = x = y =1.
2 moduli bo‘yicha qo‘shish amalining ta’rifiga asosan x = x = 0 va xx = x ( xn = x ).
Do'stlaringiz bilan baham: |
