TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Gruppen Montag

UE1		6	11	14	19	23	26
UE2		31	33	52	62	65	69
UE3		76	91	97	105	108	121
UE4		137	141
UE5		154	160	191	286	305	321
UE6		337	355	363	368	373	379
UE7		324	393	Z1	412	422	427
UE8		441a	444
UE9		447	453	456	475	500	506
UE10		514	517	523	539	565	573
UE11		542	581	587	592	210	218
UE12		222	241

Übung 1

Beispiel 6

Man beweise mittels vollständiger Induktion:

$\sum _{j=0}^{n}j2^{j}=2^{n+1}(n-1)+2\qquad (n\geq 0)$

Beispiel 11

Ist $F_{0}=0$,$F_{1}=1$ und $F_{n+2}=F_{n+1}+F_{n}$ für alle $n\in \mathbb {N}$, so gilt

$F_{n}={1 \over {\sqrt {5}}}{\Bigg [}{\Bigg (}{1+{\sqrt {5}} \over 2}{\Bigg )}^{n}-{\Bigg (}{1-{\sqrt {5}} \over 2}{\Bigg )}^{n}{\Bigg ]}$

Beispiel 14

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge $x_{1}=1$ und $x_{k+1}=x_{k}+8k$ für $1\leq k$ allgemein gilt:

$x_{n}=(2n-1)^{2}$, für alle $1\leq n$

Beispiel 19

Man untersuche mittels vollständiger Induktion, für welche $n\geq 0$ die angegebene Ungleichung gilt:

$4n^{2}\leq 2^{n}$

Beispiel 23

Wo steckt der Fehler im Induktions-”Beweis“ der folgenden Behauptung:

Ist in einer Gruppe von Personen eine Person blond, so sind alle blond.

Beweis:

a) $n=1$: Hier stimmt die Behauptung trivialerweise.

b) Die Behauptung gelte für Gruppen der Größe $n$. Nun sei von $n+1$ Personen eine blond. Man betrachte diese Person zusammenmit $n-1$ weiteren. Dann sind nach Induktionsannahme diese $n-1$ Personen auch blond. Folglich ist in der Gruppe dieser $n-1$ Personen zusammen mit der noch nicht betrachteten Personen wieder wenigstens eine blond, woraus folgt, daß auch diese letzte Person blond sein muss.

Beispiel 26

Zeigen Sie, dass ${\sqrt {5}}$ irrational ist!

Übung 2

Beispiel 31

Man finde alle sechsten Wurzeln von $z=8i$ in $\mathbb {C}$ und stelle sie in der Gaußschen Zahlenebene dar!

Beispiel 62

Lösen Sie die folgenden Kongruënzen (d.h. Gleichungen in Restklassen) bzw. beweisen Sie die Unlösbarkeit:

• $8x\equiv 4\;({\text{mod}}\ 16)$
• $8x\equiv 4\;({\text{mod}}\ 15)$

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.

Übung 3

Beispiel 76

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

$a\wedge (b\vee c)\Leftrightarrow (a\wedge b)\vee (a\wedge c)$

Beispiel 91

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

$(A\cup B)\cap (B\cup C)'\qquad \subseteq \qquad A\cap B'$

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)$

Beispiel 105

Man zeige, daß durch $aRb\Leftrightarrow 3|a^{2}-b^{2}$ für alle $a,b\in \mathbb {Z}$ eine Äquivalenzrelation $R$ in der Menge $\mathbb {Z}$ erklärt wird, und bestimme die zugehörende Partition.

Beispiel 108

Stellen Sie die folgenden Relationen im kartesischen Koordinatensystem und auch als gerichteten Graphen dar, und untersuchen Sie weiters, ob eine Äquivalenzrelation vorliegt.

$mRn\iff m+n{\text{ gerade}},m,n\in \{2,3,4,5\}$

Beispiel 121

Für $k,n\in \lbrace 1,3,4,\ldots ,10\rbrace$ sei $kRn$, falls $k$ ein Teiler von $n$ ist und $k$ und ${\frac {n}{k}}$ teilerfremd sind. Man untersuche, ob die Relation R eine Halbordnung ist und ermittle gegebenfalls das Hassediagramm.

