TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen WS12/Blatt 1 - Beispiel 4

Give a proof or a counter-example for the following statements:

(a) If $\phi \to \psi$ is a contradiction, then $\phi$ is a tautology and $\psi$ is a contradiction.

(b) If $\phi \lor \psi$ is a tautology, then $\phi$ is a tautology or $\psi$ is a tautology.

(c) If $\phi$ and $\psi$ have no propositional letter in common, then $\phi \lor \psi$ is a tautology iff $\phi$ is a tautology or $\psi$ is a tautology.

Lösungsvorschlag

(a) $\phi \to \psi$ ist syntaktisch gleich mit $\neg \phi \lor \psi$, daher ist die einzige Möglichkeit um false zu bekommen $\phi$ gleich true und $\psi$ gleich false. -> somit ist das Statement wahr.

(b) $\phi \lor \psi$ kann auch eine Tautologie werden wenn $\phi$ und $\psi$ antivalent zueinander sind.

Daher, dass das selbe Modell bei verschiedenen Interpretationen, wobei $\phi$ und $\psi$ ungleich sind, immer true ergibt und somit eine Tautologie ist. -> somit ist das Statement falsch.

(c)!!VERSUCH KEINE GARANTIE AUF RICHTIGKEIT!! Definition Wikipedia:

"In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is a variable which can either be true or false."

Wäre für mein Verständnis eigentlich der selbe Fall wie (b) da I($\phi$)=$\neg \psi$ und daher ergäbe $\phi \lor \psi$ eine Tautologie auch wenn keines der beiden tautologisch ist.

Anmerkung: so wie ich es verstehe, heißt "no propositional letters in common", dass man die Aussagen nicht über einen zugrundeliegenden Term koppeln kann, wie das bei b) ($\phi =A,\psi =\neg A$) möglich war. Ergo müsste einer der Terme eine Tautologie sein -> Aussage wahr.

Anmerkung zur Anmerkung: Der oben erwähnten Anmerkung schließe ich mich an. Dadurch, dass die Formeln keine propositional letters gemein haben, könnte man unter der Voraussetzung, dass beide keine Tautologien sind eine Interpretation wählen, die die propositional letters beider Formeln so belegt, dass beide falsch wären. Das ist sicher möglich, denn: durch die genannte Voraussetzung gibt es bestimmt eine Interpretation für beide Formeln, sodass die Interpretation der Formel falsch ist und durch die nicht vorhandene Überschneidung ist es auch sicher möglich, dass das für beide Formeln die selbe Interpretation ist. Der haarige Unterschied ist eben die Überschneidung. Würden sich die Formeln überschneiden, könnte es wie in b) eben sein, dass eine Interpretation der einen Formel immer dann falsch ist, wenn die der anderen wahr ist und es wäre somit nicht möglich eine Interpretation zu finden, die beide gleichzeitig falsch macht. Das ist aber hier nicht der Fall, sodass die einzige Möglichkeit die Disjunktion als Tautologie sicherzustellen ist, eine der beiden Formeln zur Tautologie zu machen.