Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti. Mustaqil ish

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.