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