Übung 4

Beispiel 137

Seien $f:A\rightarrow B$ und $g:B\rightarrow C$ surjektive Abbildungen. Man zeige, dass dann auch $h=g\circ f:A\rightarrow C$ surjektiv ist. ($(g\circ f)(x)=g(f(x))$)

Beispiel 141

Man zeige, daß die Funktion $f:\mathbb {R\setminus \{{\textrm {7}}\}} \rightarrow \mathbb {R\setminus \{{\textrm {2}}\}} ,\quad y={\frac {2x+1}{x-7}}$ bijektiv ist und bestimme ihre Umkehrfunktion.

Übung 5

Beispiel 154

Von $m$ weißen Kugeln, die mit den Zahlen $1,\dots ,m$ nummeriert sind, sollen $k\geq 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}}$

Beispiel 160

Wieviele Möglichkeiten gibt es, aus einem 50-bändigen Lexikon genau 6 Bücher auszuwählen,wobei zwischen zwei ausgewählten Bänden immer mindestens drei im Regal stehen bleiben sollen?

Beispiel 191

Wieviele natürliche Zahlen n mit $1\leq n\leq 10^{6}$ gibt es, die weder Quadrat, noch dritte, vierte oder fünfte Potenz einer natürlichen Zahl sind?

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 305

Man bestimme alle Bäume T, für die auch $T^{K}$ ein Baum ist. $T^{K}$ bezeichne einen komplementären Graphen definiert durch: $V(T^{K})=V(T)$ und $E(T^{K})=(V\times V)\setminus (E(T)\cup \lbrace (x,x)\mid x\in V\rbrace )$

Beispiel 321

Bestimmen Sie mit dem Algorithmus von Dijkstra einen kürzesten Weg zwischen den Knoten x und y im folgenden Graphen:

Übung 6

Beispiel 337

Untersuchen Sie, ob die Menge M mit der Operation $\circ$ ein Gruppoid, eine Halbgruppe, ein Monoid bzw. eine Gruppe ist:

$M=\{z\in \mathbb {C} \mid |z|=2\},z_{1}\circ z_{2}={\frac {z_{1}z_{2}}{2}}$

Beispiel 355

Man ergänze die folgende Operationstafel so, daß $\left\langle G=\left\{a,b,c,d\right\},*\right\rangle$ eine Gruppe ist:

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

Beispiel 363

Man bestimme alle Untergruppen der Gruppe $S_{3}$ aller Permutationen von drei Elementen mit der Operation der Hintereinanderausführung.

Beispiel 368

Sei U die von (1)(23) erzeugte Untergruppe der $S_{3}$. Man bestimme die Rechtsnebenklassen von U. Ist U ein Normalteiler von $S_{3}$?

Beispiel 373

Man zeige, daß die von ${\overline {4}}$ erzeugte Untergruppe $U$ von $\langle \mathbb {Z} _{12},+\rangle$ ein Normalteiler von $\langle \mathbb {Z} _{12},+\rangle$ ist und bestimme die Gruppentafel der Faktorgruppe $\mathbb {Z} _{12}/U$.

Beispiel 379

Sei $\varphi :G\to H$ ein Gruppenhomomorphismus. Man zeige, dass dann $\varphi (G)$ eine Untergruppe von $H$ ist.

Hinweis: Das Beispiel entspricht der Übungsaufgabe 2.36 aus dem Buch Mathematik für Informatik.

Übung 7

Beispiel 324

Man bestimme zu den Permutationen

$\sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\1&4&5&2&3&7&6&8\end{pmatrix}},\qquad \rho ={\begin{pmatrix}1&2&3&4&5&6&7&8\\5&4&2&1&8&7&6&3\end{pmatrix}}$

die Permutationen $\sigma \circ \rho ^{2}$ und $\sigma ^{-1}\rho ^{-1}\sigma ^{2}$ sowie deren Zyklendarstellungen und Vorzeichen.

Beispiel 393

