Hi
ich hab ne frage zu nem ziemlich alten thema (schon ne ewigkeit her).
+ = oder, * = und
Ich wollte mal zur übung für die klausur per induktion beweisen, dass wenn 2 formeln f und g äquivalent sind, dann sind auch die beiden formel f’ und g’ äquivalent, wobei f’ bzw. g’ aus f bzw. g hervorgehen, indem man alle * gegen + ersetzt und umgekehrt. (ist die 14. übungsaufgabe aus dem schöning, die dort aber nicht per induktion bewiesen wird)
Induktionsanfang:
Für 2 atomare formeln ist die behauptung richtig.
Induktionsvoraussetzung:
Seien f und g 2 formeln, dann gilt: wenn f ≡ g dann auch f’ ≡ g’, wobei f’ bzw. g’ durch die oben genannte umformung aus f bzw. g hervorgehen.
Induktionsschritt:
Seien f1, f2, g1 und g2 formeln und f1 ≡ g1 und f2 ≡ g2.
Aufgrund der funktion von * ergibt sich:
f1 * f2 ≡ g1 * g2
aufgrund der induktionsvoraussetzung folgt:
f’1 + f’2 ≡ g’1 + g’2
wenn man jetzt f = f1 * f2, g = g1 * g2, f’ = f’1 + f’2 und g’ = g’1 + g’2, folgt
wenn f ≡ g, dann f’ ≡ g’.
analog für die restlichen junktoren.

ich bin der meinung, dass der induktionsschritt so nicht richtig ist, aber ich weiss leider auch nicht, wie es richtig wäre. bräuchte also fremde hilfe………..

Induktionsvoraussetzung:
Seien f und g 2 formeln, dann gilt: wenn f ≡ g dann auch f’ ≡ g’, wobei f’ bzw. g’ durch die oben genannte umformung aus f bzw. g hervorgehen.
Induktionsschritt:
Seien f1, f2, g1 und g2 formeln und f1 ≡ g1 und f2 ≡ g2.

Hier liegt auf jeden Fall ein formaler Fehler: Du machst
Annahmen über f, g, f' und g' in der I.V., aber im Schluß
verwendest du f1,f2,g1,g2. Du musst das zusammenbringen
und zum Beispiel f1,g1, f2,g2 schon in der I.V. benutzen.

Sagen wir also:
f1 <=> g1 und f2 <=> g2
sowie als I.V.: f1' <=> g1' und f2' <=> g2'

I.S.:
- f1 * f2 <=> g1 * g2 (Def. des log. Und plus Substitutionstheorem (?))
- f1' + f2' <=> g1' + g2' (I.V. plus Def. Oder plus Subst.th.)
Und mit f = f1 * f2 sowie g = g1*g2 folgt:
f <=> g * f' = f1' + f2' <=> g1' + g2' = g'

Also war dein Beweis eigentlich recht ok, denke ich.

jo, danke für deine hilfe. diese induktionen sind nämlich momentan mein größtes problem in f.

Und mit f = f1 * f2 sowie g = g1*g2 folgt:
f g * f' = f1' + f2' g1' + g2' = g'

meinst du nicht
f' = f1' + f2' g1' + g2' = g'
?


was ist eigentlich mit Formeln der Art
(A v C) ^ (A v -C) äquivalent A

werden die damit auch bewiesen?
Problem: nicht beide Seiten auftrennbar


oder wenn doch auftrennbar, dann zumindest nicht so langweilig äquivalent wie im Induktionsschritt behauptet:
(A v C) ^ (A v -C) äquivalent A ^ A