Mathematische Grundlagen der Informatik und Konzepte der Modellierung I Übungen PDF

Preview

Summary

Martin-Luther-Universität Halle-WittenbergInstitut für Informatik Prof. Dr.-Ing. S. Posch, M. J. Dähne, M. M. Fröbe, M. S. WegingHalle, 7. Januar 2021Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020 / 2021 ) Übungsserie 8Bitte beachten Sie folgende Punkte: · Kommentiere...

Description

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 7. Januar 2021 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 8 Bitte beachten Sie folgende Punkte: · Kommentieren Sie Ihren Lösungsweg! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Sie können Sätze/Lemmata benutzen, die in der Vorlesung bis zur Woche VOR Ausgabe der Aufgabe schon behandelt worden sind (hier inkl. Korollar 2.37). Ausnahmen werden explizit angegeben. · Verwenden Sie möglichst die latex-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. siehe unter http://fachschaft.mathinf.uni-halle.de/informationen/latex · Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. · Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel) – bei Gruppenabgabe die aller Mitglieder. · Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt. Jeder der Beteiligten muss jede Aufgabe verstanden haben und vorrechnen können. · Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. · Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. · Letzter Abgabetermin für das 8. Übungsblatt ist Donnerstag, der 14. Januar 2021, 12.00 Uhr.

1

Aufgabe 1 (Vielfachmengen: Beweis (6 Punkte)) Es seien U ein Universum und A, B ™ U ◊

Vielfachmengen.

Zeigen Sie, dass A fl B eine Vielfachmenge ist und für alle x œ U ! " ‰AflB (x) = min ‰A (x), ‰ B (x) gilt.

Aufgabe 2 (Vielfachmengen: disjunkte Vereinigung (4 Punkte)) Es seien U ein Universum und A, B, C ™ U ◊

Vielfachmengen.

Zeigen Sie, dass das Assoziativgesetz (A ‡ B) ‡ C = A ‡ (B ‡ C ) für die disjunkte Vereinigung von Vielfachmengen gilt. Achtung: dies ist Teil des Satzes 2.39, der (natürlich) im Beweis NICHT verwendet werden darf!

Aufgabe 3 (Primfaktorzerlegung: Eigenschaften (3+2 Punkte)) Es seien n, m œ , n, m > 1 sowie N die Vielfachmenge der Primfaktoren von n und M die Vielfachmenge der Primfaktoren von m. Das Universum ist jeweils die Menge aller Primzahlen . a)

Geben Sie für n = 20790 und m = 1560 die Vielfachmengen M und N (in der Paarschreibweise) an.

b)

Ermitteln Sie die Vielfachmenge der Primfaktoren von n · m mithilfe der Aussage in Satz 2.40 iii. (in der Paarschreibweise).

Aufgabe 4 (Vielfachmengen: kartesisches Produkt (5 + 4 Punkte)) Es seien U, V, W Vielfachmengen über dem Universum Z . (Hierbei sind die Mengedifferenz, das kartesische Produkt und Mächtigkeit für Vielfachmengen gemeint.) Zeigen Sie: a)

(U \ V ) ◊ W = (U ◊ W ) \ (V ◊ W )

b)

|U ◊ V | = |U | · |V | Hinweis: Die Mächtigkeit einer Vielfachmenge |U | ist die Anzahl der Elemente dieser Menge, d.h. |U | = ÀxœZ (‰U (x)), analog für andere Vielfachmengen.

2

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 5. November 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 1 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ihren Lösungsweg! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Verwenden Sie möglichst (bei den ersten Übungsblättern noch nicht Pflicht) die LATEX-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. siehe unter http://fachschaft.mathinf.uni-halle.de/informationen/latex Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel). Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt, jedoch muss jeder der Beteiligten jede Aufgabe verstanden haben und vorrechnen können. Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. Letzter Abgabetermin für das 1. Übungsblatt ist Donnerstag, der 12.11.2020, 12.00 Uhr. Abgabetermin ist immer donnerstags.

