Lösungsvorschlag Diskrete Mathematik FS18: Unterschied zwischen den Versionen

Aus VISki
Wechseln zu: Navigation, Suche
K (zusätzliche Lösung zu 4.e.iii)
 
Zeile 1: Zeile 1:
 +
 +
==Other Solutions==
 +
My solutions for this exam (incomplete and without warranty): [https://galli.me/ETH/Lösungen/Discrete%20Mathematics/DiskMat_FS18.pdf]
  
 
=='''1''' a) ==
 
=='''1''' a) ==

Aktuelle Version vom 22. Januar 2019, 10:07 Uhr

Other Solutions

My solutions for this exam (incomplete and without warranty): [1]

1 a)

i) |{1,2} x {1,2,3}| = 6

ii) || = 0, since any element of the natural numbers is also element of the rational numbers.

iii)

1 b)

i)

ii) Claim: transitive transitive.

Proof: transitive . We know that every element of is also a subset of . Therefore, the only element of that needs to be checked is (since ). We know, that every element of is also element of . Therefore we know . This means that we have . The set is therefore transitive.

1) c)

i) Let and countable.

Claim: countable.

Proof: Define and arbitrary. if i even; if i odd. Since , i.e. no element of A and B are the same, we know that we have an injection of C into . Therefore is countable.

ii) Claim: If countable and uncountable, then is uncountable.

Proof: Assume countable. We can affiliate each element of C with one of the sets . We know that both sets are countable. However, we previously proved that then is countable. This is a contradiction to the fact, that C is uncountable! Therefore must be uncountable.

2 a)

1) Yes, an example is on .

2)

2 b)

2 c)

i) Let if even and if odd. We therefore have and .

3 a)

i)

ii) gcd(1188,954) = 18

3 b)

3 c)

Lemma:

If and are relatively prime, then:

Suppose without limitation to the generality that .

Then there are infinitely many numbers , such that is prime and .

For all these k we have , because is only divided by and itself and .

4 a)

4 b)

4 c)

4 d)

Let , .

(distributive law)

(additive inverse and commutativity)

4 e)

Let .

i) Claim: is a field.

Proof: By Lemma 5.35, is a ring. Theorem 5.37 states, that a ring is a field iff irreducible. Therefore we need to show that irreducible. is irreducible, if it has no roots in GF(2): irreducible in .

ii) Claim: All elements of are generators.

Proof: We know that . Since irreducible, contains all elements of except 0. Therefore . 7 is a prime number and by Corollary 5.11 groups of prime order are cyclic and in such groups every element is a generator.

iii) Solve in .

Solution: Let . We then have .

( is also a solution.)

5 a)

5 b)

5 c)

Claim: The resolution calculus is not complete.

Proof: Counterexample to res. calculus being complete:

Let and . We know . But there is no way to derive from using the resolution calculus. Therefore the res. calculus is not complete.