|
Mustaqil ish mavzu: teng kuchli formulalar. Tavtologiya va ziddiyatlar
|
| bet | 2/3 | | Sana | 15.01.2024 | | Hajmi | 19.55 Kb. | | #137506 |
Bog'liq marufjonov avazbek diskiret22 415544564, ayubxon, 1-25, Амалий иш-3, Амалий иш-1, axborot-kutubxona lot, Exploring-British-and-American-Lifestyles, 3 2 Хайъат Кадрлар салоҳияти Э Шакиров, 411-buyruq ijrosi, Sport maydonchalari.pptx [Автосохраненный], register 9637 2023, Mustaqil ish Dasturlash, Mavzu, fozilTavtologiya haqida tushuncha.
Tavtologiya. Tabiiyki, berilgan formula uning tarkibida qatnashuvchi elementar mulohazalarning mumkin bo'lgan barcha qiymatlar satrlari ucnun turli qiymatlar, jumladan, faqat ch yoki faqat yo qiymat qabul qilishi mumkin.
1- ta’rif. Tarkibidagi elementar mulohazalarning mumkin bo'lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.
misol. D = x /\ (x —> у) —> у formula tavtologiyadir. Bu tasdiqning to'griligini tekshirish uchun 1- jadvalni (D formulaning qiymatlar jadvalini) tuzamiz.
Berilgan D formula uning tarkibida qatnashuvchi x va у elementar mulohazalarning mumkin bo'lgan hamma qiymatlar satrlarida faqat ch qiymat qabul qilgani uchun, u tavtologiyadir, ya’ni x/\(x —> у) —> у=J
misol. Berilgan B = (x —> у) —> у(x —> у) —> z formulani tekshirish uchun uning chinlik jadvalini tuziladi.
ko‘rinib turibdiki, (x \/ y) —> (x —> y) = J , lekin B =J
Aynan chin formulalar mantiqda katta ahamiyatga ega bo'lib, ular mantiq qonunlarini ifodalaydi. Shu sababli, mantiq algebrasida yechilish muammosi deb yuritiluvchi chekli miqdordagi amal yordamida berilgan ixtiyoriy mantiqiy formulaning aynan chin yoki aynan chin emasligini aniqlash masalasi dolzarb muammo hisoblanadi.
1- misol. Yuqorida keltirilgan algoritmdan foydalanib, a) (y\/z) xy , b)zy<—>xy va d) x + y + z funksiyalami kontaktli sxemalar orqali realizatsiya qilish kerak boisin. a )f1 (x ,y ,z ) = (y \/ z ) —>xy funksiyani knsh ko‘rinishga keltiramiz va uni soddalashtirish uchun tanish boigan ushbu x \/ xy = x , x (x \/ y ) = x , x \/ xy = x \/ у , x \/ xy = x \/ у , x (x \/ y ) = xy , x (x \/ y ) = xy teng kuchli formulalardan foydalanamiz: f 1(x, у, z) = у \/z \/ xy = yz \/ xy = y (z \/ x ) (14-a shakl), b) f 2 (x , y, z) = zy<—>yx=(zy \/yx )( yx \/ zy) = = (z \/ y \/ yх) (х \/ y \/ zy) = (z \/ y)(x \/ y) (14-b shakl), d) f 3 = x + y + z = ( x \/ y \/ z ) ( x \/ y \/ z ) ( x \/ y \/ z ) /\ (x \/ y \/ z) (14-d shakl). Parallel-ketma-ket ulash natijasida hosil qilingan sxemalar klassini induktiv tarzda ifodalayli
Tavtologiya xususiy hollarining isbotlanuvchanligi
Ravshanki, har qanday aksioma teorema bo‘ladi. Bu teoremaning isboti bir qadamdan iborat bo‘ladi.
Teorema. Agar birinchi tartibli T nazariyaning A formulasi tavtologiyaning xususiy holi bo ‘isa, u holda A formula T nazariyaning teoremasi bo'ladi va uni ushbu bobning 2- paragrafidagi (1), (2) va (3) mantiqiy aksiomalar va xulosa qoidasini qo llash yo ‘li bilan keltirib chiqarish mumkin.
Isboti. xl,x2,...,xn - B formula tarkibiga kiruvchi o‘zgaruvchilar majmui va a formula в tavtologiyadan o ‘miga qo‘yish qoidasi orqali hosil qilingan bo'lsin. Matumki, bu holda В formulani H = {xl, x2,...,xn} majmuadan keltirib chiqarish mumkin. Buning uchun quyidagi qoida bo'yicha o‘rniga qo'yish amalini bajaramiz:
agar biror x o‘zgaruvchi В formula tarkibida bo'lsa, u holda har bir keltirib chiqarish formulasi tarkibidagi x o’rniga T nazariyaning A formulasini hosil qilish uchun В dagi o'sha x o'zgaruvchi o'm ini oladigan formula qo'yiladi; agar biror x o'zgaruvchi В tarkibida bo'lmasa, u holda keltirib chiqarish formulalari tarkibidagi shu o'zgaruvchining har bir joyiga T nazariyaning ixtiyoriy bitta formulasi qo'yiladi. Shunday qilib keltirib chiqarilgan formulalar ketma-ketligi nazariyadagi A formulaning T nazariyada keltirilib chiqarilishi bo'ladi.
Teoremaning isbotida faqatgina ushbu bobning 2- paragrafidagi (1), (2), (3) aksiomalar va xulosa qoidasidan foydalanildi.
Agar mulohazalar hisobidagi xulosa qoidasini A , A —> В tavtologiyalarga qomlasak, u holda В tavtologiyaga kelamiz. Shunday qilib, agar H(A) va H(A — > В ) tavtologiyalar bomsa, u holda H(B ) ham tavtologiya bo’ladi. H operatsiyani A va \/xA formulalarga qomlash natijasida olingan natijalar bir xil bomganligi uchun, agar H(A) tavtologiya bomsa, u holda H(\/xA) ham tavtologiya bo’ladi. Demak, agar predikatlar hisobida A teorema bomsa, u holda H(A) tavtologiya bo’ladi. Yuqoridagilardan shu narsa kelib chiqadiki, agar predikatlar hisobida В va В isbotlanuvchi bo‘ladigan shunday В formula mavjud bo‘lsa edi, u holda mulohazalar hisobida H(B) va H(B) tavtologiya, ya’ni isbotlanuvchi formulalar bo‘lar edi. Ammo bu mumkin emas. Demak, predikatlar hisobi zidsizdir.
|
| |
