Beweis der Aussagenlogik

15.10.2013, 09:57

felix93

Beweis der Aussagenlogik

Folgendes, ich soll zeigen, dass folgende zwei Aussagen logisch äquivalent sind:

$\begin{eqnarray*} \psi \text{ ist eine Folgerung von }\phi_{1},...,\phi_{k} \end{eqnarray*}$
$\begin{eqnarray*} ((\bigwedge\limits_{i=1}^k \phi_k) \rightarrow \psi) \text{ ist eine Tautologie.} \end{eqnarray*}$

Zwar ist mir vollends bewusst, dass eine aussagenlogische Formel $\begin{eqnarray*} \psi \end{eqnarray*}$ dann und nur dann aus einer anderen aussagenlogischen Formel $\begin{eqnarray*} \phi \end{eqnarray*}$ (oder Eben die Menge $\begin{eqnarray*} P \end{eqnarray*}$ aller $\begin{eqnarray*} \phi \end{eqnarray*}$ ) folgt, wenn $\begin{eqnarray*} P \rightarrow \psi \end{eqnarray*}$ eine Tautologie ist. Aber, wie man einen Beweis angeht, ist mir nicht ganz klar.

Vielen Dank, Felix

15.10.2013, 10:20

jimmyt

Auf diesen Beitrag antworten »

Ein Vorschlag, wie wäre es damit:

$\begin{eqnarray*} (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A) \quad \text{(Beweis durch Kontraposition)} \end{eqnarray*}$

15.10.2013, 10:51

felix93

Auf diesen Beitrag antworten »

Entschuldigung, ich bin ein kleiner Beweismuffel, bzw. komme erst seit neustem damit in Kontakt. Also die von dir beschriebene Formel stellt eine Implikation auf andere (zwar äquivalente) Weise dar, ich soll doch aber eine Äquivalenz beweisen...

Mein zweites Problem ist, dass ich nicht genau weiß, wie ich eine "Folgerung" formalisieren soll, weil sie in meinem Begriffsradius das gleiche wie die Implikation darstellt.

Vielen dank für die schnelle Antwort

15.10.2013, 13:28

jimmyt

Auf diesen Beitrag antworten »

Du brauchst dich für nichts entschuldigen! Augenzwinkern

Zitat:

Original von felix93
...
Mein zweites Problem ist, dass ich nicht genau weiß, wie ich eine "Folgerung" formalisieren soll, weil sie in meinem Begriffsradius das gleiche wie die Implikation darstellt.
...

Damit würde ich mal anfangen. Wie habt ihr denn den Begriff Folgerung definiert?
Im Internet habe ich folgende Definition gefunden:

Zitat:

Eine Formel $\begin{eqnarray*} G \end{eqnarray*}$ heißt eine Folgerung von $\begin{eqnarray*} F_1, \dots,F_k \end{eqnarray*}$ falls für jede Belegung, die sowohl zu $\begin{eqnarray*} F_1, \dots,F_k \end{eqnarray*}$ als auch zu $\begin{eqnarray*} G \end{eqnarray*}$ passend ist, gilt:
Wenn $\begin{eqnarray*} A \end{eqnarray*}$ Modell von $\begin{eqnarray*} (F_1, \dots,F_k) \end{eqnarray*}$ ist, dann ist $\begin{eqnarray*} A \end{eqnarray*}$ auch Modell von $\begin{eqnarray*} G \end{eqnarray*}$ .

Ich gebe aber keine Garantie, dass diese Definition generell anerkannt ist. Habe ich im Internet gefunden. Kann auch sein, dass ihr das anders definiert habt.

Aber die Definition der Folgerung brauchst du in jedem Fall.

Zum Beweis:
Entweder du kannst 1. für $\begin{eqnarray*} A \end{eqnarray*}$ und 2. für $\begin{eqnarray*} B \end{eqnarray*}$ nehmen.
Oder du machst den Beweis links nach rechts ( $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ ) und umgekehrt ( $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ ). (Sorry, ich weiß nicht wie der Fachausdruck dafür ist.)

Dieser zweite Weg ist glaube ich bei Äquivalenz sogar besser, weil, wie du schon angemerkt hast, sollst du ja die Äquivalenz beweisen.
Aber zu allererst benötigst du die Def. von Folgerung.

15.10.2013, 14:41

felix93

Auf diesen Beitrag antworten »

Unsere Definition lautet im Grunde wie deine:

Zitat:

