Semester 2, 2018

Homework (Week 1)

1 Predicate Logic

1.1 Question 1

For which values of $$A$$ and $$B$$ does the boolean expression $$\varphi = \neg (A \Rightarrow B) \lor \neg B$$ hold?

Using a truth table:

 $$A$$ $$B$$ $$A \Rightarrow B$$ $$\neg B$$ $$\varphi$$ $$\bot$$ $$\bot$$ $$\top$$ $$\top$$ $$\top$$ $$\bot$$ $$\top$$ $$\top$$ $$\bot$$ $$\bot$$ $$\top$$ $$\bot$$ $$\bot$$ $$\top$$ $$\top$$ $$\top$$ $$\top$$ $$\top$$ $$\bot$$ $$\bot$$

This is an answer but it is not so informative. Using boolean manipulation instead:

\begin{array}{lcl} \neg (A \Rightarrow B) \lor \neg B & = & \neg (\neg A \lor B) \lor \neg B \\ & = & (A \land \neg B) \lor \neg B \\ & = & (A \lor \neg B) \land (\neg B \lor \neg B) \\ & = & (A \lor \neg B) \land \neg B \\ & = & \neg B \\ \end{array}

Here we can see clearly that $$\varphi$$ holds only when $$B$$ is false, and the value of $$A$$ does not matter.

1.2 Question 2

Simplify the boolean expression $$(A \Rightarrow B) \lor (B \Rightarrow A)$$

\begin{array}{lcl} (A \Rightarrow B) \lor (B \Rightarrow A) & = & (\neg A \lor B) \lor (\neg B \lor A) \\ & = & (\neg A \lor A) \lor (\neg B \lor B) \\ & = & \top \lor \top\\ & = & \top \\ \end{array}

This proof is not constructive. Discuss what it means for a proof to be constructive.

1.3 Question 3

Which one of the expressions listed below is a possible formalisation of the phrase: Not all that glitters is gold.

1. $$\exists x.\ (\mathit{Glitter}(x) \Rightarrow \mathit{Gold}(x))$$
2. $$\forall x.\ (\neg (\mathit{Glitter}(x)) \Rightarrow \mathit{Gold}(x))$$
3. $$\neg \forall x.\ (\mathit{Glitter}(x) \Rightarrow \mathit{Gold}(x))$$
4. $$\forall x.\ \neg ((\mathit{Glitter}(x) \Rightarrow \mathit{Gold}(x)))$$

The answer is number 3. Number 1 merely states that there exists a thing that either does not glitter, or that is glittering gold. Number 2 suggests that everything that does not glitter is gold. Number 4 suggests that everything glitters and is not gold.

1.4 Question 4

Which of the expressions listed below is a possible formalisation of the Abraham Lincoln quote: You can fool all the people some of the time, and some of the people all the time, but you cannot fool all the people all the time.

1. $$\forall p.\ \forall t.\ (\mathit{Fool}(p, t) \land \neg \mathit{Fool}(p, t))$$
2. $$\forall p.\ \exists t.\ \mathit{Fool}(p, t) \land \exists p.\ \forall t.\ \mathit{Fool}(p, t) \Rightarrow \exists p.\ \exists t.\ \neg \mathit{Fool}(p, t))$$
3. $$\forall p.\ \exists t.\ \mathit{Fool}(p, t) \land \exists p.\ \forall t.\ \mathit{Fool}(p, t) \land \neg \forall p.\ \forall t.\ \mathit{Fool}(p, t)$$
4. $$\forall p.\ \exists t.\ \mathit{Fool}(p, t) \land \exists p.\ \forall t.\ \mathit{Fool}(p, t) \land (False \Rightarrow \forall p.\ \forall t.\ \mathit{Fool}(p, t))$$
5. $$\exists t.\ \forall p.\ \mathit{Fool}(p, t) \land \forall t.\ \exists p.\ \mathit{Fool}(p, t) \land \neg \forall t.\ \forall p.\ \mathit{Fool}(p, t)$$

I believe 3 and 5 are valid interpretations of the quote. Discuss the differences with your tutor.

1.5 Question 5

Given the following function

$f (n) = \begin{cases} 0 & \text{if}\ n = 0 \\ 2n - 1 + f(n-1) & \text{if}\ n > 0 \end{cases}$

Prove that $$\forall n \in \mathbb{N}.\ f(n) = n^2$$.

Proof by mathematical induction on the natural number $$n$$.

Base Case: $$n = 0$$

\begin{array}{lcl} f(0) & = & 0 \\ & = & 0^2 \\ & & \blacksquare \end{array}

Inductive Case: $$n = k + 1$$, for arbitrary $$k \in \mathbb{N}$$. Assume the inductive hypothesis that $$f(k) = k^2$$.

\begin{array}{lcl} f(k+1) & = & 2(k+1) - 1 + f(k) \\ & = & 2k + 2 - 1 + f(k) \\ & = & 2k + 1 + f(k) \\ & = & 2k + 1 + k^2 \quad \text{(I.H)}\\ & = & k^2+k+k+1 \\ & = & k(k+1)+(k+1) \\ & = & (k+1)(k+1) \\ & = & (k+1)^2 \\ & & \blacksquare \end{array}

Thus $$f(n) = n^2$$ for all $$n \in \mathbb{N}$$.