Logik f¨ur Informatiker 1. Grundlegende Beweisstrategiensofronie/logik-ss-2012/slides/... · Logik f¨ur Informatiker 1. Grundlegende Beweisstrategien Viorica Sofronie-Stokkermans

Logik fur Informatiker

1. Grundlegende Beweisstrategien

Viorica Sofronie-Stokkermans

Universitat Koblenz-Landau

e-mail: [email protected]

1

Mathematisches Beweisen

Mathematische Aussagen

- haben oft die Form: Wenn A, dann B.

- als Formel: A → B

Mathematischer Beweis

- bzgl. eines vorgegebenen Axiomensystems

- mit Hilfe von Inferenzregeln

2

Grundlegende Beweisstrategien

Mathematische Aussagen der Form A → B (Wenn A, dann B)

- Direkter Beweis:

Annahme: A gilt. Benutze A, Axiome, und Inferenzregeln

um B zu beweisen.

3



- Direkter Beweis:


um B zu beweisen.

Behauptung: Das Quadrat einer ungeraden naturlichen Zahl n ist stets ungerade.

n ungerade → n2 ungerade.

4



- Direkter Beweis:


um B zu beweisen.

Behauptung: Das Quadrat einer ungeraden naturlichen Zahl n ist stets ungerade.

Beweis: Es sei n eine ungerade naturliche Zahl. Dann lasst sich n darstellen als

n = 2k + 1, wobei k eine naturliche Zahl oder Null ist. Daraus folgt mit Hilfe der

ersten binomischen Formel

n2 = (2k + 1)2 = 4k

2 + 4k + 1 = 2 · (2k2 + 2k) + 1.

Aus der Moglichkeit, n2 so darzustellen folgt, dass n2 ungerade ist.

5



- Beweis durch Kontraposition:

Beweis von ¬B → ¬A.

- Beweis durch Widerspruch:

Beweise dass A ∧ ¬B → falsch

6







Behauptung: Ist die Wurzel aus einer geraden naturlichen Zahl n eine naturliche

Zahl, so ist diese gerade.

n gerade und√

n = k ∈ N → k gerade

Beweis durch Kontraposition: Zu zeigen:√n = k ∈ N und k ungerade → n ungerade.

7







Behauptung: Ist die Wurzel aus einer geraden naturlichen Zahl n eine naturliche

Zahl, so ist diese gerade.

Beweis: Angenommen,√

n = k ware ungerade. Dann ist wegen der bereits be-

wiesenen Behauptung auch k2 = n ungerade, und das ist ein Widerspruch zu der

Voraussetzung, dass n gerade ist.

Also ist die getroffene Annahme falsch, d.h.,√

n ist gerade.

8


Mathematische Aussagen, die nicht die Form A → B haben

- Aquivalenzbeweis (A ⇔ B) (A genau dann, wenn B)

Beweise dass A → B und dass B → A.

(Wenn A, dann B, und wenn B, dann A.)

9


- Beweis durch Fallunterscheidung

Um B zu beweisen, beweise dass A1 → B, . . . ,An → B,

wobei A1 ∨ · · · ∨ An ≡ wahr

10





Behauptung: Jede Primzahl p≥3 hat die Form p = 4·k±1 mit einer naturlichen Zahl k.

Beweis: Man unterscheidet folgende vier Falle fur die Zahl p, von denen immer genau

einer eintritt:

1. p = 4k2. p = 4k + 13. p = 4k + 24. p = 4k + 3 = 4(k + 1) − 1

Im ersten dieser Falle ist p durch 4 teilbar und damit keine Primzahl, im dritten Fall ist p

durch 2 teilbar und somit ebenfalls keine Primzahl.

Also muss einer der Falle zwei oder vier eintreten, das heißt p hat die Form p = 4 · k ± 1

mit einer naturlichen Zahl k.

11





Es sei angemerkt, dass die Fallunterscheidung zwar vollstandig sein

muss, aber die untersuchten Falle sich nicht gegenseitig ausschließen

mussen.

12


Aussagen mit Quantoren

A

x ∈ U : (p(x) → q(x))

Wahle a beliebig aus U.

Beweis der Implikation p(a) → q(a).

Da a beliebig gewahlt werden kann, folgtA

x ∈ U : p(x) → q(x)

13



A

x ∈ U : (p(x) → q(x))

Wahle a beliebig aus U.


Da a beliebig gewahlt werden kann, folgtA

