Fachschaft Mathematik & Informatik Mengen & Logik Mathe-Vorkurs August 2007 Fachschaft Mathematik und Informatik

Fachschaft Mathematik & Informatik

Mengen & Logik

Mathe-VorkursAugust 2007

Fachschaft Mathematik und Informatik www.fim.uni-mannheim.de

21.08.2007 Mengen & Logik - 2 -


Themen:

I. Logik

II. Mengen

21.08.2007 Mengen & Logik - 3 -


I. Logik

1. Grundlagen

(a) Aussagendefinition

(b) Wahrheitswerte

2. Logische Operatoren

21.08.2007 Mengen & Logik - 4 -


(a) Aussagendefinition-Was ist eine Aussage?

• In der Logik betrachtet man Aussagen

• Der Inhalt einer Aussage ist unwichtig, es geht nur um deren Wahrheitsgehalt

• Es gibt nur ‚wahr‘ und ‚falsch‘

• Es gilt: wahr (true) = 1 falsch (false) = 0

• Def.: Eine Aussage ist ein Satz, der entweder wahr oder falsch ist.

21.08.2007 Mengen & Logik - 5 -


(a) Was ist eine Aussage?

Beispiele:

Beispiele für eine wahre Aussage:

• „Luft enthält Sauerstoff.“

• „1 + 1 = 2“

• „Es gibt keine natürliche Zahl x, für die gilt: x² = 7.“

Beispiele für eine falsche Aussage:

• „Der Blauwal ist ein Fisch“.

• „1+1=3“

• „Es gibt reelle Zahlen deren Quadrat –1 ist.“

21.08.2007 Mengen & Logik - 6 -


(a) Was ist eine Aussage?

Weitere Beispiele:

• „Wie spät ist es?“

Frage

• „Bitte denken Sie nach!“

Aufforderung

• „Es gibt ein x, so dass 2 * x = 1.“

sog. Aussageform, hängt davon ab wie x belegt wird ob es zur wahren oder falschen Aussage wird

21.08.2007 Mengen & Logik - 7 -


(b) Wahrheitswerte & Gleichheit

• Es kommt nur auf den Wahrheitsgehalt einer Aussage an, nicht auf deren Inhalt.

• Bezeichner für Aussagen: A, B, C, ...

• Wahrheitswert einer Aussage: z(A) = 0 oder 1 Aussage wahr: z(A) = 1 Aussage falsch: z(A) = 0

• Def.: Die Aussagen A und B heißen gleich, wenn sie denselben Wahrheitswert haben. Also gilt A = B, wenn z(A) = z(B) erfüllt ist.

21.08.2007 Mengen & Logik - 8 -


I. Logik

1. Grundlagen

2. Verknüpfungen

(a) Logische Operatoren

(b) Implikation

(c) Äquivalenz

(d) Was bedeutet dies für Beweise?

21.08.2007 Mengen & Logik - 9 -



Was ist ein logischer Operator?

• Jeder Operator symbolisiert eine bestimmte Funktion

• Verknüpft zwei (oder mehr) Ausdrücke

– Dazu benutzt man sog. logische Operatoren und Wahrheitstabellen

• Wahrheitstabellen: Jede mögliche Kombination aufnehmen

21.08.2007 Mengen & Logik - 10 -



Negation: ‚nicht‘ = ‚NOT‘

• Symbol: ‚‘

• Wahrheitstabelle:

A A

0

1 0

1

21.08.2007 Mengen & Logik - 11 -



Konjunktion: ‚und‘ = ‚AND‘

• Symbol: ‚‘• Wahrheitstabelle:

A B A B0 0

0 1

1 0

1 1

0

1

0

0

21.08.2007 Mengen & Logik - 12 -



Disjunktion: ‚oder‘ = ‚OR‘

• Symbol: ‚‘• Wahrheitstabelle:

A B A B0 0

0 1

1 0

1 1 1

0

1

1

21.08.2007 Mengen & Logik - 13 -