1

Empfehlung bei Aufgaben 1 und 2 (keine Pflicht): Verwendung von LATEX Aufgabe 1 (Formeln mit Summenzeichen (4 Punkte)) Schreiben Sie folgende Gleichungen in gedruckter Form auf. Geben Sie jeweils auch die Summenformel-Schreibweise P (mit Summenzeichen ) gedruckt an. a) e = 1+

1 1 1 1 + + + + 2! 3! 4! 5!

b) ln

1+x 1−x

= 2 x+

x3 x5 x7 + + + 7 3 5

mit |x| < 1

Aufgabe 2 (Formeln über 2 Zeilen, Nummerierung von Formeln (3 Punkte)) Geben Sie die folgenden mathematische Formeln in gedruckter Form an, wobei Sie a durch A, b durch γ und c durch 2 ersetzen. Geben Sie auch die Nummern (1) und (2) hinter den Formeln mit an. a) 2 (a + b)

c =

2 a c + 2 b c

lim

ab =

i→∞

a b

− 100 i + 10

(1)

(2)

Aufgabe 3 (Mengen (4+4 Punkte)) Es sei

die Menge der ganzen Zahlen.

Betrachten Sie die folgenden Teilmengen A, B, C und n

A = {3n : n

a)

B = {2n : n

}

C = {n : n

und n2

: 4} 100}

Drücken Sie jede der folgenden Mengen unter Verwendung von Mengenoperationen auf den Mengen A, B, C und aus: a1)

Die Menge U aller ungeraden ganzen Zahlen

a2)

V = {−10, −8, −6, −4, −2, 0, 2, 4, 6, 8, 10}

a3)

W = {6n : n

und n

2} 2

a4) b)

X = {−9, −7, −5, −3, −1, 1, 3, 5, 7, 9}

Geben Sie zu jeder der 7 Mengen A, B, C, U, V, W, X die jeweils fehlende extensionale bzw. intensionale Darstellung an.

Aufgabe 4 (Mengen-Anwendungen (2 + 3 Punkte)) a)

Gegeben seien die folgenden Mengen: A = Menge aller Studierenden der Uni Halle B = Menge aller männlichen Studenten in Deutschland C = Menge aller in Deutschland Studierenden im ersten Semester D = Menge aller Studierenden in Halle, die nicht Informatik studieren E = Menge aller Studierenden in Europa, die Bioinformatik studieren F = Menge aller Studierenden, die Lehramt Informatik (Gymnasium) an der Uni Halle studieren Beschreiben Sie die Menge aller derjenigen Studierenden im ersten Semester in Informatik, Bioinformatik und Lehramt Informatik (Gymnasium), die donnerstags 15.30 Uhr in der Vorlesung MGI+KdM sitzen (sollen), mithilfe der Mengen A bis F. Erläutern Sie dabei Ihre Lösung, z.B. den schrittweisen Aufbau der Ergebnismenge.

b)

Geben Sie jeweils eine intensionale Darstellung für folgende Mengen an: {2, 4, 8, 16, 32,

}

Menge aller unmittelbaren Nachfolger von quadratischen Zahlen, die zwischen 8 und 80 liegen abgeschlossenes Intervall [0, 1]

Aufgabe 5 (Elemente von Mengen (4 Punkte)) Wir betrachten die Menge ↵ ⌦ M = {1, 2, 3, 4}, , {0, 1}, {0}

{0, 1}?

Welche der folgenden Aussagen sind falsch? Begründen Sie Ihre Antwort. a)

{ }

b)

0

M M

c)

{0, 1, 2, 3, 4, 5}

d)

{1, 2}

{{3, 4}}

{1, 2, 3, 4, 6}

M

M