x ∈ U : p(x) → q(x)

Behauptung:

A

n ∈ N : (n ist gerade und√

n ist eine naturliche Zahl| {z }

p(n)

→√

n ist gerade| {z }

q(n)

).

Beweis: Sei n beliebig aus N. Wir zeigen, dass wenn n gerade ist und√

n eine naturliche

Zahl ist, dann√

n gerade ist (das wurde auf Seite 6 bewiesen).

14



E

x (p(x) → q(x))

Sei a ein geeignetes Element aus U.


Damit folgtE

x ∈ U : p(x) → q(x).A

x

E

y A(x , y)

15


Beweise mittels Vollstandiger Induktion

16

Induktion

Wesentliches Beweisprinzip in Mathematik und Logik

17

Induktion


Einfache Version

Induktion uber die naturlichen Zahlen N

(natural induction)

18

Induktion


Einfache Version

Induktion uber die naturlichen Zahlen N

(natural induction)

Generalization

Noethersche Induktion

(noetherian induction/

induction over well-founded partially ordered sets)

19

Emmy Noether

Geboren 1882 in Erlangen

Gestorben 1934 in Princeton (USA)

Mitbegrunderin der modernen Algebra

20

Emmy Noether

Geboren 1882 in Erlangen

Gestorben 1934 in Princeton (USA)

Mitbegrunderin der modernen Algebra

Allgemein heißt eine geordnete algebraische Struktur

noethersch, wenn es in ihr keine unendlich absteigenden

Ketten gibt.

21

Induktion uber die naturlichen Zahlen

Idee: Definition der naturlichen Zahlen

(A1) 0 ist eine naturliche Zahl

(A2) Jede naturliche Zahl n hat einen Nachfolger S(n)

(A3) Aus S(n) = S(m) folgt n = m

(A4) 0 ist nicht Nachfolger einer naturlichen Zahl

(A5) Jede Menge X , die 0 und mit jeder naturlichen Zahl n

auch deren Nachfolger S(n) enthalt, umfasst alle

naturlichen Zahlen.

22




naturlichen Zahlen.

A

X Menge: Falls 0 ∈ X , und

A

n ∈ N : n ∈ X → n + 1 ∈ X

so

A

n ∈ N : n ∈ X

23




naturlichen Zahlen.

A


A

n ∈ N : n ∈ X → n + 1 ∈ X

so

A

n ∈ N : n ∈ X

Induktionssatz

Gelten die beiden Aussagen:

- p(0) und

-

A

n ∈ N : p(n)→ p(n + 1),

dann gilt auch

A

n ∈ N : p(n).

24




naturlichen Zahlen.

A


A

n ∈ N : n ∈ X → n + 1 ∈ X

so

A

n ∈ N : n ∈ X

Induktionssatz


- p(0) und Induktionsbasis

-

A

n ∈ N : p(n)→ p(n + 1), Induktionsschritt

dann gilt auch

A

n ∈ N : p(n).

25


Struktur eines Induktionsbeweises

(1) Induktionsbasis: Beweise p(0)

(2) Induktionsschritt: Beweise p(n)→ p(n + 1)

fur ein beliebiges n ∈ N

26


Struktur eines Induktionsbeweises


(2) Induktionsvoraussetzung: Fur ein beliebig gewahltes

n ∈ N gilt p(n)

(3) Induktionsschluss: Folgere p(n + 1) aus der

Induktionsvoraussetzung p(n)

27

Beispiel

Behauptung: Die Summe der ersten n ungeraden Zahlen ist n2.

Fur alle n ∈ N,

n−1X

i=0

(2i + 1) = n2.

28

Beispiel


Fur alle n ∈ N,

n−1X

i=0

(2i + 1) = n2.p(n) :

n−1X

i=0

(2i + 1) = n2


n = 0: 0 = 02

29

Beispiel


Fur alle n ∈ N,

n−1X

i=0

(2i + 1) = n2.p(n) :

n−1X

i=0

(2i + 1) = n2

(1) Induktionsbasis: Beweise p(0) OK


n ∈ N gilt p(n):

n−1X

i=0

(2i + 1) = n2

30

Beispiel


Fur alle n ∈ N,

n−1X

i=0

(2i + 1) = n2.p(n) :

n−1X

i=0

(2i + 1) = n2

(1) Induktionsbasis: Beweise p(0) OK


n ∈ N gilt p(n):

