FC1 Week 3 SGT

1

Construct truth table for:

$$((\neg ((\neg r)\to p))\vee (p\wedge q))\wedge (p\vee ((\neg p)\wedge (\neg q)))$$

$r$	$p$	$q$	$\neg q$	$\neg p$	$(\neg p)\wedge (\neg q)$	$p\vee ((\neg p)\wedge (\neg q))$	$p\wedge q$	$\neg r$	$(\neg r)\to p$	$\neg ((\neg r)\to p)$	$(\neg ((\neg r)\to p))\vee (p\wedge q)$	$((\neg ((\neg r)\to p))\vee (p\wedge q))\wedge (p\vee ((\neg p)\wedge (\neg q)))$
F	F	F	T	T	T	T	F	T	F	T	T	T
F	F	T	F	T	F	F	F	T	F	T	T	F
F	T	F	T	F	F	T	F	T	T	F	F	F
F	T	T	F	F	F	T	T	T	T	F	T	T
T	F	F	T	T	T	T	F	F	T	F	F	F
T	F	T	F	T	F	F	F	F	T	F	F	F
T	T	F	T	F	F	T	F	F	T	F	F	F
T	T	T	F	F	F	T	T	F	T	F	T	T

It is not a tautology but it is satisfiable.

title:
Correct answer.

2

a. $(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$

$p$	$q$	$r$	$p\wedge q$	$(p\wedge q)\wedge r$
F	F	F	F	F
F	F	T	F	F
F	T	F	F	F
F	T	T	F	F
T	F	F	F	F
T	F	T	F	F
T	T	F	T	F
T	T	T	T	T

$p$	$q$	$r$	$q\wedge r$	$p\wedge (q\wedge r)$
F	F	F	F	F
F	F	T	F	F
F	T	F	F	F
F	T	T	F	F
T	F	F	F	F
T	F	T	F	F
T	T	F	T	F
T	T	T	T	T

Hence they are logically equivalent.

b. $\neg (p\wedge q)\equiv (\neg p)\vee (\neg q)$

$p$	$q$	$p\wedge q$	$\neg (p\wedge q)$
F	F	F	T
F	T	F	T
T	F	F	T
T	T	T	F

$p$	$q$	$\neg q$	$\neg p$	$(\neg p)\vee (\neg q)$
F	F	T	T	T
F	T	F	T	T
T	F	T	F	T
T	T	F	F	F

Hence they are logically equivalent.

3

1. There exists a tourist in London that likes the British Museum.
2. All tourists in London like the British Museum.
3. There does not exist a tourist in London that likes the British Museum.
4. There exists a tourist in London that does not like the British Museum.
5. Not all tourists in London like the British Museum.
6. All tourists in London do not like the British Museum.

4

Let $C(x)$ be that $x$ has a cat. Let $D(x)$ be that $x$ has a dog. Let $F(x)$ be that $x$ has a ferret.

1. $\exists x(C(x)\wedge D(x)\wedge F(x))$
2. $\forall x(C(x)\oplus D(x)\oplus F(x))$
3. $\exists x(C(x)\wedge F(x)\wedge \neg D(x))$
4. $\neg \exists x(C(x)\wedge D(x)\wedge F(x))$ $\neg \exists x(C(x)\vee D(x)\vee F(x))$ Both of these are right.
5. $\exists x(C(x)\oplus D(x)\oplus F(x))$

5

Prove by induction that $n<2^n$ for all positive integers $n$.

Step 1: Test for $n=1$

$$\begin{array}{l}1<2^1\\ 1<2\end{array}$$

Step k: Assume it works for $n=k$

$$\begin{array}{l}\text{IH}=k<2^k\end{array}$$

Step k+1: Test if it holds for $n=k+1$

$$\begin{array}{rl}k& <2^k(\times 2)\\ 2k& <2\times 2^k\\ 2k& <2^{k+1}\\ k+1\le 2k& <2^{k+1}\\ k+1& <2^{k+1}\end{array}$$

Alternative method:

$$\begin{array}{rl}k& <2^k\\ k+1& <2^k+1\\ & <2^k+2\\ & <2^k+2^k\\ k+1& <2^{k+1}\end{array}$$

This is our inductive hypothesis with $n=k+1$. Hence since it holds for the base case, and when $n=k+1$, then by mathematical induction it works for all positive integers $n$.

6

{
	"url":"[FC1 Week 3 SGT.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%203.%20Functions/FC1%20Week%203%20SGT.pdf)",
	"page":[2],
	"scale":1,
	"rect":[70, 180, 200, 460]
}

$\max (x-1,y-1)=k$ Let $x,y=1$, $\max (0,0)=k=0$ which is a contradiction as $k$ must be a positive integer.