absoluter beweis der widerspruchsfreiheit

29.11.2004, 17:03

Jan

absoluter beweis der widerspruchsfreiheit

hallo!
ich habe hier ein buch liegen, in dem ein absoluter beweis der widerspruchsfreiheit der elementaren aussagenlogik skizziert wird. das system ist folgendermaßen formalisiert:

p, q, r... sind satzvariable.

~ bedeutet "nicht"
€ bedeutet "wenn...dann..."
v bedeutet "oder"
. bedeutet "und"

es gibt 2 umformungsregeln:
erstens darf eine satzvariable einheitlich durch eine neue formel ersetzt werden (z.b. erhält man so aus p € p durch substitution (p v q) € (p v q).
zweitens modus ponens (also aus p und p € q folgt q).

man hat 4 axiome:
1. (p v p) € p
2. p € (p v q)
3. (p v q) € (q v p)
4. (p € q) € ((r v p) € (r v q))

die beweisführung zur widerspruchsfreiheit ist mir im grundsatz klar. nur die herleitung eines benötigten theorems aus den oben genannten angaben ist mir ziemlich schleierhaft und wird leider im buch übersprungen. vielleicht kann mir hier jemand helfen:

wie kann ich im oben beschriebenen system folgendes herleiten:
p € (~p € q)
(also: "wenn p, dann, wenn non-p, so q")

ich freue mich auf antworten! smile

gruß,
JAN

29.11.2004, 18:08

therisen

Auf diesen Beitrag antworten »

Absolute Widerspruchsfreiheit? Das geht doch gar nicht oder verwirrt

Zitat:

Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.

Zitat:

Ein System kann nicht zum Beweis seiner eigenen Widerspruchsfreiheit verwendet werden.

http://de.wikipedia.org/wiki/G%C3%B6dels...A4ndigkeitssatz

Gruß, therisen

30.11.2004, 07:31

Jan

Auf diesen Beitrag antworten »

Gödels Satz gilt nur für "hinreichend mächtige" Systeme. Das von mir beschriebene System ist so "primitiv", dass ein Beweis seiner absoluten Widerspruchsfreiheit geführt werden kann.
Wenn ich mal Zeit hab, kann ich den (ziemlich kurzen) Beweis hier mal posten, aber vorher: Könnte mir bitte jemand das oben genannte Theorem aus dem Axiomen ableiten, oder zumindest einen Tipp geben, wie man das angehen soll? Hilfe

Jan

30.11.2004, 17:44

WebFritzi

Auf diesen Beitrag antworten »

Man kann das Theorem nicht beweisen, denn in den Axiomen taucht kein ~ auf.

30.11.2004, 22:47

eule

Auf diesen Beitrag antworten »

Ich habs nochmal in üblicher Notation das System aufgeschrieben.

Axiome:
$\begin{eqnarray*} 1).~(p \vee q) \Rightarrow p \end{eqnarray*}$
$\begin{eqnarray*} 2).~p \Rightarrow (p \vee q) \end{eqnarray*}$
$\begin{eqnarray*} 3).~(p \vee q) \Rightarrow (q \vee p) \end{eqnarray*}$
$\begin{eqnarray*} 4).~(p \vee q) \Rightarrow ((r \vee p) \Rightarrow (r \vee q)) \end{eqnarray*}$
Schlußregeln:
Modus Ponens MP

Ich hab die Herleitung noch nicht gefunden aber sie ist durchaus möglich da die Negation über die Substitutionsregel einegebaut werden kann.

30.11.2004, 23:28

Mazze

Auf diesen Beitrag antworten »

Zitat:

Madus Ponens MP

Kleine Verbesserung:

Das Ding nennt sich Modus Ponens Augenzwinkern

*klugscheiss*

01.12.2004, 06:26

eule

Auf diesen Beitrag antworten »

Geändert, war ein Tipfehler.

01.12.2004, 14:25

Jan

Auf diesen Beitrag antworten »

Zitat:

Original von eule
Ich habs nochmal in üblicher Notation das System aufgeschrieben.

Axiome:
$\begin{eqnarray*} 1).~(p \vee q) \Rightarrow p \end{eqnarray*}$
$\begin{eqnarray*} 2).~p \Rightarrow (p \vee q) \end{eqnarray*}$
$\begin{eqnarray*} 3).~(p \vee q) \Rightarrow (q \vee p) \end{eqnarray*}$
$\begin{eqnarray*} 4).~(p \vee q) \Rightarrow ((r \vee p) \Rightarrow (r \vee q)) \end{eqnarray*}$
Schlußregeln:
Modus Ponens MP

Ich hab die Herleitung noch nicht gefunden aber sie ist durchaus möglich, da die Negation über die Substitutionsregel einegebaut werden kann.

danke dafür, im formeleditor hab ich die betreffenden zeichen nicht gefunden, und meine kenntnisse von latex-code sind doch eher bescheiden smile

und @webfritzi: man kann das mit sicherheit beweisen, der verfasser von meinem buch wusste schon, was er da schreibt Augenzwinkern

Neue Frage »

Antworten »

absoluter beweis der widerspruchsfreiheit

Verwandte Themen