Ausschließende Disjunktion: ‚Exklusives oder‘ = ‚XOR‘

• Symbol: ‚XOR‘, manchmal auch ‚‘


A B A B

0 0

0 1

1 0

1 1 0

0

1

1

21.08.2007 Mengen & Logik - 14 -



• Aussagen lassen sich miteinander verknüpfen

• Beispiel: A B A B

0 0

0 1

1 0

1 1

A B A

0 0

0 1

1 0

1 1

und:

( AB) = A B (Gesetz von De Morgan)

0

0

0

1

1

1

1

0

1

1

0

0

1

0

1

0

1

1

1

0

( A B)

B A B

21.08.2007 Mengen & Logik - 15 -



• Es gibt „Rechenregeln“ für logische Operatoren

• Dienen zur Umformung von logischen Gleichungen

• Alle Regeln können mittels Wahrheitstabellen bewiesen werden

• Vereinfachen den mathematischen Alltag (kein erneuter Beweis notwendig bei Anwendung)

21.08.2007 Mengen & Logik - 16 -



• Assoziativität: ( A B ) C = A ( B C )

( A B ) C = A ( B C )

• Kommutativität: A B = B AA B = B A

• Doppelnegation: ( A ) = A = A

Ein paar Rechengesetze...

Noch ein paar Regeln

21.08.2007 Mengen & Logik - 17 -



• Distributivität: ( A B ) C = ( A C ) ( B C ) ( A B ) C = ( A C ) ( B C )

• Komplementarität: A ( A ) = 0B ( B ) = 1

• Neutralität: A 1 = AA 0 = 0A 1 = 1A 0 = A

• Idempotenz: A A = AA A = A

• De Morgan: ( A B ) = A B( A B ) = A B

21.08.2007 Mengen & Logik - 18 -


(b) Implikation

• Weiterer logischer Operator

• Symbol: ‚‘


A B A B

0 0

0 1

1 0

1 1

1

0

1

1

21.08.2007 Mengen & Logik - 19 -


(b) Implikation

Beispiel: „Wenn es regnet, ist die Strasse nass“

• Aussage A: „Wenn es regnet.“

• Aussage B: „ist die Strasse nass.“

A B A B

0 0 1

0 1 1

1 0 0

1 1 1

Die Behauptung wird erfüllt: Es regnet und die Strasse ist nass. Die Behauptung ist also wahr.

1 11

21.08.2007 Mengen & Logik - 20 -


(b) Implikation




A B A B

0 0 1

0 1 1

1 0 0

1 1 1

1 0 0

Es regnet, aber die Strasse ist nicht nass. Obwohl dies vorher behauptet wurde. Somit ist die Implikation ist falsch.

21.08.2007 Mengen & Logik - 21 -


(b) Implikation




A B A B

0 0 1

0 1 1

1 0 0

1 1 1

0 0 1

0 1 1

Es regnet nicht, ist die Strasse nun nass? Für die Implikation ist irrelevant, ob die Strasse nass ist oder nicht. Da nichts über den Fall ausgesagt wird, ist die Aussage A B also korrekt.

21.08.2007 Mengen & Logik - 22 -


(c) Äquivalenz

• Noch ein logischer Operator

• Symbol: ‚‘

• Logischer Zusammenhang: AB = (AB) (BA)

• Wahrheitstabelle: A B A B

0 0 1

0 1 0

1 0 0

1 1 1

• Die Äquivalenz ist eine „doppelte Implikation“.

21.08.2007 Mengen & Logik - 23 -


(c) Äquivalenz

1. Beispiel:

Es sei f eine Funktion. Ist f(x) konstant, so folgt () f(x) = f(-x).

korrekte Implikation

Die andere Richtung funktioniert nicht: Wenn f(x) = f(-x) gilt, dann ist () f(x) konstant.

Stimmt nicht!

Gegenbeispiel: f(x) = x²

f(x) = f(-x) ist wahr

f(x) = x² ist jedoch nicht konstant

Die Implikation gilt nur in eine Richtung!

