19
TheoLog (Subject) / Logik (Lesson)
Advertisement
- Warum benötigt man Prädikatenlogik? Wie unterscheidet sie sich zur Aussagenlogik? Aussagenlogik ist zu schwach für die Represäntation von Wissen, da die atomaren Aussage keine (logisch definierte) Bedeutung haben. Prädikatenlogik ermöglicht Aussagen über Objekte. Prädikatenlogik besitzt sogenannte Quantoren, welche Aussagen über Variablen aussagen. ∀ Gilt die Aussage, egal was ich für x einsetze? ∃ Gilt die Aussage für mindestens ein x?
- Was ist ein Term? Jede Variable x ist ein Term f(x) ist ein Term h(x,y) ist ein Term c Konstante ist ein Term
- Was ist eine Unterformel? Jede Teilformel einer Formel, dazu zählt auch die Formel selbst!
- Wann ist eine Formel offen, wann geschlossen? Eine Formel ist offen, sofern sie freie Variablen (nicht gebunden) enthält, ansonsten ist sie geschlossen.
- Aus was besteht eine Struktur? Eine Struktur besteht aus einer Grundmenge (Alle x die man einsetzten könnte) und einer Interpretationsfunktion , welche jeder Funktion der Stelligkeit k eine k-stellige Funktion zuweist und jedem Prädikat Symbol P der Stelligkeit k eine k-stellige Relation zuweist
- Wie unterscheiden sich der Allquantor und der Existenzquantor? ∀ = Man muss alle Elemente der Strukturgrundmenge △ einsetzen und schauen, ob alle den Wahrheitswert 1 ergeben. Wenn ja, dann ist die allquantifizierte Formel wahr. ∃ = Man muss mindestens ein Element der Strukturgrundmenge △ finden, welches den Wahrheitswert 1 ergibt. Ist dies der Fall, dann ist die Formel wahr.
- Was ist der semantische Unterschied zwischen diesen Aussagen? ∀x.∃year.Hotel(x)→bookingstatus(x,Dec,year) =Full ∃year.∀x.Hotel(x)→bookingstatus(x,Dec,year) =Full 1) Für alle Hotels gibt es ein Jahr, wo gilt dass sie im Dezember ausgebucht sind. -> In irgendeinem Jahr 2) Es gibt ein Jahr für alle Hotels, wo gilt dass sie im Dezember ausgebucht sind. -> Im selben Jahr
- Wann sind zwei Formeln äquivalent? Wenn sie die selben Modelle haben.
- Wie lauten die Regeln in Bezug auf eine Interpretation I ist ein Modell für eine Formel? I ist ein Modell für eine Relation P(t1...tk) gdw. (t1...tk) Element von P^a ist I ist ein Modell für A ∨ B gdw. I ein Modell für A oder für B ist I ist ein Modell für A ∧ B gdw. I ein Modell für A und für B ist I ist ein Modell für ¬A gdw. sie kein Modell für A ist I ist ein Modell für ∀x.A gdw. (Λ, w(x/d) ein Modell für A ist. I ist ein Modell für ∃x.A gdw. (Λ, w(x/d) ein Modell für A ist.
- Wann ist eine Interpretation ein Modell einer Formelmenge? Wenn I Modell jedes Elements der Formelmenge ist
- Advertisement
- Wann ist eine Formel erfüllbar bzw. unerfüllbar? Eine Formel oder Formelmenge ist erfüllbar, wenn sie ein Modell besitzt. Besitzt sie keins, ist sie unerfüllbar. Eine Formel oder Formelmenge ist allgemeingültig, wenn alle Interpretationen Modelle sind. Sind nicht alle Modelle, so ist sie widerlegbar.
- Was ist die semantische Konsequenz? Eine Formel A folgt aus einer Formelmenge F, gdw. jedes Modell von F auch ein Modell von A ist. F |= A
- Wann sind zwei Formel äquivalent? Wenn sie die gleichen Modelle besitzen.
- Wie kann man zeigen, dass eine Formel allgemeingültig ist? Indem man zeigt, dass die Negation der Formel unerfüllbar ist. (Resolution)
- Wie zeigt man die semantische Konsequenz zweier Formeln? (Aus A folgt B) Zeige , dass (A ∧ ¬B) unerfüllbar ist.
- Wann ist eine Formel in Prädikatenlogik mit Gleichheit erfüllbar? Genau dann wenn Formel A (EQ) und Formel B (EQ) erfüllbar in der Prädikatenlogik ohne Gleichheit sind. Dabei bedeutet (EQ) dass man jedes Vorkommen von A in der Formel durch EQ ersetzt.
- Wann heisst eine Formel relational? Wenn sie nur Funktionssymbole der Stelligkeit 0 enthält. (a)
- Wie lautet das Auswertungsproblem? Erfüllt eine Interpretation I eine Formel A mit der Interpretation (Λ, w)? Diese Problem ist PSPACE vollständig.
- Was ist eine konjunktive Anfrage? Eine relationale Formel der Form Quantoren.Konjugation atomarer Formeln Sie ist NP vollständig