Beweis des Deduktionstheorems

05.04.2010, 16:58

René Schwarz

Beweis des Deduktionstheorems

Hallo,

folgende Aufgabenstellung habe ich im Rahmen des Durcharbeitens eines Vorlesungsskriptes gefunden:

Zitat:

Beweisen Sie:
Sei $\begin{eqnarray*} F \end{eqnarray*}$ eine endliche Menge $\begin{eqnarray*} F = \{ F_1, F_2, \ldots, F_n \} \end{eqnarray*}$ von Formeln. Dann gilt $\begin{eqnarray*} F \models G \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} F_1 \wedge F_2 \wedge \ldots \wedge F_n \rightarrow G \end{eqnarray*}$ eine Tautologie ist.

Da ich leider selbst bisher keine eigenständige Logikausbildung hatte, ist ein solcher Beweis für mich nicht einfach. In der Literatur konnte ich bereits entdecken, dass es sich hierbei anscheinend um den Beweis des Deduktionstheorems handelt.

Meinem Verständnis nach liese sich die Aufgabenstellung nun wie folgt aufstellen (Bemerkung: $\begin{eqnarray*} G \end{eqnarray*}$ ist eine Formel aus der Formelmenge $\begin{eqnarray*} A_\text{Form} \end{eqnarray*}$ ):

$\begin{eqnarray*} F = \{ F_1, F_2, \ldots, F_n \}, \quad n \in \mathbb{N} \end{eqnarray*}$

$\begin{eqnarray*} \qquad \end{eqnarray*}$ $\begin{eqnarray*} G \in A_\text{Form} \end{eqnarray*}$

Beweisen Sie:

$\begin{eqnarray*} F \models G \Leftrightarrow \forall_{\sigma \in \Sigma} \ I(F_1 \wedge F_2 \wedge \ldots \wedge F_n \rightarrow G)(\sigma) = 1 \end{eqnarray*}$

Zeichenerklärung

$\begin{eqnarray*} \begin{split} A_\text{Form} & \qquad & \text{(beliebige) Formelmenge} \\ \sigma & \qquad & \text{eine mögliche Belegung der aussagenlogischen Variablen} \\ \Sigma & \qquad & \text{Menge aller möglichen Belegungen} \\ I(F)(\sigma) = 1 & \qquad & \text{Interpretation der Formel } F \text{ bezüglich einer möglichen Belegung } \sigma \text{ mit der Auswertung wahr} \\\end{split}<br /> \end{eqnarray*}$

Nun komme ich aber leider nicht mehr weiter. In einingen Dokumenten habe ich gesehen, dass man diesen Sachverhalt mit einem Beweis durch Widerspruch lösen könnte.

In Kutschera/Breitkopf, Einführung in die moderne Logik, 8. Aufl. (2007) findet sich auch ein Beweis des Theorems, den ich aber nicht nachvollziehen kann.

Vielleicht kann jemand (allgemeinverständlich) weiterhelfen.

Vielen Dank im Voraus!

Neue Frage »

Antworten »

Beweis des Deduktionstheorems

Verwandte Themen