TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Gruppen Mittwoch

Aus VoWi
Zur Navigation springen Zur Suche springen
UE1 77 83 85 89 96 97
UE2 4 16 24 27 33 39
UE3 45 57 69 104 118 132
UE4 142 148 154
UE5 155 167 178 187 196 200
UE6 270 286 302 290 306 312
UE7 297 308 315 320 210 216
UE8 219 235 242
UE9 331 358 360 386 367 381
UE10 391 395 406 412 437 457
UE11 504 485 516 549 559 530
UE12 538 564 579

Übung 1

Beispiel 77

Entscheiden Sie mit Hilfe einer Wahrheitstafel, ob die folgende Äquivalenz richtig ist.

(a \wedge \neg b) \wedge \neg c \Leftrightarrow a \wedge \neg(b \wedge \neg c)

Beispiel 83

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 83

Beispiel 85

Man bestimme alle m,n ∈ N, für welche die Prädikate P(n) bzw. P(n,m) in eine wahre Aussage übergehen.
(a) P(n): n! ≤ 10n

(b) P(n): (n2 −5n−6 ≥ 0) ⇒ (n ≤ 10)


(c) P(n,m) : (m = n!) ⇒ (m ist durch 10 teilbar)

Beispiel 89

Beweisen Sie die folgende Beziehung mit Hilfe von Elementtafeln oder geben Sie ein konkretes Gegenbeispiel an:

 (A \setminus B)  \setminus C \qquad = \qquad A \setminus (B \setminus C)

Beispiel 96

Beweisen Sie die folgenden Beziehung mit Hilfe von Elementtafeln oder geben Sie ein konkretes Gegenbeispiel an:

 A \triangle (B \cap C) \qquad = \qquad (A \triangle B) \cap (A \triangle C)

Beispiel 97

Beweisen oder widerlegen Sie die folgenden Identitäten für Mengen:

 (A \times B) \cap (B \times A) = (A \cap B) \times (A \cap B)

Übung 2

Beispiel 4

Beweisen Sie mittels vollständiger Induktion:

 \sum_{j=2}^{n} j(j-1) = \frac{(n-1)n(n+1)}{3} \qquad ( n \geq 2 )

Induktionsanfang:  n = 2

Ergibt

 2(2-1) = \frac{(2-1)2(2+1)}{3}

 2 = \frac{1*2*3}{3}

Induktionsannahme:

 \sum_{j=2}^{n} j(j-1) = \frac{(n-1)n(n+1)}{3} \qquad

Induktionsvorraussetzung/Induktionsbehauptung: Es muss gezeigt werden dass gilt:

 \sum_{j=2}^{n+1} j(j-1) = \frac{(n)(n+1)(n+2)}{3}

(Alle n durch n+1 ersetzt)

Induktionsschluss: (Nachweis der Induktionsvorraussetzung)

Die rechte Seite wird mit (n+1)(n+1-1) addiert. Im folgenden wird nur die rechte Seite gerechnet - es soll sich ergeben:  \frac{(n)(n+1)(n+2)}{3}

 \frac{(n-1)n(n+1)}{3} + (n+1)(n) =

 = \frac{(n-1)n(n+1) + 3(n+1)(n)}{3} =

 = \frac{n((n-1)(n+1) + 3(n+1))}{3} =

 = \frac{n(n+1)((n-1) + 3)}{3} =

 = \frac{n(n+1)(n+2)}{3}

Q.e.d.

Ergänzung: linke Seite

 \sum_{j=2}^{n+1} j(j-1)=

 \sum_{j=2}^{n} j(j-1)+ n(n+1)

Beispiel 16

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge x_{0}=1 und x_{k+1}=ax_{k}+b für k\geq0 (wobei a,b \in \mathbb{R},a\neq1) allgemein gilt:

x_{n}=a^{n}+b*\frac{a^{n}-1}{a-1}, für alle n\geq0.

