HS24

Difficulty with

• Task 1
  • c (little bit)
  • d (little bit)
  • e (not solved on my own)
• Task 2
  • b (not solved on my own)
  • d (not solved on my own)
• Task 3
  • a
    • 1 (not solved)
    • 2 (not solved)
  • c (not solved)
  • d (after a lot of hints)
  • e (not solved)
• Task 4
  • b (difficult)
  • c (notation issues)
  • d (notation issues)

Took around 5h with breaks and thinking.

Task 1

a)

1.) Keep in mind that if the question asks “cross” and “circle” then an element can be both. 2.) We can use propositional logic to find the solution to such set problems, but best is to use a Venn Diagram.

b)

State that we use the definition of $\cap$ .

c)

Check again on how to prove surjectivity and well-definedness. The given answer is bad.

d)

Prove this by induction. I did not get this.

Task 2

3

Computing the gcd of two numbers like $81$ and $48+3^{2}5$. We have to use Lemma 4.2 which states that $\gcd (a,b)=\gcd (a,R_a(b))$

Task 3

a)

2.) Generator of largest cyclic subgroup of $⟨{\mathbb{Z}}_a\times {\mathbb{Z}}_b⟩$ and compute it’s order https://exams.vis.ethz.ch/exams/h1cr1i7i.pdf?answer=yvao6e5upbww5g8a

3.) Smallest $n>8$ such that ${\mathbb{Z}}_8^{\ast }$ isomorphic to ${\mathbb{Z}}_n^{\ast }$? Note that even though $\phi (8)=\phi (10)$, ${\mathbb{Z}}_{10}^{\ast }$ is cyclic ($10=2\cdot 5$) and thus not isomorphic. The next higher is ${\mathbb{Z}}_{12}^{\ast }$.

Task 4

a)

2.) Note that CNF and DNF are not mutually exclusive. 3.) Tautologies are modeled by every formula! Don’t fall into that trap.

c) Extend res. calc.

First show how you convert the clauses into formulas explicitly, stating:

1. Let the clause $K$ be represented as a formula in CNF of the form $F={\vee }_{L_K\in K}{L}_K$ where it is a disjunction of the literals of $K$ and where the literal $L$ gets decoupled into it’s atomic formula representation.
2. $F\models G⟹F\to G$ (Lemma saying "$F\models G$" equivalent to "$F\to G$" is a tautology) Then we can use standard rules to prove.

d) Construct a new Interpretation

We can define a new interpretation $B=(U,\varphi ,\psi ,\xi )$ such that the universe, $\phi$, $\xi$ remain the same, especially $Q^B$ is the same as $Q^A$. Then we define $\psi$ in $B$ to extend $\psi$ of $A$ by the unary function $f:U\to U$. For each $u$ in $U$, we define $f(u)=v$ where $v$ any element in $U^A$ such that $A_{[x\to u][y\to f^B(u)]}(Q(x,y))=1$, which exists under our assumption as shown before.