Exercises#

Exercise 1.1

Which of the following are tautologies?

$(p_{1} \Rightarrow (p_{2} \Rightarrow p_{3})) \Rightarrow (p_{2} \Rightarrow (p_{1} \Rightarrow p_{3}))$
$((p_{1} \lor p_{2}) \land (p_{1} \lor p_{3})) \Rightarrow (p_{2} \lor p_{3})$
$(p_{1} \Rightarrow (\neg p_{2})) \Rightarrow (p_{2} \Rightarrow (\neg p_{1}))$

Solution

Proposition 1: This is a tautology because the only way a valuation of this proposition can be false is if

\begin{array}{r} \begin{aligned} v (p_{1} \Rightarrow (p_{2} \Rightarrow p_{3})) & = 1, \\ v (p_{2} \Rightarrow (p_{1} \Rightarrow p_{3})) & = 0. \end{aligned} \end{array}

The second condition can occur only if $v (p_{2}) = 1$ and $v (p_{1} \Rightarrow p_{3}) = 0,$ which can in turn occur only if $v (p_{1}) = 1$ and $v (p_{3}) = 0.$ But if all of these conditions hold, then

v (p_{1} \Rightarrow (p_{2} \Rightarrow p_{3})) = 0,

which means that

v (p_{1} \Rightarrow (p_{2} \Rightarrow p_{3})) \Rightarrow (p_{2} \Rightarrow (p_{1} \Rightarrow p_{3})) = 1.

Therefore the proposition is a tautology.

Proposition 2: This is not a tautology because if $v (p_{1}) = 1$ and $v (p_{2}) = v (p_{3}) = 0,$ we have

\begin{aligned} v (p_{1} \lor p_{2}) & = 1, v (p_{1} \lor p_{3}) & = 1, v ((p_{1} \lor p_{2}) \land (p_{1} \lor p_{3})) & = 1, v (p_{2} \lor p_{3}) & = 0, \end{aligned}

which implies that

v (((p_{1} \lor p_{2}) \land (p_{1} \lor p_{3})) \Rightarrow (p_{2} \lor p_{3})) = 0.

Proposition 3: This is a tautology. The only way for a valuation of this proposition to be false is if

\begin{aligned} v (p_{1} \Rightarrow (\neg p_{2})) & = 1, v (p_{2} \Rightarrow (\neg p_{1})) & = 0. \end{aligned}

The latter of these conditions can occur only if $v (p_{2}) = 1$ and $v (\neg p_{1}) = 0,$ so $v (p_{1}) = 1.$ But that would imply $v (p_{1} \Rightarrow (\neg p_{2})) = 0.$ Contradiction.

Exercise 1.2

Write down a proof of $⊥\Rightarrow q .$ Use this to write down a proof of $p \Rightarrow q$ from $\neg q .$

Solution

Part 1: First, we show that if $a, b, c$ are propositions, then $a \Rightarrow c$ can be proved from $a \Rightarrow b$ and $b \Rightarrow c .$ To show this, we can use the steps

$(a \Rightarrow (b \Rightarrow c)) \Rightarrow ((a \Rightarrow b) \Rightarrow (a \Rightarrow c))$ from axiom 2.
$(b \Rightarrow c) \Rightarrow (a \Rightarrow (b \Rightarrow c))$ from axiom 1.
$(b \Rightarrow c)$ by hypothesis.
$(a \Rightarrow (b \Rightarrow c))$ by modus ponens on (2) and (3).
$(a \Rightarrow b) \Rightarrow (a \Rightarrow c)$ by modus ponens on (1) and (4).
$(a \Rightarrow b)$ by hypothesis.
$(a \Rightarrow c)$ by modus ponens on (5) and (6).

Now, consider the following steps

$⊥\Rightarrow (\neg q \Rightarrow⊥)$ from axiom 1.
$⊥\Rightarrow \neg \neg q,$ since this is the same as (2).
$\neg \neg q \Rightarrow q,$ by axiom 3.

We therefore have $⊥\Rightarrow \neg \neg q$ and $\neg \neg q \Rightarrow q .$ Repeating the first proof with $a =⊥, b = \neg \neg q, c = q,$ we obtain a proof for $⊥\Rightarrow q .$

Part 2: We show that $\neg p ⊢ p \Rightarrow q .$ From the deduction theorem, we have $\neg p ⊢ p \Rightarrow q$ if and only if ${\neg p, p} ⊢ q .$ This is equivalent to $⊥⊢ q,$ so we are done.

Exercise 1.3

Use the deduction theorem to show that $p ⊢ \neg \neg p .$

Solution

Note that $\neg \neg p = \neg p \Rightarrow⊥ .$ Therefore $p ⊢ \neg \neg p$ if and only if $p ⊢ \neg p \Rightarrow⊥ .$ By the deduction theorem, this holds if and only if ${p, \neg p} ⊢⊥,$ which we know holds. We conclude that $p ⊢ \neg \neg p .$