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.