Durchschnittlicher Fortschritt
Empfohlene Karteikarten-Sets
Karteikarten im Karteikarten-Set
Noch nicht gestartet (14)
Wann ist eine Menge von Aussagen wiederspruchsfrei?
Eine Menge von Aussagen heißt konsistent (widerspruchsfrei), wenn
es mindestens eine Belegung der Variablen gibt, so dass alle Aussagen wahr sind.
Gebe die Präzedenz aller Operatoren der Aussagenlogik an.
¬ NOT vor ∣ NAND vor ↓ NOR vor ∧ AND vor ∨ OR vor → IMPL vor ↔ ÄQUIV
d.h.
¬ bindet am stärksten, ↔ bindet am schwächsten
Was ist eine Tautologie?
Als Tautologien (allgemeingültige Aussage) bezeichnet man
logische Ausdrücke, die unabhängig von der Belegung der Variablen immer den
Wert wahr ergeben.
Was ist eine Kontradiktion?
Als Kontradiktion (widersprüchliche Aussage) bezeichnet man
logische Ausdrücke, die unabhängig von der Belegung der Variablen immer den
Wert falsch ergeben.
Definiere CNF.
Ein aussagenlogischer Ausdruck A ist in konjunktiver Normalform (CNF) falls er eine Konjunktion von Disjunktionen von Literalen ist, d.h.:
A = A₁ ∧ A₂ ∧ ... ∧ Aₙ
wobei jedes Aᵢ die Form λ₁ ∨ λ₂ ∨ λⱼ ∨ λ ₘᵢ hat und jedes λⱼ ein Literal ist.
Definiere DNF.
Ein aussagenlogischer Ausdruck A ist in disjunktiver Normalform
(DNF), falls er eine Disjunktion von Konjunktionen von Literalen ist, d.h.:
A = A₁ ∨ A₂ ∨ ... ∨ Aₙ
wobei jedes Aᵢ die Form λ₁ ∧ λ₂ ∧ λⱼ ∧ λ ₘᵢ hat und jedes λⱼ ein Literal ist.
Wie geht man bei der Resolutionswiderlegung (
Resolutionsrefutation) vor?
Ablauf:
- Negation der Konklusion einer Schlussfolgerung durch konjunktive Verknüpfung mit den Prämissen (z.B. {Q, R} ⊢S wird zu Q ∧ R ∧ ¬ S).
- Überführung des Gesamtausdrucks in die CNF und Erzeugung der Klauselmenge
- Durchführung der Resolution: Erzeugung alternativer Resolutionsableitung bis ein Widerspruch abgeleitet oder die Resolution vollständig erzeugt wurde (z.B. nach linearer Resolution).
Die Aussage ist korrekt wenn eine leere Klausel resolviert wird, also die Klauselmenge nicht wiederspruchsfrei ist.
Was versteht man unter Resolution in der Aussagenlogik?
- Unter Resolution versteht man eine systematische und automatisierbare Methode zur Behandlung logischer Probleme.
- Wir wollen nachweisen, dass aus gegebenen Aussagen Q und R (Annahmen oder Prämissen genannt) eine Schlussfolgerung S ( Konklusion, Konsequenz ) gezogen werden kann.
- Wir schreiben hierfür {Q, R} ⊢S
- Wir sagen S ist ableitbar (oder resolvierbar ) aus Q und R
- Wird eine leere Klausel erreicht wird das Symbol ⊥ zur Darstellung verwendet
Was ist eine Klausel?
Eine Klausel ist eine endliche Disjunktion von Literalen, d.h. entspricht
der Form
p₁ ∨ p₂ ∨ pₖ
wobei jedes pᵢ ein (positives oder negatives) Literale ist.
Was ist ein Literal?
- Ein Literal ist ein Atom oder die Negation eines Atoms.
- Als atomare Ausdrücke oder Atome bezeichnen wir nicht weiter zerlegbare Grundaussagen.
Erläutere die Begriffe Prädikat und Quantor.
- Prädikate beschreiben Eigenschaften von Objekten und Beziehungen zwischen Objekten.
- ∀ Allquantor „für alle“
- ∃ Existenzquantor „es existiert“
Wann ist ein Prädikat erfüllbar und wann gültig?
- Ein Prädikat heißt erfüllbar, wenn es mindestens eine Variabelbelegung gibt für welche das Prädikat wahr ist.
- Ein Prädikat heißt gültig, wenn es unter allen Variabelbelegungen wahr ist.
Worin unterscheiden sich freie und gebundene Variabeln?
- Eine Variable heißt (durch einen Quantor) gebunden , wenn sie innerhalb des Wirkungsbereichs dieses Quantors vorkommt.
- Nicht gebundene Variablen heißen frei. Ob eine Aussage wahr ist, hängt in der Regel auch von der Belegung den freien Variablen ab.
Was ist eine Hornklausel?
- Eine Horn Klausel ist eine Klausel in der alle Literale negiert sind, mit Ausnahme höchstens eines Literals.