Exercises#

Star Issue Watch Follow

\(\newcommand{\vd}{\vdash}\) \(\newcommand{\dvd}{\models}\) \(\newcommand{\imp}{\Rightarrow}\) \(\newcommand{\or}{\vee}\) \(\newcommand{\and}{\wedge}\)

Exercise 1.1

Which of the following are tautologies?

\((p_1 \imp (p_2 \imp p_3)) \imp (p_2 \imp (p_1 \imp p_3))\)
\(((p_1 \or p_2) \and (p_1 \or p_3)) \imp (p_2 \or p_3)\)
\((p_1 \imp (\neg p_2)) \imp (p_2 \imp (\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{split}\begin{align} v(p_1 \imp (p_2 \imp p_3)) &= 1, \\ v(p_2 \imp (p_1 \imp p_3)) &= 0. \end{align}\end{split}\]

The second condition can occur only if \(v(p_2) = 1\) and \(v(p_1 \imp 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

\[\begin{equation} v(p_1 \imp (p_2 \imp p_3)) = 0, \end{equation}\]

which means that

\[\begin{equation} v(p_1 \imp (p_2 \imp p_3)) \imp (p_2 \imp (p_1 \imp p_3)) = 1. \end{equation}\]

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{align} v(p_1 \or p_2) &= 1, v(p_1 \or p_3) &= 1, v((p_1 \or p_2) \and (p_1 \or p_3)) &= 1, v(p_2 \or p_3) &= 0, \end{align}\]

which implies that

\[\begin{equation} v(((p_1 \or p_2) \and (p_1 \or p_3)) \imp (p_2 \or p_3)) = 0. \end{equation}\]

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

\[\begin{align} v(p_1 \imp (\neg p_2)) &= 1, v(p_2 \imp (\neg p_1)) &= 0. \end{align}\]

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 \imp (\neg p_2)) = 0.\) Contradiction.

Exercise 1.2

Write down a proof of \(\perp \imp q.\) Use this to write down a proof of \(p \imp q\) from \(\neg q.\)

Solution

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

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

Now, consider the following steps

\(\perp \imp (\neg q \imp \perp)\) from axiom 1.
\(\perp \imp \neg \neg q,\) since this is the same as (2).
\(\neg \neg q \imp q,\) by axiom 3.

We therefore have \(\perp \imp \neg \neg q\) and \(\neg \neg q \imp q.\) Repeating the first proof with \(a = \perp, b = \neg \neg q, c = q,\) we obtain a proof for \(\perp \imp q.\)

Part 2: We show that \(\neg p \vd p \imp q.\) From the deduction theorem, we have \(\neg p \vd p \imp q\) if and only if \(\{\neg p, p\} \vd q.\) This is equivalent to \(\perp \vd q,\) so we are done.

Exercise 1.3

Use the deduction theorem to show that \(p \vd \neg \neg p.\)

Solution

Note that \(\neg \neg p = \neg p \imp \perp.\) Therefore \(p \vd \neg \neg p\) if and only if \(p \vd \neg p \imp \perp.\) By the deduction theorem, this holds if and only if \(\{p, \neg p\} \vd \perp,\) which we know holds. We conclude that \(p \vd \neg \neg p.\)