21.08.2007 Mengen & Logik - 24 -


(c) Äquivalenz

2. Beispiel:Es gilt f(x) = f(-x) genau dann, wenn () f symmetrisch ist.

‚‘ Wenn f(x) = f(-x) gilt, dann verläuft der Graph auf beiden Seiten der y-Achse gleich (also: Spiegelung an x=0) f ist symmetrisch.

‚‘ Wenn f symmetrisch ist, dann lässt sich der Graph von f an x=0 („y-Achse“) spiegeln. Es gilt: f(x) = f(-x)

Die Äquivalenz gilt in beiden Richtungen!

21.08.2007 Mengen & Logik - 25 -



Allgemein:

• Unbedingt Formalismus einhalten!

• Häufig sind Implikationen nötig um Beweise zu führen

Äquivalenzbeweise:

• Äquivalenz wird immer im direkten Beweis gezeigt

• Beide Richtungen zeigenoder:Nur Äquivalenzumformungen benutzen

21.08.2007 Mengen & Logik - 26 -



Zeigen Sie folgende Äquivalenz: (A (B A)) (C (D C)) (D C)

Beh.: (A (B A)) (C (D C)) (D C)Bew.: (A (B A)) (C (D C))

(A (B A)) ((C C) D) KG; AG (A (B A)) (C D) Idempotenz (A (B A)) (C D) De Morgan (A A B) (D C) AG ; KG (1 B) (D C) Komplementaritätsgesetz 1 (D C) Neutralitätsgesetz (D C)

Die Behauptung stimmt.�

21.08.2007 Mengen & Logik - 27 -


II. Mengen

1. Grundlagen

(a) Mengendefinition

(b) Leere Menge

(c) Gleichheit von Mengen

(d) Teilmengen

(e) Komplement einer Menge

(f) Mächtigkeit und Potenzmenge

(g) Produktmenge / kartesisches Produkt

2. Mengenverknüpfungen

3. Rechengesetze

21.08.2007 Mengen & Logik - 28 -



• Georg Cantor (1845 – 1918):

„Eine Menge ist eine Zusammenfassung von bestimmten, wohl unterschiedenen Objekten der Anschauung oder des Denkens, welche die Elemente der Menge genannt werden, zu einem Ganzen.“

21.08.2007 Mengen & Logik - 29 -


• Manche Mengen können abgezählt werden

Beispiele: {1, 2, ..., 10}


• Mengen werden mit Großbuchstaben, Elemente mit Kleinbuchstaben bezeichnet.

• Das Element a ist in der Menge M enthalten: a M

• Das Element b ist nicht in der Menge M enthalten: b M

• Bekannte Mengen: N, Z, R

{1, 2, ..., 1000000000000000000000}

(die reellen Zahlen sind überabzählbar!)

N Z R

21.08.2007 Mengen & Logik - 30 -



Wichtige Schreibweisen: x M : A für alle x M gilt die Aussage A x M : A es existiert (mindestens) ein x M,

so dass A gilt ! x M : A es existiert genau ein x M,

so dass A gilt

• ... Auslassungspunkte,z.B. in {1, 2, 3, ..., 100}, {2, 4, 6, 8, ...}

21.08.2007 Mengen & Logik - 31 -


(b) Leere Menge

• Enthält kein Element

• Symbole: {},

• Frage: Sind die Mengen und { } gleich oder verschieden?

Verschieden – die zweite Menge enthält ein Element, wenn auch nur das Element der leeren Menge.

21.08.2007 Mengen & Logik - 32 -


(c) Gleichheit von Mengen

• Wenn Elemente das gleiche Element bezeichnen: a = b

• Enthalten zwei Mengen A und B genau die gleichen Elemente, dann sagt man, die Mengen sind gleich, also: A = B.

• Mathematisch:

- A = B x : x A x B

• Wenn Elemente ungleiche Elemente bezeichnen: a b

• Enthalten zwei Mengen A und B ungleiche Elemente

