Klausur August '05

Benutzeravatar
John
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 12. Dez 2008 17:41
Wohnort: E-Pool

Klausur August '05

Beitrag von John » 2. Sep 2010 16:23

Ich bearbeite grade die Klausur vom 1. August 2005. Komm eigentlich ganz gut voran, wollte trotzdem mal ein paar meiner Lösungen zur "Diskussion" hier reinstellen. Falls ihr also irgendwo anderer Meinung seit, oder die gleiche Lösung habt, lasst es mich wissen.

Hier zur Aufgabe 3:

(a) Geben Sie an, welche der folgenden Bedingungen an eine Formel \(\varphi \in AL\) äquivalent sind:
(i) \(\varphi\) ist nicht allgemeingültig
(ii) \(\varphi \equiv 0\)
(iii) \(\varphi\) ist unerfüllbar
(iv) \(\neg \varphi\) ist erfüllbar
(v) \(\varphi \rightarrow \neg \varphi\) ist allgemeingültig

Lösung: Äquivalent sind einmal (i) und (iv). Außerdem der Rest, also (ii), (iii) und (v).

(b) Sind die folgenden Behauptungen über beliebige FO-Formeln wahr oder falsch? Geben Sie jeweils eine Begründung oder Gegenbeispiel an.
(i) Wenn \(\varphi\) allgemeingültig ist, so ist auch \(\exists x \varphi\) allgemeingültig.
(ii) Wenn \(\varphi\) erfüllbar ist, so ist \(\forall x \varphi\) allgemeingültig
(iii) \(\forall x \varphi\) ist allgemeingültig gdw. \(\exists x \neg \varphi\) unerfüllbar ist.

Lösung:
(i) Falsch. \(\exists x \varphi\) ist falsch bei leerer Trägermenge.
(ii) Falsch. Gegenbeispiel: \(\varphi := \exists x_1 \exists x_2 (x_1 \neq x_2) \wedge x = c\)
Hier muss die Trägermenge mind. 2 Elemente haben. Die freie Variable x muss mit c belegt werden. Wird sie jetzt allquantifiziert, kann die Formel nicht mehr erfüllbar sein.
(iii) Richtig. Das eine ist das Negat des anderen.

(c) Welche der folgenden Formelmengen sind (für jede feste, endliche Signatur S) rekursiv aufzählbar?
(i) \(\{ \varphi \in FO_0(S) : \varphi\) allgemeingültig \(\}\)
(ii) \(\{ \varphi \in FO_0(S) : \varphi\) unerfüllbar \(\}\)
(iii) \(\{ \varphi \in FO_0(S) : \varphi\) erfüllbar \(\}\)

Lösung: (i) und (ii). Allgemeingültige FO-Formeln sind rekursiv aufzählbar (mit passendem Kalkül). Nimmt man zu jeder dieser Formeln das Negat, so hat man rekursiv alle unerfüllbaren FO-Formeln aufgezählt. (iii) Nicht rekursiv aufzählbar (Vermutung, da keine Regeln existieren, um rekursiv lediglich erfüllbare Formeln zu "generieren").
DON'T PANIC

LordHoto
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 14. Dez 2009 17:00

Re: Klausur August '05

Beitrag von LordHoto » 6. Sep 2010 14:49

John hat geschrieben:(b) Sind die folgenden Behauptungen über beliebige FO-Formeln wahr oder falsch? Geben Sie jeweils eine Begründung oder Gegenbeispiel an.
(i) Wenn \(\varphi\) allgemeingültig ist, so ist auch \(\exists x \varphi\) allgemeingültig.

Lösung:
(i) Falsch. \(\exists x \varphi\) ist falsch bei leerer Trägermenge.
Wenn die Trägermenge leer ist, musst du erstmal zeigen, dass überhaupt \(\varphi\) allgemeingültig sein kann (sonst funktioniert dein Schluss nicht, denn wenn \(\varphi\) einfach nicht allgemeingültig ist, dann ist die genannte Folgerungsbeziehung ja immer wahr).

Also nehmen wir an die Trägermenge ist leer und die Signatur ist nicht leer. Wenn die Signatur leer wäre, dann muss auch \(\varphi\) leer sein (da mit \(S=\emptyset, T(S)=\emptyset\)) und damit kann \(\varphi\) nicht allgemeingültig sein kann, also ist die Aussage in diesem Fall richtig.

Nehmen wir an die Signatur ist nicht leer, dann gibt es mindestens ein Konstantensymbol, ein Funktionssymbol oder ein Relationssymbol in S. Jetzt untersuchen wir die Fälle:

1) Es gibt ein Konstantensymbol. Da die vorgeschlagene S-Struktur eine leer Trägermänge hat, kann sie dieses Konstantensymbol nicht interpretieren, daher kann es keine S-Struktur mit leerer Trägermenge geben für diese S Signatur. Daraus folgt, dass die Trägermenge nicht leer sein kann.

2) Es gibt ein Funktionssymbol der Stelligkeit n. Nach Definition 1.1 im FO Skript muss es nun in deiner S-Sturktur eine Interpretation von f mit \(f: A^{n} -> A\) geben. Da A nun leer ist, kann es eine solche Funktion nicht geben, da es kein \(x \in A\) gibt, was zugeordnet werden kann.

3) Es gibt ein Relationssymbol der Stelligkeit n. Nach Definition 1.1 im FO Skript muss es nun in deiner S-Strutkur eine Interpretation für R geben mit \(R \subseteq A^{n}\). Ich denke nicht, dass \(\emptyset^{n}\) wirklich eine sinnvolle Definition eines n-Tupels sein kann, da alle Einträge Elemente der leeren Menge sein müssen, aber die leere Menge hat keine Elemente. Daraus folgt, dass die Trägermenge nicht leer sein kann.

Also alles in allem denke ich, dass dein Gegenbeispiel mit einer leeren Trägermänge nicht funktioniert.

Überdies denke ich sogar, dass die Folgerung gilt. Sei \(\phi \in \varphi\). Jetzt gibt es zwei Fälle:

1) \(x \in frei(\phi)\), da wir wissen, dass \(\phi\) allgemeingültig ist, können wir natürlich auch x existenziell abquantifizieren (da gilt: \(\forall{x}\psi \rightarrow \exists{x}\psi\)). \(\exists{x}\phi\) ist wiederrum allgemeingültig, da \(\forall{x}\forall{x_1}...\forall{x_n}\phi( \equiv \forall{x_1}...\forall{x_n}\forall{x}\phi) \rightarrow \exists{x}\forall{x_1}...\forall{x_n}\phi \models \forall{x_1}...\forall{x_n}\exists{x}\phi\). (Für die Modellbeziehung siehe Übung 2.8 im Skript)
2) \(x \notin frei(\phi)\), da x nun schon abquantifiziert in \(\phi\) ist, ändert eine weitere Quantifizierung nichts an der Allgemeingültigkeit, da die "inneren" Quantoren die Variable "x" wieder "überschreiben" (sieht "2.2 Semantik" im Skript).
Compiler 1 Tutor WS 12/13

Benutzeravatar
John
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 12. Dez 2008 17:41
Wohnort: E-Pool

Re: Klausur August '05

Beitrag von John » 6. Sep 2010 17:29

Gute Argumentation. Du hast Recht, eine leere Trägermenge macht wenig Sinn, und wie ich jetzt sehe, ist die Trägermenge einer Struktur tatsächlich schon per Definition nicht leer. (Siehe Definition 1.1 im FO-Skript). Insofern ist also Aussage b) (i), wie du erläutert hast, wahr.
DON'T PANIC

Antworten

Zurück zu „Archiv“