7.6.2 Teljes konjunktív normálforma

Bármely Boole-féle függvényhez konstruálható olyan formula, mely a következő tulajdonságokkal rendelkezik:

  • A formula diszjunkciók konjunkciója.
  • Minden diszjunkciós tag vagy egy változó vagy annak negáltja.
  • Minden konjunkciós tagban minden változó szerepel.
  • Ugyanaz a változó egy diszjunkcióban csak egyszer szerepel.
  • Nincs két olyan konjunkciós tag, amelyek csak a változók sorrendjében különböznek.

Teljes konjunktív normálforma: A fenti tulajdonságú formulát teljes konjunktív normálformának nevezzük.

Következmény.

A fenti előállítások következménye, hogy bármely igazságfüggvény előállítható negáció, konjunkció valamint diszjunkció segítségével, azaz ez a három művelet teljes függvényrendszert alkot.

Tétel 7.3: A negáció és konjunkció önmagukban is teljes függvényrendszert alkotnak.

Bizonyítás.

Az előzőekben láttuk, hogy , amiből az állítás azonnal következik.