Beweis Aussagenlogik

11/11/2008 - 21:30 von Dominique Töpfer | Report spam
Hallo zusammen,

ich habe eine Frage zu einem Beweis aus der Aussagenlogik.

Es geht darum, zu beweisen, dass die Junktorenmenge {und, oder, ->}
nicht funktional vollstàndig ist. Mein Ansatz ist wie folgt:

Als Gegenbeispiel betrachte man !A (nicht A). Zu zeigen ist also, dass
diese Formel sich nicht mit obiger Junktorenmenge darstellen làsst.
Für einen Junktor erhàlt man:

A und A = A
A oder A = A
A -> A = 1
A und 0 = 0
A und 1 = A
usw.

Keine Formel ist àquivalent zu !A. Sei nun phi eine Formel, die nur
von A abhàngt und die nicht àquivalent zu !A ist. Wenn phi aber nur
von einer Variablen abhàngt muss phi àquivalent zu 0, 1 oder A sein
(!A wurde ja ausgeschlossen). Fügt man nun über die drei Junktoren
jeweils wieder ein A hinzu, ergibt sich

0 und A = 0, 0 oder A = A, O -> A = 1
1 und A = A, usw.

also wieder kein !A. Damit existiert keine Formel, die nur die drei
Junktoren verwendet und àquvalent zu !A ist. Die Junktorenmenge ist
also nicht funktional vollstàndig.

Ich wüsste nun gern, ob man das so machen kann, und wenn nicht, wo
genau mein Fehler liegt.

Besten Dank und viele Grüße

Dominique
 

Lesen sie die antworten

#1 Hollger
11/11/2008 - 21:49 | Warnen spam
Dominique Töpfer schrieb:

Keine Formel ist àquivalent zu !A.



Dann ist ! elementar.

Ähnliche fragen