Äquivalenzen

Def: Formeln F und G heißen äquivalent, wenn Mod(F) = Mod(G).

Satz: zu jeder Formel F existiert äquivalente Formel G in DNF.

Satz: zu jeder Formel F existiert äquivalente Formel G' in CNF.

aber ...wie groß sind diese Normalformen?