k - Bernd Baumgarten

h_da – Hochschule Darmstadt
FB Informatik
Winter 2016/17
Logik (nicht nur) für Informatiker
Dr. Bernd Baumgarten
[email protected]
http://bernd-baumgarten.de/
Folien, Skript, PVL, Aufgaben, Lösungen
: Schubladen-Bild, Kaffee-Lemma, Sportschau-Gleichnis
Arbeitsmoral-Mantra:
ISBN 978-3936973204
Aufschieb-Problem:
Später ist meist noch weniger Zeit.
 2016 Bernd Baumgarten
Mathematische Werkzeuge
2
Was ist und was nützt Logik?
 2016 Bernd Baumgarten
Mathematische Werkzeuge
3
Was ist und was nützt Logik?
Logik ist die Wissenschaft von den
• Regeln,
• Methoden und
• Grenzen
des Schlussfolgerns.
Anwendung: beim ...
•
•
•
•
Argumentieren,
Folgern,
Beweisen,
Widerlegen,
Anwendungsweisen:
• produktiv oder
• nachprüfend
 2016 Bernd Baumgarten
• Berechnen,
• Entwerfen,
• Prüfen.
Mathematische Werkzeuge
4
Übersicht über die Vorlesung
Themen
• Mathematische Werkzeuge
• Aussagenlogik (AL)
• andere Logiken (hier nur auf AL-Basis),
teilweise selbstständig zu erarbeiten
• Prädikatenlogik (PL)
Aspekte
• Grundlagen,
• Algorithmen,
• Anwendungen.
 2016 Bernd Baumgarten
Mathematische Werkzeuge
5
Mathematische Werkzeuge
• Mengen, Relationen, Funktionen
• Induktion und Rekursion
• Sprachen und Grammatiken
• Graphen und Bäume
 2016 Bernd Baumgarten
Mathematische Werkzeuge
6
Metasprachliche Symbole
(Objekt-)Sprache: Hallo, wie geht’s?
A → ¬A
Metasprache:
A → ¬A ist immer falsch
„Hallo“ hat 6 Buchstaben.
Die Vermischung von Meta- und Objektsprache ist – zusammen mit zyklischen
Definitionen – die Hauptquelle von Paradoxien (z.B. „Neunzehn Buchstaben
sind zwanzig Buchstaben.“ – „Dieser Satz ist gelogen.“)
⇔
genau dann, wenn
⇒
wenn, dann
Die Sonne geht unter. ⇔ Die Nacht beginnt.
Die Erde ist eine Scheibe. ⇒ Ich fresse einen Besen.
:⇔
ist dadurch definiert, dass
Die Spielerin hat ihr Skatspiel gewonnen.
: ⇔ Sie hat mehr als 60 Punkte in ihren Stichen erzielt.
:=
ist definiert als
 2016 Bernd Baumgarten
max(a,b) := wenn a > b dann a, sonst b.
Mathematische Werkzeuge
7
Mengen (1)
Eine Menge ist eine „Zusammenfassung M von
bestimmten wohlunterschiedenen Objekten m
unserer Anschauung oder unseres Denkens
(welche die ‚Elemente‘ von M genannt werden)
zu einem Ganzen.“
Georg Cantor 1895
a ∈ A :⇔
a ist Element von A
a ∉ A :⇔
a ist kein Element von A
{a, b, c } :=
Menge mit den Elementen a, b und c (= {c, a, b} = {a, a, b, c } )
{ } , ∅ :=
{a1, a2 , a3 , ...} :=
{a, b, c, ... , z} :=
{x | P ( x )} :=
 2016 Bernd Baumgarten
