Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja
Download 2.36 Mb.
|
7-ma\'ruza
|
1- teorema. Mantiq algebrasining ixtiyoriy formulasini KNShga keltirish mumkin.
Isboti. Mantiq algebrasining ixtiyoriy formulasini tahlil qilib, agar berilgan formula KNShda bo‘lmasa, u vaqtda quyidagi ikkita hollardan biri ro‘y berishini ta’kidlaymiz: a) berilgan formuladagi elementar mulohazalar faqat , va belgilar bilangina birlashtirilgan bo‘lsada, belgilar eng so‘nggi amallarni ifodalamaydi; b) berilgan formula tarkibidagi elementar mulohazalar , va belgilardan tashqari va/yoki belgilar bilan ham birlashtirilgan.
a (b c) (a b) (a c) teng kuchlilikdan foydalanib, ((1)ga qarang) berilgan formulani unga teng kuchli formulaga keltiramiz. elementar mulohazalari faqat , va belgilar bilangina birlashtirilgan formulani hosil qilamiz. Agar hosil qilingan formula KNShda bo‘lmasa, u vaqtda u, albatta, a) holda ifodalangan shaklda bo‘ladi. a) hol uchun ifodalangan jarayonni chekli marta qo‘llagandan so‘ng (zarur bo‘lsa (2) teng kuchliliklardan ham foydalanib) berilgan formulaga teng kuchli KNShdagi formulani hosil qilamiz. ■ Teoremaning yuqorida keltirilgan isboti konstruktiv xususiyatga ega, ya’ni bu isbotdan mantiq algebrasining berilgan formulasi uchun KNShni hosil qilishda algoritm sifatida foydalanish mumkin.
P ((( x y) (x y)) x) ((( x y) (x y)) (x y)) ((x y) x) ((x y) x) ((x y) (x y)) ((x y) (x y)) (x x y) (x x y) (x x y y) (x x y y) (x y) [J y] (J y) (x J ) (x y) J J J x y . Demak, P x y . Berilgan formulaning topilgan KNShida x va y o‘zgaruvchilarning bittagina elementar diz’yunksiyasi bor, ya’ni berilgan formula uchun KNSh bittagina x y diz’yunktiv haddan iboratdir. ■ Q (x y (x y)) ((x y) (x y)) ((x y) (x y)) ((x y) (x y)) ((x y x) (x y y)) ((x x y) ( y x y)) (x y) (x y) (x y) (x y) (x y) (x y) teng kuchliliklarga ega bo‘lamiz. Shunday qilib, (x y) (x y) formula berilgan Q formula uchun KNSh bo‘lib, u ikkita x y va x y diz’yunktiv hadlarning kon’yunksiyasidan iboratdir. ■ Download 2.36 Mb. Do'stlaringiz bilan baham: 
|