Beispiel 24

Wo steckt der Fehler im "Beweis" der Behauptung:

Je zwei natürliche Zahlen a,b sind gleich groß.

Beweis: vollständige Induktion nach dem \max\{a, b\}

a) \max\{a, b\} = 0: Hier gilt a = b = 0. Induktionsanfang

b) Die Behauptung gelte für \max\{a, b\} = n. Induktionsbehauptung

Sei nun \max\{a, b\} = n + 1. Dann ist \max\{a-1, b-1\} = n.

Es folgt aus der Induktionsvoraussetzung b), daß a-1 = b-1, womit auch a = b gilt.

möglicher Fehler: Beschränkung des Definitionsbereichs auf die "Natürlichen Zahlen", d.h. Werte

kleiner als 0 (negative Zahlen sind nicht zulässig.

Ist \max\{a, b\}=n+1= 0, dann wäre \max\{a-1, b-1\}=n \text{oder} -1 (keine natürliche Zahl)

Hapi

-- (Anm. (Baccus): Kommt mir zwar nach wie vor spanisch vor :-), wurde aber von unserem UE-Leiter heute so akzeptiert, bzw. auch so erklärt!).

-- (Anm. (Blµb): Nun, der Induktionsanfang ist max{a,b} = n, nicht = n+1, daher fallen negative Zahlen weg. Habe meine Lösung dazugeschrieben.)

Beispiel 27

Zeigen Sie, dass  \sqrt{6} irrational ist!

Beispiel 33

Man bestimme rechnerisch (ohne Taschenrechner) und graphisch Summe und Produkt der komplexen Zahlen z_1 = 3-4i und {\textstyle z_2 = [2,\frac{\pi}{2}]}.

Beispiel 39

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 39

Übung 3

Beispiel 45

Man zeige \left |\frac{z_1 + z_2}{2}\right |^2 + \left |\frac{z_1 - z_2}{2}\right |^2 = \frac{1}{2}(\left | z_1 \right |^2 + \left | z_2 \right |^2)

Beispiel 57

Man bestimme zwei ganze Zahlen x, y, welche die Gleichung 243x + 198y = 9 erfüllen.

Beispiel 69

Im europäischen Artikelnummersystem EAN werden Zahlen mit 13 Dezimalziffern der Form a_1 a_2...a_{12} p verwendet. Dabei wird die letzte der 13 Ziffern, das ist die Prüfziffer p im EAN-Code so bestimmt, dass

 a_1 + 3a_2 + a_3 + 3a_4 + ... + a_{11} + 3a_{12} + p \equiv 0 \mod 10

gilt. Man zeige, dass beim EAN-Code ein Fehler in einer einzelnen Ziffer stets erkannt wird, während eine Vertauschung von zwei benachbarten Ziffern genau dann nicht erkannt wird, wenn die beiden Ziffern gleich sind oder sich um 5 unterscheiden.

Beispiel 104

Man untersuche nachstehend angeführte Relationen R\subseteq{M^2} im Hinblick auf die Eigenschaften Reflexivität (R), Symmetrie (S), Antisymmetrie (A) und Transitivität (T):

a) M = \text{Menge aller Einwohner von Wien (Volkszählung 2001)}, a R b \Leftrightarrow a \text{ ist verheiratet mit } b

b) M \text{ wie oben}, a R b \Leftrightarrow a \text{ ist nicht aelter als }b

c) M \text{ wie oben}, a R b \Leftrightarrow a \text{ ist so gross wie }b

d) M = \mathbb R, a R b\Leftrightarrow a-b\in\mathbb Z

e) M = \mathbb R^n, (x_1,...,x_n) R (y_1,...,y_n) \Leftrightarrow x_i\leq y_i \forall i=1,...,n

Beispiel 118

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 118

Beispiel 132

