Diskussion:Baumkalkül

Ein Abschnitt zur Geschichte der Baumkalküle fehlt noch, bisher findet man nur unter den Literaturangaben einen Hinweis auf den (oder nur einen?) Begründer dieses Beweisverfahrens. --185.46.137.5 22:41, 7. Feb. 2018 (CET)

Unverständlich

Ich wollte wissen, wie man eine tautologische Formel nach dem Verfahren analytisches Tableaux verifiziert. Weder dieser noch der engliche Artikel haben mir dabei wirklich geholfen. Mit der Lektüre

Lecture 9: Analytic Tableaux vs. Refinement logic. In: CS 4860: Applied Logic (Fall 2012), Cornell University: Computer Science.

ist es mir aber sofort nach fünf Minuten verständlich geworden. Nachrechnen brachte mir nach weiteren fünf Minuten die Erkenntnis wann/ob/warum man die Elemente in einem UND-Strang auf Zweige verteilen darf (Distributivgesetz). Meine nächste Frage war dann, wie die Komplexität im Vergleich zu Brute-Force ist.

Also mir ist jetzt schon klar, dass $F\varphi$ genauer $I(\varphi )=F$ bedeutet. Mir ist auch klar, dass

$(\models \varphi )\iff \forall I(I(\varphi )=T)\iff \neg \exists I(I(\varphi )=F).$

Gut, nehmen wir die Kontroposition in reiner Aussagenlogik als Beispiel:

$\varphi :=((P\rightarrow Q)\rightarrow (\neg Q\rightarrow \neg P)).$

Die Regeln führen auf

$(I(\varphi )=F)\iff [(I(P)=F)\lor (I(Q)=T)]\land (I(Q)=F)\land (I(P)=T).$

Verteilt man noch auf das ODER, gelangt man zu dem Schluss dass die rechte Seite kontradiktorisch ist, unabhängig von $I$. Damit gilt $\models \varphi$.

Im Fall der Aussagenlogik lässt sich das natürlich zu

${\overline {\varphi }}\longleftrightarrow ({\overline {P}}\lor Q)\land {\overline {Q}}\land P$

abkürzen, weil die Metatheoreme das erlauben.

Mein Problem mit dem Artikel ist nun, dass man Varianten und die Verallgemeinerung des Verfahrens zur Anwendung auf andere Logiken jetzt im nächsten Abschnitt diskutieren kann, nachdem der Leser das elementare Prinzip verstanden hat. --Rumil (Diskussion) 20:00, 21. Mär. 2018 (CET)

Sorry, in Retrospektive ist der Artikel noch mit am verständlichsten. Es ist jetzt nicht der didaktisch hochwertigste Artikel, aber er ist in Ordnung. Mir ist auch ein Denkfehler unterlaufen. Tatsächlich wird darauf abgezielt, die Tautologie auf Unerfüllbarkeit der Negation umzuformulieren:

${\begin{aligned}&(\models \varphi )\iff \forall I(I(\varphi )=1)\iff \forall I(I(\neg \varphi )=0)\\&\iff \neg \exists I(I(\neg \varphi )=1)\iff \neg \operatorname {erf} [\neg \varphi ].\end{aligned}}$

Der Witz an dem Verfahren ist dabei ja, dass man nun skolemisieren darf, weil Erfüllbarkeitsäquivalenz ausreicht. D. h. $\varphi$ wird genau dann tautologisch sein, wenn die Skolemisierung von $\neg \varphi$ unerfüllbar ist. Das wird im Artikel leider nicht erwähnt. --Rumil (Diskussion) 21:38, 25. Aug. 2018 (CEST)