leere Menge
Menge mit den Elementen a1, a 2 und a3 „usw.“
Menge mit den Elementen a, b und c „usw. bis“ z
Menge aller Objekte mit der Eigenschaft P
(Existenz durch Komprehensionsaxiom garantiert)
Mathematische Werkzeuge
8
Mengen (2)
Z
Z
Wichtige Mengen:
IN
natürliche Zahlen ohne 0 = { 1, 2, 3, ...}
IN0
natürliche Zahlen mit 0 = { 0, 1, 2, ...}
Achtung: Manche Autoren (z.B. DIN 5473) verwenden IN = { 0, 1, 2, ...} !
IR
reelle Zahlen
ganze Zahlen
I
Q
rationale Zahlen
A = B ⇔ Für alle x gilt: x ∈ A ⇔ x ∈ B .
A ⊆ B :⇔ Für alle x ∈ A gilt x ∈ B .
P( A) := {M | M ⊆ A} (auch 2 A )
A ∩ B := {x | x ∈ A und x ∈ B}
A ∪ B := {x | x ∈ A oder x ∈ B}
A \ B := {x | x ∈ A und x ∉ B
 2016 Bernd Baumgarten
}
Extensionalitätsaxiom
Teilmenge
Potenzmenge
Durchschnittsmenge
Vereinigungsmenge
Mengendifferenz
Mathematische Werkzeuge
9
Mengen (3)
A1× ... × An bzw. ∏ ni=1 Ai := {(a1, ..., an ) | ai ∈ Ai für i = 1,..., n} (kartesisches) Produkt
U mit: Für alle x gilt x ∈ U .
A
Allmenge
Komplement
:= U \ A
Ü1
Die Naive Mengenlehre ist widersprüchlich (s.u.) – aber ganz brauchbar.
Komprehensionsaxiom auf P(x):⇔ x ∉ x anwenden:
Sei N := {x | P ( x )}. Dann ist N ∈ N ⇔ P (N ) ⇔ N ∉ N .
Def. N
(Bertrand Russell 1903)
Def. P
Trotzdem:
Aus dem Paradies, das uns Cantor geschaffen,
soll uns niemand vertreiben können.
David Hilbert 1926
Und wie?
 2016 Bernd Baumgarten
Axiomatische Mengenlehre (zumindest theoretisch)
Mathematische Werkzeuge
10
Relationen (1)
R ⊆ A1 × ... × An (n-stellige) Relation R zwischen Mengen A1, ... , An , n ∈ IN 0
R(a1, ..., an ) :⇔ (Schreibweise für …)
(a1, ..., a n ) ∈ R
aRb :⇔ (Schreibweise für …)
R(a,b)
Ein R ⊆ A × A , also eine zweistellige Relation R auf einer Menge A ist …
symmetrisch
antisymmetrisch
transitiv
reflexiv
 2016 Bernd Baumgarten
:⇔ für alle a, b ∈ A gilt: aRb ⇒ bRa;
:⇔ für alle a, b ∈ A gilt: aRb und bRa ⇒ a=b;
:⇔ für alle a, b, c ∈ A gilt: (aRb und bRc) ⇒ aRc;
:⇔ für alle a ∈ A gilt: aRa.
Mathematische Werkzeuge
11
Relationen (2)
Eine zweistellige Relation R auf einer Menge ist …
Äquivalenzrelation
:⇔ R symmetrisch, transitiv und reflexiv
(entspricht Partition)
Äquivalenzklassen
≤
Halbordnung
:⇔ R antisymmetrisch, transitiv und reflexiv
Sei R ⊆ A1 × A2 zweistellige Relation ...
R linkstotal
A1
R rechtseindeutig
 2016 Bernd Baumgarten
A2
A1
:⇔ für jedes a ∈ A1 existiert ein b ∈ A2 mit aRb
A2
:⇔ für alle a ∈ A1, b1, b2 ∈ A2 gilt:
aR b1 und aR b2 ⇒ b1 = b2
Mathematische Werkzeuge
12
Funktionen (1)
f (totale) Funktion oder Abbildung von A in B, kurz
f : A → B :⇔
f ⊆ A × B , f linkstotal und rechtseindeutig
B A :=
(Eine partielle Funktion / Abbildung ist ...
Menge aller Abbildungen von A in B
nicht unbedingt linkstotal.)
Totale Funktionen sind spezielle partielle Funktionen!
Deff := {a ∈ A | es ex. b ∈ B : (a, b ) ∈ f } Definitionsbereich partielles f : A → B
Bei totalem f : A → B : Deff := A .
)
f [M ], M ⊆ A1 := {f ( x ) | x ∈ M } = {b ∈ B | es ex. a ∈ A : (a, b ) ∈ f }
Funktionsbeschreibung (total), Beispiel:
 2016 Bernd Baumgarten
