Definíció: Egy F formulahalmaznak az f formula logikai következménye, ha a változók minden olyan kiértekélésére, amely mellett F összes eleme igaz egyben az f formula is igaz lesz.
Definíció: Ha az f formula logikai következménye az üres halmaznak, akkor azt mondjuk, hogy f tautológia.
Példa: Egy formulában fogalmazzuk meg, hogy négy tárgyat három dobozba rakva lesz két tárgy, amely ugyanabba a dobozba kerül. Először lássuk a változóinkat:
Majd fogalmazzuk meg hogy minden tárgy legalább(!) egy dobozba kerül:
Majd fogalmazzuk meg hogy lesz olyan tárgy, amely ugyanabba a dobozba kerül:
Két formulánk konjunkcióval összekötve a fenti állítást írja le, azaz tautológia.
Definíció: Egy f és egy g formula (szemantikusan) ekvivalensek ha ugyanazt a Boole-függvényt írják le. Ezzel ekvivalens, hogy az f <-> g formula egy tautológia.
Lemma:
Lemma: (i) Egy tautológiába helyettesítve tautológiát kapunk.
(i)' Két ekvivalens formulában ugyanazt a helyettesítést végezve ekvivalens formulákhoz jutunk.
(ii) Egy formula részformuláját a részformula egy ekvivalensével helyettesítve az eredeti formulával ekvivalenset kapunk.
Lemma:
(i) Minden De Morgan bázisú formula átalakítható egy vele ekvivalens formulává, amely negációt csak változókra alkalmazootan tartalmaz.
(ii) Minden De Morgan bázisú formula átalakítható egy vele ekvivalens DNF, illetve CNF formulává.