Manche Ausdrücke sind immer wahr, egal wie man die Variablen belegt. Und manche sagen genau dasselbe, obwohl sie verschieden aussehen. Rechts steht jedes Mal die Wahrheitstafel als Beweis: Gleiche Spalten heißen gleiche Ausdrücke. Mit Weiter geht es Schritt für Schritt voran.
Skript Teil 1, Folien 12 bis 14: Tautologie, Gleichheit und Rechengesetze.
Wer eine Formel vereinfachen will, braucht Regeln, die den Wert nicht ändern. Diese Regeln heißen Rechengesetze. Damit man ihnen trauen kann, prüft man jedes mit der Tafel.
So gehen wir vor:
Ein logischer Ausdruck wird Tautologie genannt, wenn sich für alle Kombinationen der Argumente immer der Wahrheitswert 1 ergibt. Ergibt sich immer 0, dann heißt der Ausdruck eine Kontradiktion.
Eine Tautologie ist immer wahr: In ihrer Spalte steht nur 1. Eine Kontradiktion ist immer falsch: nur 0. Die meisten Ausdrücke sind keins von beiden.
Rechts stehen die drei Beispiele des Skripts. Zwei lange Ausdrücke haben oben kurze Namen bekommen: und .
vergleicht „wenn , dann “ mit „wenn nicht , dann nicht “. Das zweite heißt Kontraposition.
Beide Implikationen haben die Spalte 1101. Gleiche Werte in jeder Zeile, also ist das überall 1.
Beispiel: „Wenn es regnet, ist die Straße nass“ sagt dasselbe wie „Wenn die Straße nicht nass ist, regnet es nicht“.