Logische Gesetze Methoden zum Beweisen und zum Vereinfachen
Beweisen lassen sich Regeln und Gesetze in der Logik durch Wahrheitstabellen. Besteht eine Regel jedoch aus mehreren atomaren Aussagen, die in Kombination zu weiteren komplexen Aussagen führen, dann wird die Wahrheitstabelle sehr groß. Wie wir bereits wissen, besteht eine Wahrheitstabelle, in die \(n\) einfache Aussagen eingehen, aus \(2^n\) Zeilen. Bei drei einfachen Aussagen bedeutet dies bereits eine Tabelle mit \(8\) Zeilen. Oft ist es dann einfacher, andere Methoden zum Beweis einer Aussage anzuwenden.
Wir können bereits bewiesene Regeln und Gesetze verwenden, um Aussagen zu vereinfachen oder weitere Regeln und Gesetze zu beweisen. In den folgenden Kapiteln lernen wir verschiedene Regeln kennen. Sie alle können dazu benutzt werden, komplexe Aussagen zu vereinfachen.
Eine dritte Methode ist, aufgrund der möglichen Wahrheitswertkombinationen Rückschlüsse auf die zu beweisende Regel zu geben. Hierzu benötigt man oft Fallunterscheidungen.
Beispiel:
Wir werden nun das Absorptionsgesetz mit unterschiedlichen Methoden beweisen. Das Absorptionsgesetz für die Konjunktion lautet:
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\iff \alpha\enspace\) ist eine Tautologie |
Beweis mit einer Wahrheitstabelle
Wir beweisen das Absorptionsgesetz mit einer Wahrheitstabelle. In die Tabelle gehen die einfachen Aussagen und die komplexen Aussagen als Spalten ein, die Bestandteil des Absorptionsgesetzes sind. Dies sind also die einfachen Formeln \(\alpha\) und \(\beta\), die zusammengesetzten Formeln \(\alpha \lor \beta\) und \(\alpha \land (\alpha \lor \beta)\) und als rechte Spalte die zu beweisende Aussage \((\alpha \land (\alpha \lor \beta))\iff \alpha\).
Da die Tabelle aus zwei einfachen Aussagen aufgebaut ist, besteht sie aus \(2^2=4\) Zeilen. Wir füllen diese Zeilen mit Wahrheitswerten, wobei wir sämtliche Wahrheitswertkombinationen für die einfachen Aussagen angeben und sich alle anderen Wahrheitswerte entsprechend ihrer Aussage ergeben.
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \lor \beta & \alpha \land (\alpha \lor \beta) & (\alpha \land (\alpha \lor \beta)) \iff \alpha\ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Da die letzte Spalte nur wahre Werte enthält, ist die Aussage \((\alpha \land (\alpha \lor \beta))\iff \alpha\) eine Tautologie.
Beweis unter Verwendung anderer Gesetze
Wir beweisen das Absorptionsgesetz, indem wir andere Gesetze anwenden. Diese Gesetze werden wir erst in den folgenden Kapiteln diskutieren und die Beweise dieser Gesetze an entsprechender Stelle angeben. Wir können hier also voraussetzen, dass die verwendeten Gesetze ihre Gültigkeit haben.
Wir bringen den Ausdruck der linken Seite \(\alpha \land (\alpha \lor \beta)\) durch Äquivalenzumformungen auf den Ausdruck der rechten Seite \(\alpha\). Wir beginnen mit einem Trick, indem wir das Neutralitätsgesetz \((\gamma\lor \mathrm{f}) \iff \gamma \) mit \(\gamma = \alpha\) verwenden. Wir erhalten dann die folgende Äquivalenz
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(((\alpha \lor \mathrm{f})\land (\alpha \lor \beta))\) |
Wir wenden zweimal das Kommutativgesetz \((\mu \land \nu ) \iff (\nu \land \mu)\) an, einmal für \(\mu=\alpha\) und \(\nu=\mathrm{f}\) und einmal für \(\mu=\alpha\) und \(\nu=\beta\). Damit erhalten wir
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(((\mathrm{f} \lor \alpha)\land (\beta \lor \alpha))\) |
Nun wenden wir das Distributivgesetz \(((\mu \land \nu) \lor \gamma) \iff ((\mu \lor \gamma) \land (\nu \lor \gamma))\) an für \(\mu=\mathrm{f}\), \(\nu=\beta\) und \(\gamma=\alpha\) und erhalten
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(((\mathrm{f} \land \beta)\lor \alpha)\) |
Mit dem Kommutativgesetz \((\mu \land \nu) \iff (\nu \land \mu)\) für \(\mu=\mathrm{f}\) und \(\nu=\beta\) ergibt sich
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(((\beta \land \mathrm{f})\lor \alpha)\) |
Wir wenden das Dominanzgesetz \((\gamma \land \mathrm{f}) \iff \mathrm{f}\) für \(\gamma = \beta\) an und erhalten
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(( \mathrm{f}\lor \alpha )\) |
Mit dem Kommutativgesetz \((\mu \land \nu) \iff (\nu \land \mu)\) für \(\mu=\mathrm{f}\) und \(\nu=\alpha\) ergibt sich
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \((\alpha \lor \mathrm{f})\) |
Mit der Neutralitätsgesetz \((\gamma\lor \mathrm{f}) \iff \gamma\) für \(\gamma=\alpha\) erhalten wir schließlich
\(\qquad\) | \((\alpha \land (\alpha \lor \beta))\) | \(\enspace\iff\enspace\) | \(\alpha\) |
Wir haben also gezeigt, dass man das Absorptionsgesetz aus anderen Gesetzen herleiten kann.
Beweis durch Argumentation
Wir beweisen das Absorptionsgesetz mithilfe logischer Argumentationen. Hierbei unterscheiden wir einzelne Wahrheitswerte und überlegen uns, was für Auswirkungen sie auf die zu beweisende Aussage haben.
Wir bezeichnen zur Vereinfachung die linke Seite mit \(\gamma\), d.h. \(\gamma = \alpha \land (\alpha \lor \beta )\). Wir müssen nachweisen, dass \(\gamma \iff \alpha \) eine Tautologie ist, d.h. dass \(\gamma\) stets denselben Wahrheitswert hat wie \(\alpha\). Dazu unterscheiden wir zwei Fälle:
\(\tiny\blacksquare\quad\) | Fall 1:\(\enspace\alpha\) ist wahr Dann ist die Oder-Aussage \(\alpha \lor \beta \) ebenfalls wahr. Das bedeutet, dass die Und-Aussage \(\gamma \) aus zwei wahren Teilaussagen besteht, nämlich aus \(\alpha\) und \((\alpha \lor \beta )\). Damit ist auch \(\gamma\) wahr, d.h. \(\gamma\) hat den selben Wahrheitswert wie \(\alpha\). |
\(\tiny\blacksquare\quad\) | Fall 2: \(\enspace\alpha\) ist falsch In diesem Fall ist auch die gesamte Und-Aussage \(\gamma \) falsch, d.h. \(\gamma\) hat in diesem Fall ebenfalls den selben Wahrheitswert wie \(\alpha\). |
Egal, welchen Wahrheitswert \(\alpha\) annimmt, \(\gamma\) wird immer den gleichen Wahrheitswert annehmen. Wir haben also gezeigt, dass die Aussage \(\gamma \iff \alpha\) eine Tautologie ist.
\(\enspace\)