Buxoro davlat universiteti axborot texnologiyalari fakulteti

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
BUXORO DAVLAT UNIVERSITETI
AXBOROT TEXNOLOGIYALARI FAKULTETI
1-1KIDT-21 GURUH TALABASI JO‘RAYEV OG‘ABEKNING
Diskret matematika va matematik mantiq fanidan
Mustaqil ishi

Tuzuvchi: O.Jo’rayev

Tekshirdi: SH.Do’stova

Mavzu: Teng kuchli formulalar

Reja:
1.Teng kuchli formula nima ?
2.Teng kuchli formulalarga doir teoremalar
3.Xulosa

1. Agar berilgan ikkita formula tarkibida ishtirok etuvchi elementar mulohazalarning har bir qiymatlar satri uchun bu formulalarning qiymatlari bir xil bo‘lsa, u holda ular teng kuchli formulalar deb ataladi.

Tarkibida x_i(i=)o’zgaruvchilarning mumkin bo’lgan barcha qiymatlar tizimida A(x₁,x₂,…,x_n) va (x₂,..,x_n) formulalarning qiymatlari ustuni bir xil bo’lsa,u holda bu formulalar o’zaro teng kuchli formulalar deyiladi va uni A(x₁,x₂,..,x_n)=B(x₁,x₂,..,x_n) ko’rinishida belgilanadi.
2-ta’rif:A va B formulalar berilgan bo’lsin.Ushbu formulalardagi elementlar mulohazalarning har bir qiymatlar satri uchun A va B formulalarning mos qiymatlari bir xil bo’lsa A va B formulalar teng kuchli formulalar deb ataladi va bu A=B tarzida belgilanadi.
A va B formulalarning chinlik jadvallarida kamida bitta qiymatlar satrida Ava B ning qiymatlar bir xil bo’lmasa,u holda A va B formulalar teng kuchlimas formulalar deb ataladi va A^B ko’rinishida belgilanadi.
Masalan,x^y=xVy,x^y=(xVy)A(xVy),xAy=xAx,xVy=yVx,…lar teng kuchli formulalar hisoblanadi.Berilgan formulalarning teng kuchlilikka tekshirishning bir nechta usullari mavjud:
a)Ikkala formulaning ham chinlik jadvalini tuzib,o’zgaruvchilarning mumkin bo’lgan barcha qiymatlarida formulalar mos ravishda bir xil qiymat qabul qilinishini ko’rsatish;
b)Ikkala formulani ham teng kuchli almashtirish natijasida soddalashtirish va hosil bo’lgan sodda formulani teng kuchlilikka tekshirish;
Mulohazalar algebrasining istalgan formulasining qiymatlari E={0,1} dan iboratdir.
Bizga E={0,1} va En=ExEx…xE={(1,1,…,1),(1,0,0,...,0),…,(0,0,0,..,0)}to’plamlar berilgan bo’lsin.
3-ta’rif.En^E ga akslantiruvchi istalgan qoida bu funksiyadir.Bu funksiyaning aniqlanish sohasi,funksiya o’zgaruvchilari soniga qarab,mos ravishda f(x)^E={0,1} f(x+,x2)^E2=ExE={(1,1),(1,0),(0,1),(0,0)},…f(x+,x2,x3…,xn)^En=ExEx…xE={(1,1,…,1),(1,0,0,…,0),…,(0,0,0,..,0)} ko’rinishida bo’lgan 2n ta tartiblangan n liklardan iborat bo’ladi.Funksiya ta’rifidan ko’rinib turibdiki,mulohazalar algebrasining istalgan formulasi mulohazalar algebrasining biror formulasini hosil qiladi.Chunki har bir formula bevosita En^Ega akslantiradi.Bu algebrasida konyuksiya amali matematika fanidagi 0 va 1sonlarning ko’paytirilishi bilan ustma ust tushadi.Ammo dizyunsiya amali biz bilgan +amali E={0,1}to’plamdan chiqib ketadi.Ushbu muammoni bartaraf qilish uchun rus olimi I.I.Jegalkin ikki modulga asosan qo’shish amalini kiritadi.x va y o’zgaruvchilarining ikki moduli bo’yicha yig’indi amalining qiymatlari quyidagilardan iborat.
x
y
x+y
1 1 0
1 0 1
0 1 1
0 0 0
Teng kuchli bo’lish munosabati ekvivalent binary munosabat ekanligi ravshandir,ya’ni bu munosabat
1.A=A-refleksivlik.
2.Agar A=B bo’lsa, u holda B=A bo’ladi-simmetriklik va
3.Agar A=B va B=C bo’lsa, u holda A=C bo’ladi-tanzitivlik xossalariga egadir.
Teorema:A(B)-jumlalar algebrasining ixtiyoriy formulasi,uning qism formulasi bo’lsin.Agar B=C bo’lsa, u holda A(B)=A(C) bo’ladi.
2.Teorema:A va B formulalar teng kuchli bo’lishi uchun A (v)va B(v) formulalar teng kuchli bo’lishi zarur va yetarli.
Isboti:A va B bo’lsin.U vaqtda hamma holatlarda bu formulalar bir xil qiymatga ega bo’ladi.U holda A(v) va B(v) formulalar ham chinlik jadvalining har bir satrida bir xil qiymatlarga ega bo’ladi.Demak,A=B(v).Xuddi shunga o’xshash, A=B(v) dan A=B belib chiqadi.
2-teorema.A va B formulalar teng kuchli bo’lishi uchun A-B formula aynan chin(tavtologiya) bo’lishi zarur va yetarli.
Isboti.A=B bo’lsin.Bu holda ekvivalentlik ta’rifga asosan,A-B ning hamma satrlaridagi qiymatlari “ch”dan iborat,demak,A-B tavtologiyani ifodalaydi.

