Herleitung mittels Sequenzenkalkül

04.04.2014, 20:46

daLoisl

Herleitung mittels Sequenzenkalkül

Guten Abend,

ich soll zeigen oder widerlegen, ob folgende Aussage gilt:
Wenn $\begin{eqnarray*} \Gamma \phi \psi \end{eqnarray*}$ herleitbar ist, so ist auch $\begin{eqnarray*} \Gamma \neg \phi \neg \psi \end{eqnarray*}$ herleitbar.

Ich weiß nicht, wie alltäglich solche Aufgaben sind, daher ein paar Infos:
$\begin{eqnarray*} \Gamma \end{eqnarray*}$ ist eine Folge Boole'scher Ausdrücke. $\begin{eqnarray*} \phi \end{eqnarray*}$ , $\begin{eqnarray*} \psi \end{eqnarray*}$ sind Boole'sche Ausdrücke.
Eine Sequenz $\begin{eqnarray*} \phi_0 \phi_1 ... \phi_{n-1} \phi_n \end{eqnarray*}$ ist herleitbar gdw. es eine Herleitung von $\begin{eqnarray*} \phi_0 \phi_1 ... \phi_{n-1} \phi_n \end{eqnarray*}$ mithilfe des Sequenzenkalküls gibt.

Ich habe in etwa die Regeln zur Verfügung, die auf http://de.wikipedia.org/wiki/Sequenzenkalk%C3%BCl unter "Grundregeln" und "Junktorenregeln" stehen.

Nun mein Ansatz:
Also die Erfahrung sagt mir, dass die Aussage nicht stimmt. Klassisch wäre nun zu zeigen, dass ein $\begin{eqnarray*} \Gamma \end{eqnarray*}$ existiert, sodass $\begin{eqnarray*} \Gamma \phi \psi \end{eqnarray*}$ herleitbar ist, aber $\begin{eqnarray*} \Gamma \neg \phi \neg \psi \end{eqnarray*}$ nicht.
Nun kann ich mir vorstellen, ein $\begin{eqnarray*} \Gamma \end{eqnarray*}$ zu konstruieren, für dass ich ersteres zeigen kann. Aber wie kann man zeigen, dass etwas nicht herleitbar ist?

lg,
daLoisl

04.04.2014, 22:07

weisbrot

Auf diesen Beitrag antworten »

RE: Herleitung mittels Sequenzenkalkül

Zitat:

Aber wie kann man zeigen, dass etwas nicht herleitbar ist?

der sequenzkalkül ist korrekt, d.h. wenn $\begin{eqnarray*} \Gamma\phi \end{eqnarray*}$ ableitbar ist, dann folgt auch $\begin{eqnarray*} \phi \end{eqnarray*}$ logisch aus $\begin{eqnarray*} \Gamma \end{eqnarray*}$ . das kannst du benutzen, um ein gegenbeispiel zu finden.
lg

07.04.2014, 19:11

daLoisl

Auf diesen Beitrag antworten »

Danke, damit habe ich es geschafft.

Neue Frage »

Antworten »

Herleitung mittels Sequenzenkalkül

Verwandte Themen