Von der Abbildung $f:(\mathbb {Z} _{3})^{2}\rightarrow (\mathbb {Z} _{3})^{4}$ sei bekannt, daß $f$ ein Gruppenhomomorphismus bezüglich der Addition ist (die jeweils komponentenweise definiert sein soll), sowie dass

${\begin{aligned}f(0,1)=(0,1,1,2)\\f(1,0)=(1,0,2,0)\end{aligned}}$.

Man ermittle f $(w)$ für alle $w$ Element von $(\mathbb {Z} _{3})^{2}.$

Beispiel Z1

Betrachten Sie die Gruppe $(\mathbb {C} \setminus \{0\},\cdot )$.

Sei $U=\{z\in \mathbb {C} \mid |z|=1\}$. Zeigen Sie, dass $U$ ein Normalteiler von $(\mathbb {C} \setminus \{0\},\cdot )$ ist.

Zeigen Sie weiters, dass $f:\mathbb {C} \setminus \{0\}\rightarrow \mathbb {C} \setminus \{0\},z\mapsto |z|$ ein Gruppenhomomorphismus ist.

Verwenden Sie diesen und den Homomorphiesatz, um eine zu $\mathbb {C} \setminus \{0\}/U$ isomorphe Untergruppe von $(\mathbb {C} \setminus \{0\},\cdot )$ zu finden.

Beispiel 412

Von der Menge $K\subseteq \mathbb {C}$ sei bekannt:

i) $\mathbb {R} \subseteq K$

ii) $1+3i\in K$

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

Zeigen Sie, dass $K=\mathbb {C}$ sein muss.

Beispiel 422

Sei $\langle R,+,*\rangle$ ein Ring. Man zeige, dass dann auch $R\times R$ mit den Operationen

$(a,b)+(c,d)=(a+c,b+d)$ $(a,b)*(c,d)=(a*c,b*d)$

ein Ring ist.

Beispiel 427

Man ermittle, ob beim Übergang von $R$ zu $R\times R$ (Beispiel 422) die folgenden Eigenschaften erhalten bleiben:

1. Kommutativität,
2. Nullteilerfreiheit,
3. Existenz eines Einselements.

Übung 8

Beispiel 441

Nur teilweise gelöst: b) ist ungelöst.

Man zeige, dass die folgenden algebraischen Strukturen Verbände sind. Welche sind außerdem distributiv, und welche sind Boolesche Algebren

a) $(\mathbb {R} ,\mathrm {min} ,\mathrm {max} )$

b) $(\mathbb {N} \setminus \{0\},\mathrm {ggT} ,\mathrm {kgV} )$

Beispiel 444

Sei $M$ die Menge aller Teiler von 60. Bestimmen Sie alle Komplemente in $(M,ggT,kgV)$. Ist diese Struktur eine Boolsche Algebra?

Übung 9

Beispiel 447

Bildet $\mathbb {R} ^{2}$ mit den angegebenen Operationen einen Vektorraum über $\mathbb {R}$

$(x_{1},x_{2})+(y_{1},y_{2})=(x_{1}+y_{1},0),\lambda (x_{1},x_{2})=(\lambda *x_{1},0)$

Beispiel 453

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=2y\}$

Beispiel 456

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\;|\;xy=0\}$

Beispiel 475

Bestimmen Sie den kleinsten Teilraum des Vektorraumes aus 474) der die Polynome $x$ und $x^{3}$ enthält.

Übung 10

Beispiel 514

Sei $V=\mathbb {C} ^{3},$

${\begin{aligned}U&=\{(z_{1},z_{2},z_{3})\in V\mid z_{1}+z_{2}=z_{3}\},\\W&=\{(z_{1},z_{2},z_{3})\in V\mid z_{2}=-z_{1}\}.\end{aligned}}$

Zeigen Sie, dass $U$ und $W$ Teilräume von $V$ sind und bestimmen Sie deren Dimension.

Beispiel 523

Sei $U$ die Menge aller $n\times n$-Matrizen $B$ über $\mathbb {R}$ mit ${\text{det }}B=\pm 1$. Man zeige, dass $U$ Normalteiler von der Gruppe $\langle G,\cdot \rangle$ aller regulären $n\times n$ Matrizen A über $\mathbb {R}$ ist (Gruppe aus Bsp. 522) .

