Ich bin grade im Infostudium und habe das Fach Mathematische Logik. Schon in der ersten Woche habe ich einige Probleme. Es geht vorallem um die Herangehensweise wie ich die Folgende Aufgabe beweise. Ich weiß nicht wirklich wie ich semantisch beweisen soll, weil wir es sonst immer mit Wahrheitstabellen gemacht haben.
Vielen Dank im Voraus.
Eine Formel \( \varphi \in \mathrm{AL} \) heißt nicht-trivial, wenn sowohl \( \varphi \) als auch \( \neg \varphi \) erfüllbar ist. Außerdem definieren wir den Junktor,\( \oplus^{\prime \prime} \) durch \( \llbracket \varphi \oplus \psi \rrbracket^{\jmath}=1 \) gdw. \( \llbracket \varphi \rrbracket^{j} \neq \llbracket \psi \rrbracket^{\jmath} \) (exklusives Oder).
(a) Sind folgende Formeln Tautologien, nicht-trivial oder unerfüllbar? Argumentieren Sie semantisch mittels Interpretationen (ohne Wahrheitstabellen und Äquivalenzumformungen).
(i) \( ((A \oplus B) \oplus (C \oplus D)) \wedge(\neg (A \rightarrow B) \wedge \neg(C \rightarrow D))\)
(ii) \( ((X \rightarrow \neg X) \vee(Y \rightarrow \neg Y)) \wedge((X \rightarrow 0) \oplus(1 \rightarrow Y)) \)
(b) Zeigen Sie nur durch Åquivalenzumformungen, dass folgende Formeln logisch äquivalent sind.
\( (A \vee(A \wedge B)) \vee(C \wedge D)\)
und
\( (\neg C \rightarrow A) \wedge((\neg A \rightarrow C) \wedge \neg(\neg A \wedge \neg D))\)
Hinweis: Sie dürfen auch die Åquivalenz \( \psi \rightarrow \varphi \equiv \neg \psi \vee \varphi \) für \( \psi, \varphi \in \mathrm{AL} \) verwenden.