$\begin{eqnarray*} \psi \end{eqnarray*}$ heißt Folgerung der Formeln $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$ , falls für jede Belegung $\begin{eqnarray*} \omega(\cdotp) \end{eqnarray*}$ der atomaren Ausdrücke von $\begin{eqnarray*} \psi \end{eqnarray*}$ und $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$ gilt, wenn $\begin{eqnarray*} \omega(\cdotp) \end{eqnarray*}$ ein Modell für $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$ ist, dann ist $\begin{eqnarray*} \omega(\cdotp) \end{eqnarray*}$ auch ein Modell für $\begin{eqnarray*} \psi \end{eqnarray*}$ .

Wenn $\begin{eqnarray*} \psi \end{eqnarray*}$ also eine Folgerung von $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$ ist, dann bedeutet das also sowas wie $\begin{eqnarray*} \omega(\psi) \leftrightarrow \omega(\phi_1),...,\omega(\phi_k) \end{eqnarray*}$ ?

16.10.2013, 11:49

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von felix93
Unsere Definition lautet im Grunde wie deine:

Zitat:

...

Ok, dann gehen wir von dieser Definition mal aus.
Ich interpretiere eure Definition so:

$\begin{eqnarray*} \omega (\phi_1, ..., \phi_k) = 1 \quad \Rightarrow \quad \omega (\psi) = 1 \end{eqnarray*}$

$\begin{eqnarray*} \omega (\phi_1, ..., \phi_k) = 0 \quad \Rightarrow \quad \omega (\psi) = 1 \lor \omega (\psi) = 0 \end{eqnarray*}$

Zitat:

Original von felix93
Wenn $\begin{eqnarray*} \psi \end{eqnarray*}$ also eine Folgerung von $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$ ist, dann bedeutet das also sowas wie $\begin{eqnarray*} \omega(\psi) \leftrightarrow \omega(\phi_1),...,\omega(\phi_k) \end{eqnarray*}$ ?

Nein, das glaube ich nicht. Äquivalenz heißt, entweder beide Seiten haben den Wahrheitswert 1 oder beide haben den Wert 0.
Aber bei der Folgerung ist nirgends definiert, dass, falls $\begin{eqnarray*} \omega (\phi_1, ..., \phi_k) = 0 \end{eqnarray*}$ ist, dass dann auch $\begin{eqnarray*} \omega (\psi)=0 \end{eqnarray*}$ sein muss.
Ein Modell ist für mich eine Belegung der freien Variablen eines logischen Ausdrucks, durch die der gesamte Ausdruck wahr wird.

Vorschlag für den Beweis:

links nach rechts ( $\begin{eqnarray*} \text{1.} \Rightarrow \text{2.} \end{eqnarray*}$ ):

$\begin{eqnarray*} \psi \end{eqnarray*}$ ist eine Folgerung von $\begin{eqnarray*} \phi_1, ..., \phi_k \end{eqnarray*}$

