Strukturelle Induktion Logik

Question

Aufgabe:

Beweisen Sie mittels struktureller Induktion, dass für jede aussagenlogische Formel F mit A !∈ Var(F) und jede Belegung α gilt, dass å [A→0](F ) = å(F ). Hierbei bezeichnet α[A→b] die Belegung, die α so abändert, dass sie A den Wert b zuordnet.

Genauer:

α[A→b] (x)=  α(x) falls x != A

                  b sonst.

Answer 1

IA: Sei F eine Variable mit F ≠ A.

Dann ist α[A→b] (x) = α(x) laut Definition von α.

IV:  Sei α[A→b] (x) = α(x) für jede Formel x mit Verschachtelungstiefe < n und A ∉ Var(x).

IS: Sei F eine Formel mit Verschachtelungstiefe n und F = G ° H, wobei ° ein aussagenlogischer Junktor ist und A ∉ Var(F) ist.

Laut Definition von Var ist dann A ∉ Var(G) und A ∉ Var(H).

Außerdem haben G und H Verschachtelungstiefen < n.

Also ist α[A→b] (G) = α(G) und α[A→b] (H) = α(H) laut IV und Definition von α.

Also ist auch α[A→b] (F) = α[A→b] (F) laut Definition von α.