Morgansche Regel

Lemma (de Morgansche Regel). Für alle $ϕ, ψ \in A L$ gilt:

\neg (ψ \land ϕ) \equiv \neg ψ \lor \neg ϕ .

Beweis. Sei

β

eine passende Belegung.

Dann gilt

[[\neg (ψ \land ϕ)]]^{β} = 1 gdw. [[ψ \land ϕ]]^{β} = 0

gdw. mindestens eins von [[ψ]]^{β}, [[ϕ]]^{β} gleich 0

gdw. mindestens eins von [[\neg ψ]]^{β}, [[\neg ϕ]]^{β} gleich 1.

gdw. [[\neg ψ \lor \neg ϕ]]^{β} = 1.