Formale Herleitungen

Question

kann jemand mir bei diese Aufgaben helfen, da ich keine Ahnung habe, wie man es lösen kann.

Danke.

In der Vorlesung wurde der folgende Beweiskalkül von Shoenfield betrachtet:
Axiome: ¬ϕ ∨ ϕ
Regeln: (ϕ / ϕ ∨ ψ)   (ϕ ∨ ϕ / ϕ)   (ϕ ∨ (ψ ∨ χ) / (ϕ ∨ ψ) ∨ χ )  (ϕ ∨ ψ   ¬ϕ ∨ χ   /  ψ ∨ χ)
Wir schreiben ϕ1, . . . ,ϕn l- ψ, falls es einen Beweisbaum gibt, dessen Blätter Axiome oder Aussagen in {ϕ1, . . . ,ϕn} sind
und dessen Wurzel ψ ist. Beweisen Sie durch die Angabe eines entsprechenden Beweisbaums:

(a) ϕ ∨ ψ  l-  ψ ∨ ϕ
(b) ϕ,ϕ → ψ  l-  ψ (hierbei ist ϕ → ψ eine Abkürzung für ¬ϕ ∨ ψ)
(c) ϕ ∨ ψ,¬ϕ  l-  ψ
(d) ¬¬ϕ  l-  ϕ

Comments

Vom Duplikat:

Titel: formale herleitungen pradikatenlogik

Stichworte: prädikatenlogik,logik,beweis,quantoren,teiler

In der Vorlesung wurde der folgende Beweiskalkül von Shoenfield betrachtet:
Axiome: ¬ϕ ∨ ϕ
Regeln: ϕ
ϕ ∨ ψ
ϕ ∨ ϕ
ϕ
ϕ ∨ (ψ ∨ χ)
(ϕ ∨ ψ) ∨ χ
ϕ ∨ ψ ¬ϕ ∨ χ
ψ ∨ χ
Wir schreiben ϕ1
, . . . ,ϕn ψ, falls es einen Beweisbaum gibt, dessen Blätter Axiome oder Aussagen in {ϕ1
, . . . ,ϕn
} sind
und dessen Wurzel ψ ist. Beweisen Sie durch die Angabe eines entsprechenden Beweisbaums:
1
(a) ϕ ∨ ψ ψ ∨ ϕ
(b) ϕ,ϕ → ψ ψ (hierbei ist ϕ → ψ eine Abkürzung für ¬ϕ ∨ ψ)
(c) ϕ ∨ ψ,¬ϕ ψ
(d) ¬¬ϕ ` ϕ

Answer 1

wie man es lösen kann.

Du wirst nicht auf Anhieb den vollständigen Beweisweg überblicken. Also hilft nur ausprobieren. Mit der Zeit wirst du ein Gespür dafür entwickeln, welche Regel wohl wie angewendet werden muss um das zu erreichen was du willst.

Es gibt einen recht sicheren Weg, den Aufbau dieses Gespürs zu vermeiden: die Aufgaben nicht selbst lösen. In diesem Sinne schade ich jetzt mal deinem Gespür, indem ich dir die Möglichkeit nehme, (a) selbst zu lösen:

Mittels χ := ϕ  wird

        (ϕ ∨ ψ  ¬ϕ ∨ χ  /  ψ ∨ χ)

zu

        (ϕ ∨ ψ  ¬ϕ ∨ ϕ  /  ψ ∨ ϕ) .

Weil ϕ ∨ ψ eine Aussage in {ϕ1, . . . ,ϕn} = {ϕ ∨ ψ} ist, und ¬ϕ ∨ ϕ ein Axiom ist, ist  {ψ ∨ ϕ} aus {ϕ ∨ ψ} beweisbar.

Quizzfrage: Wie bin ich so schnell auf die Verwendung der Regel (ϕ ∨ ψ  ¬ϕ ∨ χ  /  ψ ∨ χ)  gekommen?

Comments

Danke Oswald, aber ich weiss leider auch nicht wie ich es lösen kann. Kannst du mir zeigen wie man es löst ?

---

Also er hat dir doch bereits mit (a) gezeigt wie man es löst indem man die vierte Regel benutzt:

Die vierte Regel besagt dass wenn ϕ ∨ ψ und ¬ϕ ∨ χ gelten, daraus folgt, dass auch ψ ∨ χ gilt. (Sprich: ϕ ∨ ψ und ¬ϕ ∨ χ beweisen ψ ∨ χ)

Setzt man jetzt einfach χ := ϕ und setzt das in die Regel ein hat man:
ϕ ∨ ψ, ¬ϕ ∨ ϕ |-  ψ ∨ ϕ.

So habe ich das zumindest verstanden.
Wie man jetzt allerdings einen Beweisbaum daraus aufschreibt weiß ich leider auch nicht.