2.A-B tavtalogiya bo’lsin.U holda A-B har bir satrida “ch”qiymatga ega bo’ladi.Bundan esa A va B ning har bir satridagi qiymatlari bir xil, ya’ni A=B kelib chiqadi.

3-teorema.A-B aynan chin bo’lishi uchun A(v)-B(v)aynan chin bo’lishi zarur va yetarli.
4-teorema.P formulaning istalgan A qismi o’niga shu A bilan teng kuchli B formulani qo’yishdan hosil bo’lgan yangi Q formula formula bilan teng kuchlidir.
Algebrada ma’lum bo‘lgan ayrim ayniyatlarga o‘xshash mantiqiy teng kuchliliklarini va teng kuchli formulalarga doir ayrim teoremalarni keltiramiz.
Ma’lumki, haqiqiy sonlarni qo‘shish va ko‘paytirish amali uchun quyidagi tasdiqlar o‘rinlidir:
1) ixtiyoriy ikkita va sonlar uchun bo‘ladi (qo‘shishning kommutativlik qonuni);
2) ixtiyoriy uchta , va sonlar uchun bo‘ladi (qo‘shishning assotsiativlik qonuni);
3) ixtiyoriy ikkita va sonlar uchun bo‘ladi (ko‘paytirishning kommutativlik qonuni);
4) ixtiyoriy uchta , va sonlar uchun bo‘ladi (ko‘paytirishning assotsiativlik qonuni);
5) ixtiyoriy uchta , va sonlar uchun bo‘ladi
(ko‘paytirishning yig‘indiga nisbatan distributivlik qonuni).
Mulohazalar algebrasida bu ayniyatlarga o‘xshash, ixtiyoriy mantiqiy , va o‘zgaruvchilar uchun quyidagi teng kuchliliklar o‘rinlidir:
, (1)
,
Mantiqiy ifodada ishtirok etuvchi belgisini va belgilari orqali hamda belgisini va belgilari orqali ifodalash mumkin. Bu tasdiq ikki karra inkorni o‘chirish qonuni va de Morgan qonunlari deb ataluvchi teng kuchliliklarga asoslanadi. Ikki karra inkorni o‘chirish qonuni
, (8)
de Morgan qonunlari esa
, (9)
(10)
teng kuchliliklar bilan ifodalanadi. Bu qonunlarning o‘rinliligi esa chinlik jadvallari yordamida osongina tekshiriladi.
Mantiqiy ifodada ishtirok etuvchi belgisini va belgilari orqali ifodalash uchun
(11)
va, shunga o‘xshash, belgisini va belgilari orqali ifodalash uchun
(12)
teng kuchliliklardan foydalaniladi.