Lösungsvorschlag Diskrete Mathematik FS18

Aus VISki
Wechseln zu: Navigation, Suche

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) || = 4

1 b)


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

2 c)

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

3 a)


ii) gcd(1188,954) = 18

3 b)

3 c)


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)

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 .

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.