Grundlagen der Aussagenlogik Flashcards
(69 cards)
1
Q
Alphabet der Aussagenlogik - Definition
A
2
Q
Aussagenvariable - Definition
A
3
Q
A
Ja
4
Q
A
Nein, da das <- Symbol nicht Teil des Alphabets ist.
5
Q
A
Ja
6
Q
A
7
Q
A
Nein, da die äußeren Klammern fehlen.
8
Q
Präferenzregel - Klammersetzung
A
9
Q
Präferenzregel - logisches und/oder auf Mengen
A
10
Q
Präferenzregel - Variablenbezeichnung
A
Variablen können statt V_i auch mit römischen Großbuchstaben z.B. X, Y, Z usw. bezeichnet werden.
11
Q
Syntax der Aussagenlogik - Definition
A
12
Q
Syntax- und Ableitungsbäume - Beispiel
A
13
Q
Unterformel - Definiton
A
14
Q
Unterformel Beispiel:
A
15
Q
Was sind atomare Formel oder kurz atome?
A
16
Q
Was sind aussagenlogische Verknüpfungen
A
17
Q
Welcher Wert seht für wahr?
A
1
18
Q
Welcher Wert seht für falsch
A
0
19
Q
A
20
Q
Wahrheitsbelegung - Definition
A
21
Q
Was ist eine passende Belegung?
A
22
Q
Semantikfunktion:
A
23
Q
Negation - Definition
A
24
Q
Konjugation - Definition
A
25
Disjunktion - Definition
26
Impliktaion - Definition
27
Biimplikation - Definition
28
Notation für Belegungen
29
Notation für Formeln
30
Notation von Mengen von Formeln
31
Model - Definition
32
Erfüllbarkeit - Definition
## Footnote
Phi muss in AL sein
33
Allgemeingültigkeit - Definition
## Footnote
Phi muss in AL sein.
34
Allgemeingültigkeit - Proposition
35
Welche Methoden gibt es um die Allgemiengültigkeit und Erfülbarkeit von Funktionen zu unterscheiden?
* Wahrheitstafeln
* Resolution
* Sequenzenkalkül
36
Koinzidenzlemma
37
Wahrheitstafeln
38
Effizient von Wahrheitstafeln
Die Wahrheitstafel einer Formel mit n Variablen hat 2^n Zeilen, die alle ausgerechnet werden müssen. Das macht das Wahrheitstafelverfahren extrem ineffizient, außer für sehr kleine Formeln. Das Wahrheitstafelverfahren findet daher in der Praxis keine nennenswerte Anwendung.
39
Folgerung - Definition
40
Folgerung für Mengen
## Footnote
Falls Phi nur eine Formel enthält, schreiben wir psi folgt aus phi
41
Äquivalenz - Definition
42
nützliche Beziehungen zwischen Folgerung und Äquivalenz
43
Äquivalenz - dopplete Negation
44
Äquivalenz - Elimination der Implikation
45
Äquivalenz - Elimination der Biimplikation
46
Äquivalenz - de Morgansche Regel
47
Äquivalenz - Distributivität
48
Äquivalenz - Absorbtionsgesetz
49
Äquivalenz - Kommutativität von land und lor
50
Äquivalenz - Assoziativität von land und lor
51
Äquivalenz - Satz vom ausgeschlossenen Dritten
51
Äquivalenz - Satz vom Wiederspruch
52
Äquivalenz - Idempotenz von land und lor
53
Äquivalenz - Identität von land und lor
54
Welche aussagenlogische Operation wird als Disjunktion bezeichnet?
Das logische Oder.
55
Welche aussagenlogische Operation wird als Konjunktion bezeichnet?
Das logische Und.
56
Substitution
57
Ersetzungslemma
58
Wie verhalten sich große Konjunktion und Disjunktion auf eine leere Mengen?
59
Korollar 2.41
60
Was wird als reduzierte Formel bezeichnet?
Wenn die Formel keine Konjunktion, Implikation oder Biimplikation mehr enthält, also nur aus Verum, Falsum, Variablen, Disjunktion und der Negation besteht.
60
Normalform - Definition
61
Negationsnormalform (NNF) - Definition
62
Literal - Definition
63
disjunktive Normalform (DNF) und Konjunktive Normalform (KNF) - Definition
64
DNF - äquivalenz zu Formeln
Jede Formel phi in AL ist äquivalent zu einer Formel in disjunktiver Normalform.
65
KNF - äquivalenz zu Formeln
Jede formel phi in AL ist äquivalent zu einer Formel in konjunktiver Normalform
66
Korollar - Anzahl nicht-aquivalenter aussagenlogischer Formeln mit n Variablen
Für jedes n der natrürlichen Zahlen existieren genau 2^2^n paarweise nicht-äquivalente aussagenlogische Formeln mit n Variablen.
67
Erfülbarkeit in disjunktiver Normalform
Formeln in disjunktiver Normalform können sehr effizient auf Erfüllbarkeit gestet werden, es gibt aber für alle n in N Formeln bei der die länge der kürzesten äquivalenten DNF Formel exponentiell länger ist. Es gibt also keine Weg aussagenlogische Formeln in disjunktive oder konjunktive Normalform unzuwandeln.