3

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 12. November 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 2 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ihren Lösungsweg ausreichend! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Verwenden Sie möglichst die LATEX-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. Siehe http://fachschaft.mathinf.uni-halle.de/informationen/latex Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel)—bei Gruppenabgabe die aller Mitglieder. Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt. Jeder der Beteiligten muss jede Aufgabe verstanden haben und vorrechnen können. Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. Letzter Abgabetermin für das 2. Übungsblatt ist Donnerstag, der 19.11.2020, 12.00 Uhr.

1

Aufgabe 1 (Mengen-Anwendungen (6 Punkte)) Sei die Menge der reellen Zahlen, + die Menge der positiven reellen Zahlen, − die Menge der negativen reellen Zahlen, +0 die Menge der nichtnegativen reellen Zahlen und 0− die Menge der nichtpositiven reellen Zahlen. Bestimmen Sie jeweils A A=

+

und B =

−

A=

+

und B =

+ 0

A=

+

und B =

− 0

A=

−

und B =

+ 0

A=

−

und B =

− 0

A=

+ 0

und B =

− 0

B und A

B für

Aufgabe 2 (Beweis Mengenoperationen (6 Punkte)) Wir betrachten die Mengen A, B, C. a)

Beweisen Sie (A

C)

(B

C)

(A

B)

C

(Hinweis: z.B. durch Fallunterscheidung) b)

Beweisen Sie (A

B)

C

(A

C)

(B

C)

(Hinweis: z.B. durch Fallunterscheidung) c)

Beweisen Sie (A

B)

C = (A

C)

(B

C)

Aufgabe 3 (Beweise: Mengenoperationen (3 + 4 + 3 Punkte)) Es seien A, B, C beliebige Mengen. Beweisen Sie folgende Aussagen: a)

A

b)

für A C = Hinweise:

B=B

A gilt A

C

A \ (B \ C)

mittels Widerspruchsbeweis seien A und B Aussagen: nicht (A und B) genau dann, wenn (nicht A) oder (nicht B) c)

A= (Hinweis: Sie dürfen Lemma 2.3 aus der Vorlesung und die Aussage A für jede Menge A verwenden.)

2

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 19. November 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 3 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ihren Lösungsweg ausreichend! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Sie können die Sätze/Lemmata bis inklusive 2.7 benutzen. Verwenden Sie möglichst die LATEX-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. Siehe http://fachschaft.mathinf.uni-halle.de/informationen/latex Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel)—bei Gruppenabgabe die aller Mitglieder. Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt. Jeder der Beteiligten muss jede Aufgabe verstanden haben und vorrechnen können. Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. Letzter Abgabetermin für das 3. Übungsblatt ist Donnerstag, der 26.11.2020, 12.00 Uhr.

1

Aufgabe 1 (Beweise: Mengenoperationen (6 Punkte)) Es seien A, B, C beliebige Mengen. Beweisen Sie folgende Aussage: Aus A B = B folgt A B = A (Empfehlung: Beweis durch Kontraposition)

Aufgabe 2 (Operationen mit Mengen und Komplement (5 Punkte)) Gegeben seien die Mengen A = {Anna, Beate, Clara} und B = {Arthur, Boris, Chris} über dem Grundbereich U = {Anna, Beate, Clara, Dana, Ella, Arthur, Boris, Chris, Dieter, Erik}, also A, B U. Geben Sie die folgenden Mengen extensional an: a)

(A

b)

(A)

c)

(A

B)

d)

(A

B) \ {Beate, Clara, Dana, Arthur, Erik} \ ( (U)

e)

{x : x

B) (B )

{B, (U)} ∧

{Anna})

x\ }

Hinweis: Die Namen Anna, Beate, Clara, . . . dürfen abgekürzt An, Be, Cl, . . . geschrieben werden.

Aufgabe 3 (Beweise: Komplementmengen (5 Punkte)) Sei U ein Universum. Zeigen Sie für beliebige Mengen A, B a) b)

A (A

U

(A) = B)

(A)

(B )