n−1X

i=0

(2i + 1) = n2

(3) Induktionsschluss: Folgere p(n + 1) aus p(n)

p(n + 1) :n

X

i=0

(2i + 1) = (n + 1)2.

Beweis:nX

i=0

(2i + 1) = (

n−1X

i=0

(2i + 1)) + (2n + 1)p(n)= n

2+ (2n + 1) = (n + 1)

2.

31

Verallgemeinerte vollstandige Induktion



p(0) und

A

n ∈ N : p(0) ∧ p(1) ∧ · · · ∧ p(n)→ p(n + 1)

dann gilt die Aussage

A

n ∈ N : p(n).

32

Wohlfundierte (Noethersche) Induktion



p(0) und

A

n ∈ N : p(0) ∧ p(1) ∧ · · · ∧ p(n)→ p(n + 1)


A

n ∈ N : p(n).

Aquivalent


p(0) und

A

n ∈ N : (

A

k ∈ N : (k < n + 1→ p(k))→ p(n + 1))


A

n ∈ N : p(n).

33




p(0) und

A

n ∈ N : p(0) ∧ p(1) ∧ · · · ∧ p(n)→ p(n + 1)


A

n ∈ N : p(n).

Aquivalent

Gilt die Aussage:

A

n ∈ N : (

A

k ∈ N : (k < n→ p(k))→ p(n))


A

n ∈ N : p(n).

34


Theorem:

Falls

A

n ∈ N : (

A

k ∈ N : (k < n→ p(k))→ p(n)) P

dann gilt

A

n ∈ N : p(n) Q

Beweis: Zu zeigen: P → Q

Kontrapositionsbeweis: Wir zeigen, dass ¬Q → ¬P

Annahme: ¬Q := ¬(

A

n ∈ N : p(n)) ≡

E

n ∈ N : ¬p(n).

> wohlfundierte Ordnung auf N: es gibt keine unendliche Folge

x1, . . . , xn, . . . mit x1 > x2 > · · · > xn > . . . .

Sei Y = {n ∈ N | ¬p(n)} 6= ∅. Dann hat Y ein minimales Element m, d.h.

E

m(m ∈ Y ∧ (

A

k ∈ N : (k < m→ k 6∈ Y ))) = ¬P.

35


Theorem:

Falls

A

n ∈ N : (

A

k ∈ N : (k < n→ p(k))→ p(n)) P

dann gilt

A

n ∈ N : p(n) Q

Beweis: Zu zeigen: P → Q

Kontrapositionsbeweis: Wir zeigen, dass ¬Q → ¬P

Annahme: ¬Q := ¬(

A

n ∈ N : p(n)) ≡

E

n ∈ N : ¬p(n).

> wohlfundierte Ordnung auf N: es gibt keine unendliche Folge

x1, . . . , xn, . . . mit x1 > x2 > · · · > xn > . . . .

Sei Y = {n ∈ N | ¬p(n)} 6= ∅. Dann hat Y ein minimales Element m, d.h.

E

m(m ∈ Y ∧ (

A

k ∈ N : (k < m→ k 6∈ Y ))) = ¬P.

36


Theorem:

Falls

A

n ∈ N : (

A

k ∈ N : (k < n→ p(k))→ p(n)) P

dann gilt

A

n ∈ N : p(n) Q

Verallgemeinerung

- beliebige Menge A statt N

- < “partielle” Ordnung auf A

- < wohlfundiert (es gibt keine unendliche Folge x1, . . . , xn, . . . mit

x1 > x2 > · · · > xn > . . . )

37

Binare Relationen

Definition:

Eine binare Relation R uber einer Menge A ist eine Teilmenge von A× A.

R binare Relation: R ⊆ A× A.

Statt (x , y) ∈ R schreiben wir: R(x , y) oder xRy .

38

Partielle Ordnungen

Definition:

Eine binare Relation R uber einer Menge A ist eine partielle Ordnung gdw.

• R ist reflexiv:

A

x ∈ A(xRx)

• R ist transitiv:

A

x , y , z ∈ A(xRy ∧ yRz → xRz)

• R ist antisymmetrischA

x , y ∈ A(xRy ∧ yRx → x = y)

39

Partielle Ordnungen

Definition:


• R ist reflexiv:

A

x ∈ A(xRx)


A



x , y ∈ A(xRy ∧ yRx → x = y)

Dann heißt (A,R) eine partiell geordnete Menge

