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.