$\begin{eqnarray*} \stackrel{1.}{\Rightarrow}\omega (\phi_1, ..., \phi_k) = \text{true} \quad \Rightarrow \quad \omega (\psi) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \left ( \left (\bigwedge\limits_{i=1}^k \phi_k \right ) \Rightarrow \psi \right ) = \text{true} \Leftrightarrow( \underbrace{\phi_k \wedge \phi_k \wedge \dots \wedge \phi_k)}_{k-mal} \Rightarrow \psi) = \text{true} \Leftrightarrow(\phi_k \Rightarrow \psi) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \stackrel{1.}{\Rightarrow} \omega (\phi_k)=\text{true} \quad \Rightarrow \quad \omega (\psi) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} (\omega (\phi_k)=\text{true} \Rightarrow \omega (\psi) = \text{true}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow (\text{true} \Rightarrow \text{true}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow \text{true} = \text{true} \Rightarrow \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \stackrel{1.}{\Rightarrow} \omega (\phi_k)=\text{false} \quad \Rightarrow \quad \omega (\psi) = \text{true} \lor \omega (\psi) = \text{false} \end{eqnarray*}$

$\begin{eqnarray*} (\omega (\phi_k)=\text{false} \Rightarrow \omega (\psi) = \text{true}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow (\text{false} \Rightarrow \text{true}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow \text{true} = \text{true} \Rightarrow \text{true} \end{eqnarray*}$

$\begin{eqnarray*} (\omega (\phi_k)=\text{false} \Rightarrow \omega (\psi) = \text{false}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow (\text{false} \Rightarrow \text{false}) = \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow \text{true} = \text{true} \Rightarrow \text{true} \end{eqnarray*}$

$\begin{eqnarray*} \stackrel{2.}{\Rightarrow} \left ( \left (\bigwedge\limits_{i=1}^k \phi_k \right ) \Rightarrow \psi \right ) \text{ ist eine Tautologie} \end{eqnarray*}$

ToDo:
rechts nach links ( $\begin{eqnarray*} \text{1.} \Leftarrow \text{2.} \end{eqnarray*}$ ):

$\begin{eqnarray*} \dots \end{eqnarray*}$

17.10.2013, 11:04

jimmyt

Auf diesen Beitrag antworten »

Ich glaube es geht auch ganz gut mit Beweis durch Kontraposition:

$\begin{eqnarray*} \text{a) links nach rechts} \quad (\text{1.} \Rightarrow \text{2.}) \end{eqnarray*}$

$\begin{eqnarray*} \text{1.} \Rightarrow \text{2.} \Leftrightarrow \neg \text{2.} \Rightarrow \neg \text{1.} \end{eqnarray*}$

$\begin{eqnarray*} \text{b) rechts nach links} \quad (\text{2.} \Rightarrow \text{1.}) \end{eqnarray*}$

$\begin{eqnarray*} \text{2.} \Rightarrow \text{1.} \Leftrightarrow \neg \text{1.} \Rightarrow \neg \text{2.} \end{eqnarray*}$

Ansatz des Beweises:

zu a)

$\begin{eqnarray*} \neg \text{2.} \Rightarrow \left ( \left ( \bigwedge_{i=1}^k \phi_k\right ) \Rightarrow \psi \right) \text{ ist keine Tautologie} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \omega \left ( \left ( \bigwedge_{i=1}^k \phi_k \right) \right )=\text{ true} \quad \Rightarrow \quad \omega (\psi) \neq \text{ true} = \text{false} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \omega \left ( \phi_1, \dots, \phi_k \right )=\text{ true} \quad \Rightarrow \quad \omega (\psi) \neq \text{ true} = \text{false} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \psi \text{ ist keine Folgerung von } \phi_1, \dots, \phi_k \quad \Rightarrow \quad \neg \text{1.} \end{eqnarray*}$

zu b) $\begin{eqnarray*} \dots \end{eqnarray*}$

Aber vlt. hast du die Aufgabe mittlerweile schon gelöst. Kurze Rückmeldung wäre nett. Augenzwinkern

20.10.2013, 12:38

felix93

Auf diesen Beitrag antworten »

Zitat:

Original von jimmyt
Aber vlt. hast du die Aufgabe mittlerweile schon gelöst. Kurze Rückmeldung wäre nett. Augenzwinkern

Nein, hab ich noch nicht. Hatte nur erstmal anderes zu tun und hab mit der Aufgabe noch etwas Zeit. Also b.) sieht dann so aus nehme ich an:

$\begin{eqnarray*} \text{b.) } 2 \rightarrow 1 2 \rightarrow 1 \leftrightarrow \neg 1 \rightarrow \neg 2 \neg 1 \rightarrow \psi \text{ ist keine Folgerung von } (\phi_1 ,..., \phi_k) \rightarrow \omega(\phi_1 ,..., \phi_k) = 1 \rightarrow \omega(\psi) \not= 1 \rightarrow \omega(\psi) = 0 \rightarrow \omega(\bigwedge\limits_{i=1}^k (\phi_i)) = 1 \rightarrow \omega(\psi) \not= 1 \rightarrow \omega(\psi)=0 \rightarrow ((\bigwedge\limits_{i=1}^k (\phi_i)) \rightarrow \psi) \text{ nicht tautologisch} \rightarrow \neg 2 \end{eqnarray*}$

Vielen Dank für deine Hilfe, ist das so ok?

PS.: Wieso ist mein Latex rechtsbündig?

20.10.2013, 13:52

jimmyt

Auf diesen Beitrag antworten »

Das sieht meiner bescheidenen Meinung nach ganz gut aus.
Für die Implikation gilt, dass $\begin{eqnarray*} 1 \Rightarrow 0 \end{eqnarray*}$ immer $\begin{eqnarray*} 0 \end{eqnarray*}$ ist. Und genau das hast du ja drin.

Zu Latex:
Ich glaube dein Latex ist rechtsbündig, weil du innerhalb von $\begin{eqnarray*} \text{[latex]} \dots \text{[latex]} \end{eqnarray*}$ Zeilen umgebrochen hast.

z.B.:

$\begin{eqnarray*} \text{Dies ist eine Latex-Zeile.} \end{eqnarray*}$

$\begin{eqnarray*} \text{Dies sind} \text{2 Latex-Zeilen mit Umbruch.} \end{eqnarray*}$

Neue Frage »

Antworten »

Beweis der Aussagenlogik

Verwandte Themen