COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

Homework (Week 1)

Table of Contents

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}\).

2 Haskell

Please make sure you get Haskell set up on your system or on CSE machines. See Setting up Haskell for more details.

Once it is uploaded, also take a look at the lecture code and experiment with it.

2018-11-16 Fri 19:37

Announcements RSS