Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja
Download 2.36 Mb.
|
7-ma\'ruza
|
4 - misol. Formulani MKNShga keltirish algoritmidan foydalanib x , y , z va u elementar
mulohazalarning A (x x) ( y y) (z u) formulasini MKNShga keltiramiz. Dastlab, algoritmning 1- bandiga ko‘ra, berilgan A formulani KNShga keltiramiz. Buning uchun, avvalo, a b a b va a b (a b) (a b ) teng kuchliliklardan foydalanib A formulani faqat kon’yunksiya, diz’yunksiya va inkor mantiqiy amallari orqali ifodalaymiz: A (x x) ( y y) ((z u) (z u )) . Hosil bo‘lgan formulaga x x A teng kuchlilikni qo‘llasak, formula (x x) ( y y) (z u) (z u ) KNShga keladi. KNSh ifodasida barcha elementar diz’yunksiyalar turlicha bo‘lganligi sababli algoritmning 2- bandini bajarishga hojat yo‘q. KNSh ifodasidagi 1- va 2- elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar bo‘lmaganligi uchun algoritmning 3- banda ifodalangan jarayonlarni bajarishga o‘tamiz. KNSh ifodasidagi hech qaysi elementar diz’yunksiya ifodasida birorta ham o‘zgaruvchi o‘zining inkori bilan birgalikda qatnashmaganligi sababli 3- banddagi a) hol bu yerda ro‘y bermaydi. KNSh ifodasidagi 1- elementar diz’yunksiyada x , 2- elementar diz’yunksiyada esa y ikki marta qatnashgani uchun b) holda bayon qilingandek ish yuritib, A formula uchun barcha elementar diz’yunksiyalari to‘g‘ri elementar diz’yunksiyalardan iborat x y (z u) (z u ) KNShni hosil qilamiz. Ushbu bobning 5- paragrafidagi 2- teoremaga asosan, A formula tavtologiya emas. Algoritmning 4- bandini bajaramiz. Ko‘rinib turibdiki, KNShdagi 1- elementar diz’yunksiyada y , z va u , 2- elementar diz’yunksiyada x , z va u , 3- va 4- elementar diz’yunksiyalarda esa x va y o‘zgaruvchilar yoki ularning inkorlari yo‘q. Shularni e’tiborga olib, KNSh ifodasidagi to‘rtala elementar diz’yunksiyalarni to‘liq elementar diz’yunksiyalar shakliga keltirish maqsadida 4- bandda ifodalangan jarayonni qo‘llaymiz. Natijada 1- elementar diz’yunksiya ( x ) uchunx x ( y y) (x y) (x y) (( x y) (z z )) (( x y) (z z )) (x y z) (x y z ) (x y z) (x y z ) ((x y z) (u u )) ((x y z ) (u u )) ((x y z) (u u )) ((x y z ) (u u )) (x y z u) (x y z u ) (x y z u) (x y z u ) (x y z u) (x y z u ) (x y z u) (x y z u ) , 2- elementar diz’yunksiya ( y ) uchun2 y (x y z u) (x y z u ) (x y z u) (x y z u ) (x y z u) (x y z u ) (x y z u) (x y z u ) , 2 Bu yerda va keyingi elementar diz’yunksiyalar uchun oralik teng kuchliliklarni tushirib qoldirdik. Download 2.36 Mb. Do'stlaringiz bilan baham: 
|