Beispiel 565

Man berechne:

$\left|{\begin{array}{rrrr}1&3&-1&5\\2&7&0&2\\-1&-2&4&0\\1&2&-5&-3\end{array}}\right|$

Beispiel 573

Nur teilweise gelöst: b) fehlt

a) Für welche $x\in \mathbb {Q}$ ist die Matrix A singulär?

$A={\begin{pmatrix}x&2&2\\1&1&x\\1&x&-1\end{pmatrix}}$

b) Bestimmen Sie für $x=1$ die inverse Matrix $A^{-1}$.

Übung 11

Beispiel 542

Wir betrachten Systeme von drei Ebenengleichungen $f_{i}(x,y,z)=a_{i1}x+a_{i2}y+a_{i3}z=bi$ mit Lösungsmengen $L_{i}\subseteq \mathbb {R} ^{3},i=1,2,3$. Geben Sie jeweils eine Systemmatrix

${\begin{pmatrix}a_{11}&a_{12}&a_{13}&b_{1}\\a_{21}&a_{22}&a_{23}&b_{2}\\a_{31}&a_{32}&a_{33}&b_{3}\end{pmatrix}}$

mit geeigneten $a_{ij}$ und $b_{i}$ aus $\mathbb {R}$ so an, dass die $L_{i}$ folgende Lage zueinander haben:

(a) $L_{1}\cap L_{2}\cap L_{3}={(1,1,1)}$

(b) $L_{1}\cap L_{2}\cap L_{3}=\emptyset$, und alle drei Schnitte $L_{1}\cap L_{2},L_{1}\cap L_{3}$ und $L_{2}\cap L_{3}$ sind eindimensional und parallel zur z-Achse.

Beispiel 581

Man bestimme die Eigenwerte der Matrix A sowie zu jedem Eigenwert alle Eigenvektoren:

$A={\begin{pmatrix}0&{\frac {1}{2}}&{\frac {1}{2}}\\{\frac {1}{2}}&0&{\frac {1}{2}}\\{\frac {1}{2}}&{\frac {1}{2}}&0\end{pmatrix}}$

Beispiel 587

Gegeben sei die lineare Funktion $f:\mathbb {R} ^{2}\rightarrow \mathbb {R} ^{2}{\text{ mit }}(2,1)\mapsto (-2,4){\text{ und }}(-3,0)\mapsto (0,-6)$

(a) Geben Sie eine geometrische Interpretation von $f$

(b) Wie lautet die Matrixdarstellung für $f$ (bezüglich der kanonischen Basis)?

(c) Lösen Sie das lineare Gleichungssystem $f(x,y)=(8,6)$

(d) Geben Sie sämtliche Eigenwerte mit zugehörigen Eigenvektoren von $f$ an (anschauliche Begründung genügt).

Beispiel 592

Im $\mathbb {R} ^{3}$ sei ein verallgemeinertes Skalarprodukt gegeben durch die Matrix

$G={\begin{pmatrix}13&0&-5\\0&9&-6\\-5&-6&6\end{pmatrix}}$

Berechnen Sie für die Vektoren ${\vec {x}}=(1,2,3){\text{ und }}{\vec {y}}=(3,-1,2)$

(a) die Längen von ${\vec {x}}{\text{ und }}{\vec {y}}$

(b) den Winkel $\varphi {\text{ zwischen }}{\vec {x}}{\text{ und }}{\vec {y}}$

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 218

Gesucht ist die allgemeine Lösung der linearen homogenen Differenzengleichungen

1. (a) $x_{n+2}-5x_{n+1}-6x_{n}=0$
2. (b) $x_{n+2}-6x_{n+1}+12x_{n}=0$
3. (c) $x_{n+2}-5x_{n+1}+6{,}25x_{n}=0$

Übung 12

Beispiel 222

Man bestimme die Lösung nachstehender Differenzengleichung zu den vorgegebenen Anfangsbedingungen:

$4x_{n+2}+12x_{n+1}-7x_{n}=36,\ \ x_{0}=6,x_{1}=3$