# Problem 1
## a
$\exists x . S(x) \land A(x)$

## b
$\forall x . S(x) \land T(x) \implies A(x)$

## c
1. $\nexists . T(x) \land \lnot A(x)$
2. $\nexists . T(x) \implies \lnot A(x)$
3. $\forall . T(x) \implies A(x)$

$\nexists x . T(x) \land \lnot A(x)$
$\Rightarrow$
$\forall x . \lnot(T(x) \land \lnot A(x))$
$\Rightarrow$
$\forall x . \lnot T(x) \lor A(x)$

T is true -> A has to be true
T is false -> A can be true/false

## d

$\exists x,y,z . T(x) \land T(y) \land T(z) \land \lnot S(x) \land \lnot S() \land \lnot S(z)$

# Problem 2

# Problem 3

## a) i)

$\lnot A \Rightarrow \overline{A \land A}$

$A \land B \Rightarrow \lnot(\overline{A \land B})$

## a) ii)
$A \lor B \Rightarrow (\overline{A \land B}) \land \overline{(\lnot A \land \overline{(A \land B)})}$

$A \lor B$
$\Rightarrow$
$\overline{\overline{A \lor B}}$
$\Rightarrow$
$\overline{\lnot A \land \lnot B}$

## a) iii)
$A \implies B$
$\Rightarrow$
$\overline{A \land \lnot B}$

## b)
$\lnot A\\ \Rightarrow \overline{A \land A}\\ \Rightarrow A \nabla A$

## c)
$true \Rightarrow \overline{\overline{A \land A} \land A}$

$false \Rightarrow \overline{(\overline{\overline{A \land A} \land A}) \land (\overline{\overline{A \land A} \land A})}$

True as nand
$true\\
\Rightarrow A \lor \lnot A\\
\Rightarrow \lnot( \lnot A \land A)\\
\Rightarrow \lnot A\ nand\ A\\
\Rightarrow A\ nand\ A\ nand\ A$

False as nand
$false\\
\Rightarrow A \land \lnot A\\
\Rightarrow \lnot (A\ nand\ \lnot A )\\
\Rightarrow (A\ nand\ \lnot A)\ nand\ (A\ nand\ \lnot A)\\
\Rightarrow (A\ nand\ (A\ nand\ A))\ nand\ (A\ nand\ (A\ nand\ A))\\
\Rightarrow A\ nand\ A\ nand\ A\ nand\ A\ nand\ A\ nand\ A
.$

# Problem 4

6 coins 6 coins

`3 3` and `3 3`
1 1

1st pair is right. 2nd has fake

`3 3`

1 compari

3
1 com
1 com

5 comparison

3 comparison

swap 2 coins

if same

# Problem 5
IR(r) irrational
R(r) rational

$\forall r . IR(r) \implies IR(r^{1/5})$

$\forall r . R(r^{1/5}) \implies R(r)$

Case 1:
if $R(r^{1/5})$ is $false$, then proposition is true.

Case 2:
if $R(r^{1/5})$ is $true$,

$r^{1/5} = \frac{a}{b}$

$r = (\frac{a}{b})^{5}$

# Problem 6

E(x) if x is even

$\forall w,x,y . E(z) \iff E(w) \land E(x) \land E(y)$

Two case
Case 1:
$\forall w,x,y . E(w) \land E(x) \land E(y) \implies E(z)$

Case 2:
$\forall w,x,y . E(z) \implies E(w) \land E(x) \land E(y)$

\contrapositive

$\forall w,x,y . \lnot (E(w) \land E(x) \land E(y)) \implies \lnot E(z)$

$\forall w,x,y . O(w) \lor O(x) \lor O(y) \implies \lnot E(z)$

Since z is even, it should be divisible by 2. Hence:

$w^2+x^2+y^2 = 2 (\frac{z}{2})^2$
$w^2+x^2+y^2 = 4(\frac{z}{2})^2$

This sould mean the left side _together_ should be divisible by 4.

1 is odd
$(2a+1)^2 + 2b^2 + 2c^2$ = z is even
$4a^2 + 4a + 1 + 2b^2 + 2c^2$
all terms divisible by 4, except 1.

2 are odd
$(2a+1)^2 + (2b+1)^2 + 2c^2$ = $z^2$
$4a^2 + 4a + 4b^2 + 4b + 2 + 2c^2$
Similarly, only 2 is not divisible by 4

3 are odd
$(2a+1)^2 + (2b+1)^2 + (2c + 1)^2$
$4a^2 + 4a + 4b^2 + 4b + 4c^2 + 4c + 3$
3 is not divisible.