Z
Z
Ü3
Bildmenge

f: 
 x
→ IN0
a x2
Ü2
Mathematische Werkzeuge
13
Funktionen (2)
Für f : A → B , g : B → C ist ...
g o f : A → C := die Abbildung mit g o f (a ) := g (f (a )), die
Hintereinanderausführung von f und g
f injektiv :⇔
f linkseindeutig, für alle a, b ∈ A gilt: f (a ) = f (b ) ⇒ a = b ,
f surjektiv :⇔
f rechtstotal, bzw. f [ A] = B , für alle b ∈ B existiert ein a ∈ A mit f (a ) = b
f bijektiv :⇔
f sowohl injektiv als auch surjektiv
Ü4
A → A
id A : 
x a x
identische Abbildung
f −1 : B → A :=
Umkehrabbildung zu bijektivem f : A → B
f −1( b ) := a :⇔ f(a) = b ⇒ f −1 o f = id A , f o f −1 = id B
 2016 Bernd Baumgarten
Mathematische Werkzeuge
14
Sprachen
Alphabet: A = { a1,K, a n }, auch unendlich möglich (z.B. zweistufige Sprachen)
a i ∈ A (auch „Symbol“)
Zeichen:
Wort:
w ∈ A∗ , A∗ = {( z1,K, zk ) k ∈ IN 0 , ∀1 ≤ i ≤ k : zi ∈ A },
meist ohne Komma und Klammern geschrieben als z1 K zk
eine Menge von Wörtern, L ⊆ A ∗
Sprache (über A):
leeres Wort:
ε (=( z1,K, z k ) mit k = 0)
Verkettung:
u o v := „uv“ (hintereinandergeschrieben)
a k := a … a (k-mal)■
Wiederholung:
Kleene-Stern: *
Spezialfälle
L Sprache
“null-1, ein- oder mehrmals”
L* := { w1 … w n | n ∈ IN0 , ∀1 ≤ i ≤ n: w i ∈ L } ■
w Wort
a Zeichen
w* := {w}*
a* := {a}* (= {a k | k = 0,1,... } ■
) a 0 := ε (weil kein a), und w1 … w 0 := ε (weil kein Wort)
■
 2016 Bernd Baumgarten
Mathematische Werkzeuge
15
Induktion (1)
Induktion dient ...
• zur Definition
• zum Beweis von Eigenschaften P
aller Elemente
gewisser unendlicher Mengen
Definitionsbeispiel:
Neandertaler-Zahlen NZ
1. | ist eine NZ.
2. Ist n eine NZ, dann auch n | (Nachfolger von n, succ ( n ), " n + 1" ).
3. Jede NZ entsteht durch endlich häufige Anwendung
der Regeln (1) und (2).
 2016 Bernd Baumgarten
Mathematische Werkzeuge
16
Induktion (2)
Neandertaler-Zahlen NZ ...
Heutige Schreibweise | = 1, || = 2, ..., |||||||||| = 10, usw.
natürliche Zahlen, IN
Ferner: kein Strich = 0;
1 ist Nachfolger von 0;
Wozu braucht man Regel (3)?
• Auch { |, O }* erfüllt die Regeln (1)+(2) !
Wir wollen aber nur nach Regeln (1) und (2) Gebildetes zulassen!
• Unendlichfache Anwendung der Regel (2)
|||... (unendliche Folge)?
Wir wollen aber nur endlich häufige Anwendung!
Regel (3) gehört stillschweigend zu „induktiv“.
 2016 Bernd Baumgarten
