TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen SS12/Blatt 2 - Beispiel 5

Let $L\,$ be a language of propositional logic where formulas are build only from Boolean variables using the primitive connectives $\neg \,\land \,\lor \,\rightarrow \,\leftrightarrow$ (thus $\top \,$ and $\perp \,$ are not part of the language). Furthermore, let $A\,$ be a formula of $L\,$ containing no occurrence of $\neg \,$ and let $B\,$ be any formula of $L\,$.

Show the following propositions:

1. Let $I\,$ be an interpretation assigning to all atomic formulas of $A\,$ the truth value 1. Then, $A\,$ is true under $I\,$.
2. If $\models B\leftrightarrow \neg A$, then $B\,$ contains at least one occurence of $\neg \,$

Hint: Show Item (1) by induction on the logical complexity of $A\,$ (i.e., on the number of occurences of logical connectives in $A\,$). Show Item (2) using Item (1).

Lösungsvorschlag

Es lässt sich leicht zeigen, dass bei einer jeden binären Operation die nur True-Werte als Eingangsparameter hat wieder ein True-Wert heraus kommt. Das heißt, solange wir Atome oder binäre Operationen im schrittweisen Auflösen der Formel erhalten, können wir davon ausgehen, dass I:A True ist.

Wenn wir uns Beispiel 3,4 von Übungsblatt 1 anschauen, müssen wir nun die Induktion ähnlich aufschreiben. Nur dass dieses Mal die Behauptung ist, dass f modulo 2 gleich 0 ist. Da wir nur zwei Möglichkeiten haben, Parameter sind Atome oder Parameter sind Formeln die aus binären Operationen bestehen, ist damit der erste Unterpunkt bewiesen.

Alternativer Lösungsvorschlag

Punkt 1

Mittels struktureller Induktion und der logischen Komplexität von Formeln.

Induktionsanfang:

• $lc(A)=0$ dann ist $A$ von der Form $A=\alpha$ und $\alpha$ ein Atom.
  • $I(\alpha )=t$
• $lc(A)=2$ dann ist $A$ von der Form $A=\alpha \circ \beta$.
  • $I(\alpha )=t$
  • $I(\beta )=t$

Damit sind alle Basisfälle abgedeckt.

Induktionsschritt:

• $lc(A)=n$ dann kann $A$ von folgenden Formen sein:
  • $A=A'\circ \alpha ,I(\alpha )=t$ und $lc(A')=n-2$
  • $A=A'\circ A''$ Alle Atome in $A'$ und $A''$ müssen $t$ sein, da die beiden Subformeln nur aus einer Verkettung von Basisfällen bestehen können und diese schon oben bewiesen sind.

q.e.d

Punkt 2

Lösung mittels Proof by Contradiction

1. Eine Interpretation $I$ mit der Variablenbelegung $I(\alpha _{\text{1..n}})=t$ und nehmen wir an B enthält keine Negation.

• $I\models A$ Beweis siehe Lemma 5.1
• $I\models B$ Beweis siehe Lemma 5.1

=> $\nvDash B\leftrightarrow \neg A$ und wir haben den gewünschten Clash