Untersuchen Sie, ob es sich bei den folgenden Relationen  R \subseteq A \times B um Funktionen, injektive Funktionen, surjektive Funktionen bzw. bijektive Funktionen handelt.

R = \{ (\log_2 x, x) \  | \  x \in \mathbb{R}_{+} \}, A = B = \mathbb{R}

Übung 4

Beispiel 142

Man zeige, dass die Funktion f: \mathbb{R \setminus \{\textrm{6}\}} \rightarrow \mathbb{R \setminus \{\textrm{-10}\}}, \quad y=\frac{10x+1}{6-x} bijektiv ist, und bestimme ihre Umkehrfunktion.

Beispiel 148

http://www.inf.fh-flensburg.de/lang/theor/maechtigkeit.htm

Beispiel 154

Von m weißen Kugeln, die mit den Zahlen 1, \dots, m nummeriert sind, sollen k \ge 1 Kugeln schwarz eingefärbt werden. Wieviele derartige Färbungen gibt es unter der Einschränkung, dass die Kugel mit der Nummer n schwarz ist, und alle Kugeln mit einer höheren Nummer weiß bleiben? Erklären Sie, warum aus dem Ergebnis die folgende Gleichung folgt:

\sum_{n=1}^m \binom{n-1}{k-1} = \binom{m}{k}

Übung 5

Beispiel 155

Wieviele Wörter der Länge 28 gibt es, bei denen genau 5-mal der Buchstabe a, 14-mal b, 5-mal c, 3-mal d vorkommen und genau einmal e vorkommt?

Problem ist äquivalent zu "Permutation einer Multimenge", daher:

\frac{(k_{1}+k_{2}+...+k_{n})!}{k_{1}!\cdot k_{2}! \cdot ...\cdot k_{n}!} = \frac{(5+14+5+3+1)!}{5!\cdot14!\cdot5!\cdot3!\cdot1!} = \sim 4,048 \cdot 10^{13}

--Isofx 17:58, 30. Jan. 2012 (CET)

Beispiel 167

Man bestimme für das "6 aus 45"-Lotto die Anzahl der möglichen Fünfer mit Zusatzzahl.

Beispiel 178

Berechnen Sie unter Benützung des Binomischen Lehrsatzes (und ohne Benützung der Differentialrechnung):

\sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}k5^k

Beispiel 187

Bei einem Turnier muss jeder Spieler genau einmal gegen jeden der anderen Spieler antreten. Zeigen Sie: Zu jedem Zeitpunkt des Turniers gibt es mindestens zwei Spieler die dieselbe Anzahl von Spielen bestritten haben.

Beispiel 196

Wieviele natürliche Zahlen n mit 1 \leq n \leq 1000 gibt es, die durch 3, 5 oder 13 teilbar sind? Wie viele sind weder durch 3, noch durch 5 noch durch 13 teilbar?

Beispiel 200

Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g,h in denen weder der Block "acg" noch der Block "cgbe" vorkommt. (Hinweis: Die Anzahl der Permutationen einer n-elementigen Menge ist n!).

Übung 6

Beispiel 270

Achtung! Angabe hat sich zu Beispiel WS07/ Aufgabe 172 geändert

Übungen WS07/Aufgabe 172

TU_Wien:Mathematik_1_UE_(diverse)/Übungen_WS07/Beispiel_172

Beispiel 286

Gegeben sei der ungerichtete Graph  G = \langle V,E \rangle mit V = \{a,b,c,d,e\} und E = \{ab,ac,ae,bc,bd,ce\}. Man veranschauliche G graphisch, bestimme seine Adjazenzmatrix sowie alle Knotengrade und zeige, dass die Anzahl der Knoten, die einen ungeraden Knotengrad besitzen, gerade ist. Gilt diese Aussage für jeden ungerichteten Graphen?

Beispiel 302

Unter n Mannschaften wird ein Turnier ausgetragen, und es haben insgesamt schon n + 1