40

Partielle Ordnungen

Definition:


• R ist reflexiv:

A

x ∈ A(xRx)


A



x , y ∈ A(xRy ∧ yRx → x = y)

Beispiele:

• (N,≤)

• (A,R), wobei

A = {0, a, b, 1} und

R = {(0, 0), (0, a), (0, 1), (a, a), (a, 1), (b, b), (b, 1), (1, 1)}

R partielle Ordnung: a und b in R unvergleichbar.

41

Totale Ordnungen

Definition: Sei (A, R) eine partiell geordnete Menge.

R ist eine totale Ordnung gdw. R(x , y) oder R(y , x) fur alle x , y ∈ A.

42

Minimum


Sei A′ ⊆ A, und m ∈ A′ .

m ist ein Minimales Element von A′ , gdw.: es gibt kein x ∈ A′ mit

x ≤ m, x 6= m.

43

Minimum


Sei A′ ⊆ A, und m ∈ A′ .

m ist ein Minimales Element von A′ , gdw.: es gibt kein x ∈ A′ mit

x ≤ m, x 6= m.

Beispiele:

• (N,≤). Sei A′ = {3, 5, 7, 9} ⊆ N.

3 ist ein Minimales Element von A′ .

• Sei (A,R) wobei

A = {a, b, c, d} und

R = {(a, a), (a, b), (c, c), (c, b), (c, d), (e, e), (e, d), (b, b), (d , d)}

Sei A′ = {a, b, c} ⊆ A.

A′ hat zwei minimale Elemente: a und c.

44

Wohlfundierte partielle Ordnungen

Sei (A,≤) eine partiell geordnete Menge.

Definition: x < y gdw.: (x ≤ y und x 6= y) (fur x , y ∈ A)

45



Definition: x < y gdw.: (x ≤ y und x 6= y) (fur x , y ∈ A)

Definition (Noethersch / wohlfundiert)

(A,≤) heißt noethersch (oder wohlfundiert) gdw.:

Es gibt keine unendlich absteigende Kette in A, das heißt:

Es gibt keine unendliche Folge (xi )i∈N, mit

• xi ∈ A fur alle i ∈ N und

• xi+1 < xi fur alle i ∈ N.

46



Definition:

x < y gdw.: (x ≤ y und x 6= y) (fur x , y ∈ A)

Definition (Noethersch / wohlfundiert)

(A,≤) heißt noethersch (oder wohlfundiert) gdw.:

Es gibt keine unendlich absteigende Kette in A, das heißt:

Es gibt keine unendliche Folge (xi )i∈N, mit



(Unendlich aufsteigende Ketten sind zulassig)

47

Beispiele

(N,≤) is wohlfundiert

(Z,≤) ist nicht wohlfundiert

(0 ∪ { 1n| n ∈ N},≤) ist nicht wohlfundiert

(R,≤) ist nicht wohlfundiert

48


Lemma.

(A,≤) ist noethersch (wohlfundiert) gdw.: jede nicht-leere Teilmenge von

A hat (mindestens) ein Minimales Element.

49


Lemma.



Beweis: “→”

Statt P → Q, beweisen wir ¬Q → ¬P.

Sei A′ ⊆ A nicht-leere Teilmenge von A, die kein minimales Element

enthalt. Sei x1 ∈ A′ . Da x1 nicht minimal ist, gibt es x2 ∈ A′ mit x2 < x1.

Da x2 nicht minimal ist, gibt es x3 ∈ A′ mit x3 < x2 < x1. Wir konnen

deswegen eine unendliche absteigende Kette von Elementen aus A bilden,

d.h. A ist nicht noethersch.

50


Lemma.



Beweis: “←”

Statt P → Q, beweisen wir wieder ¬Q → ¬P.

Annahme: (A,≤) ist nicht noethersch,

d.h. es gibt eine unendliche Folge (xi )i∈N, mit



Sei A′ = {xi | i ∈ N}.

Wir zeigen, dass A′ keinen minimalen Element hat: Sei a ∈ A′ . Dann a = xi

fur einen i ∈ N. Dann ist xi+1 < a; deshalb kann a nicht minimal sein.

51

Documents

Logik f¨ur Informatiker 1. Grundlegende Beweisstrategiensofronie/logik-ss-2012/slides/... · Logik f¨ur Informatiker 1. Grundlegende Beweisstrategien Viorica Sofronie-Stokkermans