Hi,

meint ihr 4.4 "Zeige das die Junktor Menge {=>,AND,OR} funktional Unvollstaendig ist" (stark verkuerzt) soll ein induktions Beweis sein?

Wie schon in der Aufgabenstellung beschrieben, soll man
ja hier eine bestimmte Aussage für alle Formeln beweisen,
und da ist die strukturelle Induktion die Standardmethode.
Jetzt musst Du Dir nur die Junktoren einmal genau ansehen um
herauszufinden, für welche Belegung [img]http://mokrates.de/cgi-bin/texstring?%5Cmathcal%7BA%7D[/img]
und welchen Wahrheitswert b Du die Aussage zeigen kannst.

Um zu zeigen, dass die Junktorenmenge funktionial UNvollständig ist, bietet sich vollständige Induktion ja eher nicht an. Damit beweist man ja, dass eine Aussage für *alle* Formeln gilt.

Hier bietet es sich vielleicht an ein Gegenbeispiel zu suchen?

Cheers,
Frank

Mein Idee war, zu erst mit Induktion zu zeigen, dass alle Formeln die man aus der Junktorenmenge bilden kann unter einer bestimmten Belegung wahr sind.
Dann ein Beispiel zu bringen fuer eine andere Formel "neg A" die falsch ist und dementsprechend nicht aus der Junktorenmenge gebildet werden kann.
(Also im Grunde der Hinweis der in der Aufgabe steht, bin mir halt nur nicht sicher ob ich einfach behaupten kann dass alle die gebildet werden wahr sind oder ob ich das Beweisen muss)

Ja, das ist gut :)

Mein Idee war, zu erst mit Induktion zu zeigen, dass alle Formeln die man aus der Junktorenmenge bilden kann unter einer bestimmten Belegung wahr sind.
Dann ein Beispiel zu bringen fuer eine andere Formel "neg A" die falsch ist und dementsprechend nicht aus der Junktorenmenge gebildet werden kann.

Ja, so meinte ich das. [img]http://www.fb18.de/gfx/23.gif[/img]

(Also im Grunde der Hinweis der in der Aufgabe steht, bin mir halt nur nicht sicher ob ich einfach behaupten kann dass alle die gebildet werden wahr sind oder ob ich das Beweisen muss)

Beweisen, siehe oben.