Spiele stattgefunden. Man zeige, dass mindestens eine Mannschaft dann bereits an mindestens 3 Spielen teilgenommen hat.

Beispiel 290

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 290

Beispiel 306

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 306

Beispiel 312

Zum Abarbeiten der Knoten eines Binärbaumes verwendet man gerne rekursive Algorithmen, die in wohldefinierter Reihenfolge die folgenden Schritte ausführen:
(1) Bearbeite den aktuellen Knoten,
(2) Gehe zur Wurzel des linken Nachfolgebaums des aktuellen Knotens,
(3) Gehe zur Wurzel des rechten Nachfolgebaums des aktuellen Knotens.
Am Beginn steht man bei der Wurzel des Gesamtbaumes. Führt man die genannten Schritte (1) bis (3) rekursiv in der angegebenen Reihenfolge aus, so spricht man von Präordertraversierung. Beim untenstehenden Baum werden die Knoten also in folgender Reihenfolge bearbeitet: A;B;D;E;H; I;C; F;G. Wie ändert sich diese Reihenfolge, wenn man im Algorithmus jeweils die Abfolge (2)(1)(3) nimmt (Inordertraversierung), wie wenn man die Abfolge (2)(3)(1) wählt (Postordertraversierung)?

Beispiel210.jpg

Übung 7

Beispiel 297

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 297

Beispiel 308

Siehe https://web.archive.org/web/*/http://www.mathematik.uni-muenchen.de/~fritsch/GRAPHEN1.pdf auf Seite 41

(man darf hier ja den urheberrechtlich geschützten Text nicht einfügen...)

Beispiel 315

Man bestimme im folgenden Graphen H mit Hilfe des Kruskalalgorithmus einen minimalen und maximalen spannenden Baum. (nur minimaler verlangt => http://www.algebra.tuwien.ac.at/institut/inf/inf_panholzer/index1_WS05.html

Beispiel 320

Im nachstehenden bewerteten Graphen bestimme man den Entfernungsbaum bezüglich des Knotens v_0.

Bsp212 1.png

Beispiel 210

{{Beispiel|status=Datei|1= Man bestimme die allgemeine Lösung der Differenzengleichung

x_{n+1} = \frac{2}{3}x_n + 1 (für n \geq 0)

und die partikuläre Lösung, die der Anfangsbedingung x_0 = 6 genügt.

Beispiel 216

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 216

Übung 8

Beispiel 219

Gesucht ist die allgemeine Lösung der linearen homogenen Differenzengleichungen

(a) x_{n+2} - 7x_{n+1} + 12x_n = 0

(b) x_{n+2} + x_{n+1} + x_n = 0

(c) x_{n+2} - 8x_{n+1} + 16x_n = 0

Beispiel 235

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 235

Beispiel 242

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 242

Übung 9

Beispiel 331

Gegeben seien die folgenden binären Operationen \bullet auf der Menge A. Man untersuche die Operationen in Hinblick auf Assoziativität, Kommutativität sowie auf Existenz von neutralen oder inversen Elementen.

(a) A = \{-1,0,1\}, \bullet \text{gewoehnliche Multiplikation}

(b) A = \mathbb N, a \bullet b = 2^{ab}

(c) A = \mathbb Q, a \bullet b = ab + 1

(d) A = \mathbb R, a \bullet b = |a + b|

(e) A \neq \emptyset, a \bullet b = a

Beispiel 358

Man ergänze die folgende Operationstafel so, daß <G={a,b,c,d},*> eine Gruppe ist:

\begin{array}{c|cccc}
* & a & b & c & d\\\hline
a& a\\
b&&&a\\
c&\\
d&&&&a
\end{array}

Beispiel 360

Man zeige: Eine nichtleere Teilmenge U einer Gruppe G (mit neutralem Element e) ist genau dann Untergruppe von G, wenn die Bedingungen

(i) a,b \in U \Rightarrow ab \in U
(ii) e \in U
(iii) a \in U \Rightarrow a^{-1} \in U

für alle a,b \in G erfüllt sind. Das ist weiters genau dann der Fall, wenn

(iv) a,b \in U \Rightarrow ab^{-1} \in U

für alle a,b \in G gilt (Untergruppenkriterium).

Beispiel 386

Bestimmen sie alle Untergruppen von \langle\mathbb{Z}_{12},+\rangle

\mathbb{Z}_{12}=\{\overline{0},\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6},\overline{7},\overline{8},\overline{9},\overline{10},\overline{11}\}

Beispiel 367

In der Symetriegruppe des Quadrats aus Aufgabe 253 bestimme die Rechts- bzw. Linksnebenklassenzerlegung nach einer

a.) von einer Drehung b.) von einer Spiegelung erzeugten Untergruppe.

