Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
22 Cards in this Set
- Front
- Back
|
Die Syntax der Aussagenlogik:
Atomare Formeln haben welche Form? |
Eine atomare Formel ist von der Form Ai mit i ∈ N, d.h. atomare Formeln sind nur die
einfachen Aussagen. |
|
|
Die Syntax der Aussagenlogik
Eine beliebige Formel entsteht wie? |
Eine beliebige Formel entsteht induktiv aus atomaren Formeln, wobei die folgenden Schritte erlaubt
sind: b1) Jede atomare Formel ist eine Formel. b2) Sind F, G zwei Formeln, so sind auch (F ∧ G) sowie (F ∨ G) Formeln. b3) Für jede Formel F ist auch ¬F eine Formel. Hierbei heißt F ∧ G die Konjunktion von F und G, F ∨ G die Disjunktion von F und G, und ¬F die Negation von F |
|
|
(¬F1 ∨ F2)
|
(F1 ⇒ F2)
Folgerung |
|
|
F1 ∧ F2) ∨ (¬F1 ∧ ¬F2)
|
(F1 ⇔ F2)
Äquivalenz |
|
|
Idempotenz
|
(F ∧ F ) ≡ F sowie (F ∨ F ) ≡ F
|
|
|
Kommutativität
|
(F ∧ G) ≡ (G ∧ F ) sowie (F ∨ G) ≡ (G ∨ F )
|
|
|
Assoziativität
|
((F ∧ G) ∧ H) ≡ (F ∧ (G ∧ H)) sowie ((F ∨ G) ∨ H) ≡ (F ∨ (G ∨ H))
|
|
|
Absorption
|
(F ∧ (F ∨ G)) ≡ F sowie (F ∨ (F ∧ G)) ≡ F
|
|
|
Distributivität
|
(F ∧ (G ∨ H)) ≡ ((F ∧ G) ∨ (F ∧ H))
sowie (F ∨ (G ∧ H)) ≡ ((F ∨ G) ∧ (F ∨ H)) |
|
|
Doppel-Negation
|
¬¬F ≡ F
|
|
|
de Morgansche Regeln
|
¬ (F ∧ G) ≡ (¬F ∨ ¬G) sowie ¬ (F ∨ G) ≡ (¬F ∧ ¬G)
|
|
|
Tautologie-Regeln
|
Ist F eine Tautologie, so gilt (F ∨ G) ≡ F sowie (F ∧ G) ≡ G.
|
|
|
Unerfüllbarkeitsregeln
|
Ist F unerfüllbar, so gilt (F ∨ G) ≡ G sowie (F ∧ G) ≡ F .
|
|
|
Was ist ein Literal?
|
Ein Literal ist eine atomare Formel oder die Negation einer atomaren Formel. Im ersten Fall
sprechen wir von einem positiven Literal, im zweiten Fall von einem negativen Literal |
|
|
Konjunktive Normalform
|
Eine Formel F ist in konjunktiver Normalform (KNF), falls sie eine Konjunktion von
Disjunktionen von Literalen ist. Mit anderen Worten, es muss Literale L ij geben, so dass F von folgender Form ist: F = (L1 1 ∨ · · · ∨ L1 m1 ) ∧ · · · ∧ (Ln 1 ∨ · · · ∨ Ln mn ) |
|
|
Die 7 Schritte für den Algorithmus zur Erzeugung einer KNF
|
0) Eliminiere ⇒ und ⇔ mittels ihrer Definition.
1) Ersetze in F jede Teilformel der Form ¬¬G durch G. 2) Ersetze in F jede Teilformel der Form ¬ (G ∧ H) durch (¬G ∨ ¬H). Entsteht hierdurch eine Teilformel der Form ¬¬K, so wende Schritt 1) an. 3) Ersetze in F jede Teilformel ¬ (G ∨ H) durch (¬G ∧ ¬H). Entsteht hierdurch eine Teilformel der Form ¬¬K, so wende Schritt 1) an. 4) Wiederhole die Schritte 2) und 3) so oft wie möglich. 5) Ersetze in F jede Teilformel der Form (G ∨ (H ∧ I)) durch ((G ∨ H) ∧ (G ∨ I)). 6) Ersetze in F jede Teilformel der Form ((G ∧ H) ∨ I) durch ((G ∨ I) ∧ (H ∨ I)). 7) Wiederhole die Schritte 5) und 6) so oft wie möglich. |
|
|
Was sind Klauseln?
|
Die Klausel K1 , K2 , . . . , Kn von F sind die Mengen der Literale der einzelnen
Disjunktionen. K1 = {L11 , L12 , . . . , L1 m1 } K1 = {L21 , L22 , . . . , L2 m2 } ... Kn = {Ln1 , Ln2 , . . . , Ln mn } |
|
|
Was ist eine Resolvente und wann liegt diese vor?
|
eien K1, K2 und K3 Klauseln. Die Klausel K3 heißt eine Resolvente von K1 und K2, wenn es
ein Literal L gibt, so dass die folgenden beiden Bedingungen erf ̈llt sind: u 1) Es gilt L ∈ K1 und ¬L ∈ K2. Ist hierbei L = ¬A ein negatives Literal, so sei ¬L = A. 2) K3 = (K1 \ {L}) ∪ (K2 \ {¬L}) |
|
|
Die 3 Schritte des Erfüllbarkeitstest für aussagenlogische Formeln
|
Gegeben sei eine aussagenlogische Formel F in KNF.
1) Bilde die Klauselmenge K (F ). 2) F ̈r n = 1, 2, 3, . . . berechne Resn (K (F )) solange, bis u ∅ ∈ Resn (K (F )) oder Resn (K (F )) = Resn−1 (K (F )) gilt. 3) Im ersten Fall gib F ist unerfüllbar aus, im zweiten Fall gib F ist erfüllbar aus und stoppe. |
|
|
Welche Konzepte hat die Prädikatenlogik zusätzlich (im Gegensatz zur Aussagenlogik)?
|
Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik um folgende
wesentliche Konzepte. • Aussagen gelten für Objekte (Individuen) eines zu modellierenden Individuenbereichs. • Variablen sind Platzhalter für Objekte des Individuenbereichs. • Formel entstehen durch Variablen in Aussagen. • Formeln werden kombiniert durch Junktoren und eingeschränkt durch a Quantoren. • Objekte können durch Terme bezeichnet werden. |
|
|
Aussagen gelten für?
|
Aussagen gelten für Objekte (Individuen) eines zu modellierenden Inudividuenbereichs.
|
|
|
Variablen sind?
|
Variablen sind Platzhalter für Objekte des Individuenbereichs.
|
