THI
Was kennzeichnet eine Aussage in der Aussagenlogik?
Sie ist ein Satz in natürlicher Sprache, der entweder wahr oder falsch ist.
Nennen Sie eine Limitierung der Aussagenlogik, die eine ausdrucksstärkere Logik wie die Prädikatenlogik notwendig macht.
Aussagen werden als Atome genutzt und nicht weiter analysiert, wodurch die innere Struktur einer Aussage verloren geht und Beziehungen zwischen Objekten oder allgemeine Aussagen schwer auszudrücken sind.
Gegeben seien die Klauseln K1 = {A, B} und K2 = {¬A, C}. Bilden Sie die Resolvente K3.
K3 = {B, C}.
Wann ist eine Konjunktion (A ∧ B) wahr?
Wenn sowohl A als auch B wahr sind.
Was ist eine Formel in konjunktiver Normalform (KNF)?
Eine Konjunktion von Disjunktionen von Literalen.
Wie wird die Äquivalenz (A ↔ B) definiert?
A → B und B → A gelten gleichzeitig.
Welchen Hauptzweck erfüllt der Resolutionskalkül in der formalen Logik?
Er dient dazu, zu testen, ob eine Formel oder eine Menge von Formeln widersprüchlich/unerfüllbar ist.
Was besagt das Resolutionslemma bezüglich einer Resolvente K3 von K1, K2 ∈ K(F)?
F ist semantisch äquivalent zu allen Formeln mit Klauselmenge K(F) ∪ {K3}.
Nennen Sie eine Menge von logischen Operatoren, die funktional vollständig ist.
{¬, ∧} oder {¬, ∨} oder {¬, ∧, ∨}.
Was ist Abstraktion in der Informatik?
Reduktion der vorhandenen Information auf die für das aktuelle Problem wesentliche Information oder Reduktion auf ein allgemeineres bzw. einfacheres Konzept.
Was ist eine atomare Aussage?
Eine Aussage, die nur einen Sachverhalt enthält und unteilbar ist, d.h. keine aussagenlogischen Verknüpfungen wie "nicht", "und", "oder" enthält.
Wann ist eine Implikation (A → B) falsch?
Eine Implikation (A → B) ist falsch, wenn A wahr ist und B falsch ist.
Was versteht man unter einem Literal in der Aussagenlogik?
Ein Atom (x) oder ein negiertes Atom (¬x).
Nennen Sie die drei Hauptbestandteile eines logischen Systems.
Syntax, Semantik, Kalkül.
Wenn eine Klauselmenge eine positive Einheitsklausel {x} enthält, was muss dann mit dem Wahrheitswert von x geschehen, um die Formel zu erfüllen?
x muss auf 1 gesetzt werden.
Was ist der erste Schritt bei der Formalisierung einer deutschen Aussage in der Aussagenlogik gemäß der Faustregel?
Die atomaren Aussagen identifizieren und durch Aussagenvariablen ersetzen.
Welcher der folgenden Punkte ist KEIN Kernaspekt formaler Sprachen?
Emotionalität
Beschreiben Sie die Grundidee des indirekten Beweises (Widerspruchsmethode).
Unter der Annahme von A und ¬B wird ein Widerspruch (z.B. 0 = 1) hergeleitet, um zu zeigen, dass A → B gilt.
Welchen Zweck erfüllt ein Modell in der Systemanalyse?
Es vereinfacht die Darstellung eines komplexen Systems zum besseren Verständnis und zur Analyse.
Nennen Sie zwei Nachteile natürlicher Sprachen für die Modellierung und Spezifikation in der Informatik.
Sie sind komplex, mehrdeutig und ungenau.
Was ist eine Einheitsklausel?
Eine Klausel, die nur aus einem (positiven oder negativen) Literal besteht.
Welcher Bereich der Informatik nutzt Hornlogik als Grundlage?
Logische Programmierung (Prolog).
Was ist eine Hornklausel?
Eine Klausel, die höchstens ein positives Literal enthält.
Was ist eine Tautologie?
Eine Formel, die für jede Belegung wahr ist (allgemeingültig).
Welchen Wahrheitswert hat eine leere Klausel?
Falsch (0)
Was ist eine Resolvente K3 von zwei Klauseln K1 und K2?
K3 = (K1 \ {L}) ∪ (K2 \ {¬L}), wenn es ein Literal L gibt, sodass L ∈ K1 und ¬L ∈ K2.
Was bedeutet es, wenn α ein Modell von F ist?
α(F) = 1
Was ist eine 'geschlossene Formel' in der Prädikatenlogik?
Eine Formel, die keine freien Variablen hat.
Welche der folgenden Regeln ist eine Idempotenz-Regel?
(F ∧ F) ≡ F
Welche primäre Einschränkung der Aussagenlogik wird durch die Prädikatenlogik behoben?
Die Aussagenlogik kann die innere Struktur von Aussagen nicht modellieren und keine Beziehungen zwischen Objekten, universelle oder existenzielle Quantifizierung ausdrücken.
Nennen Sie die zwei Haupttypen von Quantoren in der Prädikatenlogik.
Allquantor (∀) und Existenzquantor (∃)
Was ist das Hauptmerkmal einer Hornklausel?
Eine Hornklausel enthält höchstens ein positives Literal.
Was repräsentiert ein 'Term' in der Prädikatenlogik?
Ein Term repräsentiert Objekte.
Welchen Wahrheitswert hat eine leere Klausel?
0 (falsch)
Definieren Sie den Begriff 'Tautologie' für eine Formel F.
F ist eine Tautologie, wenn jede Belegung auch ein Modell von F ist.
Was bedeutet es, wenn eine Formel F 'erfüllbar' ist?
F hat mindestens ein Modell.
Was ist die grundlegende Idee des Resolutionskalküls, um die Unerfüllbarkeit einer Formel zu zeigen?
Solange Resolventen bilden, bis die leere Klausel erreicht wird.
Welche Beziehung besteht zwischen einer Tautologie F und der Formel ¬F?
Eine Formel F ist genau dann eine Tautologie, wenn ¬F unerfüllbar ist.
Wann wird eine Struktur α als 'Modell' für eine Formel F in der Prädikatenlogik bezeichnet?
Wenn α(F) = 1.
Was ist eine 'Einheitsklausel'?
Eine Klausel, die nur aus einem (positiven oder negativen) Literal besteht.
Wie ist eine Formel in Konjunktiver Normalform (KNF) strukturiert?
Eine Konjunktion von Disjunktionen von Literalen.
Was versteht man unter einem 'Literal' in der Aussagenlogik?
Ein Literal ist ein Atom x ∈ Var oder ein negiertes Atom ¬x für x ∈ Var.
Welches der folgenden ist ein Beispiel für eine 'Konstante' gemäß der Nomenklatur der Prädikatenlogik?
joAnn
Was ist der Hauptzweck des Resolutionskalküls in der formalen Logik?
Um zu testen, ob eine Formel oder eine Menge von Formeln widersprüchlich/unerfüllbar ist.
Auf welcher Form von Formeln arbeitet der Resolutionskalkül hauptsächlich?
Konjunktiver Normalform (KNF)
Wann sind zwei Formeln F und G 'semantisch äquivalent'?
Wenn α(F) = α(G) für alle Belegungen α.
Was ist der Unterschied zwischen einem Prädikat und einer Funktion in der Prädikatenlogik?
Prädikate ordnen Objekten Wahrheitswerte zu, Funktionen ordnen Objekten wieder Objekte zu.
Wann wird eine Variable in einer prädikatenlogischen Formel als 'gebunden' bezeichnet?
Eine Variable ist gebunden, wenn sie bei jedem Auftreten einem Quantor zugeordnet ist.
Was ist eine 'atomare Formel' in der Prädikatenlogik?
P(t1, ..., tk), wobei P ein k-stelliges Prädikatensymbol und t1, ..., tk Terme sind.
Nennen Sie die vier Hauptkomponenten einer 'Struktur' α = (U, φ, ψ, ξ) in der Semantik der Prädikatenlogik.
U (Universum/Grundmenge), φ (Abbildung von Funktionssymbolen auf Funktionen), ψ (Abbildung von Prädikatensymbolen auf Prädikate), ξ (Abbildung von Variablen auf Objekte).
Welcher Quantor wird typischerweise verwendet, um Existenzaussagen mit Stichworten wie "Es gibt" oder "existiert" zu formalisieren?
Existenzquantor (∃x)
Wie werden Zeitwörter bzw. Eigenschaften in der Prädikatenlogik formalisiert?
Als Prädikatensymbole
Welche der folgenden Äquivalenzen ist korrekt für Quantoren und Konjunktion?
∀x F ∧ ∀x G ≡ ∀x (F ∧ G)
Was ist die Matrixformel einer Formel in Skolemform?
Der Teil der Formel nach den Quantoren.
Welche Aussage über die Reihenfolge von Quantoren ist korrekt?
∀x∀y F ≡ ∀y∀x F
Welche der folgenden Äquivalenzen ist korrekt bezüglich der Negation und des Allquantors?
¬∀x F ≡ ∃x ¬F
Was ist ein Hauptgrund für die Unentscheidbarkeit der Prädikatenlogik im Vergleich zur Aussagenlogik?
Die Prädikatenlogik hat unendlich viele passende und unendlich große Strukturen.
Was ist das Ziel der Skolemform?
Eine erfüllbarkeitsäquivalente Pränexform ohne Existenzquantoren zu erhalten.
Gegeben ist die Formel ∃u∀x∀z∀y (Q(x) ∨ P(x, g(z)) ∨ (P(f(u), y) ∧ Q(a))). Wenn die existenziell quantifizierte Variable u durch eine Skolemkonstante k ersetzt wird, wie lautet der resultierende Ausdruck?
∀x∀z∀y (Q(x) ∨ P(x, g(z)) ∨ (P(f(k), y) ∧ Q(a)))
Was ist das Herbrand Universum D(F) für eine Formel F in Skolemform?
Die Menge aller variablenfreien Terme, die aus den Bestandteilen von F gebildet werden können.
Was ist eine Normalform in der Prädikatenlogik?
Eine Einschränkung auf der Syntax, sodass jede beliebige Formel in eine semantisch äquivalente Normalform umgewandelt werden kann.
Wenn die Formel G die Variable x nicht enthält, welche Äquivalenz gilt dann?
∀x F ∧ G ≡ ∀x (F ∧ G)
Was besagt Church's Theorem?
Es gibt kein Verfahren, das für jede prädikatenlogische Formel F in endlich vielen Schritten entscheidet, ob F erfüllbar ist.
Warum ist das Umbenennen von Variablen in der Prädikatenlogik wichtig?
Um Komplikationen zu vermeiden, wenn die gleiche Variable frei und gebunden vorkommt oder von verschiedenen Quantoren gebunden wird.
Wann wird eine Formel F als "allgemein gültig" oder "Tautologie" bezeichnet?
Wenn alle zu F passenden Strukturen α auch Modelle von F sind.
Was bedeutet es, dass die Prädikatenlogik semi-entscheidbar ist?
Wenn F unerfüllbar ist, hält das Verfahren nach endlich vielen Schritten, aber es gibt kein Verfahren, das für alle erfüllbaren F nach endlich vielen Schritten hält.
Wann sind zwei Formeln F und G erfüllbarkeitsäquivalent?
Wenn F genau dann erfüllbar ist, wenn G erfüllbar ist.
Wann ist eine Formel F "erfüllbar"?
Wenn es ein Modell für F gibt.
Was besagt der Satz von Gödel-Herbrand-Skolem?
Eine geschlossene prädikatenlogische Formel F in Skolemform ist genau dann erfüllbar, wenn die Herbrand-Expansion E(F) im aussagenlogischen Sinn erfüllbar ist.
Wie wird ¬∀x F in Pränexform transformiert?
∃x ¬F
Wie wird ein Existenzquantor ∃xk+1 in einer Formel in Skolemform ersetzt, wenn er von ∀x1...∀xk abhängt?
Durch ein neues k-stelliges Funktionssymbol f(x1,...xk).
Wann sind zwei Formeln F und G semantisch äquivalent?
Wenn sie die gleichen Modelle haben.
Welcher Quantor wird typischerweise verwendet, um Aussagen mit Stichworten wie "Alle" oder "Jede" zu formalisieren?
Allquantor (∀x)
Welche Form hat eine Formel in Pränexform?
Q₁x₁ Q₂x₂ ... Qnxn G, wobei G keine Quantoren enthält.
Was bedeutet es, wenn eine Struktur α ein Modell für eine Formel F ist?
α(F) = 1
Erklären Sie kurz, was eine Herbrand-Struktur ist.
Eine Struktur, bei der das Universum U dem Herbrand Universum D(F) entspricht und variablenfreie Terme in der Formel durch Objekte des Herbrand Universums interpretiert werden.
Was besagt der Satz von Gödel-Herbrand-Skolem?
Eine geschlossene prädikatenlogische Formel F in Skolemform ist genau dann erfüllbar, wenn die Herbrand-Expansion E(F) im aussagenlogischen Sinn erfüllbar ist.
Nennen Sie die drei Arten von Hornklauseln.
Tatsachenklauseln/Fakten, Regeln, Zielklauseln.
Was besagt Church's Theorem bezüglich der Erfüllbarkeit prädikatenlogischer Formeln?
Es gibt kein Verfahren, das für jede prädikatenlogische Formel F in endlich vielen Schritten entscheidet, ob F erfüllbar ist.
Was ist der Zweck des not-Operators in Prolog?
Er drückt aus, dass etwas nicht bewiesen werden kann (ist true, wenn das Argument false ist).
Welche der folgenden Aussagen ist eine Faustregel für rekursive Regeln in Prolog?
Zuerst eine Regel definieren, die dem Rekursionsanfang entspricht.
Nennen Sie zwei Vorteile der deklarativen Programmierung.
Die Spezifikation ist schon das Programm; der Berechnungsmechanismus ist nicht Teil des Programms und kann leicht ausgetauscht werden; deklaratives "Denken" ist oft einfacher; Output ist logische Konsequenz des Programms; Programme sind flexibel bezüglich der Fragestellung.
Was ist eine Hornklausel?
Eine Klausel, die höchstens ein positives Literal enthält.
Wie wird eine Regel in Prolog syntaktisch dargestellt, die besagt "Wenn b1 und b2 gelten, dann gilt a"?
a :- b1, b2.
Was ist die Hauptidee hinter dem "Generate & Test"-Paradigma in Prolog?
Zuerst Lösungskandidaten generieren (generate(X)), dann diese Kandidaten anhand von Bedingungen testen (test(X)).
Welche der folgenden Aussagen über die Prädikatenlogik zweiter Stufe ist korrekt?
Sie ermöglicht die Quantifizierung über Prädikate und Funktionen erster Stufe.
Was ist die "Closed World Assumption" in Prolog?
Wenn sich etwas nicht aus Fakten und Regeln ableiten lässt, ist es falsch.
Welche der folgenden Logiken ist im Allgemeinen nicht berechenbar?
Prädikatenlogik erster Stufe
Wie werden Existenzquantoren (∃y) in Prolog typischerweise behandelt, wenn die Variable nur in einem Prädikat vorkommt?
Die Variable kann durch den Underscore _ ersetzt werden, z.B. KindVon(_,X).
Wie werden Variablen in Prolog-Fakten und -Regeln typischerweise geschrieben?
Variablen beginnen mit einem Großbuchstaben, Prädikate und Konstanten werden klein geschrieben.
Was ist der Unterschied zwischen == und = in Prolog?
== prüft auf Identität der Ausdrücke ohne Variablen zu binden, während = prüft, ob Ausdrücke unifizierbar sind und dabei Variablen bindet.
Was ist der Hauptunterschied zwischen imperativer und deklarativer Programmierung?
Imperative Programmierung gibt an, WIE etwas berechnet werden soll, deklarative WAS.
Was ist ein "allgemeinster Unifikator" für eine Menge von Literalen L?
Eine Substitution s, für die für jeden weiteren Unifikator s' für L eine Substitution s'' existiert, sodass s' = s'' o s.
Was ist eine "Tatsachenklausel" in der Hornlogik?
Eine Klausel mit genau einem positiven Literal.
Welcher Vergleichsoperator in Prolog testet, ob zwei Ausdrücke unifizierbar sind und wählt eine Unifizierung aus?
=
Welche Aussage trifft auf die Erfüllbarkeit in der Prädikatenlogik zu?
Sie kann nicht so einfach überprüft werden.
Was passiert, wenn der Grundresolutions-Algorithmus auf eine erfüllbare Formel F angewendet wird?
Das Verfahren terminiert nie (Endlosschleife).
Was ist das Hauptziel des Herbrand Universums?
Die Anzahl der zu betrachtenden Strukturen einschränken.
Welches Paradigma verfolgt die Programmiersprache Prolog?
Logische Programmierung (ein Beispiel für deklarative Programmierung).
Was ist die Herbrand-Expansion E(F) einer Formel F in Skolemform?
Die Menge der prädikatenlogischen Formeln, die entstehen, wenn Variablen in G (aus F = ∀x1...∀xn G) durch Elemente des Herbrand Universums ersetzt werden.