Chr. Nelius: Mathematik für Informatiker I (WS 2000/01) 30.10.2000

\underline{(2.3) SATZ:} Formeln für ¬ , ∨ und ∧ P, Q und R seien beliebige logische Formeln. Dann sind die folgenden logischen Formeln allgemeinrichtig:

a) P ∨ (¬P)

b) ¬(P ∧ ¬P)

c) ¬(¬P) ⟺ P

d) P ∧ Q ⟺ Q ∧ P , P ∨ Q ⟺ Q ∨ P (Kommutativgesetze)

e) (P ∧ Q) ∧ R ⟺ P ∧ (Q ∧ R) , (P ∨ Q) ∨ R ⟺ P ∨ (Q ∨ R) (Assoziativgesetze)

f) ¬(P ∧ Q) ⟺ (¬P) ∨ (¬Q) , ¬(P ∨ Q) ⟺ (¬P) ∧ (¬Q) (Regeln von de Morgan)

g) P ∧(Q∨R) ⟺ (P ∧Q)∨(P ∧R) , P ∨(Q∧R) ⟺ (P ∨Q)∧(P ∨R) (Distributivgesetze)

Ein Beweis wird mit Hilfe von Wahrheitstafeln geführt.

\underline{(2.4) SATZ:} Formeln für die Implikation P, Q und R seien beliebige logische Formeln. Dann sind die folgenden logischen Formeln allgemeinrichtig:

a) (P ⟺ Q) ⟺ [(P ⟹ Q) ∧ (Q ⟹ P)]

b) [(P ⟹ Q) ∧ (Q ⟹ R)] ⟹ (P ⟹ R) (Transitivität)

c) (P ⟹ Q) ⟺ (¬P ∨ Q)

d) (P ⟹ Q) ⟺ (¬Q ⟹ ¬P) (Kontraposition)

e) (P ⟹ Q) ⟺ [(P ∧ ¬Q) ⟹ ¬P ]

f) (P ⟹ Q) ⟺ [(P ∧ ¬Q) ⟹ Q]

g) (P ⟹ Q) ⟺ [(P ∧ ¬Q) ⟹ (R ∧ ¬R)]

Ein Beweis wird mit Hilfe von Wahrheitstafeln oder durch äquivalentes Umformen geführt. Die Formeln e),f) und g) sind Grundlage für die indirekte Beweisführung.