Aussagenlogik: Lesen der Aufgabe und Zeigen der semantischen Äquivalenz mittels Äquivalenzumformungen

Question

Aufgabe:

Es sollen die semantischen Äquivalenzen für diese aussagenlogischen Formeln mit Hilfe von Äquivalenzumformungen gezeigt werden.

¬(A∨B)⇔C

\( \equiv(\neg C\vee(\neg A \wedge \neg B)) \wedge(A \vee B \vee C) \)

\( \equiv(\neg C \vee \neg A) \wedge(\neg C\vee \neg B) \wedge(A \vee B \vee C) \)

Problem 1:

Wie lese ich diese Aufgabe? Ich kenne bisher lediglich Aufgaben, bei denen Formel 1 ≡ Formel 2 gezeigt werden soll. Warum sind hier mehrere Formeln angegeben?

Problem 2:

Welchen Ansatz könnte ich für die Lösung verfolgen? Wäre wer so gnädig und könnte mir eine Lösung dieser Aufgabe als Beispiel zukommen lassen? Damit wäre mir stark geholfen!

Vielen Dank im Voraus und schönen Sonntag!

Answer 1

Aloha :)

Ich verwende immer Multiplikation \(\cdot\) für "und" und Addition \(+\) für "oder". Zusammen mit der Punkt-vor-Strich-Regel spart das viele Klammern. Wir zeigen im Folgenden, dass sich alle 3 Ausdrücke in denselben Ausdruck überführen lassen.

zu a) Logische Äquivalenz ist ja genau dann wahr, wenn beide Seiten wahr sind oder beide Seiten falsch sind:$$x\Leftrightarrow y=xy+\overline x\,\overline y$$Daher ist:$$\overline{A+B}\Leftrightarrow C=\overline{A+B}\,C+\overline{\overline{A+B}}\,\overline C=\underline{\overline A\,\overline B\,C+(A+B)\overline C}$$

zu b) Hier können wir direkt ausrechnen:$$(\overline C+\overline A\,\overline B)(A+B+C)=\overline CA+\overline CB+\underbrace{\overline CC}_{=0}+\underbrace{\overline A\,\overline B\,A}_{=0}+\underbrace{\overline A\,\overline B\,B}_{=0}+\overline A\,\overline B\,C$$$$=\underline{\overline A\,\overline B\,C+(A+B)\overline C}$$

zu c) Auch hier können wir direkt ausrechnen:$$(\overline C+\overline A)(\overline C+\overline B)(A+B+C)=(\underbrace{\overline C\,\overline C}_{=\overline C}+\overline A\,\overline C+\overline C\,\overline B+\overline A\,\overline B)(A+B+C)$$$$=(\,\overline C\underbrace{(1+\overline A+\overline B)}_{=1}+\overline A\,\overline B\,)(A+B+C)=(\overline C+\overline A\,\overline B)(A+B+C)$$$$\stackrel{(b)}{=}\underline{\overline A\,\overline B\,C+(A+B)\overline C}$$Damit haben wir die Gleichwertigkeit alle 3 Ausdrücke gezeigt.