Aufgabe 4 (Disjunkte Vereinigung (3 Punkte)) Berechnen Sie für folgende Mengen die disjunkten Vereinigungen A B, A C und B C, sofern diese definiert sind. Begründen Sie anderenfalls, warum die disjunkte Vereinigung auf diesen Mengen nicht definiert ist. A = {Elefant, Igel, Katze, Mensch, Schnabeltier} Menge von Säugetieren, B = {Biene, Drossel, Frosch, Gecko, Schnabeltier} Menge eierlegender Tiere, C = {Ameise, Biene, Hummel, Libelle, Wespe} Menge von Insekten.

2

Aufgabe 5 (Disjunkte Vereinigung Beweis (5 Punkte)) a)

Unter welchen Voraussetzungen an beliebige Mengen A, B, C sind die disjunkten Vereinigungen (A B) C und A (B C) definiert?

b)

Beweisen Sie (unter diesen Voraussetzungen), dass (A B) C = A (B C) gilt.

3

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 26. November 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 4 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ihren Lösungsweg ausreichend! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Sie können die Sätze/Lemmata (und alle Definitionen) bis inklusive 2.18 benutzen. Ausnahmen werden explizit angegeben. Verwenden Sie möglichst die LATEX-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. Siehe http://fachschaft.mathinf.uni-halle.de/informationen/latex Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel)—bei Gruppenabgabe die aller Mitglieder. Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt. Jeder der Beteiligten muss jede Aufgabe verstanden haben und vorrechnen können. Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. Letzter Abgabetermin für das 3. Übungsblatt ist Donnerstag, der 03.12.2020, 12.00 Uhr.

1

Aufgabe 1 (Neutral- und Nullelemente (6 Punkte)) Sei U ein Universum und A

U.

Beweisen Sie: a)

A

=A

b)

A

U=A

c)

A

U=U

d)

A

=

e)

(U) =

f)

( )=U

Achtung In den Beweisen dieser Aufgabe dürfen die Lemmata 2.11 bis 2.13 nicht benutzt werden.

Aufgabe 2 (Potenzmengen und Mächtigkeit (6 Punkte)) a)

b) c)

Geben Sie die Potenzmenge für U = {rot, grün, blau} extensional an. Ermitteln Sie für U = U \ {blau} die Potenzmenge 2U und geben Sie die Mächtigkeiten der Mengen U, U , 2U und 2U an. ⌦ ↵ A {blau} : A U . Ermitteln Sie die Menge 2U Berechnen Sie die Mächtigkeit der Potenzmenge von B = { , 1, 2, 3} durch Angabe aller Elemente.

Aufgabe 3 (Satz 2.20 i. (8 Punkte)) Beweisen Sie durch starke Induktion über die Mächtigkeit der Menge Y : Seien X und Y endliche disjunkte Mengen, dann ist |X Y| = |X| + |Y|. Hinweis: Y = (Y \ {y})

{y} für y

Y, Y = .

Aufgabe 4 (Vollständige Induktion (4 Punkte)) Beweisen Sie durch vollständige Induktion über der Menge der natürlichen Zahlen : 2n > n + 1 für beliebige natürliche Zahlen n

2

2

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 3. Dezember 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 5 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ihren Lösungsweg ausreichend! Nicht ausreichend kommentierte Lösungen werden als falsch gewertet. Sie können die Sätze/Lemmata bis inklusive Satz 2.20 benutzen (und alle Definitionen). Ausnahmen werden explizit angegeben. Verwenden Sie möglichst die LATEX-Vorlage der Fachschaft zur Erstellung Ihres Lösungsblattes. Siehe http://fachschaft.mathinf.uni-halle.de/informationen/latex Die Lösungen sind in gedruckter Form im .pdf-Format in ILIAS hochzuladen. Schreiben Sie auf jedes Blatt Ihren vollständigen Namen und Ihr login für das Stud.IP (5stelliges Kürzel)—bei Gruppenabgabe die aller Mitglieder. Eine Zusammenarbeit von 2-3 Studierenden ist erlaubt. Jeder der Beteiligten muss jede Aufgabe verstanden haben und vorrechnen können. Plagiate (abgeschriebene Lösungen) werden als Betrugsversuch gewertet. Warten Sie mit der Abgabe Ihrer Lösungen nicht bis zur letzten Sekunde. Letzter Abgabetermin für das 5. Übungsblatt ist Donnerstag, der 10.12.2020, 12.00 Uhr.