IN0
Mathematische Werkzeuge
17
Induktive Mengendefinition
Induktive Definition bestimmter Teilmengen einer Menge U
Seien M 0 ⊆ U , f k : U mk → U (k = 1,2, ..., evtl. partiell)
Dann existiert eine kleinste Teilmenge M von U mit den Eigenschaften
1. M 0 ⊆ M
Basiselemente
2. f k [M mk ] ⊆ M
Durchschnitt aller ...
Erweiterungsregeln
Beispiele
Arithmetische Terme, Minibeispiel:
(1) a,b sind (ab+ ⋅)-Terme.
(2) x,y (ab+ ⋅)-Terme ⇒ (x+y) und (x⋅y) (ab+ ⋅)-Terme – z.B. ((a+(b+a))⋅b)
Neandertalerzahlen als Strichlisten:
(1) | ist natürliche Zahl
(2) n natürliche Zahl ⇒ n| ist natürliche Zahl
[Was sind hier jeweils die U, M0 , fk ?]
Ü5
 2016 Bernd Baumgarten
Mathematische Werkzeuge
18
Induktiver Beweis
Induktionsprinzip (für induktive Beweise) auf induktiv definiertem M:
Gilt Eigenschaft P
(1) „auf M 0 “ (d.h. für alle Elemente von M 0 ) und
(2) wenn auf { x1, ..., x mk } , dann auch für f k ( x1, ..., x mk ) (sofern def.),
so gilt P auf ganz M.
… weil jedes Element
• entweder „von vornherein“ die Eigenschaft P hat (da es aus M 0 ist)
• oder von seinen „Bausteinen“ aus der vorigen „Generation“ bei seiner
Entstehung die Eigenschaft P „erbt“.
Ü6a
 2016 Bernd Baumgarten
Mathematische Werkzeuge
19
Rekursive Definition von Funktionen – Idee
... auf induktiv definiertem M:
f1
G1
F
M
V
f2
G2
Man baut quasi das Bild parallel mit den Aufbauschritten des Urbilds auf.
 2016 Bernd Baumgarten
Mathematische Werkzeuge
20
Rekursive Definition von Funktionen (1)
... auf induktiv definiertem M:
Seien
• ein Wertebereich V und
• für jede Erweiterungsregel k ein Gk : V mk → V
gegeben.
Dann definiert man durch
• F ( x ) ∈ V für alle x ∈ M 0 festlegen.
– Basisfälle
• F (fk ( x1, ..., x m k )) := Gk (F ( x1 ), ..., F ( x m k ))
– Rekursion
(rekursiv) eine Abbildung F : M → V ,
Geht das immer gut?
 2016 Bernd Baumgarten
Mathematische Werkzeuge
21
Rekursive Definition von Funktionen (2)
... auf induktiv definiertem M:
Seien
• ein Wertebereich V und
• für jede Erweiterungsregel k ein Gk : V mk → V
gegeben.
Dann definiert man durch
• F ( x ) ∈ V für alle x ∈ M 0 festlegen.
– Basisfälle
• F (fk ( x1, ..., x m k )) := Gk (F ( x1 ), ..., F ( x m k ))
– Rekursion
(rekursiv) eine Abbildung F : M → V ,
Aber das geht nur dann sicher gut, wenn ...
interferenzfrei,
ambivalenzfrei,
eindeutig parsebar
• jedes Element von M eine „eindeutige Entstehungsgeschichte“ hat,
• oder ein Beweis der Wohldefiniertheit gelingt.
 2016 Bernd Baumgarten
Mathematische Werkzeuge
22
Entstehungsgeschichten
Eindeutige Entstehungsgeschichte – Beispiel ☺
Neandertaler-Zahlen NZ
(A) | ist NZ.
(B) n ist NZ ⇒ n| ist NZ-Z.
Eindeutige Entstehungsgeschichte – Gegenbeispiel
Australopithecus-Zahlen:
(A) | ist APZ.
(B) n APZ ⇒ n| APZ.
(C) n APZ ⇒ |n APZ.
|| hat 2 Entstehungsgeschichten:
 2016 Bernd Baumgarten
