studyklar
MG · Übungsblatt 1 · Aufgabe 2

Tautologien nachweisen

Eine Tautologie ist ein Ausdruck, der immer wahr ist, egal welche Werte die Variablen haben. Hier wird das für zwei Ausdrücke mit einer Wahrheitstafel gezeigt. Der ganze Lösungsweg steht offen da, die Erklärung gehört jeweils zum aktuellen Schritt. Mit Weiter geht es Schritt für Schritt voran. Ein Klick auf einen Schritt springt direkt dorthin.

Die Aufgabe

Zeigen Sie, dass folgende Ausdrücke Tautologien sind:

(i)
((p⇒q)∧(¬p⇒q))⇔q\big((p \Rightarrow q) \land (\neg p \Rightarrow q)\big) \Leftrightarrow q
(ii)
(p⇒q)⇔(¬q⇒¬p)(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)

Zu zeigen ist, dass beide Ausdrücke Tautologien sind. So heißt nach der Vorlesung ein Ausdruck, der für alle Belegungen der Variablen den Wert 1 hat. Ist er dagegen immer 0, heißt er Kontradiktion.

Der sichere Weg ist die Wahrheitstafel: Man rechnet alle Zeilen aus. Steht in der letzten Spalte überall 1, ist der Ausdruck eine Tautologie. Eine einzige 0 würde reichen, um das zu widerlegen.

So gehen wir vor:

  1. (i) Tafel aufstellen, Spalte für Spalte, und verstehen, warum sie immer 1 ist.
  2. (ii) genauso, und den Namen dieser Regel kennenlernen: Kontraposition.
Merke: Tautologie heißt: in der letzten Spalte steht in jeder Zeile 1.

Vier Zeilen und eine Abkürzung

Abkürzung für die linke Seite
C=(p⇒q)∧(¬p⇒q)C = (p \Rightarrow q) \land (\neg p \Rightarrow q)
Aus Aufgabe 1 („Wahrheitstafeln aufstellen“): Eine Belegung ist eine Kombination von Werten für die Variablen, mit 1 für wahr und 0 für falsch. Jede Belegung ist eine Zeile der Tafel.

In (i) kommen nur pp und qq vor. Jede ist 0 oder 1, also gibt es 2⋅2=22=42 \cdot 2 = 2^2 = 4 Zeilen. pp wechselt langsam (0 0 1 1), qq schnell (0 1 0 1). Die Spalte „Zeile“ zählt ab 1: Zeile 1 ist p=0p = 0, q=0q = 0, Zeile 3 ist p=1p = 1, q=0q = 0.

Die große Klammer vor ⇔\Leftrightarrow bekommt einen kurzen Namen: CC. Am Ende ist dann nur noch C⇔qC \Leftrightarrow q zu prüfen.

Die erste Implikation p ⇒ q

Zeile für Zeile
p⇒q: 1, 1, 0, 1p \Rightarrow q:\ 1,\,1,\,0,\,1
Aus Aufgabe 1 („Wahrheitstafeln aufstellen“): In a⇒ba \Rightarrow b heißt aa die Voraussetzung und bb die Folgerung. Die Implikation ist nur falsch, wenn die Voraussetzung 1 ist und die Folgerung 0. In allen anderen Zeilen ist sie 1.

In p⇒qp \Rightarrow q ist das nur in Zeile 3 so: p=1p = 1, q=0q = 0. Dort steht 0, sonst 1.

Noch 9 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Tafel zu (i)

C steht für (p ⇒ q) ∧ (¬p ⇒ q)

Abbildung 1Tafel zu (i)

C steht für (p ⇒ q) ∧ (¬p ⇒ q)

Zeileppqqp⇒qp \Rightarrow q¬p\neg p¬p⇒q\neg p \Rightarrow qCCC⇔qC \Leftrightarrow q
10011001
20111111
31000101
41110111
Legendegerade ausgewertetdie Zelle, auf die es ankommtDie ganze Tafel zu (i).