close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

2x2

EinbettenHerunterladen
Organisatorisches
Verschiebung der Vorlesung:
Vorlesung am Dienstag, 18.10.2011, 13:00–16:00, entfällt.
3.0 VU Formale Modellierung
Ersatz: Mittwoch, 19.10.2011, 15:00–18:00, AudiMax
Eingangstest:
beliebig oft wiederholbar
letzter Antritt zählt
Gernot Salzer
Sie wollen teilnehmen =⇒ letzter Antritt ≥ 8 Punkte
Sie wollen kein Zeugnis =⇒ letzter Antritt < 8 Punkte
11.10.2011
Videomitschnitt vom 4.10.:
Seit gestern verfügbar, extern aber nur über VPN
Seit heute früh auch ohne VPN extern abrufbar.
2
1
Übergangsbestimmungen
Was Sie letzte Woche hörten
Bac. Medieninf., Medizinische Inf., SW&Inf.Engineering
Entweder:
6.0 VU Grundzüge der Informatik
6.0 VU Th. Inf. und Logik (alt)
Oder:
3.0 VU Formale Modellierung
6.0 VU Th. Inf. und Logik (neu)
1. Organisatorisches
Bac. Technische Informatik
6.0 VU Grundzüge der Informatik
6.0 VU Th. Inf. und Logik (alt)
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.0 VU Grundlagen digitaler Systeme
3.0 VU Formale Modellierung
6.0 VU Th. Inf. und Logik (neu)
3.1. Was ist Logik?
3.2. Aussagenlogische Funktionen
3.3. Syntax und Semantik der Aussagenlogik
Bac. Wirtschaftsinformatik
6.0 VU Th. Inf. und Logik (alt)
3.0 VU Formale Modellierung
3.0 VU Th. Inf. und Logik (neu)
„Th. Inf. und Logik (neu)“ baut auf „Formale Modellierung“ auf.
„Th. Inf. und Logik (alt)“ dieses Semester zum letzten Mal!
3
4
Was Sie letzte Woche hörten
Die Logik untersucht allgemeine Prinzipien korrekten Schließens.
Alle Menschen sind sterblich.
Sokrates ist ein Mensch.
Sokrates ist sterblich.
Prämissen, Annahmen
Konklusion, Folgerung
1. Organisatorisches
Alle US-Präsidenten sind in der USA geboren.
Schwarzenegger ist US-Präsident.
Schwarzenegger ist in der USA geboren.
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1. Was ist Logik?
3.2. Aussagenlogische Funktionen
3.3. Syntax und Semantik der Aussagenlogik
Unzulässige Inferenzen
Alle Menschen sind sterblich.
Sokrates ist sterblich.
Sokrates ist ein Mensch.
Sokrates ist ein Mensch.
Sokrates ist sterblich.
Alle Menschen sind sterblich.
Kriterium für die Gültigkeit von Inferenzregeln
Immer wenn alle Prämissen wahr sind, ist auch die Konklusion wahr.
5
nor
iff
xor
implies
1
0
0
0
∧
0
1
1
1
↑
1
1
1
0
∨
0
0
0
1
↓
1
0
0
1
≡
0
1
1
0
≡
1
0
1
1
⊃
Was Sie letzte Woche hörten
if
or
0
1
¬
y
1
0
1
0
nand
0
⊥
x
1
1
0
0
and
false
1
x
1
0
not
true
Aussagenlogische Funktionen – Zusammenfassung
6
0
1
0
0
⊃
1
1
0
1
⊂
0
0
1
0
⊂
1. Organisatorisches
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1. Was ist Logik?
3.2. Aussagenlogische Funktionen
3.3. Syntax und Semantik der Aussagenlogik
Eine Menge von Funktionen heißt vollständig (für eine Funktionsklasse),
wenn damit alle Funktionen (der Klasse) ausgedrückt werden können.
{not, and, or} ist funktional vollständig.
Begründung siehe später.
Die Mengen {not, and}, {nand}, {not, or}, {nor}, {not, implies} und
{implies, false} sind ebenfalls funktional vollständig.
7
8
Aussagenlogik – Syntax
V = {A, B, C , . . . , A0 , A1 , . . . }
Induktive Definitionen
aussagenlogische Variablen
Syntax aussagenlogischer Formeln
Die Menge A der aussagenlogischen Formeln ist die kleinste Menge, für
die gilt:
(A1) V ⊆ A
Variablen sind Formeln.
(A2) { , ⊥} ⊆ A
(A3) ¬F ∈ A, wenn F ∈ A.
und ⊥ sind Formeln.
¬F ist eine Formel, falls F eine ist.
(A4) (F ∗ G) ∈ A, wenn F , G ∈ A und ∗ ∈ {∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂}.
(F ∗ G) ist eine Formel, falls F und G welche sind und ∗ ein binäres Op.symbol ist.
U . . . Universum, Menge aller relevanten Elemente
M0 ⊆ U . . . Menge von Grundelementen
f1 : U n1 → U, f2 : U n2 → U, . . . Konstruktionsfunktionen
Stufenweise Konstruktion der Menge M
Mi+1 = Mi ∪ { f1 (x1 , . . . , xn1 ) | x1 , . . . , xn1 ∈ Mi }
∪ { f2 (x1 , . . . , xn2 ) | x1 , . . . , xn2 ∈ Mi }
∪ ···
M = limi→∞ Mi = i≥0 Mi
Induktive Definition der Menge M
M ist die kleinste Menge, für die gilt:
¬(((A ∨ B) ≡ ¬(B ↓ C )) ⊂ ((A ∨ ⊥) ∧ B)) ∈ A
M0 ⊆ M
Wenn x1 , . . . , xn1 ∈ M, dann f1 (x1 , . . . , xn1 ) ∈ M.
Wenn x1 , . . . , xn2 ∈ M, dann f2 (x1 , . . . , xn2 ) ∈ M.
9
B = {1, 0} . . . Wahrheitswerte
I : V → B . . . Wahrheitsbelegung, Interpretation
I = { I | I : V → B } . . . Menge aller Interpretationen
(A1) V ⊆ A
(A2) { , ⊥} ⊆ A
(A3) ¬F ∈ A, wenn F ∈ A.
Semantik aussagenlogischer Formeln
(A4) (F ∗ G) ∈ A, wenn F , G ∈ A und ∗ ∈ {∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂}.
Der Wert einer Formel in einer Interpretation I wird festgelegt durch die
Funktion val : I × A → B:
U . . . Menge aller Zeichenketten bestehend aus Variablen,
Operatorsymbolen und Klammern
(v1) valI (A) = I(A) für A ∈ V;
V ∪ { , ⊥} . . . Grundelemente
f↑ (F , G) = (F ↑ G)
...
f⊂ (F , G) = (F ⊂ G)