Mathematische Werkzeuge
23
Entstehungsgeschichten sind Bäume
z.B. (ab+ ⋅)-Terme, gebildet aus
• 2 Basisfällen: ‚a’ und ‚b’
• 2 Erweiterungsregeln: ‚+’-Regel und ‚•’-Regel
Beispiel:
( (a + b) • (b • a) )
•
•
(a + b)
(b • a)
+
•
a
 2016 Bernd Baumgarten
b
b
oder kurz:
a
a
•
+
b
b
a
Mathematische Werkzeuge
24
Rekursive Definition von Funktionen (3)
Wie kann rekursive Abbildungsdefinition
bei Australopithecus-Zahlen schiefgehen?
Gegenbeispiel zur Wohldefiniertheit:
Links(|) := 0;
Links(n|) := Links(n);
Links(|n) := Links(n)+1;
nicht wohldefiniert, d.h. führt zu widersprüchlichen Zuweisungen:
0 = Links(||) = 1 ??
keine eindeutige Entstehungsgeschichte …
… aber wohldefiniert auf Australopithecus-Zahlen
LorR(|) := 0;
LorR(n|) := LorR(n) +1;
LorR(|n) := LorR(n)+1;
Übung: Beweis der Wohldefiniertheit
 2016 Bernd Baumgarten
Mathematische Werkzeuge
25
Rekursive Definition von Eigenschaften
Eigenschaft = Spezialfall von Abbildung, nämlich
{W,F} !
Beispiel: Eigenschaft Gerade auf Neandertalerzahlen
Gerade(|)
Gerade(n|)
:= F
:= Wenn Gerade(n)=W, dann F, sonst W
= ¬ Gerade(n)
Ü6bc
 2016 Bernd Baumgarten