Beispiel 381

Seien \varphi:G\rightarrow H und \psi:H\rightarrow K Gruppenhomomorphismen. Man zeige: \psi\circ\varphi: G\rightarrow K ist auch ein Gruppenhomomorphismus.

Übung 10

Beispiel 391

Seien (G, ∗) und (H, ·) zwei Gruppen. Untersuchen Sie, ob (G × H, ◦) mit (a, b) ◦ (c, d) = (a ∗ c, b · d) ebenfalls eine Gruppe ist

Beispiel 395

Von der Abbildung f : \left( \mathbb{Z}_3 \right)^2 \rightarrow \left( \mathbb{Z}_3 \right)^4 sei bekannt, dass f ein Gruppenhomomorphismus bezüglich der Addition ist (die jeweils komponentenweise definiert sein soll), sowie dass f \left( 1, 0 \right) = \left( 1, 0, 0, 2 \right), f \left( 1, 1 \right) = \left( 1, 2, 0, 1 \right). Man ermittle daraus f \left( w \right) für alle w \in \left( \mathbb{Z}_3 \right)^2

Beispiel 406

Untersuchen Sie, ob die folgende Struktur ein Ring, Integritätsbereich bzw. Körper ist:

M = \mathbb{Q}[\sqrt{5}] = \{a + b*\sqrt{5} | a,b \in \mathbb{Q}\} mit der Addition und Multiplikation aus \mathbb{R}.

Beispiel 412

Von der Menge K \subseteq \C sei bekannt:

i) \R \subseteq K

ii) 1 + 3i \in K

iii) <K, +, \cdot> ist ein Körper (mit der Addition bzw. Multiplikation aus \C).

Zeigen Sie, dass K = \C sein muss.

Beispiel 437

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 437

Beispiel 457

Untersuchen Sie, ob W Teilraum des Vektorraums V=\mathbb{R}^3 über \mathbb{R} ist und beschreiben Sie die Menge W geometrisch:

W=\{(x, y, z)\in V\;|\;x+y+z \le 0\}

Übung 11

Beispiel 504

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 504

Beispiel 485

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 485

Beispiel 516

Sei V=\mathbb{C}^3, U=\{(z_1, z_2, z_3)\in V|z_1=2z_2=3z_3\}, W=\{(z_1,z_2,z_3)\in V|z_2=0\}. Zeigen Sie, daß U und W Teilräume von V sind und bestimmen Sie deren Dimension.

Beispiel 549

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 549

Beispiel 559

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 559

Beispiel 530

Übung 12

Beispiel 538

Bestimmen Sie mit dem Gauß'schen Eliminationsverfahren die Lösung des Gleichungssystems über dem Körper K:

a) K=\mathbb{R}

b) K=\mathbb Z_2


\begin{align}
-3x_1 &+ x_2 + 2x_3 &+ x_4 &= 2\\
-x_1 &+ x_2 + x_3 &- x_4 &= 1\\
-5x_1 &+ x_2 + 3x_3 &+ 3x_4 &= 1
\end{align}

Beispiel 564

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 564

Beispiel 579

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 579