|
Igazságfüggvények, normálformák
Déni 2008.02.05. 17:31
Igazságfüggvények, normálformák
Minden kétváltozós műveletet felírhatunk a negáció, a diszjunkció és a konjunkció segítségével (ůA, AŮB, AÚB).
A®B=ůAÚB
A«B=(A®B)Ů(B®A)=(ůAÚB)Ů(ůAÚB)
AŻB=ů(AÚB)
A˝B=ů(AŮB)
AĹB=ů(A«B)=ů ( (ůAÚB) Ů (ůBÚA) )=(AŮůB)Ú(BŮůA)
A kettőnél több változós műveletek körében sem jutunk „lényegesen új” műveletekhez: az eddig megismert műveletekkel már az ítéletkalkulus minden lehetséges művelete kifejezhető.
Az ítéletkalkulus minden művelete előállítható negáció, diszjunkció és konjunkció segítségével.
A B C g(A,B,C)
i i i h
i i h h
i h i h
i h h i
h i i h
h i h i
h h i i
h h h h
Tudjuk jól, hogy a diszjunkció akkor és csak akkor igaz, ha valamelyik tagja igaz . g értéktáblában 3 igaz sor van. Fejezzük ki g-t egy 3 tagű diszjunkcióval. Az egyes tagokat konjunkciókkal fogjuk megadni úgy, hogy pontosan akkor legyenek igazak, amikor azt g értéktáblázata előírja.
g(A,B,C)=(AŮůBŮůC) Ú (ůAŮBŮůC) Ú (ůAŮůBŮC)
Az egyes igazi soroknak megfelelő konjunkciós tagokat a következő módon építjük föl: amelyik változó értéke igaz, azt negálatlanul, amelyik hamis, azt negálva vesszük be a konjunkciós tagba. Pl.:
A B C D f(A,B,C,D)
i h h i i
h i h i i
h h i h i
egyébként h
AŮůBŮůCŮD
ůAŮBŮůCŮD Vegyük ezek diszjunkcióját
ůAŮůBŮCŮůD
f(A,B,C,D)=(AŮůBŮůCŮD)Ú(ůAŮBŮůCŮD)Ú(ůAŮůBŮCŮůD)
Hasonló eljárással bármely értéktáblázat i értékű sorainak ismeretében felírhatunk egy olyan formulát, amelyben csak a ů , Ů , Ú műveletek szerepelnek , és amelynek értéktáblázata azonos az adott értéktáblázattal. Ha a táblázatban nincs i értékű sor, akkor a keresett formula nyílván azonos h-val.
Az így kapott formulákat diszjunktív normálformáknak nevezzük.
DEF: Diszjunktív normálforma : olyan diszjunkció, amelynek tagjai konjunkciók, e konjunkciók tagjai pedig változók vagy változók negáltjai.
2. Ha viszont egy értéktáblázat h értékű soraiból indulunk ki, akkor így járhatunk el: Minden h értékű sorhoz készítünk olyan diszjunkciót, amelynek tagjai a vizsgált sor változói, i értékűek negálva, h értékűek negálatlanul. Az adott sor szerinti értékeléssel diszjunkciónk minden tagja, így az adott diszjunkció is hamis lesz. E diszjunkciók konjunkciója azonos lesz a táblázat adta művelettel, hiszen ha e konj. valamely tagja hamis, akkor a művelet értéke is hamis. Pl.:
A B C f(A,B,C)
i h i h
h h h h
egyébként i
(ůAÚBÚůC)Ů(AÚBÚC)şf(A,B,C)
-ha nincs hamis sor, akkor fşi
Konjunktív normálforma: formula, amely olyan konjunkció, amelynek tagjai diszjunkciók, e diszjunkciók tagjai pedig változók vagy változók negáltjai.
Az ítéletkalkulus olyan formulái, melyekben csak ů , Ů , Ú műveletek szerepelnek és amelyekben a ů jel csak puszta változókra vonatkozik, alkalmasak kapcsolók rendszeréből álló áramkörök leírására. Az egymástól független kapcsolóknak különböző, az egyállásúaknak azonos, a váltóállásúaknak pedig azonos, de ellentétes nagyságú változókat, a sorbakapcsoltaknak konjunkciót, a párhuzamosan kapcsoltaknak diszjunkciót feleltetve meg. Az említett formulák és áramkörök között megfeleltetést létesítünk. Az igaz ill. a hamis logikai értéknek a vezető, ill. a szigetelő állapot felel meg.
|
AJÁNLOM AZ OLDALT
