Resolutionskalkül: Mit Hilfe der Kontradiktion kann man die Aussagenlogik beweisen.

Question

Aufgabe:

Untersuchen Sie mit dem Resolutionskalkül, ob die folgende Formel eine Tautologie ist.

\( \left(x_{1} \wedge \neg x_{2} \wedge \neg x_{3}\right) \vee\left(x_{1} \wedge \neg x_{2} \wedge x_{3}\right) \vee\left(\neg x_{1} \wedge \neg x_{2}\right) \vee\left(x_{2} \wedge x_{3}\right) \vee\left(x_{2} \wedge \neg x_{3}\right) \)

Ansatz:

Hier habe ich erstmal mit deMorgan die Negation gebildet, aber um die Kontradiktion zu Zeigen(Definition der Tautologie). Habe es versucht, mit Verdopplung zu zeigen, bin aber nicht weiter gekommen.

Answer 1

Das läuft aufs stupide Ausmultiplizieren hinaus.

$$ \left( x _ { 1 } \wedge \neg x _ { 2 } \wedge \neg x _ { 3 } \right) \vee \left( x _ { 1 } \wedge \neg x _ { 2 } \wedge x _ { 3 } \right) \vee \left( \neg x _ { 1 } \wedge \neg x _ { 2 } \right) \vee \left( x _ { 2 } \wedge x _ { 3 } \right) \vee \left( x _ { 2 } \wedge \neg x _ { 3 } \right) \\ \Leftrightarrow \left[ \left( x _ { 1 } \wedge \neg x _ { 2 } \right) \wedge \left( \neg x _ { 3 } \vee x _ { 3 } \right) \right] \vee \left( \neg x _ { 1 } \wedge \neg x _ { 2 } \right) \vee \left[ x _ { 2 } \wedge \left( x _ { 3 } \vee \neg x _ { 3 } \right) \right] \\ \Leftrightarrow \left( x _ { 1 } \wedge \neg x _ { 2 } \right) \vee \left( \neg x _ { 1 } \wedge \neg x _ { 2 } \right) \vee x _ { 2 } \\ \Leftrightarrow \left[ \neg x _ { 2 } \wedge \left( x _ { 1 } \vee \neg x _ { 1 } \right) \right] \vee x _ { 2 } \\ \Leftrightarrow \neg x _ { 2 } \vee x _ { 2 } = \text{ WAHR } $$

Ich habe hier zweimal das Distributivgesetz verwendet und außerdem die Tatsache, dass A v -A immer eine wahre Aussage ist, da A entweder zutrifft oder nicht.

Comments

achso.ok

im Tutorium haben wir immer gelernt die Negation erstmal zu bilden.