Prädikatenlogik

13.01.2009, 11:17

donvito

Prädikatenlogik

Hallo ihr Mathecracks,

könnte mir jemand sagen, wie ich zeige, dass
- eine Formel F in Prädikatenlogik eine Tautologie ist. Ich denke, dazu muss ich zeigen, dass Nicht-F unerfüllbar ist. Doch wie stelle ich das an?
- zwei Formeln äquivalent sind. Per Definition ist das genau dann der Fall, wenn sie für alle Strukturen die gleiche Belegung ergeben. Nur gibt es ja unedlich viele Strukturen...

Würde mich sehr freuen, wenn jemand einen Tipp parat hätte.

13.01.2009, 21:57

Mazze

Auf diesen Beitrag antworten »

Zitat:

- eine Formel F in Prädikatenlogik eine Tautologie ist. Ich denke, dazu muss ich zeigen, dass Nicht-F unerfüllbar ist. Doch wie stelle ich das an?

Nicht-F unerfüllbar ist ein Weg. Oder Du zeigst das jede Belegung den Wahrheitswert wahr liefert. Als Beispiel :

$\begin{eqnarray*} \theta = \phi \vee (\phi \rightarrow \psi) \end{eqnarray*}$

Dies ist eine Tautologie. Ist $\begin{eqnarray*} \phi \equiv T \end{eqnarray*}$ so ist $\begin{eqnarray*} \theta \equiv T \end{eqnarray*}$ ist $\begin{eqnarray*} \phi \equiv F \end{eqnarray*}$ so ist $\begin{eqnarray*} \phi \rightarrow \psi \equiv T \end{eqnarray*}$ also ist Theta eine Tautologie.

Zitat:

- zwei Formeln äquivalent sind. Per Definition ist das genau dann der Fall, wenn sie für alle Strukturen die gleiche Belegung ergeben. Nur gibt es ja unedlich viele Strukturen...

$\begin{eqnarray*} \phi \leftrightarrow \psi \Leftrightarrow \phi \rightarrow \psi \wedge \psi \rightarrow \phi \end{eqnarray*}$

Wenn man logische Aussagen zeigen will muss man nicht alles in Formeln packen. Man kann immer auch ein Paar worte schreiben. Schema-F gibts nur für endliche Mengen die nicht zu groß sind.

19.01.2009, 19:02

donvito

Auf diesen Beitrag antworten »

Danke schonmal! Hat mir sehr geholfen!

Und jetzt wüßte ich gerne noch, wie ich mithilfe des Satzes von Herbrand zeige, dass F eine Tautologie ist.

Und was versteht ihr unter Herbrand-Normalform? In Wikipedia findet man den Begriff leider nicht! ICh denke das ist die Herbrand-Expansion, oder?

Neue Frage »

Antworten »

Prädikatenlogik

Verwandte Themen