Transcript
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