- A B ( x A : x B ) ( y B : y A )

21.08.2007 Mengen & Logik - 33 -


(d) Teilmengen

• Teilmengen enthalten einen Teil der Elemente aus einer anderen Menge (Obermenge), sind jedoch immer vollständig in dieser enthalten (keine Elemente außerhalb Obermenge).

mathematisch: A O x A : x O • Echte Teilmenge: Keine Mengen-Gleichheit

mathematisch: A O ( x A : x O ) ( A O )

21.08.2007 Mengen & Logik - 34 -


(e) Komplement einer Menge

• Das Komplement enthält alle Elemente aus einer Obermenge O, die nicht in der Menge A enthalten sind.

• Es kommt auf die Obermenge an!

• Schreibweise: = { x O : x A }A

A

O

21.08.2007 Mengen & Logik - 35 -


(f) Mächtigkeit & Potenzmenge

• Mächtigkeit: Anzahl der Elemente einer Menge, | A |

• Potenzmenge: Menge aller Teilmengen einer Menge, (A)

• Beispiel: A = {1, 2, 3}

Mächtigkeit und Potenzmenge?

| A | = 3

(A) = {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

21.08.2007 Mengen & Logik - 36 -


(g) Produktmenge / kartesisches Produkt

• Das kart. Produkt ist die Menge aller geordneten Paare (a, b), wobei a Element aus A und b Element aus B ist.

• Schreibweise: A B („A kreuz B“)

• Math. Definition: A B = { (a, b) | a A b B }

• Natürlich auch mit mehreren Mengen möglich

21.08.2007 Mengen & Logik - 37 -


II. Mengen

1. Grundlagen


(a) Vereinigung

(b) Durchschnitt

(c) Differenz

3. Rechengesetze

21.08.2007 Mengen & Logik - 38 -


(a) Vereinigung

• Symbol: ‚‘

• A B = { x O : x A x B }

Enthält alle Elemente, die entweder in A oder in B enthalten sind (oder auch in beiden Mengen).

n

ii 1

A

• Beispiel: {1, 2, 3} {3, 4} = ?

• Schreibweise bei mehreren Mengen:

{1, 2, 3, 4}

21.08.2007 Mengen & Logik - 39 -


(b) Durchschnitt

• Symbol: ‚‘

• A B = { x O : x A x B }

Enthält nur die Elemente, die in beiden Mengen enthalten sind.n

ii 1

A• Schreibweise bei mehreren Mengen:

• Beispiel: {1, 2, 3} {3, 4} = ?{3}

21.08.2007 Mengen & Logik - 40 -


(c) Differenz

• Symbol: ‚\‘, manchmal auch: ‚‘• A \ B = A – B = { x O : x A x B }

Enthält alle Elemente aus A, die nicht in B enthalten sind.

• Beispiel: {1, 2, 3} \ {3, 4} = ?{1, 2}

21.08.2007 Mengen & Logik - 41 -


II. Mengen

1. Grundlagen


3. Rechengesetze

21.08.2007 Mengen & Logik - 42 -


3. Rechengesetze

Auf den Mengen-Operatoren und :

• Kommutativgesetz: A B = B A

A B = B A

• Assoziativgesetz: ( A B ) C = A ( B C )

( A B ) C = A ( B C )

• Distributivgesetz: A ( B C ) = ( A B ) ( A C )

A ( B C ) = ( A B ) ( A C )

• De Morgansche Gesetze:

A B A B A B A B

21.08.2007 Mengen & Logik - 43 -


• Noch Fragen?• Wie gehts jetzt weiter?

– Ab 14:30 in B6 A0.01: Komplexe Zahlen• Bei späteren Fragen könnt ihr euch an die

Fachschaft oder direkt an mich wenden:– [email protected]

– [email protected]

21.08.2007 Mengen & Logik - 44 -


Ende

Documents

Fachschaft Mathematik & Informatik Mengen & Logik Mathe-Vorkurs August 2007 Fachschaft Mathematik und Informatik