Formale Logik und Verifikation
Grundlagen der Theoretischen Informatik
Grundlagen der Theoretischen Informatik
-
- 1 / 26
-
Cartes-fiches
Wofür steht /\
Konjunktion
UND Verknüfpung
Wofür steht V
Disjunktion
ODER Verknüpfung
Wofür steht →
Implikation
Daraus folgt
Wofür steht ⇔
Äquivalenz
Gleichwertig
Für was stehen diese Zeichen
|- , |=, <, →
logische Implikation
⇒
Was ist ein Literale
Eine elementare Aussage,
sinvollerweise mit einem Buchstaben abgekürzt
Wie nennt man eine elementare Aussage
Literal
Was ist eine aussagenlogische Formel
Es ist eine Verknüpfung von endlich vielen Literalen mit logischen Operratoren
Wie nennt man eine Verknüpfung von endlich vielen Literalen mit logischen Operratoren
(aussagenlogische) Formel
Was bedeutet die Konstante T
T ist immer wahr und ist das neutrale Element bezüglich der Konjunktion
Was ist das neutrale Element von der Konjunktion und wie wird es dargestellt
Wahr, und wird mit einem 'T' dargestellt
Was bedeutet die Konstante ┴
┴ bedeutet immer falsch und ist das neutrale Element bezüglich Disjunktion
Was ist das neutrale Element bezüglich Disjunktion und wie wird es dargestellt
Esi ist falsch und wir mit '┴' dargestellt
Wann ist eine Formel erfüllbar?
Wenn es eine Belegung der Literale einer Formel gibt,
die für die gesamte Formel einen Wahrheitswert 'w' ergibt.
Was heißt Tautologie?
Eine Formel heißt Tautologie oder gültig wenn sie bei jeder Belegung den Wahrheitswert w hat
Was bedeutet widersprüchlich?
Eine Formel heißt widersprüchlich, wenn sie bei keiner Belegung den Wahrheitswert w hat.
Defenition:
Erfüllbarkeitsproblem ( Satisfiability SAT)
Eine aussagenlogische Formel ist in konjunktiver Normalform (KNF),
wenn sie als Konjunktion von Disjunktionen aus Aussagen oder Negationen von Aussagen dargestellt ist.
Was bedeutetet die Abkürzung SAT?
Satisfiability (Erfüllbarkeitsbroblem)
Was bedeutet die Abkürzung KNF?
konjunktiver Normalform
Was ist ein Literal?
Ein Literal ist eine Aussage oder die Negation einer Aussage
Beispiel: p ¬p r ¬r
Was ist eien Klausel?
Eine Klausel ist eine Disjunktion aus Literalen.
Beispiel: p v ¬q v r ¬p v ¬q v ¬r
Was ist eine Formel in KNF?
eine Formel in KNF ist eine Konjunktion von Klauseln.
Beispiel: (p v ¬q v r) /\ (¬p v ¬q v ¬r) /\ ( p v q)
Welche Spezialfälle gibt es von der konjunktiven Normalform?
Eine Klausel darf auch nur aus einem Literal bestehen.
Eine Formel darf auch nur aus einer Klausel bestehen.
Eine leere Klausel entspricht dem neutralen Element der Disjunktion ┴
Eine leere Formel entspricht dem neutralen Element der Konjunktion T
Wie wird eine leeren Klausel bewertet?
Eine leere Klausel entspricht dem neutralen Element der Disjunktion ┴ ?
Wie wird eine leere Formel bewertet?
Eine leere Formel entspricht dem neutralen Elelent der Konjunktion T
Welche Schritte müssen durchgeführt um eine Formel in eine KNF ( Konjunktive Normalform )
1. Elemenieren der Äquivalenzen und Implikationen durch Umformen
2. Alle Negationen auserhalb von Klammern mit deMorgan auflösen.
3. Distributivgesetz anweden damit Konjunktionen und darunter Disjunktionen
