Prädikatenlogik: Freie und gebundene Variablen

Question

Ich hoffe ihr könnt mir hier helfen:

Ich habe in einer Übungsaufgabe rekursiv die Menge Frei(F) definiert, jetzt soll ich diese Definition auf die Formeln anwenden. Die Menge soll alle freien Variablen der jeweiligen Prädikatenlogischen Formeln enthalten:

F₁= Q(x)∨∀zP(x, g(z))∨∃x∀y(P(f(x), y)∧Q(a))

F₂= ((Q(x)∨∃x∀y(P(f(x), z)∧Q(a)))∨∀zR(x, z, g(x)))

So bekomme ich also folgende Mengen:

Frei(F₁) = {x,a}

Frei(F₂)  = {x,z,a}

Stimmen diese beiden Mengen also sind dies die freien Variablen?

Answer 1

Passt.

Comments

Das war eine falsche Antwort, die zwecks Rückgabe der Punkte zum Kommentar "degradiert" wurde.

Hallo Biberix,

> Frei(F₁) = {x,a}   Frei(F₂)  = {x,z,a} 

Stimmen diese beiden Mengen also sind dies die freien Variablen?

Variable in prädikatenlogischen Formeln werden durch die Quantoren ∃ oder ∀  gebunden.

Das ist nur bei  a  nicht der Fall:

F₁= Q(x) ∨ ∀z P(x, g(z)) ∨ ∃x∀y (P(f(x), y) ∧ Q(a))

F₂= ((Q(x) ∨ ∃x∀y (P(f(x), z) ∧ Q(a))) ∨ ∀z R(x, z, g(x)))

Gruß Wolfgang

---

Ich fürchte, das passt nicht.

Nachtrag:

Ich ziehe die Kritik zurück! (vgl. meinen vorletzen Kommentar) 

---

Eben weil a nicht durch einen Quantor gebunden wird, ist a frei.

---

Ja aber nur a. Aber du hast recht, ich hätte das Richtige nicht rot markieren sollen, werde das ändern.

---

Ich fürchte, das passt nicht. (Vgl. meine Antwort)

---

Dann solltest du vielleicht mal mein Argument widerlegen.

Nachtrag:

Wurde inzwischen widerlegt.

---

Gilt der Wirkungsbereich auch „rückwirkend“?

---

Frei(F1) = Frei(Q(x)∨∀zP(x, g(z))∨∃x∀y(P(f(x), y)∧Q(a)))

=Frei (Q(x)) ∪ Frei(∀zP(x, g(z))∨∃x∀y(P(f(x), y)∧Q(a)))

={x} ∪ {a} = {x,a}

---

Du hast recht, habe mich davon überzeugt, dass eine Variable bereits als "frei" bezeichnet wird, wenn sie an mindestens einer Stelle der Formel nicht quantifiziert ist.

Ziehe meine falsche Antwort zurück (→ Kommentar). Wer will schon Punkte geschenkt bekommen!

---

Kein Thema, ich bedanke mich für deine Mühe. Du warst vermutlich bei „vollfrei“ - da wäre deine Aussage vermutlich korrekt.

---

Sorry, den Begriff "vollfrei" habe ich tatsächlich noch nie gehört. Sonst wäre der Fehler wohl nicht passiert. :-)