Aufgabe 1 (Relationen: Beweis (6 Punkte)) Beweisen Sie die folgende Aussage aus Satz 2.21 für beliebige Mengen U, V, W: (U V) W = (U W) (V W) Die Sonderfälle (U V) nicht berücksichtigen.

W=

und (U

W)

(V

W) =

brauchen Sie

Distributivgesetze für logische Operationen UND/ODER dürfen angewendet werden. Dies ist in Analogie zum Distributivgesetze für Mengen: Satz 2.7): für beliebige Aussagen A,B,C gilt: (A oder B) und C gdw. (A und C) oder (B und C) A und (B oder C) gdw. (A und B) oder (A und C) 1

Aufgabe 2 (Beispiel: Projektion, Verkettung, kartesisches Produkt, Selektion (7 Punkte)) Gegeben seien die Universen U1 = {1, 2, 3, 4}, U2 = {a, b, c, d}, U3 = {↵, , , }, U4 = {1, 2, 3}, U5 = {b, c} und die Relation ⇢ U1 U2 U3 U4 U5 mit ⇢ = {(1, x2 , x3 , x4 , c) : x2 {a, b}, x3 {, , }, x4 {1, 2}} {(2, d, , 3, b)}. Ermitteln Sie a)

alle Elemente von ⇢,

b)

die Projektion von ⇢ auf 3, also ⇢ ↓3 ,

c)

die Projektion von ⇢ auf 5, also ⇢ ↓5 ,

d)

die Projektion von ⇢ auf I = {1, 3}, also ⇢ ↓{1,3} ,

e)

die Projektion von ⇢ auf I = {3, 4}, also ⇢ ↓{3,4} ,

f)

die Verkettung von ⇢ ↓{1,3} und ⇢ ↓{3,4} ,

g)

das kartesische Produkt von ⇢ ↓{1,3} und ⇢ ↓{3,4} (Def. 2.12),

h)

die Selektion sel1,4 ' (⇢), wobei ' = {(1, 1), (2, 1), (1, 2), (2, 2), (3, 1), (3, 2)} sei,

i)

die Selektion sel3,4  (⇢), wobei  die unter e) berechnete Relation sei.

Aufgabe 3 (Relationen: Projektion (4 Punkte)) Es seien U1 , U2 , , Un Universen, ⇢,  U1 U2 , ik } {1, , n}, wobei i1 < i2 < und I = {i1 , i2 , Es sei ferner (⇢ ) ↓I = . Beweisen Sie: (⇢ ) ↓I ⇢ ↓I

Un Relationen < ik .

 ↓I

Aufgabe 4 (Relationen: Verkettung (3 + 4 Punkte)) ⌧, ⇠ und ⇢ seien 2-stellige Relationen über einem Universum U. Außerdem sei (⌧ ⇠) ⇢ = . a) b)

Beweisen Sie: (⌧ ⇠) ⇢ (⌧ ⇢)

(⇠ ⇢ )

Gilt auch die Gleichheit? Beweisen oder widerlegen Sie.

2

Martin-Luther-Universität Halle-Wittenberg Institut für Informatik Prof. Dr.-Ing. S. Posch, M.Sc. J. Dähne, M.Sc. M. Fröbe, M.Sc. S. Weging

Halle, 10. Dezember 2020 Mathematische Grundlagen der Informatik und Konzepte der Modellierung (WS 2020/2021) Übungsserie 6 Bitte beachten Sie folgende Punkte: Kommentieren Sie Ih...