Post on 15-Nov-2019
transcript
Induktives Beweisen
6. Induktives Beweisen - Themenubersicht
Ordnungsrelationen
Partielle OrdnungenQuasiordnungenTotale OrdnungenStriktordnungenOrdnungen und Teilstrukturen
Noethersche Induktion
Anwendung: Terminierungsbeweise
Verallgemeinerte Induktion
Anwendung: Fibonacci-Funktion
Strukturelle Induktion
Anwendung: Boolesche Terme
Vollstandige Induktion
Anwendung: Gesetze naturlicher ZahlenProf. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 144 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Definition 6.1 (5.1)
Eine homogene Relation � ⊆ A× A heisst partielle Ordnung oder auchHalbordnung, gdw.
1 � ist reflexiv: ∀ a ∈ A. a � a
2 � ist antisymmetrisch: ∀ a1, a2 ∈ A. a1 � a2 ∧ a2 � a1 ⇒ a1 = a2
3 � ist transitiv: ∀ a1, a2, a3 ∈ A. a1 � a2 ∧ a2 � a3 ⇒ a1 � a3
Beispiele
⊆ auf P(M) fur beliebige Grundmenge M.
Teilbarkeitsbeziehung | auf N.
Teilzeichenreihenbeziehung auf A∗ definiert durch:
w ′ v w ⇔df ∃w1,w2 ∈ A∗. w1 w ′ w2 = w .
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 145 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Definition 6.2 (Ordnung auf N) (5.2)
Fur n,m ∈ N definiere wir eine Relation ≤ durchn ≤ m ⇔df ∃ k ∈ N. n + k = m.
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
→ Spater: ≤ ist total.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 146 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
Beweis (Reflexivitat): Sei n ∈ N. Fur k = 0 gilt dann n + 0 = 0 + n = n,also auch n ≤ n.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 147 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
Beweis (Antisymmetrie (1/3)): Seien m, n ∈ N mit n ≤ m und m ≤ n.Dann existieren Zahlen k1, k2 ∈ N mit :
n + k1 = m
m + k2 = n
Setzt man m aus der ersten Gleichung in die Zweite ein, erhalt man(n + k1) + k2 = n. Wegen der Assoziativitat und Kommutativitat derAddition folgt (k1 + k2) + n = n.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 148 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
Beweis (Antisymmetrie (2/3)): Gemaß der Definition der Additionnaturlicher Zahlen (siehe Definition 4.2(a)) folgt daraus
(k1 + k2) + n = 0 + n
und weiterk1 + k2 = 0
Es bleibt noch nachzuweisen, dass die bereits k1 = 0 impliziert.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 149 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
Beweis (Antisymmetrie (3/3)): Angenommen k1 ware von 0 verschieden.Dann gabe es nach Lemma 4.1 eine naturliche Zahl k ′1 mit k ′1 = s(k1) unddamit wegen der Definition der Addition naturlicher Zahlen auch mit:
k1 + k2 = s(k ′1) + k2Def.4.2.(a)
= s(k ′1 + k2).
Also ware k1 + k2 ein Nachfolger einer naturlichen Zahl und damit von 0verschieden, im Widerspruch zu k1 + k2 = 0.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 150 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Partielle Ordnungen
Satz 6.3 (5.1)
≤ ist eine partielle Ordnung auf N.
Beweis (Transitivitat: Seien n,m, p ∈ N mit n ≤ m und m ≤ p. Dannexistieren Zahlen k1, k2 ∈ N mit:
n + k1 = m
m + k2 = p
Setzt man m aus der ersten Gleichung in die Zweite ein, so erhalt man(n + k1) + k2 = p. Mit der Assoziativitat der Addition folgt
n + (k1 + k2) = p
und damit n ≤ p.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 151 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Quasiordnungen
Definition 6.1
Eine homogene Relation - ⊆ A× A heisst Quasiordnung oder auchPraordnung, gdw.
1 - ist reflexiv: ∀ a ∈ A. a - a
2 - ist transitiv: ∀ a1, a2, a3 ∈ A. a1 - a2 ∧ a2 - a3 ⇒ a1 - a3
Beispiel
“Kleiner oder gleich groß”-Beziehung auf Menge von Personen.
Teilbarkeitsbeziehung | auf Z (Beachte −1|1 und 1| − 1).
Implikation “⇒” auf Booleschen Termen.
“Weniger machtig”-Beziehung ≤ auf Mengensystemen.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 152 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Quasiordnungen
Beobachtung
Quasiordnung - ⊆ A× A induziert Aquivalenzrelation auf A durch:
a1 ∼ a2 ⇔df a1 - a2 ∧ a2 - a1.
Man spricht hier auch vom Kern der Quasiordnung.
- bildet partielle Ordnung auf A/ ∼.
Beispiel
Implikation “⇒” auf Booleschen Termen ist Quasiordnung.
Kern von “⇒” ist die semantische Aquivalenz auf Booleschen Termen.
Implikation auf Klassen semantisch aquivalenter Boolescher Terme istpartielle Ordnung.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 153 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Totale Ordnungsrelationen
Definition
Eine Quasiordnung - ⊆ A× A, in der alle Elemente vergleichbar sind,heißt totale Quasiordnung oder auch Praferenzordnung, d.h.
∀ a1, a2 ∈ A. a1 - a2 ∨ a2 - a1
Beispiel
“Weniger machtig”-Beziehung ≤ auf Mengensystemen.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 154 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Totale Ordnungsrelationen
Definition
Eine partielle Ordnung � ⊆ A× A, in der alle Elemente vergleichbar sind,heißt totale Ordnung oder auch lineare Ordnung, d.h.
∀ a1, a2 ∈ A. a1 � a2 ∨ a2 � a1
Beispiel
≤ auf N.
Lexikographische Ordnung auf A*.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 155 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Striktordnungen
Beobachtung
Zu einer gegebenen Quasiordnung - lasst sich die zughorige Striktordnung≺ definieren durch:
a1 ≺ a2 ⇔df a1 - a2 ∧ a1 6∼ a2 .
Lemma 6.4 (5.1)
1 ≺ ist asymmetrisch, d.h.: ∀ a1, a2 ∈ A. a1 ≺ a2 ⇒ a2 6≺ a1
2 ≺ ist transitiv, d.h.: ∀ a1, a2, a3 ∈ A. a1 ≺ a2 ∧ a2 ≺ a3 ⇒ a1 ≺ a3
Folgerung: ≺ ist irreflexiv, d.h.: ∀ a ∈ A. a 6≺ a
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 156 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Striktordnungen
Beobachtung
Zu einer gegebenen Striktordnung ≺ lasst sich die zughorige partielleOrdnung definieren durch:
a1 � a2 ⇔df a1 ≺ a2 ∨ a1 = a2 .
Definition
Reduziert man eine Striktordnung auf die unmittelbar benachbartenAbhangigkeiten erhalt man die Nachbarschaftsordnung ≺N definiert durch:
a1 ≺N a2 ⇔df a1 ≺ a2 ∧ @ a3 ∈ A. a1 ≺ a3 ≺ a2 .
Graphische Darstellung von ≺N als Hasse-Diagramm bekannt.
Es gilt: ≺∗N=�
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 157 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Teilbarkeitsordnungen
Teilbarkeitsordnungen auf {1, 2, 3, 4, 6, 12} als (a) Partielle Ordnung (b)Striktordnung (c) Nachbarschaftsordnung
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 158 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Hasse-Diagramme
Hasse Diagramme zu (a) ≤ auf N, (b) ⊆ auf P({1, 2, 3}), (c) | auf{1, . . . , 12}.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 159 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Extremalelemente
Definition 6.5 (Minimale, maximale Elemente) (5.3)
Sei � ⊆ A× A partielle Ordnung und B ⊆ A. Ein Element b ∈ B heißt
1 minimales Element in B ⇔df @ b′ ∈ B. b′ ≺ b und
2 maximales Element in B ⇔df @ b′ ∈ B. b ≺ b′.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 160 / 182
Induktives Beweisen 6.1 Ordnungsrelationen
Extremalelemente
Definition 6.7 (Kleinstes, großtes Element) (5.4)
Sei � ⊆ A× A partielle Ordnung und B ⊆ A. Ein Element b ∈ B heißt
1 kleinstes Element in B ⇔df ∀ b′ ∈ B. b � b′ und
2 großtes Element in B ⇔df ∀ b′ ∈ B. b′ � b.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 161 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Noethersche Ordnungen
Definition 6.9 (5.5)
Eine Quasiordnung - ⊆ A×A heißt Noethersch genau dann, wenn jedenichtleere Teilmenge von M ein minimales Element besitzt.
Satz 5.2 (Absteigende Kettenbedingung)
Eine Quasiordnung (M,�) ist genau dann Noethersch, wenn es in M keineunendliche, echt absteigende Kette x0 � x1 � x2 . . . gibt.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 162 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Noethersche Ordnungen
Satz 5.2 (Absteigende Kettenbedingung)
Eine Quasiordnung (M,�) ist genau dann Noethersch, wenn es in M keineunendliche, echt absteigende Kette x0 � x1 � x2 . . . gibt.
Beweis “⇒”: Sei x0 � x1 � x2 . . . eine unendliche, echt absteigende Kettein M. Dann ist A =df {x0, x1, x2 . . . } nichleer. Angenommen nun es gabeein minimales Element amin ∈ A. Dann existierte ein Index i mit xi = amin.Wegen xi � xi+1 ware xi aber im Widerspruch zur Annahme nicht minimal.Folglich gibt es kein minimales Element in A und M ist nicht Noethersch.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 163 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Noethersche Ordnungen
Beispiel 6.10 (5.3)
1 ≤ auf N ist Noethersch, denn jede nichtleere Teilmenge enthalt sogarein kleinstes Element.
2 Die Teilzeichenreichenbeziehung v auf A∗ ist Noethersch.
3 ⊆ ist Noethersch auf P(M) fur jede endliche Grundmenge M.
Beispiel 6.11 (Nicht Noethersche Ordnungen) (5.4)
1 ≤ auf Z ist nicht Noethersch, denn Z besitzt kein minimales Element.
2 ≤ auf Q≥0 ist nicht Noethersch, denn {12 ,
13 ,
14 , . . .} besitzt kein
minimales Element.
3 ⊆ auf P(N) ist nicht Noethersch, denn{N, N\{0}, N\{0, 1}, N\{0, 1, 2}, . . .} besitzt kein minimalesElement.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 164 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Noethersche Induktion
Beweisprinzip 6.12 (Noethersche Induktion)(7)
Sei - ⊆ M×M eine Noethersche Quasiordnung. Lasst sich eine AussageA uber M fur jedes m ∈ M aus der Gultigkeit der Aussage fur alle echtkleineren Elemente ableiten, dann ist sie fur jedes m ∈ M wahr.
(∀m ∈ M.
(∀m′ ∈ M. m′ ≺ m ⇒ A(m′)
)⇒ A(m)
)⇒ ∀m ∈ M. A(m).
Beweis: Per Kontraposition.Falls ∀m ∈ M. A(m) nicht gilt, existiert nichtleere Menge G ⊆ M vonGegenbeispielen.
G =df {g ∈ M | ¬A(g)}.
Weil - Noethersch ist, existiert ein minimales Gegenbeipiel gmin ∈ G .gmin verletzt dann den Induktionsschluss.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 165 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Anwendung: Kommutativitat der Addition
Satz 6.19(2)
∀ n,m ∈ N. n + m = m + n.
Beweis durch Noethersche Induktion uber komponentenweise Ordnung aufN× N.
(n,m) ≤ (n′,m′) ⇔df n ≤ n′ ∧ m ≤ m′.
Details: Skript.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 166 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Anwendung: Terminierung
Euklidischer Algorithmus
ggt : N× N→ N
ggt(n,m) =
n + m falls n = 0 oder m = 0ggt(n −m,m) falls m < nggt(n,m − n) falls n < m
Terminierung: Noethersche Quasiordnung auf N× N:
(n,m) .sum (n′,m′) ⇔df n + m ≤ n′ + m′.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 167 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Anwendung: Terminierung
Ackermann-Funktion
ack : N× N→ N
ack(n,m) =
m + 1 falls n = 0ack(n − 1, 1) falls n > 0, m = 0ack(n − 1, ack(n,m − 1)) falls n > 0, m > 0
Terminierung: Lexikographische Ordnung (Noethersch und total) aufN× N:
(n,m) ≤lex (n′,m′) ⇔df n < n′ ∨ (n = n′ ∧ m ≤ m′).
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 168 / 182
Induktives Beweisen 6.2 Noethersche Induktion
Anwendung: Terminierung
Collatz-Funktion
col : N\{0} → {1}
col(n) =
1 falls n = 1col(n/2) falls n geradecol(3n + 1) falls n ungerade
Terminierung: Keine geeignete Noethersche Ordnung bekannt.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 169 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Beweisprinzip Verallgemeinerte Induktion
Beweisprinzip 6.13 (Verallgemeinerte Induktion)(8)
Lasst sich eine Aussage uber naturliche Zahlen fur jede naturliche Zahl ausder Gultigkeit der Aussage fur alle kleineren naturlichen Zahlen ableiten,dann ist sie fur jede naturliche Zahl wahr.(∀ n ∈ N. (∀m ∈ N. m < n ⇒ A(m)) ⇒ A(n)
)⇒ ∀ n ∈ N. A(n).
Spezialfall der Noetherschen Induktion
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 170 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Anwendung Fibonacci-Zahlen
Definition 6.14 (5.6)
fib(0) =df 0fib(0) =df 1fib(n + 1) =df fib(n) + fib(n − 1)
Es gilt: ∀ n ∈ N. fib(n) < 2n.
Beweis:
n = 0. Dann fib(0)Def.= 0 < 1 = 20.
n = 1. Dann fib(1)Def.= 1 < 2 = 21.
n ≥ 2. Dann gilt:
fib(n)Def.
= fib(n − 2) + fib(n − 1)IA< 2n−2 + 2n−1
≤ 2n−1 + 2n−1 = 2 · 2n−1 = 2n.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 171 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Strukturelle Induktion
Erinnerung: Induktiv strukturierte Mengen (Folie 119)
Definition 4.4
1 A eine Menge elementarer oder atomarer Bausteine und
2 O eine Menge von Operatoren (oder Konstruktoren) mit zugehorigenStelligkeiten k ≥ 1, die es erlauben, kleinere Bausteine zu grosserenEinheiten zusammenzusetzen.
Die durch A und O induktiv beschriebene Menge M ist die kleinsteMenge, fur die gilt:
1 A ⊆ M und
2 Ist o ein Operator der Stelligkeit k und sind m1, . . . ,mk ∈ M, so istauch o(m1, . . . ,mk) ∈ M.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 172 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Strukturelle Induktion
Gegeben:
Induktiv strukturierte Menge M mit Atomen A und Konstruktoren O
Eigenschaft A uber M.
Ziel: Beweise, dass A(m) gilt fur alle Elemente m ∈ M.
Vorgehen:1 Man beweist, dass A fur jedes Atom a ∈ A gilt.
2 Man beweist fur jeden Konstruktor o ∈ O, dass unter derVoraussetzung, dass A fur beliebige m1, . . . ,mk ∈ M gilt, A auchfur o(m1, . . . ,mk) gilt.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 173 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Strukturelle Induktion
Beweisprinzip 6.15 (Strukturelle Induktion) (9)
Sei M induktiv strukturierte Menge (mit Atomen A, Konstruktoren O).Lasst sich eine Aussage A uber M fur jedes Atom a ∈ A beweisen, undlasst sich fur jeden Konstruktor o ∈ O aus der Gultigkeit der Aussage furm1, . . . ,mk ∈ M die Gultigkeit fur o(m1, . . . ,mk) ableiten, dann ist A furjedes m ∈ M wahr.((∀ a ∈ A. A(a)
)∧(∀ o ∈ O,m1, . . . ,mk ∈ M.(A(m1) ∧ · · · ∧ A(mk)
)⇒ A
(o(m1, . . . ,mk)
)))⇒ ∀m ∈ M. A(m)
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 174 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Strukturelle Induktion
.. als Spezialfall Noetherscher Induktion.
Nachbarschaftsordnung ≺N durch induktive “Bauanleitung” derStrukturen:
m1 ≺N m2 ⇔df ∃ o ∈ O. m2 = o(m′1, . . . ,m′k) ∧m1 ∈ {m′1, . . . ,m′k}.
“Ist-Teilstruktur”-Relation � als reflexiv-transitive Hulle von ≺N , d.h:� = ≺∗N .
Klar: � ist Noethersch.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 175 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Anwendung: Aussagenlogik
Satz 6.16 (Funktionale Vollstandigkeit von ¬und∧) (5.3)
Wir betrachten aussagenlogische Formeln (Definition 2.5, Folie 37),aufgefasst als induktiv beschriebene Menge aus den Atomen a, b, c , . . .(elementare Aussagen) sowie dem einstelligen Konstruktor ¬ und denzweistelligen Konstruktoren ∧,∨,⇒,⇔.
Zu jeder aussagenlogischen Formel φ existiert eine semantisch aquivalenteFormel φ′, so dass φ′ lediglich die Junktoren ¬ und ∧ enthalt.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 176 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Anwendung: Aussagenlogik
Beweis: (Strukturelle Induktion)
Uber den induktiven Aufbau von φ:
Fall 1: φ = a. Trivial, denn φ enthalt keine Junktoren.
Fall 2: φ = ¬ψ. Nach der Induktionsannahme (IA) existiert Formelψ′ ≡ ψ, so dass ψ′ nur ¬ und ∧ enthalt. Dies gilt dann auchfur φ′ = ¬ψ′, und es gilt φ′ ≡ φ.
Fall 3: φ = ψ1 ∧ ψ2. Dann existieren nach der IA ψ′1 ≡ ψ1, ψ′2 ≡ ψ2
mit der gewunschten Eigenschaft, und φ′ = ψ′1 ∧ ψ′2 ≡ φenthalt ebenfalls nur ¬ und ∧.
Fall 4: φ = ψ1 ∨ ψ2. Dann existieren nach der IA ψ′1 ≡ ψ1, ψ′2 ≡ ψ2
mit der gewunschten Eigenschaft, undφ′ = ¬(¬ψ′1 ∧ ¬ψ′2) ≡ φ enthalt ebenfalls nur ¬ und ∧.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 177 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Anwendung: Aussagenlogik
Beweis: (Strukturelle Induktion)
Uber den induktiven Aufbau von φ:
Fall 5: φ = ψ1 ⇒ ψ2. Dann existieren nach der IA ψ′1 ≡ ψ1,ψ′2 ≡ ψ2 mit der gewunschten Eigenschaft, undφ′ = ¬(ψ′1 ∧ ¬ψ′2) ≡ φa enthalt ebenfalls nur ¬ und ∧.
Fall 6: φ = ψ1 ⇔ ψ2. Dann existieren nach der IA ψ′1 ≡ ψ1,ψ′2 ≡ ψ2 mit der gewunschten Eigenschaft, undφ′ = ¬(¬(ψ′1 ∧ ψ′2) ∧ ¬(¬ψ′1 ∧ ¬ψ′2)) ≡ φb enthalt ebenfallsnur ¬ und ∧.
aAufgrund der Aquivalenz A ⇒ B ≡ ¬A∨B und der deMorganschen Regeln.bAufgrund der Aquivalenz A ⇔ B ≡ (A ∧ B) ∨ (¬A ∧ ¬B) und der
deMorganschen Regeln.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 178 / 182
Induktives Beweisen 6.4 Verallgemeinerte Induktion
Anwendung: Boolesche Terme
Satz 6.13 (Kompositionalitat von [[ · ]]B)(Kap. 5.7.2, 5.7.3)
Seien t, t ′, t ′′ ∈ BT mit t ′ ≡ t ′′. Dann gilt
t[t ′/x ] ≡ t[t ′′/x ],
dass heißt man darf (simultan) Gleiches durch (semantisch) Gleichesersetzen.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 179 / 182
Induktives Beweisen 6.3 Vollstandige Induktion
Beweisprinzip: Vollstandige Induktion
Beweisprinzip 6.18 (Vollstandige Induktion)(10)
Ist eine Aussage A uber naturliche Zahlen fur 0 wahr und lasst sich ihreGultigkeit fur jede großere naturliche Zahl aus der Gultigkeit der Aussagefur ihren Vorganger ableiten, dann ist sie fur jede naturliche Zahl wahr.(
A(0) ∧ ∀ n ∈ N. A(n) ⇒ A(n + 1))⇒ ∀ n ∈ N. A(n).
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 180 / 182
Induktives Beweisen 6.3 Vollstandige Induktion
Vollstandige Induktion
Satz 6.15 (5.4)
Seien n,m, k ∈ N. Dann gilt:
Assoziativitat:1) (n + m) + k = n + (m + k)2) (n ·m) · k = n · (m · k)
Kommutativitat:1) n + m = m + n2) n ·m = m · n
Neutrale Elemente:1) n + 0 = n2) n · 1 = n
Distributivitat:(n + m) · k = n · k + m · k
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 181 / 182
Induktives Beweisen 6.3 Vollstandige Induktion
Beispiele
Beispiel 6.16 (5.5)
Fur alle n ∈ N gilt:
1 Es gibt 2n Teilmengen von n–elementigen Mengen.
2n∑
i=1i = n∗(n+1)
2 , Summe der ersten n naturlichen Zahlen.
3n∑
i=1(2i − 1) = n2, Summe der ersten n ungeraden Zahlen.
Prof. Dr. Bernhard Steffen Mathematik fur Informatiker 1 - 2013 182 / 182