10
Aussagenlogik – Semantik
A ist die kleinste Menge, für die gilt:

f¬ (F ) = ¬F




f∧ (F , G) = (F ∧ G) 

...
(v2) valI ( ) = 1 und valI (⊥) = 0;
(v3) valI (¬F ) = not valI (F );
(v4) valI ( (F ∗ G) ) = valI (F ) valI (G),
wobei die logische Funktion zum Operator ∗ ist.
. . . Konstruktionsfunktionen
11
12
Wert von ((A ∧ ¬B) ⊃ ⊥) für I(A) = 1 und I(B) = 0
=
=
=
=
Eine Formel F heißt
gültig, wenn valI (F ) = 1 für alle I ∈ I;
valI (((A ∧ ¬B) ⊃ ⊥))
···
(I(A) and not I(B)) implies 0
(1 and not 0) implies 0
0
erfüllbar, wenn valI (F ) = 1 für mindestens ein I ∈ I;
widerlegbar, wenn valI (F ) = 0 für mindestens ein I ∈ I;
unerfüllbar, wenn valI (F ) = 0 für alle I ∈ I.
Folgerung:
Wahrheitstafel
F ist gültig/erfüllbar/widerlegbar/unerfüllbar genau dann,
wenn ¬F unerfüllbar/widerlegbar/erfüllbar/gültig ist.
Kompakte Berechnung der Formelwerte für alle Interpretationen
Unter jedem Operator steht der Wert der entsprechenden Teilformel.
A B ((A ∧ ¬ B) ⊃ ⊥)
1 1
1 0 01 1 0
1 0
1 1 10 0 0
0 1
0 0 01 1 0
0 0
0 0 10 1 0
x ¬
1 0
0 1
x
1
1
0
0
y ∧ ⊃
1 1 1
0 0 0
1 0 1
0 0 1
13
Was Sie heute erwartet
((A ∧ ¬B) ⊃ ⊥) ist erfüllbar und widerlegbar.
A B ((A ∧ ¬ B) ⊃ ⊥)
1 1
1 0 01 1 0
1 0
1 1 10 0 0
0 1
0 0 01 1 0
0 0
0 0 10 1 0
Die Formel ist
erfüllbar (daher nicht unerfüllbar),
1. Organisatorisches
widerlegbar (daher nicht gültig).
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
(A ∨ ¬A) ist gültig und erfüllbar.
A (A ∨ ¬ A)
1 1 1 01
0 0 1 10
Die Formel ist
gültig (daher nicht widerlegbar),
erfüllbar (daher nicht unerfüllbar).
(A ∧ ¬A) ist unerfüllbar und widerlegbar.
A (A ∧ ¬ A)
1 1 0 01
0 0 0 10
14
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Die Formel ist
unerfüllbar (daher nicht erfüllbar),
widerlegbar (daher nicht gültig).
15
16
B, and, or, not, 0, 1 ist eine Boolesche Algebra
Zwei Formeln F und G heißen äquivalent, geschrieben F = G,
wenn valI (F ) = valI (G) für alle Interpretationen I gilt.
Das heißt, es gelten folgende Gleichungen.
(A ∧ B) ∧ C = A ∧ (B ∧ C )
(A ∨ B) ∨ C = A ∨ (B ∨ C )
A∧B =B∧A
A∨B =B∨A
A∧A=A
A∨A=A
A∧ =A
A∨⊥=A
A ∧ ¬A = ⊥
A ∨ ¬A =
A ∧ (A ∨ B) = A
A ∨ (A ∧ B) = A
A ∧ (B ∨ C ) = (A ∧ B) ∨ (A ∧ C )
A ∨ (B ∧ C ) = (A ∨ B) ∧ (A ∨ C )
¬(A ∧ B) und (¬A ∨ ¬B) sind äquivalent
A B ¬(A ∧ B) = (¬A ∨ ¬B)
01 0 01
1 1 0 1 1 1
01 1 10
1 0 1 1 0 0
10 1 01
0 1 1 0 0 1
0 0 1 0 0 0
10 1 10
Äquivalenz bleibt bei der Ersetzung von Variablen durch Formeln erhalten.
¬(
A
∧ B ) = (¬
A
∨¬ B )
[A → (C ∨ D), B → ¬D]
Ersetzen einer Teilformel durch eine äquivalente liefert eine äquiv. Formel.
(A ⊃ ¬(A ∧ B)) = (A ⊃ (¬A ∨ ¬B))
¬(A ∧ B) = (¬A ∨ ¬B)
17
Weitere Äquivalenzen
A↑B
A↓B
A⊃B
A⊂B
A ≡ B = (¬A ∨ B) ∧ (A ∨ ¬B)
= (A ∧ B) ∨ (¬A ∧ ¬B)
A ≡ B = (¬A ∨ ¬B) ∧ (A ∨ B)
= (A ∧ ¬B) ∨ (¬A ∧ B)
= ¬A ∨ ¬B
= ¬A ∧ ¬B
= ¬A ∨ B
= A ∨ ¬B
Schreibvereinfachung: keine Außenklammern, keine Klammern bei
geschachteltem ∧ oder ∨ (Assoziativität!)
A ∧ B ∧ C = ((A ∧ B) ∧ C ) = (A ∧ (B ∧ C ))
2M , ∩, ∪, , ∅, M . . . Beispiel einer anderen Booleschen Algebra
2M . . . Menge aller Teilmengen der Menge M, Potenzmenge
X . . . Komplement der Menge X bzgl. M
(X ↑ Y ) ↑ ( ↑ Y )
= (¬X ∨ ¬Y ) ↑ (¬ ∨ ¬Y )
= ¬(¬X ∨ ¬Y ) ∨ ¬(¬ ∨ ¬Y )
= (¬¬X ∧ ¬¬Y ) ∨ (¬¬ ∧ ¬¬Y )
= (X ∧ Y ) ∨ ( ∧ Y )
= (X ∧ Y ) ∨ Y
=Y
Ersetzen von Junktoren durch ∧, ∨ und ¬
Assoziativität
Kommutativität
Idempotenz
Neutralität
Komplement
Absorption
Distributivität
18
A ↑ B = ¬A ∨ ¬B
A ↑ B = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
¬¬A = A
A∧
= A, Komm. ∧
A ∨ (A ∧ B) = A, Komm. ∧, ∨
Verschieben der Negation
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
Äquivalenzen für
A∧ =A
A∨⊥=A
De Morgan Regeln
und ⊥
A∧⊥=⊥
A∨ =
A ∧ ¬A = ⊥
A ∨ ¬A =
¬¬A = A
¬ =⊥
¬⊥ =
19
20
Logische Konsequenz
A, A ∨ B |= B ? Nein!
I(A) I(B) A, A ∨ B |=I B
1
1
1
1
1
1
0
1
1
E 0
0
1
1
0
1
0
0
0
0
0
F1 , . . . , Fn |=I G: „Aus valI (F1 ) = · · · = valI (Fn ) = 1 folgt valI (G) = 1.“
„Falls in der Wahrheitsbelegung I alle Prämissen wahr sind,
dann ist auch die Konklusion wahr in I.“
I(A) I(B) A, A ∨ B |=I B
1
1
1
1 11 1
1 11 0 E 0
1
0
1
0
1
0 01 1
0
0
0 00 0
0
A, A ⊃ B |= B ? Ja!
I(A) I(B) A, A ⊃ B |=I B
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
0
0
0
1
Logische Konsequenz
F1 , . . . , Fn |= G: F1 , . . . , Fn |=I G gilt für alle Interpretationen I.
„Die Formel G ist eine logische Konsequenz der Formeln F1 , . . . , Fn .“
A
A⊃B
B
x
Wenn x , dann y .
y
Ist eine gültige Inferenzregel!
Kriterium für die Gültigkeit von Inferenzregeln
„Die Formel G folgt aus den Formeln F1 , . . . , Fn .“
Konvention: „|= G“ (n = 0) bedeutet „G ist gültig.“
I(A) = 1, I(B) = 0:
Es gilt valI (A) = valI (A ∨ B) = 1,
aber valI (B) = 1!
Immer wenn alle Prämissen wahr sind, ist auch die Konklusion wahr.
22
21
Äquivalenz, Konsequenz und Gültigkeit
Was Sie heute erwartet
Die Formeln F und G sind äquivalent (F = G) genau dann,
wenn F ≡ G eine gültige Formel ist.
1. Organisatorisches
Deduktionstheorem
2. Was bedeutet Modellierung?
3. Aussagenlogik
G folgt aus F1 , . . . , Fn genau dann, wenn Fn ⊃ G aus F1 , . . . , Fn−1 folgt.
F1 , . . . , Fn |= G genau dann, wenn F1 , . . . , Fn−1 |= Fn ⊃ G.
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Mehrfache Anwendung liefert:
F1 , . . . , Fn |= G genau dann, wenn F1 ⊃ (F2 ⊃ · · · (Fn ⊃ G) · · · ) gültig.
Wegen A ⊃ (B ⊃ C ) = (A ∧ B) ⊃ C erhalten wir weiters:
F1 , . . . , Fn |= G genau dann, wenn (F1 ∧ · · · ∧ Fn ) ⊃ G gültig.
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Das heißt: Semantik (= und |=) ausdrückbar in der Syntax (≡ und ⊃).
Ist nicht in jeder Logik möglich!
23
24
Von der Funktion zur Formel
Rezept für Zweifelsfälle der aussagenlogischen Modellierung
1
Identifiziere die elementaren Aussagen.
2
Analysiere alle Wahrheitsbelegungen.
3
Gegeben: Funktion f : Bn → B (z.B. als Wahrheitstafel)
Gesucht: Formel, die f darstellt
Wähle geeignete logische Funktionen
(unbeirrt von Intuition und natürlicher Sprache)
A B C
x y z
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
Klingt ja nicht schlecht, aber:
Wie kann man eine beliebige Funktion auf eine Kombination der
vordefinierten logischen Grundfunktionen zurückführen?
Beziehungsweise:
Wie kann man eine beliebige Funktion mit den vordefinierten Operatoren
als Formel darstellen?
F [A, B, C ]? := (A∧B∧C ) ∨ (A∧¬B∧¬C ) ∨ (¬A∧B∧C )
f (x , y , z)
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
Gesucht: Ein allgemeines Verfahren (ein „Algorithmus“), das zu einer
gegebenen Funktion eine passende Formel liefert.
25
Von der Funktion f : Bn → B zur Formel DNFf
Von der Funktion zur Formel
Gegeben: Funktion f : Bn → B (z.B. als Wahrheitstafel)
Gesucht: Formel, die f darstellt
A B C
x y z
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
26
Notation:
F [A, B, C ]?:= (¬A∨¬B∨C ) ∧ (¬A∨B∨¬C ) ∧ (A∨¬B∨C ) ∧ · · ·
f (x , y , z)
1
1
1
1
11
0
0
1
1
11
0
1
0
1
11
1
1
1
1
11
1
1
1
1
11
0
1
1
0
11
0
1
1
1
01
0
1
1
1
10
27
{F , G, H, . . . } = F ∧ G ∧ H ∧ · · ·
{F , G, H, . . . } = F ∨ G ∨ H ∨ · · ·
{} =
{} = ⊥
Charakteristisches Konjunkt für b = (b1 , . . . , bn ) ∈ Bn :
Kb = { Ai | bi = 1, i = 1..n } ∧ { ¬Ai | bi = 0, i = 1..n }
b = (1, 0, 1, 1)
=⇒
Kb = A1 ∧ ¬A2 ∧ A3 ∧ A4
Ib . . . Interpretation definiert durch Ib (Ai ) = bi
Kb hat den Wert 1 für Ib , und 0 für alle anderen Interpretationen.
Ib : A1 → 1, A2 → 0, A3 → 1, A4 → 1
=⇒
valIb (Kb ) = 1
Disjunktive Normalform für f : Bn → B
DNFf = { Kb | f (b) = 1, b ∈ Bn } repräsentiert die Funktion f , d.h.:
valIb (DNFf ) = f (b) für alle b ∈ Bn .
28
Von der Funktion f : Bn → B zur Formel KNFf
Notation:
{F , G, H, . . . } = F ∧ G ∧ H ∧ · · ·
{F , G, H, . . . } = F ∨ G ∨ H ∨ · · ·
A1 A2 A3
Kb
Db
b
f (b)
1
1
1
1 A1 ∧ A2 ∧ A3 =: K111
¬A1 ∨ ¬A2 ∨ A3
1
1
0
0
¬A1 ∨ A2 ∨ ¬A3
0
1
0
1
1
0
0
1 A1 ∧ ¬A2 ∧ ¬A3 =: K100
1 ¬A1 ∧ A2 ∧ A3 =: K011
0
1
1
A1 ∨ ¬A2 ∨ A3
0
1
0
0
A1 ∨ A2 ∨ ¬A3
0
0
0
1
0
0
0
0
A1 ∨ A2 ∨ A3
{} =
{} = ⊥
Charakteristisches Disjunkt für b = (b1 , . . . , bn ) ∈ Bn :
Db = { Ai | bi = 0, i = 1..n } ∨ { ¬Ai | bi = 1, i = 1..n }
b = (1, 0, 1, 1)
=⇒
Db = ¬A1 ∨ A2 ∨ ¬A3 ∨ ¬A4
Ib . . . Interpretation definiert durch Ib (Ai ) = bi
Db hat den Wert 0 für Ib , und 1 für alle anderen Interpretationen.
Ib : A1 → 1, A2 → 0, A3 → 1, A4 → 1
=⇒
=: D010
=: D001
=: D000
DNFf = K111 ∨ K100 ∨ K011
valIb (Db ) = 0
KNFf = D110 ∧ D101 ∧ D010 ∧ D001 ∧ D000
Konjunktive Normalform für f : Bn → B
KNFf = { Db | f (b) = 0, b ∈ Bn } repräsentiert die Funktion f , d.h.:
valIb (KNFf ) = f (b) für alle b ∈ Bn .
=: D110
=: D101
Folgerung:
29
Was Sie heute erwartet
{not, and, or} ist funktional vollständig.
30
Normalformen
Literal: Variable oder negierte Variable, also A, ¬A, B, ¬B, . . .
Negationsnormalform (NNF)
1. Organisatorisches
Literale sowie
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
und ⊥ sind in NNF.
(F ∧ G) und (F ∨ G) sind in NNF, wenn F und G in NNF sind.
Keine Formel sonst ist in NNF.
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
NNF: (¬A ∨ ((B ∨ ¬C ) ∧ ))
Keine NNFs: ¬¬A, ¬(A ∧ B), ¬⊥
DNFf und KNFf sind Formeln in NNF.
Disjunktive Normalform (DNF)
, ⊥ sowie Disjunktionen von Konjunktion von Literalen:
((¬)A1,1 ∧ (¬)A1,2 ∧ (¬)A1,3 ∧ · · · ) ∨ ((¬)A2,1 ∧ (¬)A2,2 ∧ (¬)A2,3 ∧ · · · ) ∨ · · ·
Konjunktive Normalform (KNF)
31
, ⊥ sowie Konjunktionen von Disjunktion von Literalen:
((¬)A1,1 ∨ (¬)A1,2 ∨ (¬)A1,3 ∨ · · · ) ∧ ((¬)A2,1 ∨ (¬)A2,2 ∨ (¬)A2,3 ∨ · · · ) ∧ · · ·
32
Normalformen
Normalformen
Formeln, die gleichzeitig in DNF und KNF sind:
Weitere Normalformen:
⊥
(¬)
(¬)
Beschränkung auf andere Operatoren, etwa ↑
Andere Einschränkungen der Struktur, etwa
Konjunktion von Disjunktionen von Konjunktionen von Literalen
(ermöglicht kleinere Formeln als DNF oder KNF)
A1 ∧ (¬)A2 ∧ · · · ∧ (¬)An
A1 ∨ (¬)A2 ∨ · · · ∨ (¬)An
Normalformen für die Funktion f von vorhin
DNFf = K111 ∨ K100 ∨ K011
(A2 ∧ A3 ) ∨ (A1 ∧ ¬A2 ∧ ¬A3 )
KNFf = D110 ∧ D101 ∧ D010 ∧ D001 ∧ D000
(A1 ∨ A3 ) ∧ (¬A2 ∨ A3 ) ∧ (A2 ∨ ¬A3 )
(A1 ∨ A2 ) ∧ (¬A2 ∨ A3 ) ∧ (A2 ∨ ¬A3 )
Noch mehr Normalformen für die Funktion f von vorhin
maximale DNF, NNF
minimale DNF, NNF
maximale KNF, NNF
minimale KNF, NNF
andere minimale KNF, NNF
(A2 ↑ A3 ) ↑ (A1 ↑ ((A2 ↑ A2 ) ↑ (A3 ↑ A3 ) ↑ (A2 ↑ A2 ) ↑ (A3 ↑ A3 )))
((A1 ∧ ¬A3 ) ∨ A2 ) ∧ (¬A2 ∨ A3 )
NNF
Normalformen sind in der Regel nicht eindeutig.
Typische Problemstellung: Finde kleine oder kleinste Normalform.
33
34
Konstruktion von DNFs/KNFs – Semantische Methode
Konstruktion von DNFs/KNFs – Algebraische Methode
Gegeben: Aussagenlogische Formel F
Gesucht: Äquivalente Formel in DNF/KNF
Gegeben: Aussagenlogische Formel F
Gesucht: Äquivalente Formel in DNF/KNF
1
Stelle die zu F gehörige Funktion f als Wahrheitstafel dar.
2
Konstruiere DNFf bzw. KNFf .
A1 A2 A3 F := (A1 ⊃ (A2 ≡ A3 )) ∧ (¬A1 ⊃ (A2 ∧ A3 ))
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
0
1
2
K111
K100
K011
D110
D101
3
D010
D001
D000
DNF: F = K111 ∨ K100 ∨ K011
KNF: F = D110 ∧ D101 ∧ D010 ∧ D001 ∧ D000
4
Ersetze alle Junktoren durch ∧, ∨ und ¬.
A ↑ B = ¬A ∨ ¬B
A ↓ B = ¬A ∧ ¬B
A ⊃ B = ¬A ∨ B
A ≡ B = (¬A ∨ B) ∧ (A ∨ ¬B) = (A ∧ B) ∨ (¬A ∧ ¬B)
A ≡ B = (¬A ∨ ¬B) ∧ (A ∨ B) = (A ∧ ¬B) ∨ (¬A ∧ B)
Verschiebe Negationen nach innen, eliminiere Doppelnegationen.
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
Wende das Distributivgesetz an.
¬¬A = A
DNF: Schiebe Disjunktionen nach außen mittels
A ∧ (B ∨ C ) = (A ∧ B) ∨ (A ∧ C )
KNF: Schiebe Konjunktionen nach außen mittels
A ∨ (B ∧ C ) = (A ∨ B) ∧ (A ∨ C )
Eliminiere
A∧ =A
A∨⊥=A
35
A ⊂ B = A ∨ ¬B
und ⊥.
A∧⊥=⊥
A∨ =
A ∧ ¬A = ⊥
A ∨ ¬A =
¬ =⊥
¬⊥ =
(Äquivalenzen werden hier von links nach rechts angewendet.)
36
((A1 ↑ A2 ) ⊃ ¬A2 ) ∧ (¬A1 ⊃ (A2 ∧ ⊥))
1
2
3
4
Ersetze alle Junktoren durch ∧, ∨ und ¬:
( ( A1 ↑ A2 ) ⊃ ¬A2 ) ∧ ( ¬A1 ⊃ (A2 ∧ ⊥))
( (¬A1 ∨ ¬A2 ) ⊃ ¬A2 ) ∧ ( ¬A1 ⊃ (A2 ∧ ⊥))
(¬(¬A1 ∨ ¬A2 ) ∨ ¬A2 ) ∧ ( ¬A1 ⊃ (A2 ∧ ⊥))
(¬(¬A1 ∨ ¬A2 ) ∨ ¬A2 ) ∧ (¬¬A1 ∨ (A2 ∧ ⊥))
Verschiebe Negationen nach innen, eliminiere Doppelnegationen:
(¬(¬A1 ∨ ¬A2 ) ∨ ¬A2 ) ∧ (¬¬A1 ∨ (A2 ∧ ⊥))
((¬¬A1 ∧ ¬¬A2 ) ∨ ¬A2 ) ∧ (¬¬A1 ∨ (A2 ∧ ⊥))
( (A1 ∧
A2 ) ∨ ¬A2 ) ∧ ( A1 ∨ (A2 ∧ ⊥))
Wende das Distributivgesetz an:
DNF: ((A1 ∧ A2 ) ∨ ¬A2 ) ∧ (A1 ∨ (A2 ∧ ⊥))
(((A1 ∧ A2 ) ∨ ¬A2 ) ∧ A1 ) ∨ (((A1 ∧ A2 ) ∨ ¬A2 ) ∧ (A2 ∧ ⊥))
(((A1 ∧ A2 ) ∨ ¬A2 ) ∧ A1 ) ∨ (A1 ∧ A2 ∧ A2 ∧ ⊥) ∨ (¬A2 ∧ A2 ∧ ⊥)
(A1 ∧ A2 ∧ A1 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ A2 ∧ ⊥) ∨ (¬A2 ∧ A2 ∧ ⊥)
(A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ ⊥) ∨ (¬A2 ∧ A2 ∧ ⊥) (Idemp.)
KNF: ((A1 ∧ A2 ) ∨ ¬A2 ) ∧ (A1 ∨ (A2 ∧ ⊥))
(A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ (A1 ∨ (A2 ∧ ⊥))
37
(A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ (A1 ∨ A2 ) ∧ (A1 ∨ ⊥)
Welche Methode ist besser?
Vereinfache mit den Regeln für
und ⊥:
DNF: (A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ ⊥) ∨ (¬A2 ∧ A2 ∧ ⊥)
(A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ ⊥) ∨ ⊥
(A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ ⊥)
(A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ ⊥
(A1 ∧ A2 ) ∨ (¬A2 ∧ A1 )
DNF erreicht!
A1 ∧ (A2 ∨ ¬A2 )
(Distributivgesetz, keine DNF mehr)
A1 ∧
A1
(wieder DNF)
KNF: (A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ (A1 ∨ A2 ) ∧ (A1 ∨ ⊥)
(A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ (A1 ∨ A2 ) ∧ A1
KNF erreicht!
(A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ A1
(Absorption)
(A1 ∨ ¬A2 ) ∧ ∧ A1
(keine KNF mehr!)
(A1 ∨ ¬A2 ) ∧ A1
(wieder KNF)
A1
(Absorption)
38
Was Sie heute erwartet
Gefühlsmäßig: Die semantische Methode ist übersichtlicher.
Theoretisch: Beide Methoden sind schlecht, denn beide sind im
schlechtesten Fall exponentiell:
1. Organisatorisches
Semantische Methode: Aufwand immer exponentiell in Variablenzahl!
Wahrheitstafel besitzt 2Variablenzahl Zeilen.
Algebraische Methode: Schritt 3 (Distributivgesetz) ist aufwändig,
kann zu einer exponentiellen Verlängerung der Formel führen.
Praktisch:
Semantische Methode nur brauchbar bei Formeln mit sehr wenigen
Variablen. Immer exponentiell in Variablenzahl, liefert immer die
maximale DNF/KNF.
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Algebraische Methode teilweise auch für große Formeln brauchbar,
insbesondere mit Computerunterstützung. Kann auch kleine
DNFs/KNFs liefern.
39
40
Das Erfüllbarkeitsproblem der Aussagenlogik
Methoden zur Lösung von SAT
Erfüllbarkeitsproblem (Satisfiability, SAT)
Wahrheitstafel:
Berechne den Formelwert der Reihe nach für jede Interpretation.
Antwort „ja“, sobald man den Wert 1 erhält; „nein“, wenn immer 0.
Unbrauchbar, da exponentiell: 2Variablenzahl Interpretationen!
Gegeben: aussagenlogische Formel F
Frage: Ist F erfüllbar, d.h., gibt es ein I ∈ I, sodass valI (F ) = 1?
Effiziente Verfahren zur Lösung von SAT sind wichtig in der Praxis:
Viele praktische Aufgaben lassen sich als Probleme der Aussagenlogik
formulieren, wie z.B.
Verifikation von Hard- und Software
Planungsaufgaben, Logistik-Probleme
Die meisten aussagenlogischen Fragen lassen sich zu einem
(Un)Erfüllbarkeitsproblem umformulieren:
G gültig ⇐⇒ ¬G unerfüllbar
G widerlegbar
G =H
F1 , . . . , Fn |= G
⇐⇒
¬G erfüllbar
⇐⇒
F1 ∧ · · · ∧ Fn ∧ ¬G unerfüllbar
⇐⇒
G ≡ H unerfüllbar
41
USD 1.000.000,– Prämie für einen effizienten SAT-Solver
Umwandlung in DNF:
Wandle F in eine disjunktive Normalform um.
Antwort „nein“, wenn man ⊥ erhält; „ja“ sonst.
Unbrauchbar: F meistens in Fast-KNF. Distributivgesetz verlängert F
exponentiell.
SAT-Solver: Programme, die SAT lösen.
Verwenden fortgeschrittene algebraische/graphorienierte/logische
Methoden mit besonderen Datenstrukturen.
Können SAT für Formeln mit Millionen von Variablen lösen.
Stand der Technik bei der Verifikation von Prozessoren etc.
Aber: Exponentielle Laufzeit für manche Formelarten!
P versus NP
Gilt P = NP oder P = NP (gleichbedeutend mit P
. . . oder für den Beweis, dass es diesen nicht geben kann.
Abzuholen beim Clay Mathematics Institute (www.claymath.org)
für das offene Milleniumsproblem „P versus NP“.
42
NP)?
SAT ist in NP: Gegeben I, lässt sich valI (F ) = 1 leicht überprüfen.
Die Suche nach so einem I scheint aber aufwändig (exponentiell?).
Weiters warten ewiger Ruhm, eine ProfessorInnenstelle, . . .
P: Klasse der Probleme, deren Lösungen sich effizient (polynomiell) finden
lassen.
NP: Klasse jener Probleme, deren Lösungen sich effizient (polynomiell)
verifizieren lassen; die Suche nach der Lösung kann aber aufwändig sein.
SAT ist NP-vollständig: SAT gehört zu den schwierigsten Problemen in NP.
Kann man ein NP-vollständiges Problem effizient lösen, dann kann man
alle Probleme in NP effizient lösen.
SAT polynomiell lösbar =⇒ P = NP
SAT prinzipiell nicht polynomiell lösbar =⇒ P = NP
HAMILTON-KREIS ist in NP
Gegeben: Eine Gruppe Studierender, einige davon vertragen sich nicht.
Frage: Gibt es eine Sitzordnung für einen runden Tisch, sodass sich
Sitznachbarn vertragen?
Wenn alle sitzen, ist die Bedingung leicht zu überprüfen.
Das Finden einer geeigneten Sitzordnung erweist sich als schwierig.
43
44
Falls Ihnen SAT nicht gefällt . . .
Meinungsumfrage unter Experten (W.I.Gasarch, 2002)
Wann wird das Problem P = NP gelöst werden?
?
12
13
10
5
5
12
10
5
bis 2070
18%
61%
k.A.
1
7
5
Unmögliche Stellung
5
„2“, aber 5 Bomben in der Umgebung
„6“, aber nur drei mögliche Bomben
0
„1“, aber keine Bombe in der Umgebung
MINESWEEPER polynomiell lösbar =⇒ P = NP
20
0
2–
20
09
20
10
–2
01
9
20
20
–2
02
9
20
30
–2
03
9
20
40
–2
04
9
20
50
–2
05
9
20
60
–2
06
9
20
70
–2
07
9
20
80
–2
08
9
20
90
–2
09
9
21
00
–2
19
9
22
00
–3
00
0
0
Gegeben: eine Minesweeper-Stellung
Frage: Ist die Stellung zulässig/möglich?
nach 2060
21%
4
MINESWEEPER
ni
e
Anzahl
Wie wird die Antwort lauten?
P = NP
61%
weder-noch
4% P = NP
9%
MINESWEEPER prinzipiell nicht polynomiell lösbar =⇒ P = NP
26%
k.A.
45
Was Sie heute erwartet
46
Obst, Schachteln und Aufschriften
1
Auf dem Tisch stehen drei Schachteln.
2
Jede Schachtel enthält Äpfel, Bananen oder Orangen.
1. Organisatorisches
3
Keine zwei Schachteln enthalten dasselbe Obst.
2. Was bedeutet Modellierung?
3. Aussagenlogik
4
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Jede Schachtel trägt die Aufschrift „Äpfel“, „Bananen“ oder
„Orangen“.
5
Keine zwei Schachteln tragen dieselbe Aufschrift.
6
In keiner Schachtel ist drin, was drauf steht.
7
Sie öffnen die Schachtel mit der Aufschrift „Orangen“ und finden
darin Äpfel.
Welches Obst verbirgt sich hinter den anderen Aufschriften?
47
48
Obst, Schachteln und Aufschriften – Modellierung
1
2
Obst, Schachteln und Aufschriften – Modellierung (2)
Auf dem Tisch stehen drei Schachteln: A, B, C
Jede Schachtel enthält Äpfel (a), Bananen (b) oder Orangen (o).
Xy . . . „Schachtel X enthält das Obst y .“, z.B.:
Bo . . . „Schachtel B enthält Orangen.“
5
F5 :=
(SAa ⊃ (¬SBa∧¬SCa)) ∧ (SAb ⊃ (¬SBb∧¬SCb)) ∧ (SAo ⊃ (¬SBo∧¬SCo)) ∧
(SBa ⊃ (¬SAa∧¬SCa)) ∧ (SBb ⊃ (¬SAb∧¬SCb)) ∧ (SBo ⊃ (¬SAo∧¬SCo)) ∧
(SCa ⊃ (¬SAa∧¬SBa)) ∧ (SCb ⊃ (¬SAb∧¬SBb)) ∧ (SCo ⊃ (¬SAo∧¬SBo))
F2 := (Aa ∨ Ab ∨ Ao) ∧ (Ba ∨ Bb ∨ Bo) ∧ (C a ∨ C b ∨ C o)
3
6
Keine zwei Schachteln enthalten dasselbe Obst.
Jede Schachtel trägt die Aufschrift „Äpfel“, „Bananen“ oder
„Orangen“.
SXy . . . „Schild auf Schachtel X hat Aufschrift y .“, z.B.:
SBo . . . „Schachtel B trägt die Aufschrift ‚Orangen‘.“
F4 := (SAa ∨ SAb ∨ SAo) ∧ (SBa ∨ SBb ∨ SBo) ∧ (SCa ∨ SCb ∨ SCo)
In keiner Schachtel ist drin, was drauf steht.
F6 := (SAa ⊃ ¬Aa) ∧ (SAb ⊃ ¬Ab) ∧ (SAo ⊃ ¬Ao) ∧
(SBa ⊃ ¬Ba) ∧ (SBb ⊃ ¬Bb) ∧ (SBo ⊃ ¬Bo) ∧
(SCa ⊃ ¬C a) ∧ (SCb ⊃ ¬C b) ∧ (SCo ⊃ ¬C o)
F3 := (Aa ⊃ (¬Ba ∧ ¬C a)) ∧ (Ab ⊃ (¬Bb ∧ ¬C b)) ∧ (Ao ⊃ (¬Bo ∧ ¬C o)) ∧
(Ba ⊃ (¬Aa ∧ ¬C a)) ∧ (Bb ⊃ (¬Ab ∧ ¬C b)) ∧ (Bo ⊃ (¬Ao ∧ ¬C o)) ∧
(C a ⊃ (¬Aa ∧ ¬Ba)) ∧ (C b ⊃ (¬Ab ∧ ¬Bb)) ∧ (C o ⊃ (¬Ao ∧ ¬Bo))
4
Keine zwei Schachteln tragen dieselbe Aufschrift.
7
Die Schachtel mit der Aufschrift „Orangen“ enthält Äpfel.
F7 := (SAo ⊃ Aa) ∧ (SBo ⊃ Ba) ∧ (SCo ⊃ C a)
50
49
Das Geheimnis der verschwundenen Äpfel
Das Geheimnis der verschwundenen Äpfel (2)
Welches Obst verbirgt sich hinter den anderen Aufschriften?
Modellierungsproblem:
A, B und C sind unsere internen Namen für die Schachteln.
1. Versuch: Enthält Schachtel A die Äpfel?
„Computer says no.“
F2 , F3 , F4 , F5 , F6 , F7 |= Aa
Solange wir nicht festlegen, wie die Schachteln beschriftet sind,
können die Äpfel überall sein.
?
Antwort „Nein“ bedeutet, dass die Äpfel nicht zwingend in der
jeweiligen Schachtel sind.
( c BBC, „Little Britain“)
2. Versuch: Enthält Schachtel B die Äpfel?
„Computer says no.“
F2 , F3 , F4 , F5 , F6 , F7 |= Ba
Weitere Annahme:
?
8
F8 := SAa ∧ SBb ∧ SCo
3. Versuch: Enthält Schachtel C die Äpfel?
„Computer says no.“
F2 , F3 , F4 , F5 , F6 , F7 |= C a
Wo sind die Äpfel geblieben?
A ist mit „Äpfel“, B mit „Bananen“ und C mit „Orangen“ beschriftet.
Nun erhalten wir:
?
F2 , F3 , F4 , F5 , F6 , F7 , F8 |= Ab
F2 , F3 , F4 , F5 , F6 , F7 , F8 |= Bo
51
Schachtel „Äpfel“ enthält Bananen, Schachtel „Bananen“ Orangen.
52
Obst, Schachteln und Aufschriften – Modellierung (3)
Obst, Schachteln und Aufschriften – Modellierung (4)
Vereinfachung: Nütze die eindeutige Beziehung zwischen Schachteln und
Aufschriften (F8 ) bereits bei der Modellierung.
F2 , F3 , F4 , F5 , F6 , F7 , F8
18 Variablen
Xy . . . „Schachtel mit Aufschrift X enthält das Obst y .“
A = „Äpfel“, B = „Bananen“, C = „Orangen“
Jede Schachtel trägt eine Aufschrift.
überflüssig
5
Keine zwei Schachteln tragen dieselbe Aufschrift.
überflüssig
6
In keiner Schachtel ist drin, was drauf steht.
KNF mit 25 Konjunkten
Direkte Formalisierung der
Angabe
Erfordert ein wenig
Nachdenken
Die erste Modellierungung sollte die Problembeschreibung möglichst
direkt wiedergeben. Keine Optimierung!
Weniger Variablen können ein Vorteil sein (vor allem, wenn es viel
weniger sind), müssen aber nicht.
F6 := ¬Aa ∧ ¬Bb ∧ ¬C o
In der Schachtel mit der Aufschrift „Orangen“ befinden sich Äpfel.
Kleinere/Weniger Formeln können ein Vorteil sein (vor allem, wenn sie
viel kleiner/viel weniger sind), müssen aber nicht.
F7 := C a
Damit erhalten wir:
9 Variablen
KNF mit 57 Konjunkten
4
7
F2 , F3 , F6 , F7
Eine für SAT-Solver optimierte Modellierung erfordert Erfahrung und
Kenntnis der angewendeten Methode. Ist nicht das Ziel dieser
Lehrveranstaltung!
F2 , F3 , F6 , F7 |= Ab ∧ Bo
54
53
Was Sie heute erwartet
Dualität von Funktionen, Operatoren und Formeln
Beobachtung 1: „and“ und „or“ verhalten sich spiegelbildlich bzgl. 0 und 1.
x
1
1
0
0
1. Organisatorisches
2. Was bedeutet Modellierung?
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
y x and y
1
1
0
0
1
0
0
0
x or y
1
1
1
0
x
0
0
1
1
y x or y
0
0
1
1
0
1
1
1
x and y
0
0
0
1
„and“ ist eine Konjunktion für 1 und eine Disjunktion für 0.
„or“ ist eine Konjunktion für 0 und eine Disjunktion für 1.
Beobachtung 2: Boolesche Algebra ist symmetrisch bzgl. ∧/∨ und
55
(A ∧ B) ∧ C = A ∧ (B ∧ C )
A∧B =B∧A
A∧A=A
A∧ =A
A ∧ ¬A = ⊥
A ∧ (A ∨ B) = A
A ∧ (B ∨ C ) = (A ∧ B) ∨ (A ∧ C )
/⊥.
(A ∨ B) ∨ C = A ∨ (B ∨ C )
A∨B =B∨A
A∨A=A
A∨⊥=A
A ∨ ¬A =
A ∨ (A ∧ B) = A
A ∨ (B ∧ C ) = (A ∨ B) ∧ (A ∨ C )
56
Duale Funktionen
G[A1 , . . . , An ] . . . „Formel G enthält die Variablen A1 , . . . , An “
G[H1 , . . . , Hn ] . . . Formel, die aus G[A1 , . . . , An ] entsteht,
wenn Ai überall durch Hi ersetzt wird.
Anmerkung: Diese Bedingung ist gleichbedeutend mit jeder der folgenden:
Duale Formeln
Zwei n-stellige Funktionen f und g heißen dual zueinander, wenn gilt:
not f (x1 , . . . , xn ) = g(not x1 , . . . , not xn ).
not f (not x1 , . . . , not xn ) = g(x1 , . . . , xn )
f (x1 , . . . , xn ) = not g(not x1 , . . . , not xn )
f (not x1 , . . . , not xn ) = not g(x1 , . . . , xn )
¬F [¬A1 , . . . , ¬An ] ist dual zu F [A1 , . . . , An ].
„and“ und „or“ sind dual, da not(x and y ) = (not x ) or (not y ).
¬((¬A ∨ ¬¬B) ⊃ ¬A) ist dual zu (A ∨ ¬B) ⊃ A.
Duale Operatoren
Sei G die Formel, die aus F durch Ersetzen aller Operatoren durch ihre
dualen hervorgeht. Dann ist G dual zu F .
Zwei Operatoren heißen dual, wenn die zugehörigen Funktionen dual sind.
true /
not / ¬
false / ⊥
not / ¬
and / ∧
nand / ↑
iff / ≡
ist dual zu
or / ∨
nor / ↓ xor / ≡
(und umgekehrt).
implies / ⊃
if / ⊂
—/⊂
—/⊃
¬(((A ∧ B) ≡ ¬(B ↑ C )) ⊃ ((A ∧ ) ∨ B)) ist dual zu
¬(((A ∨ B) ≡ ¬(B ↓ C )) ⊂ ((A ∨ ⊥) ∧ B))
57
F ∗ , G ∗ . . . irgendwelche dualen Formeln zu F bzw. G
F = G gilt genau dann, wenn F ∗ = G ∗ gilt.
F =G
(A ∧ B) ∧ C = A ∧ (B ∧ C )
A∧B =B∧A
A∧A=A
A∧ =A
A ∧ ¬A = ⊥
A ∧ (A ∨ B) = A
A ∧ (B ∨ C ) = (A ∧ B) ∨ (A ∧ C )
F ∗ = G∗
(A ∨ B) ∨ C = A ∨ (B ∨ C )
A∨B =B∨A
A∨A=A
A∨⊥=A
A ∨ ¬A =
A ∨ (A ∧ B) = A
A ∨ (B ∧ C ) = (A ∨ B) ∧ (A ∨ C )
(F ∗ )∗ = F
F ist gültig genau dann, wenn F ∗ unerfüllbar ist.
F ⊃ G ist gültig genau dann, wenn G ∗ ⊃ F ∗ gültig ist.
...
Dualität ist nicht dasselbe wie Negation!
Zwei Formeln F [A1 , . . . , An ] und G[A1 , . . . , An ] heißen dual zueinander,
wenn gilt: ¬F [A1 , . . . , An ] = G[¬A1 , . . . , ¬An ]
59
58
Document
Kategorie
Gesundheitswesen
Seitenansichten
40
Dateigröße
758 KB
Tags
1/--Seiten
melden