Lösungsvorschlag Diskrete Mathematik FS16

Aus VISki
Wechseln zu: Navigation, Suche

Prüfung vom 26. August 2016.

Kurzaufgaben

a)

b)

c)

Nein.

d)


e)


f)



g)

Jedes Element ungleich Null ist entweder Unit (besitzt ein Inverses Element) oder Nullteiler.

Fehler beim Parsen (Syntaxfehler): {\displaystyle \vert{\mathbb{Z}_{30}}\vert = 30 \\ \vert{\mathbb{Z}^{\ast}_{30}}\vert = \phi(30) = (2-1)\cdot 2^{1-1} \cdot (3-1) \cdot 3^{1-1} \cdot (5-1)\cdot 5^{1-1} = 8 \\ 30-8-1=21 }

h)

Keinen, 10 ist keine Primzahlpotenz

i)

Fehler beim Parsen (Syntaxfehler): {\displaystyle \forall{y}( \exists{z}\: P(x,y,z) \wedge \forall x\: \neg Q(x)) \\ \forall{y}( \exists{z}\: P(x,y,z) \wedge \forall u\: \neg Q(u)) \\ \forall{y}\exists{z}\:\forall u\:(P(x,y,z) \wedge \neg Q(u)) \\ }

Die freie Variable darf nicht umbenannt werden.

Mengen, Relationen und Funktionen

a)

reflexiv: falsch,

irreflexiv: korrekt

symmetrisch: korrekt

anti-symmetrisch: falsch,

transitiv: falsch, aber

b)

c)

d)

Kombinatorik und Abzählbarkeit

a)

b)

c)

Graphentheorie

a)

b)

Zahlentheorie

a)

zu Zeigen:

Power: 1 2 3 4 5 6 7 8 9 10
Number: 2 4 8 16 32 64 128 256 512 1024
Mod 11: 2 4 8 5 10 9 7 3 6 1
Power: 1 2 3 4 5
Number: 3 9 27 81 243
Mod 11: 3 9 5 4 1


Fehler beim Parsen (Syntaxfehler): {\displaystyle R_{11}(2^{2016} + 3^{2016} -1) \\ = R_{11}(R_{11}(2^{2016}) + R_{11}(3^{2016}) + R_{11}(-1)) \\ = R_{11}(R_{11}(2^{2016}) + R_{11}(3^{2016}) + R_{11}(10)) \\ = R_{11}(R_{11}(2^{201 \cdot 10+6}) + R_{11}(3^{5 \cdot 403+1}) + 10) \\ = R_{11}(R_{11}(2^{201 \cdot 10}\cdot 2^6) + R_{11}(3^{5\cdot 403} \cdot 3^1) + 10) \\ = R_{11}(R_{11}(R_{11}(2^{10})^{201}\cdot R_{11}(2^6)) + R_{11}(R_{11}(3^{5})^{403} \cdot R_{11}(3)) + 10) \\ = R_{11}(R_{11}((1)^{201}\cdot R_{11}(2^6)) + R_{11}((1)^{403} \cdot R_{11}(3)) + 10) \\ = R_{11}(R_{11}(2^6) + R_{11}(3) + 10) \\ = R_{11}(R_{11}(64) + R_{11}(3) + 10) \\ = R_{11}(9 + 3 + 10) \\ = R_{11}(22) = 0 \\ }

b) Wir beweisen die stärkere Aussage: Für jedes gilt oder oder

oder oder oder oder

Laut Theorem 4.1 (Skript 2016) , wobei

Fallunterscheidung:

Da es für alle gilt, gilt es insbesondere für die Ungeraden. □

c) Aussage: 5 ist die einzige Primzahl, die sowohl als Summe als auch als Differenz zweier Primzahlen geschrieben werden kann.

Wir sehen sofort, dass 2 und 3 nicht als Summen zweier Primzahlen geschrieben werden können. Wir müssen die Aussage also noch für Primzahlen >5 beweisen. 2 ist die einzige gerade Primzahl (denn alle Primzahlen >2 haben den Primfaktor 2 keine PZ). Folglich muss einer der Summanden immer 2 sein (, da die Summe zweier ungeraden Zahlen eine gerade Zahl ergibt und das keine PZ sein kann). Der andere Summand muss sein (und natürlich eine PZ). Wir schreiben ihn wie folgt , wobei ungerade ist. Gemäss Teilaufgabe (b) ist oder oder für jede ungerade Zahl wahr. ist offensichtlich falsch, da laut unserer Annahme eine Primzahl ist. Also wird entweder oder durch drei geteilt. In anderen Worten: 3 teilt entweder die Summe oder Differenz zwischen einer beliebigen Primzahl und 2. □

Algebra

a) Beweis mit Widerspruch: Sei eine Gruppe. Sei die multiplikative Gruppe von . Laut Lagrange muss gelten Widerspruch! gerade teilt ungerade.

b) Fehler beim Parsen (Syntaxfehler): {\displaystyle \{0\}\} ,Fehler beim Parsen (Syntaxfehler): {\displaystyle \{0,2\}\} ,Fehler beim Parsen (Syntaxfehler): {\displaystyle \{0,1,2,3\}\}
Jede Ordnung der Untergruppe muss nach LaGrange die Ordnung der Gruppe teilen.

c)

d) Gemäss dem rechts- und linksdistributiven Gesetz (Ringaxiom 3) haben wir:

Fehler beim Parsen (Syntaxfehler): {\displaystyle (1+1)(a+b)=(1+1)a + (1+1)b=a+a+b+b\\ (1+1)(a+b)=1(a+b) + 1(a+b)=a+b+a+b }

Die Addition mit den Inversen (Subtraktion) von und ergibt somit:

Logik und Beweise

a)

b)

c)

d)