Ersetzung der Aussagen in einer Tautologie
Haben wir eine Tautologie gegeben, so können wir die einzelnen Aussagen durch andere ersetzen. Die so gebildete neue Aussage bleibt eine Tautologie.
Beispiel:
Die Aussage
\(\qquad\) | \((A \lor B) \iff (B \lor A)\) |
ist eine Tautologie.
Substituieren wir in dieser Aussage \(A\) durch \((\lnot A \land B)\), so ist diese neue Aussage
\(\qquad\) | \((\underbrace{A}_{(\lnot A \land B)} \lor B) \iff (B \lor \underbrace{A}_{(\lnot A \land B)})\) |
\(\qquad\) | \(((\lnot A \land B) \lor B) \iff (B \lor (\lnot A \land B))\) |
ebenfalls eine Tautologie.
Beweis
Wir können diese Tautologien anhand von Wahrheitstabellen zeigen.
Wahrheitstabelle zu \((A \lor B) \iff (B \lor A)\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & A \lor B & B \lor A & (A\lor B) \iff (B \lor A) \ \\ \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{w} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Wahrheitstabelle zu \(((\lnot A \land B) \lor B) \iff (B \lor (\lnot A \land B))\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot A & \lnot A \land B & (\lnot A \land B) \lor B & B \lor (\lnot A \land B) & ((\lnot A \land B)\lor B) \\ & & \hspace{-0.8em} & & & & & \iff(B \lor (\lnot A \land B)) \ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\ \hline\end{array}\) |
\(\enspace\)