Question

wie kann ich das aussagelogische Koinzidenzlemma mithilfe von struktureller Induktion beweisen?

Answer 1

Seien \(A_1,\dots,A_n,B\) Variablen und \(T,T_1,T_2\) Formeln in denen nur die Variablen \(A_1,\dots,A_n\) vorkommen.

Seien \(I_\top, I_\bot: \{A_1,\dots,A_n,B\}\to \{\top,\bot\}\) Interpretationen mit \(I_\top(X) = I_\bot(X)\) für alle \(X\in \{A_1,\dots,A_n\}\) und \(I_\top(B) = \top, I_\bot(B)=\bot\).

Dann ist \(A_i|_{I_\top} = I_\top(A_i) = I_\bot(A_i) = A_i|_{I_\bot}\) für alle \(i\in \{1,\dots,n\}\).

Angenommen es gilt \(T|_{I_\top} = T|_{I_\bot}\). Falls \(T|_{I_\top} = \top\) ist, dann ist \(\neg T|_{I_\top} = \bot = \neg T|_{I_\bot}\). ist dagegen \(T|_{I_\top} = \bot\), dann ist \(\neg T|_{I_\top} = \top = \neg T|_{I_\bot}\).

Comments

aber wie beweist man das mit struktureller Induktion?

---

Indem man es für atomare Formeln beweißt (Induktionsanfang) und für jede Formel, die man mittels Junktoren einer funktional vollständigen Menge (zum Beispiel {¬, ∨}) bilden kann (Induktionsschritt).

---

könntest du vielleicht mal den Induktionsanfang und den Induktionsschritt für eine Formel machen damit ich das verstehe weil ich weiß nicht wie ich vorgehen muss

---

Beides steht in meiner Antwort.