TU Wien:Algebra und Diskrete Mathematik VO (Karigl)/Prüfung 2016-09-30

Zeit: 100 Minuten

Aufgabe 1

Wie viele natürliche Zahlen n mit $1\leq n\leq 10^{6}$ gibt es, die weder durch 2 teilbar, noch Quadratzahlen, noch dritte Potenzen natürlicher Zahlen sind?

Aufgabe 2

Sei G die Gruppe der Permutationen $\{(1),(12),(123),(13),(132),(23)\}$ bezüglich der Komposition von Abbildungen. Man interpretiere diese Permutation als Symmetrieoperation (Drehung und Spiegelungen) eines gleichseitigen Dreiecks. Ferner gebe man die Gruppentafel, das neutrale Element sowie alle inversen Elemente an und bestimme alle Untergruppen von G.

Aufgabe 3

Für welche Werte des Parameters u besitzt die Matrix

$A={\begin{pmatrix}-2&1&u\\0&-2&5\\5&-2&15\end{pmatrix}}$

eine inverse Matrix?

Aufgabe 4

Bäume und Wälder:

• Was versteht man in der diskreten Mathematik unter einem Baum, was unter einem Wald? Geben Sie je ein Beispiel an.
• Charakterisieren Sie Bäume und Wälder mit Hilfe von Wegen (ohne Beweis).
• Was ist ein spannender Baum bzw. spannender Wald, was ist ein Wurzelbaum, ein Binärbaum? Man gebe je ein Beispiel an.

Aufgabe 5

Es sei $P(n)$ eine Aussage für natürliche Zahlen $n\in \mathbb {N}$, die durch vollständige lnduktion bewiesen werden soll. Man beantworte dazu folgende Fragen bzw. überprüfe nachstehende Aussagen (bitte ankreuzen; es können keine, genau eine oder auch mehrere Antworten zutreffend sein):

Pluspunkt für eine richtige Antwort:
Punkte für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

	Der Induktionsbeweis besteht aus einem Induktionsanfang und einem Induktionsschritt.
	Die Aussage P(n) kann auch als Ungleichung formuliert sein.
	Der Induktionsbeweis ist auch für Aussagen $P(n)$ für $n\in \mathbb {Q}$ zulässig.
	Das Induktionsprinzip lautet in der Sprache der Logik: $P(0)\land (\forall n\in \mathbb {N} \colon P(n)\land P(n+1))\Rightarrow \forall n\in \mathbb {N} \colon P(n)$

2 Der Induktionsanfang kann sich auf folgende Werte von n beziehen:

	n = 0
	n = 1
	n beliebig

3 Im Induktionsschritt muss bewiesen werden:

	$P(n)$
	$P(n+1)$
	$P(n)\Rightarrow P(n+1)$

Geben Sie schließlich ein Beispiel für eine Aussage P(n) an, die nicht gültig ist,

(a) obwohl der Induktionsanfang erüllt ist bzw.

(b) obwohl der Induktionsschluss richtig ist.