Mathematische Werkzeuge
26
Grammatiken
Eine Grammatik ist ein Quadrupel G = ( N, T, S, R) mit
•
•
•
•
einem Alphabet N von Nichtterminalzeichen,
einem Alphabet T von Terminalzeichen, N ∩T = ∅ ,
einen Startzeichen S ∈ N,
einer endlichen Menge R ⊆ (N ∪ T )∗ × (N ∪ T )∗ von Regeln.
Schreibweisen (v,w) ∈ R:
(v,w),(v,w') ∈ R:
v→w
v → w | w'.
G definiert („erzeugt“) eine Sprache von Terminalzeichenwörtern,
L(G) := H(G) ∩ T*,
wobei die Hilfssprache H(G) ⊆ (N ∪ T)* induktiv gegeben ist durch
• S∈H(G)
• r v s ∈ H(G) ∧ v → w ⇒ r w s ∈ H(G).
Ü7
 2016 Bernd Baumgarten
Mathematische Werkzeuge
27
Graphen (1)
Gerichteter Graph :=
zweistellige Relation über einer Menge
(i.a. graphisch dargestellt).
a
b
c
e
d
entspricht {(a,b), (b,c), (c,a), (b,d), (c,c), (d,b)}
über {a,b,c,d,e}.
a, b, ..., e
(a,b), (b,c), usw.
 2016 Bernd Baumgarten
sind Knoten (mit angeben! Sonst e unbekannt.)
sind Kanten.
Mathematische Werkzeuge
28
Graphen (2)
Ungerichteter Graph
Paar-&Single(!)mengenmenge
(bzw. symmetrische Relation)
über einer Menge (mit angeben! Sonst e unklar.)
a
b
c
e
d
entspricht
{ {a,b}, {b,c}, {c,a}, {c}, {b,d} }
bzw. { (a,b), (b,a), (a,c), (c,a), (b,c), (c,b), (b,d), (d,b), (c,c) } .
über {a,b,c,d,e}
 2016 Bernd Baumgarten
Mathematische Werkzeuge
29
Bäume
zahlreiche Definitionsmöglichkeiten
Baum
Kinder haben
Reihenfolge?
geordnet / ungeordnet
endlich / unendlich viele Knoten
endlich verzweigt / nicht
…
…
als spezielle ungerichtete/gerichtete Graphen,
spezielle Halbordnungen usw.
a
b
e
c d
f
 2016 Bernd Baumgarten
Kinderzahl
a ist die Wurzel
b, c, d sind Kinder von a (Grad von a ist 3)
c, d, e, f sind die Blätter
a – b – e ist ein Zweig (Pfad Wurzel–Blatt)
Ast(b)
Ü8
Mathematische Werkzeuge
30
Königs Lemma
Welche dieser 3 Bäume mit
unendlich vielen Knoten
sind als Gegenbeispiel für
welche Hypothese geeignet?
•
•
•
•
•
•
/\
/\
/\
/|\
/|\
| \
\
Pfade sind immer endlich lang.
Jeder Baum mit unendlich vielen Knoten hat einen unendlichen Pfad.
Jeder Baum mit unendlich vielen Knoten hat endliche Pfade „beliebiger Länge.“
Sind in einem Baum alle Pfade endlich so ex. eine maximale Pfadlänge.
Sind in einem Baum alle Pfade endlich so hat er endlich viele Knoten.
Sind in einem Baum die Grade beschränkt, hat er endlich viel Knoten.
Jeder Baum mit unendlich vielen
Knoten allesamt endlichen Grades
besitzt einen unendlichen Pfad.
Dénes Kőnig (1936)
Gilt auch wenn die Grade unbeschränkt sind!
Beweisidee
5
∞
usw.
 2016 Bernd Baumgarten
19
Knotenzahl
des Astes
Mathematische Werkzeuge
31
Anwendungen von Königs Lemma
A. Ein Solitaire-Spiel
Voraussetzung:
Du bist unsterblich.
Material:
Du hast einen Kartenvorrat, der zu jeder natürlichen Zahl n beliebig viele
Karten enthält, auf denen „n“ steht (bzw. sie sind grenzenlos lieferbar).
Spielablauf:
1. Nimm eine Karte „n“ nach Wunsch aus dem Vorrat.
2. Wiederhole, solange möglich:
Lege eine Deiner Karten, „m“, ab und ersetze sie aus dem Vorrat durch
beliebig aber endlich viele Karten mit (evtl. unterschiedlichen) „k“, k<m.
Ziel:
Spiele unendlich lange (d.h. unendlich oft Spielzug 2)!
Geht das?
B. Anwendung in der Logik
 2016 Bernd Baumgarten
König’s Lemma ⇒ nein!
Kompaktheitssätze (
später)
Mathematische Werkzeuge
32
Beschriftete Graphen und Bäume (1)
In gewöhnlichen Graphen und Bäumen gibt es jeden Knotennamen nur
einmal, der Name identifiziert den Knoten.
In knotenbeschrifteten Graphen und Bäumen
sieht man nur die Knotenanschriften,
die sich auch wiederholen dürfen.
Die Namen werden meist ignoriert, so wie hier
a
b
d
a
d
Mathematisch: + Abbildung Knotenmenge → Anschriftenmenge
+
Anwendung:
Syntaxbäume (geordnet) von Termen
Beispiel: ((1+(a+1))+b)
(vgl. Entstehungsgeschichten bei Induktion)
 2016 Bernd Baumgarten
b
+
+
1
a
1
Mathematische Werkzeuge
33
Beschriftete Graphen und Bäume (2)
Es gibt auch kantenbeschriftete
sowie gleichzeitig knoten- und
kantenbeschriftete Graphen und
Bäume.
a
1
1
a
b
2
3
1
d
d
3
Mathematisch: + Abbildung Kantenmenge → Anschriftenmenge
Spezialfall:
Automaten (deterministisch/nicht-deterministisch)
Mathematisch: kantenbeschrifteter Graph
+ spezielle Eigenschaft der Kantenbeschriftung (falls determ.)
+ ausgezeichnete(r) Anfangsknoten
+ ausgezeichnet Menge akzeptierender Knoten
Theoretische Informatik: Anwendung auf formale Sprachen
 2016 Bernd Baumgarten

Download Report