Chr. Nelius: Mathematik für Informatiker I 30.10.2000

(2.4b) Nachweis der Transitivität von “⟹“ mit Hilfe einer Wahrheitstafel

((P⟹Q) ∧ (Q⟹R)) ⟹ (P⟹R)

P Q R P⟹Q Q⟹R (P⟹Q) ∧ (Q⟹R) P⟹R ((P⟹Q) ∧ (Q⟹R)) ⟹(P⟹R)
W W W  W  W  W  W  W
W W F  W  F  F  F  W
W F W  F  W  F  W  W
W F F  F  W  F  F  W
F W W  W  W  W  W  W
F W F  W  F  F  W  W
F F W  W  W  W  W  W
F F F  W  W  W  W  W

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

\underline{B) Prädikatenlogik} Es sei A(x) ein Prädikat.

Bezeichnung  Bedeutung
∀ x : A(x)  für alle x gilt A(x)
∀ x ∈ M : A(x) für alle Elemente x einer Menge M gilt A(x)
∃ x : A(x)  es gibt ein x,für das A(x) gilt

∃ x ∈ M : A(x) es gibt ein Element x aus einer Menge M für

das A(x) gilt

\underline{(2.5) SATZ:} Negation von Formeln mit ∀ und ∃ a) ¬( ∀ x : A(x) ) ⟺ ( ∃ x : ¬A(x) )

b) ¬( ∃ x : A(x) ) ⟺ ( ∀ x : ¬A(x) )