Mantiq algebrasi ikkitaraflama qonuni. Reja

Jegalkin ko‘phadi. Mantiq algebrasidagi istalgan funksiyani yagona arifmetik ko‘phad shakliga keltirish mumkin. Haqiqatan ham, biz oldingi paragraflarda istalgan funksiyani kon’yunksiya va inkor mantiqiy amallar orqali ifodalash mumkinligini ko‘rgan edik. Yuqorida kon’yunksiya, diz’yunksiya va inkor mantiqiy amallarni arifmetik amallar orqali ifodaladik. Demak, istalgan funksiyani arifmetik ko‘phad shakliga keltirish mumkin. 1- t a ’ r i f. x x x a k  i i ... i  1 2 ko‘rinishdagi ko‘phad Jegalkin ko‘phadi deb ataladi, bu yerda hamma xi j o‘zgaruvchilar birinchi darajada qatnashadi, ( ,..., ) 1 k i i qiymatlar satrida hamma j i lar har xil bo‘ladi, {0, 1} a E2  . 2- t a ’ r i f. x x x a k i  i ... i  1 2 ko‘rinishdagi funksiya chiziqli funksiya deb ataladi, bu yerda {0, 1} a E2  . Chiziqli funksiyaning ifodasidan ko‘rinib turibdiki, n ta argumentli chiziqli funksiyalar soni 1 2 n ga teng va bir argumentli funksiyalar doimo chiziqli funksiya bo‘ladi. .
Mantiq algebrasidagi monoton funksiyalar

1. 
   t a ’ r i f. Agar i  i tengsizlik hech bo‘lmaganda bitta i uchun bajarilsa yoki  va  qiymatlar satrlari ustma-ust tushsa, u holda  qiymatlar satri  qiymatlar satridan oldin keladi deb aytamiz va    shaklda yozamiz.
   
2. 
   2- t a ’ r i f. Agar munosabatdan ( ,..., ) ( ,..., ) 1 n 1 n f    f   tengsizlikning bajarilishi kelib chiqsa, u holda ( ,..., ) 1 n f x x funksiya monoton funksiya deb ataladi.
   

3- t a ’ r i f Agar  munosabatdan ( ,..., ) ( ,..., ) 1 n 1 n f f   tengsizlikning bajarilishi kelib chiqsa, u holda ( ,..., ) 1 n f x x nomonoton funksiya deb ataladi.
Asosiy elementar mantiqiy funksiyalardan 0, 1, x , xy , x  y funksiyalar monoton, x , x  y , x  y , x  y funksiyalar esa nomonoton funksiyalardir.

1. 
   t e o r e m a . Monoton funksiyalarning superpozitsiyasidan hosil qilingan funksiya ham monoton funksiya bo‘ladi. I s b o t i . Ф monoton funksiyalar sistemasi bo‘lsin. Shu sistemadagi funksiyalar superpozitsiyasidan hosil qilingan funksiya monoton bo‘lishini isbot qilish kerak. Matematik induksiya usulini qo‘llaymiz. Baza: 0 rangli superpozitsiya uchun bu tasdiqning to‘g‘riligi ravshan, chunki Ф sistemadagi hamma funksiyalar monoton funksiyalardir
   

Kon’yunksiya va diz’yunksiya monoton funksiya bo‘lganligi uchun, 1- teoremaga asosan, ularning superpozitsiyasidan hosil qilingan funksiya ham monoton bo‘ladi. 2- t e o r e m a . Agar f (x1 ,..., xn )  M bo‘lsa, u holda undan argumentlari o‘rniga 0, 1 va x funksiyani qo‘yish usuli bilan x funksiyani hosil qilish mumkin.

1. 
   t a ’ r i f. Agar elementar kon’yunksiya (diz’yunksiya) ifodasida ishtirok etuvchi har bir elementar mulohaza shu ifodada faqat bir marta uchrasa, u holda bu ifoda to‘g‘ri elementar kon’yunksiya (diz’yunksiya) deb ataladi.
   
