Prüfung, Weihrauch, 11.92

Wie sind aussagenlogische Formeln definiert?

Wozu sind die Klammern bei Ausdrücken wie (a_^b) erforderlich?

(Eindeutige Zerlegbarkeit, Rekursionssatz für Peano-Algebren)

Wann heißt eine aussagenlogische Formel erfüllbar?

(Erläuterung der Semantik der Aussagenlogik)

Ist die Menge der aussagenlogischen Formeln entscheidbar?

(Wahrheitstafel-Methode)

Was besagt der Kompaktheitssatz der Aussagenlogik?

(Topologie des Cantorschen Raumes, wegen Zusammenhang zur Typ-II-Theorie)

Wie sind prädikatenlogische Formeln definiert?

Welche Begriffe der Gültigkeit gibt es in der Prädikatenlogik?

Ist die Menge der allgemeingültigen prädikatenlogischen Formeln entscheidbar?

(Nein: Reduktion auf das Wortproblem für Semi-Thue-Systeme)

Ist die erwähnte Menge rekursiv aufzählbar?

(Allabschluß, Pränexe Normalformen, Skolemisierung, Instanzen, Herbrand-Strukturen, Interpretationen und zugehörige Sätze)

Was kann man über die Ausdrucksstärke der Prädikatenlogik mit Gleichheit sagen?

(definitorische Erweiterungen, Charakterisierbarkeit von Kongruenzrelationen und Faktorstrukturbildung)

Was sind Unifikatoren?

(Definition und Anwendung bei der SLD-Resolution)

Prüfung 6.5.92

Syntax der Aussagenlogik

Semantik der Aussagenlogik

Erfüllbarkeit

(Kompaktheitssatz der Aussagenlogik)

Was ist eine Tautologie?

Sind die erfüllbaren aussagenlogischen Formeln entscheidbar?

(Ja: Wahrheitstafel-Methode)

Welcher Aufwand?

((n-1)^.2ⁿ, Koinzidenzlemma)

Gibt es ein schnelleres Verfahren?

(Wohl nicht: Die Menge der aussagenlogischen Tautologien ist ein NP-vollständiges Problem)

Syntax der prädikatenlogischen Formeln?

(Alphabet, Variablen, Prädikate, Funktionen, m, Typ, Terme, Primformeln, prädikatenlogische Formeln)

Semantik der prädikatenlogischen Formeln?

(t-Struktur, Auswertungsfunktion für Terme und Wahrheitswertfunktion für Formeln)

Wann ist eine prädikatenl. Formel gültig, erfüllbar, allgemeingültig?

Sind die allgemeingültigen prädikatenl. Formeln entscheidbar?

(Nein: Rückführung auf das Semi-Thue-System)

Sind sie rekursiv aufzählbar?

(Ja: Beweis durch Angabe eines Algorithmus:

1) Wenn wÏPF dann Endlosschleife

2) Negation, Allabschluß, pränexe Normalform bilden

3) Skolemisierung, (Herbrand-Modelle erläutern)

4) Instantiierung

5) Abbildung aus die Menge der aussagenl. Formeln

6) Falls eine nicht-erfüllbare Teilmenge gefunden wird (Kompaktheitssatz der Aussagenlogik) halten

Muß die Prädikatenlogik mit Gleichheit vollständig neu definiert werden?

(Nein: Man betrachtet (I,J)-Strukturen mit =^. Î I und Strukturen, in denen =^. als Gleichheit in der Trägermenge interpretiert wird)

Wo unterscheidet sich die Ausdrucksstärke der Prädikatenlogik mit und ohne Gleichheit?

