Beweisen Sie, dass für alle G, H ∈ For_AL die aussagenlogische Formel eine Tautologie ist.

Question

Es sei Var_AL eine Menge von Aussagevariablen und es sei For_AL die Menge aller aussagenlogischen Formeln über Var_AL. Beweisen Sie, dass für alle G, H ∈ For_AL die aussagenlogische Formel
(G → H) → (¬H → ¬G)
eine Tautologie ist.
Was ist eine Tautologie und wie beweise ich das?

Answer 1

Hallo,

Eine Tautologie ist eine aussagenlogische Formel, die für jede Belegung der Aussagevariablen mit Wahrheitswerten immer den Wert "wahr" hat.

Das ist hier der Fall: 

(G → H) → (¬H → ¬G) 

⇔ (¬H ∨¬G) → (¬( ¬G) ∨¬(¬H))   nach Definition von "→"

⇔ (¬H ∨¬G) → (G ∨ H)                nach Definition von "→"

⇔ ¬ (¬G ∨¬H)  ∨ (¬H ∨¬G)          Gesetz von de Morgan

⇔ ¬(G∧H) ∨ (H∧G) wahr wegen Kommutativität von ∧ und dem Gesetz vom ausgeschlossenen Dritten: A ∨¬A ist wahr.

Gruß Wolfgang