2. 
   t a ’ r i f. Agar berilgan elementar mulohazalarning har biri elementar kon’yunksiya (diz’yunksiya) ifodasida faqat bir matra qatnashsa, bu ifoda shu elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya (diz’yunksiya) deb ataladi.
   

3. 
   t a ’ r i f. Agar formulaning KNShi (DNShi) ifodasida bir xil elementar diz’yunksiyalar (kon’yunksiyalar) bo‘lmasa va barcha elementar diz’yunksiyalar (kon’yunksiyalar) to‘g‘ri hamda ifodada qatnashuvchi barcha elementar mulohazalarga nisbatan to‘liq bo‘lsa, u holda bu ifoda mukammal kon’yunktiv normal shakl (mukammal diz’yunktiv normal shakl) deb ataladi.
   

Elementar mulohazalarning aynan yolg‘on bo‘lmagan ixtiyoriy formulasini MDNShga keltirish mumkin. I s b o t i . Elementar mulohazalarning aynan yolg‘on formulasidan farqli berilgan formulasini A bilan belgilab, avvalo, A formulani MKNShga keltiramiz. A  A teng kuchlilikdan foydalanib, A formulaning MKNShi tarkibida qatnashuvchi barcha ifodalardagi  belgi o‘rniga  belgi va, aksincha,  o‘rniga  hamda elementar mulohazalar o‘rinlariga mos ravishda ularning inkorlari, va, aksincha, elementar mulohazalarning inkorlari o‘rinlariga mos ravishda ularning o‘zlari qo‘yilsa, u holda A formulaning MDNShi hosil bo‘ladi.
Mulohazalar algebrasida funksiya tushunchasi. Oddiy algebradagi funksiya tushunchasiga o‘xshash, mulohazalar algebrasida ham funksiya tushunchasi23 kiritilishi mumkin. Ushbu paragrafda mulohazalar algebrasining funksiya tushunchasini chuqurroq o‘rganamiz. Ma’lumki, oddiy algebrada funksiyaning qiymatlari turli usullar vositasida, masalan, jadval yordamida berilishi mumkin. Mulohazalar algebrasida ko‘pchilik tushunchalarni ifodalashda chinlik jadvallari qulay vosita hisoblanadi. Chinlik jadvallarida faqat ikkita o‘zgarmas (0 va 1) ishtirok etadi. Shu tufayli {0, 1} E2  deb belgilaymiz. 1- t a ’ r i f. Argumentlari va o’zi E2 to’plamdan qiymatlar qabul qiluvchi funksiya mulohazalar algebrasining funksiyasi deb ataladi.
Funksiyalar teng kuchliligi. Mulohazalar algebrasida teng kuchli formulalar tushunchasi kiritilgan edi. Bu yerda ham n argumentli funksiyalar teng kuchliligi tushunchasini kiritish mumkin. 3- t a ’ r i f. f va g funksiyalar mulohazalar algebrasining funksiyalari, n x , x ,...,x 1 2 o’zgaruvchilar esa ularning hech bo’lmaganda bittasining argumentlari bo’lsin. Agar n x , x ,...,x 1 2 argumentlarning barcha qiymatlar satrlari uchun f va g funksiyalarning mos qiymatlari bir xil bo’lsa, u holda f va g funksiyalar teng kuchli funksiyalar deb ataladi. Agar berilgan funksiyalar teng kuchli bo‘lmasa, u holda ular teng kuchlimas funksiyalar deb yuritiladi

Foydalanilgan adabiyotlar:
1.Тўраев Ҳ.Т., Математик мантиқ ва дискрет математика, Тошкент: Ўқитувчи
нашриёти, 2003, 378 б.
2.Лихтарников Л.М., Сукачева Т.Г., Математическая логика. Курс лекций.
Задачник-практикум и решения, Санк-Петербург: ЛАНЬ, 1999, 286 с.
3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.
Учебное пособие. Москва: Наука.
4. Искандаров Р.И., Математик логика элементлари, Самарқанд: СамДУ, 1970, 324 б.

1