# Lösungsvorschlag Diskrete Mathematik FS18

Wechseln zu: Navigation, Suche

## Other Solutions

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

## 1 a)

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

ii) |${\displaystyle (\mathbb {N} \setminus \mathbb {Q} )\times \{1\}}$| = 0, since any element of the natural numbers is also element of the rational numbers.

iii) ${\displaystyle P(\{\{\emptyset \}\emptyset \})=\{\emptyset ,\{\emptyset \},\{\{\emptyset \}\},\{\{\emptyset \},\emptyset \}\}}$

## 1 b)

i) ${\displaystyle \emptyset }$

ii) Claim: ${\displaystyle A}$ transitive ${\displaystyle \Rightarrow A\cup \{A\}}$ transitive.

Proof: ${\displaystyle A}$ transitive ${\displaystyle \Rightarrow \forall x\in A:x\subseteq A}$. We know that every element of ${\displaystyle A}$ is also a subset of ${\displaystyle A}$. Therefore, the only element of ${\displaystyle A\cup \{A\}}$ that needs to be checked is ${\displaystyle A}$ (since ${\displaystyle A\in (A\cup \{A\})}$). We know, that every element of ${\displaystyle A}$ is also element of ${\displaystyle A\cup \{A\}}$. Therefore we know ${\displaystyle A\subseteq (A\cup \{A\})}$. This means that we have ${\displaystyle \forall x\in (A\cup \{A\}):x\subseteq (A\cup \{A\})}$. The set is therefore transitive.

## 1) c)

i) Let ${\displaystyle A\cap B=\emptyset }$ and ${\displaystyle A,B}$ countable.

Claim: ${\displaystyle A\cup B}$ countable.

Proof: Define ${\displaystyle C:=A\cup B}$ and ${\displaystyle c_{i}\in C}$ arbitrary. ${\displaystyle c_{i}=a_{i}}$ if i even; ${\displaystyle c_{i}=b_{i}}$ if i odd. Since ${\displaystyle A\cap B=\emptyset }$, i.e. no element of A and B are the same, we know that we have an injection of C into ${\displaystyle \mathbb {N} }$. Therefore ${\displaystyle C}$ is countable.

ii) Claim: If ${\displaystyle A}$ countable and ${\displaystyle C}$ uncountable, then ${\displaystyle C/A}$ is uncountable.

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

## 2 a)

1) Yes, an example is ${\displaystyle \rho :=\{(1,1),(2,2),(3,3)\}=:id}$ on ${\displaystyle \{1,2,3\}}$.

2) ${\displaystyle \rho :=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}}$

## 2 c)

i) Let ${\displaystyle f(n):=2}$ if ${\displaystyle n}$ even and ${\displaystyle f(n):=4}$ if ${\displaystyle n}$ odd. We therefore have ${\displaystyle f\neq f_{2},f\neq f_{4}}$ and ${\displaystyle f_{2}\leq f\leq f_{4}\iff \forall n\in \mathbb {N} :f_{2}(n)|f(n)\wedge f(n)|f_{4}(n)}$.

## 3 a)

i) ${\displaystyle R_{11}(2^{1408})=R_{11}(R_{11}(2^{10})^{140}\cdot R_{11}(2^{8}))=3}$

ii) gcd(1188,954) = 18

## 3 c)

Lemma: ${\displaystyle gcd(m,n)=gcd(m,n-qm)}$

If ${\displaystyle a+k}$ and ${\displaystyle b+k}$ are relatively prime, then:

${\displaystyle gcd(a+k,b+k)=1\implies gcd(a+k,b+k-(a+k))=gcd(a+k,b-a)=1}$

Suppose without limitation to the generality that ${\displaystyle b-a>0}$.

Then there are infinitely many numbers ${\displaystyle k}$, such that ${\displaystyle a+k}$ is prime and ${\displaystyle a+k>b-a}$.

For all these k we have ${\displaystyle gcd(a+k,b-a)=1}$ , because ${\displaystyle a+k}$ is only divided by ${\displaystyle 1}$ and itself and ${\displaystyle b-a.

## 4 d)

Let ${\displaystyle a}$, ${\displaystyle b\in R}$.

${\displaystyle (a+b)\in R}$

${\displaystyle (a+b)=(a+b)^{2}}$

${\displaystyle (a+b)=a*a+a*b+b*a+b*b}$ (distributive law)

${\displaystyle (a+b)=a+a*b+b*a+b}$ ${\displaystyle (a*a=a)}$

${\displaystyle (a+b)-(a+b)=a*b+b*a}$ (additive inverse and commutativity)

${\displaystyle 0=a*b+b*a}$

${\displaystyle -a*b=b*a}$

${\displaystyle a*b=b*a}$ ${\displaystyle (a=-a)}$

## 4 e)

Let ${\displaystyle A:=\mathbb {Z} _{2}[x]_{x^{3}+x^{2}+1}}$.

i) Claim: ${\displaystyle A}$ is a field.

Proof: By Lemma 5.35, ${\displaystyle F[x]_{m(x)}}$ is a ring. Theorem 5.37 states, that a ring ${\displaystyle F[x]_{m(x)}}$ is a field iff ${\displaystyle m(x)}$ irreducible. Therefore we need to show that ${\displaystyle m(x)}$ irreducible. ${\displaystyle m(x)}$ is irreducible, if it has no roots in GF(2): ${\displaystyle m(0)=1,m(1)=1\Rightarrow m(x)}$ irreducible in ${\displaystyle A}$.

ii) Claim: All elements of ${\displaystyle A^{*}}$ are generators.

Proof: We know that ${\displaystyle |A|=2^{3}=8}$. Since ${\displaystyle m(x)}$ irreducible, ${\displaystyle A^{*}}$ contains all elements of ${\displaystyle A}$ except 0. Therefore ${\displaystyle |A^{*}|=|A|-1=7}$. 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 ${\displaystyle y^{2}+(x^{2}+1)y+(x^{2}+x+1)=0}$ in ${\displaystyle A}$.

Solution: Let ${\displaystyle y:=x+1}$. We then have ${\displaystyle (x+1)^{2}+(x^{2}+1)\cdot (x+1)+(x^{2}+x+1)=(x^{2}+1)+(x^{3}+x^{2}+x+1)+(x^{2}+x+1)=x^{3}+x^{2}+1=0}$.

(${\displaystyle y=x^{2}+x}$ is also a solution.)

## 5 c)

Claim: The resolution calculus is not complete.

Proof: Counterexample to res. calculus being complete:

Let ${\displaystyle F:=A}$ and ${\displaystyle G:=A\vee B}$. We know ${\displaystyle F\models G}$. But there is no way to derive ${\displaystyle K(A\vee B)}$ from ${\displaystyle K(A)}$ using the resolution calculus. Therefore the res. calculus is not complete.