U aynan yolgon formuladir


Form ulalarning normal shakllari



Yüklə 488,36 Kb.
səhifə2/3
tarix03.05.2023
ölçüsü488,36 Kb.
#106576
1   2   3
Chinlik jadvali yordamida formulalarni mukammal diz’yunktiv normal formaga va mukammal kon’yunktiv normal formaga keltirish

Form ulalarning normal shakllari
Teng kuchli almashtirishlar bajarib, muloxazalar algebrasining formulalarini xar xil kurinishlarda yozish mumkin. Masalan, A -+ VS formulani L v i? C yoki {A v B )(A v Q . kurinishlarda yoza olamiz.

Mantik algebrasining kontakt va rele-kontaktli sxemalar, diskret texnikadagi tadbiqlarida va matematik mantikning boshk.a masalalarida formulalarning normal shakllari katga axamiyatga ega. Kuyidagi belgilashni kiritamiz:



kurinishdagi formula elementar dizʼyunksiya deb ataladi, bu yerda xam a = {st,, st2, ..., стл} ixtiyoriy kiymatlar satri va x(. uzgaruvchilar orasida bir xillari bulishi mumkin.

3 - t a ʼ r i f . Elementar dizʼyunksiyalarning konʼyu nksiyasi formulaning konʼyunktiv normal shakli (KNSH ) va element ar konʼyunksiyalarning dizʼyunksiyasi formulaning dizʼyunktiv normal shakli (DNSH) deb ataladi.

KN SH ga (x v u ) l (Zs v z) a (x v u v z) formula va D N SH ga x y v x z v xyz formula misol bula oladi.

1-teorema. Elementar muloxazalarning xar bir R formulasiga teng kuchli konʼyunktiv normal shakldagi Q formula mavj ud.

Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz:





  1. Rdagi elementar muloxazalar l va v amallari bilangina birlashtirilgan bulsa xam, lekin d sunggi amalni ifodalamaydi. Bu xolda Av(BaC) = (Av B)a(AvB) istributivlik konunidan foydalanib, sunggi amali d dan iborat teng kuchli formulaga keltiramiz;

  2. R formula - , V, d, -u, mantikiy amallar vositasida tuzilgan biror formulani ifodalasin. U xolda R ga (3) teng kuchliliklarni tatbik etib, R bilan teng kuchli va v, l bilan ifodalangan R 1 formulani xosil kilamiz. Agar R1 K N SH kurinishida bulmasa, unga Av (Ba Q = (AvB)a (Av B) distributivlik konunini tatbik etib, chekli adamlardan keyin R bilan teng kuchli Q konʼyunktiv normal shakldagi formulaga kelamiz.

Izox- R formulani konʼyunktiv normal shaklga keltirish jarayonida



Shunday kilib, P formulaning K N SH bittagina dizʼyunktiv (xvy) xaddan iborat ekan.





R formula tavtologiya ekanligini chinlik jadvaliga murojaat kilmay turib xam nikdash mumkinmi degan savolga kuyidagi chinlik alomati deb atalgan eorema ijobiy javob beradi.

2-teorema. R formula doimo chin bulishi uchun uning K N SH dagilar bir elementar dizʼyunktiv %adida kam ida bitta elementar muloxaza bilan birga bu muloxazaning inkori ham mavjud bulishi zarur va yetarli.
Isbot:


  1. R formulaning

R = A1 a A2 A ... a A„ (5)

K N SH dagi xar bir A1. xadida kamida bitta elementar muloxaza bilan birga bu muloxazaning inkori xam mavjud bulsin, yaʼni A/ = x v x v u v ...v i shaklida bulsin, u xolda x v x - J va J v A = J larga asosan A,- = J v ( y v . . . v u v V) = J buladi. Demak, R = J a J a ... a J = J buladi, yaʼni aynan chin formula buladi.




  1. Endi R tavtologiya bulsin va A, uning K N SH dagi shunday elementar dizʼyunktiv xadi bulsinki, unda birorta elementar muloxaza bilan birga uning inkori katnashmagan bulsin. Masalan, A, = x v u v ... v i shaklida bulsin. Endi, elementar muloxazalarning shunday kiymatlar satrini olaylikki, bu satrda x ning kiymati yo, u ning kiymati ch, Z ning kiymati yo, ..., i ning kiymati yo bulsin. U vakgda

D. = x v u v ... v i = yo v ch v ... v yo = yo v ... v yo = yo.

Demak, R = A1 a A2 a ... a A„ n i n g kiymati xam yolgon buladi. Ammo, eoremaning shartiga asosan R ning kiymati aynan chindir. Natijada karama-karshilikka keldik. Demak, elementar dizʼyu nksiyalarning xar bir xadida birorta muloxaza uzi va u:;ining inkori bilan katnashishi shart.






Yüklə 488,36 Kb.

Dostları ilə paylaş:
1   2   3




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin