1
MoBi Mathematik A
1. Mathematische Logik
Carl Herrmann
Health Data Science Unit - BioQuant and Medical Faculty Heidelberg
October 7, 2019
2
1.1 Einführung
3
Logische Aussagen
Logische Aussagen bilden den Grundstein der Logik.
Beispiele von logischen Aussagen:
I 3 > 2
I 2 > 5
I ”es ist kalt”
I A ⊂ BFolgende Beispiele sind KEINE logischen Aussagen:
I ”Gib mir das Buch!”
I ”wo bin ich?”
Definition/Zuweisung:
A :⇐⇒ ”es ist kalt”
4
Eigenschaften von Aussagen
1. Aussagen sind wahr oder falsch.
2. Zwei Aussagen sind äquivalent, wenn sie den gleichen
Wahrheitsgehalt haben (Überprüfung über
Wahrheitstabellen, siehe später!)
Schreibweise der Äquivalenz: A ⇐⇒ BI ”A ist äquivalent zu B”I ”A dann und nur dann wenn B”I ”A if and only if B”
3. man kann Aussagen verneinen ¬A4. man kann Aussagen verknüpfenn anhand von Junktoren
I und: A ∧ BI oder: A ∨ BI Kontravalenz A∨̇B (”entweder oder aber nicht beides”)
5
Wahrheitstabellen
Man kann den Wahrheitsgehalt einer Aussage über eine
Wahrheitstabelle bestimmen
A B A ∨ B A ∧ B A∨̇B ¬A ¬B A ⇐⇒ Bw w w w f f f w
w f w f w f w f
f w w f w w f f
f f f f f w w w
Satz von Morgan:
¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B
6
Implikationen
A⇒ B : ”wenn A, dann folgt B”
A B A⇒ Bw w w
w f f
f w w
f f w
Schwer, intuitiv zu verstehen, da zwischen A und B nicht
notwendigerweise ein logischer Zusammenhang besteht:
I ”Wenn Schweine fliegen können, dann werde ich 100 Jahrealt”: Implikation ist wahr (siehe Tabelle)
I ”Wenn der Mond hell leuchtet, dann besteht er aus Käse”:Implikation ist falsch
7
Implikationen
A⇒ B:I A ist eine hinreichende Bedingung für B
I B ist eine notwendige Bedingung für A
Beispiel:
I ”Wenn ein Tier ein Primate ist, dann ist es ein Wirbeltier”:P ⇒WI Wirbeltier notwendige Bedingung: wenn ein Tier kein
Wirbeltier ist, dann kann es kein Primate sein (notwendig!)I Primate hinreichende Bedingung: wenn ein Tier ein Primate
ist, dann ist es auch notwendigerweise ein Wirbeltier!
8
Implikationen
Es gilt:
(A ⇐⇒ B) ⇐⇒ (A⇒ B) ∧ (B ⇒ A)
A B A ⇐⇒ B A⇒ B B ⇒ A (A⇒ B) ∧ (B ⇒ A)w w
w f
f w
f f
9
Aussageformen
I Aussageformen sind ”Aussagen mit Variablen”I Beispiel:
I A(x , y) :⇐⇒ ”Person x ist mit Person y verheiratet”I C (n) :⇐⇒ ”Zahl n durch 2 teilbar
x , y , n sind Variablen, die unterschiedliche Werte inbestimmten Mengen annehmen können.I n ∈ N : natürliche ZahlenI x , y ∈ P : Menge der Personen im Heiratsalter
I Achtung! Aussageformen sind weder richtig noch falsch!I Aussageformen werden zu Aussagen, wenn die Variablen
bestimmte Werte annehmenI C (5) ist eine Aussage, die falsch istI C (4) ist eine Aussage, die wahr ist
10
Quantoren
I Quantoren sind Operatoren, mit denen man ausAussageformen Aussagen bilden kann
I Übliche Quantoren:I ∀ : ”für jedes”
(Beispiel: ∀x ∈ R : x2 ≥ 0I ∃ : ”es gibt”
Beispiel: ∀x ∈ R∗,∃y ∈ R : xy = 5I ∃! : ”es gibt ein einziges”
Beispiel: ∀x ∈ R∗,∃!y ∈ R : xy = 1I @ : ”es gibt kein”
Beispiel: @x ∈ R : x · 0 = 1
11
Aussageformen und Mengen
I Man kann anhand von Aussageformen Mengen definierenI A = {n ∈ N : C (n)} : alle natürlichen Zahlen, die durch 2
teilbar sindI B = {n ∈ Z : C (n)} : alle ganze Zahlen, die durch 2 teilbar
sindI V = {x ∈ P : ∃y ∈ P : A(x , y)} : alle verheirateten Personen
I V in Worte: ”Menge aller Personen x , sodass es eine Person ygibt, sodass x und y verheiratet sind.”
I das Doppelzeichen ”:” in der Klammer bedeutet”...sodass...”oder ”...das die Bedingung erfüllt”
12
Verneinung von Aussagen mit Quantoren
I BeispielI A :⇐⇒ ”es gibt ein Tier x , das ein Wirbeltier ist”I ¬A :⇐⇒ ”für jedes Tier x gilt: es ist kein Wirbeltier”
I hier ist A wahr und ¬A falsch!I mit Quantoren:
I A :⇐⇒ ∃x ∈ T : W (x)(wobei T die Menge aller Tiere ist, und W (x) die Aussageform”x ist ein Wirbeltier”)
I ¬A :⇐⇒ ∀x ∈ T : ¬W (x)I Also gilt: die Verneinung einer Aussage mit ”es gibt” führt zu
einer Aussage mit ”für alle”
13
Verneinung von Aussagen mit Quantoren
I BeispielI A :⇐⇒ ”für alle Primaten x gilt: x ist ein Wirbeltier”I ¬A :⇐⇒ ”es gibt einen Primaten x für das gilt: x ist kein
Wirbeltier”
I hier ist A wahr und ¬A falsch!I mit Quantoren:
I A :⇐⇒ ∀x ∈ P : W (x)(wobei P die Menge aller Primaten ist, und W (x) dieAussageform ”x ist ein Wirbeltier”)
I ¬A :⇐⇒ ∃x ∈ P : ¬W (x)I Also gilt: die Verneinung einer Aussage mit ”für alle... führt
zu einer Aussage mit ”es gibt...”
14
1.2 Wahre Aussagen und Beweise
15
Wahre/falsche Aussagen
Woher weiß man, ob eine Aussage wahr oder falsch ist?
I falsche Aussagen: ein Gegenbeispiel genügt, um sie zuwiderlegen!
I Beispiel: ∀x ∈ T : W (x)Falsch, denn Gegenbeispiel: x = Fliege!
16
Wahre Aussagen
Verschiedene Arten von wahren Aussagen in der Mathematik
I Axiom : wahr per DefinitionI Geometrie: ”Zu jeder Geraden und jedem Punkt, das nicht auf
der Geraden liegt gibt es genau eine andere Gerade durch
diesen Punkt, die parallel zur ersten verläuft”I Arithmetik ”Jede natürliche Zahl hat genau einen Nachfolger”
Axiome sind Grundsätze einer Theorie (Beispiel: euklidische
Geometrie)
I Lemma / Satz / Theorem: müssen bewiesen werden!I arithmetischer Grundsatz: ”Jede natürliche Zahl kann durch
ein Produkt von Primzahlen dargestellt werden”
17
Wahre Aussagen
I Vermutungen: sind (noch) nicht bewiesen!I Fermat Vermutung: ”die Gleichung an + bn = cn hat für n > 2
keine lösung mit a, b, c positive natürliche Zahlen”I im 17. Jahrhundert von Pierre Fermat formuliert, 1994 von
Andrew Wiles bewiesen (also keine Vermutung mehr, sondern
Satz!)I 4-Farben Vermutung: ”Jede Karte kann mit 4 Farben bemalt
werden, sodass keine zwei benachbarten Länder die gleiche
Farbe haben”I 1852 formuliert, 2005 durch Aufzählung aller 633 möglichen
Fälle bewiesen.
I es gibt noch eine Reihe ungelöster Vermutungen:https://www.claymath.org/millennium-problems
18
Beweise
Es gibt verschiedene Arten von Beweisen:
direkter Beweis: leitet den Satz aus anderen bekannten wahren
Aussagen her
I Beispiel: Primate?⇒ Wirbeltier
I Beweis: bekannt sei : (a) Primate ⇒ Säugetier und (b)Säugetier ⇒ Wirbeltier. Aus (a) und (b) und der Eigenschaftder Transitivität der Implikation folgt:
Primate ⇒ WirbeltierDas Symbol steht für ”quod erat demonstrandum”(”dies war
zu beweisen”) und steht am Ende eines Beweises.
19
Beweise
Kontraposition
I beruht auf der Eigenschaft A⇒ B ⇐⇒ ¬B ⇒ ¬A (kannüber eine Wahrheitstabelle überprüft werden!)
I Beispiel: Beweis von r irrational ⇒√r irrational
I man beweist stattdessen:√r rational ⇒ r rational
I Beweis:
20
Beweise
indirekter Beweis
I man verneint die Behauptung
I man versucht, einen Widerspruch zu zeigen
I das bedeutet, dass die Verneinung falsch sein muss, also istdie ursprüngliche Aussage wahr!
I Beispiel:√
2 ist irrational
I Beweis:
21
Beweise
vollständige Induktion: wird verwendet, um Aussagen zu
natürlichen Zahlen ∀n ∈ N : A(n) zu beweisen.I besteht aus 2 Schritten
1. Induktionsanfang: man zeigt, dass A(0) wahr ist (oder A(1)
wenn n ∈ N∗)2. Induktionsschritt: man zeigt, dass A(n)⇒ A(n + 1) (also wenn
A(n) gilt, dann gilt auch A(n + 1))
I Beispiel: A(n) :⇐⇒∑n
i=1 i =12n(n + 1)
22
Vertändnisfragen
1. Versuchen Sie die Kontravalenz anhand der
Junktoren/Negation auszudrücken!
2. Finden Sie Beispiele von notwendigen und hinreichenden
Bedingungen!
3. Zeigen Sie, dass A⇒ B ⇐⇒ ¬B ⇒ ¬A