(In der Prädikatenlogik ohne Gleichheit kann die Gleichheit von Elementen in Strukturen nicht beschrieben werden, aber die Ununterscheidbarkeit von Elementen bzgl. Prädikaten und Funktionen kann durch Formeln ausgedrückt werden. Durch Faktorisieren erhält man eine (t,=^. )-Struktur (Trägermenge besteht aus den Äquivalenzklassen. In der PL mit Gleichheit können Strukturen bis auf Isomorphie charakterisiert werden.)

Prüfung, Weihrauch, 1.92

Syntax der Aussagenlogik

Semantik der Aussagenlogik

Was ist eine Belegung?

(Rekursionssatz, Peano-Algebra, eindeutige Zerlegbarkeit)

Wann ist eine Formel allgemeingültig?

Wann ist eine Formel erfüllbar?

Ist es entscheidbar, ob eien Formel erfüllbar ist?

(Ja: Wahrheitswerttabelle)

Komplexität des Verfahrens

Kompaktheitssatz und Erfüllbarkeit von Mengen aussagenlogischer Formeln.

Syntax der Prädikatenlogik.

Struktur, Belegung, Semantik.

Wann ist eine prädikatenlogische Formel allgemeingültig?

Ist die Allgemeingültigkeit entscheidbar?

(Nein: Beweisidee)

Aber rekursive Aufzählbarkeit

(pränexe Normalform, Skolemsche Normalform, Herbrandstrukturen, Instanzen, prädikatenlogische Interpretation, Rückführung auf aussagenlogische Formeln und Kompaktheitssatz)

Prädikatenlogik mit Gleichheit.

Prüfung, Weihrauch, 9.90

Syntax der Aussagenlogik

Syntax der Prädikatenlogik.

Semantik der Aussagenlogik

Wann heißt eine Formel der Aussagenlogik allgemeingültig? Wann heißt sie erfüllbar? Implikation einer Formel aus einer anderen? Wann folgt eien Formel aus einer Menge von Formeln?

Ist es entscheidbar, ob eien Formel erfüllbar ist?

(Ja: Wahrheitswerttabelle)

Komplexität des Verfahrens

Welche Aussage kann man über die Erfüllbarkeit einer unendlichen Menge aussagenlogischer Formeln machen?

(Kompaktheitssatz)

Semantik der Prädikatenlogik.

Wann ist eine prädikatenlogische Formel allgemeingültig?

Ist die Menge der allgemeingültigen Formeln entscheidbar?

(Nein, aber sie ist rekursiv-aufzählbar)

Nach welchem Verfahren ist die Menge rekursiv-aufzählbar?

Bleiben die Formeln bei Umformungen äquivalent zueinander?

(Bei Umformung in die pränexe Normalform ja, bei der in die Skolemsche Normalform nein, es bleibt aber die Erfüllbarkeit erhalten)

Prüfung, Weihrauch, 26.11.90

Syntax der Aussagenlogik

Semantik der Aussagenlogik

Ist der Wert einer aussagenlogischen Formel berechenbar?

(Ja: Wahrheitswerttabelle)

Komplexität des Verfahrens

Syntax der Prädikatenlogik.

Semantik der Prädikatenlogik.

Entscheidbarkeit, Aufzählbarkeit, Rekursionssatz.

Wann ist der Rekursionssatz anwendbar?

(Peano-Algebra)

Welche Eigenschaften hat eine Peano-Algebra?

Was unterscheidet die PL ohne Gleichheit von der mit Gleichheit?

Weitere Prüfungen

Was kann man über die Erfüllbarkeit einer Menge von aussagenlogischen Formeln sagen?

(Kompaktheitssatz)

Warum müssen die Klammern in (aÙb) in aussagenlogischen Formeln stehen?

Semantik der Prädikatenlogik.

(Struktur S zu einem Typ t, Belgung s, Wertefunktion für Terme, Wahrheitswertfunktion für Formeln, insbesondere waren hinzuschreiben: WW_S(R(t₁,...,t_m(R)))(s)=1 gdw. P_R(W(t₁)(s),...,W(t_m(R))(s)) gilt.)

Gültigkeit in einer Struktur unter einer Belegung. Gültigkeit in einer Struktur. Allgemeingültigkeit.

Abschluß einer Formel. a allgemeingültig gdw. "a allgemeingültig.

(Beweisidee mit Koinzidenzlemma)