6.4. Solutions Deduction#

Solutions to Section 2.5

Solution to Exercise (1†)

In order to verify the validity of modus tollens, we need to verify that \(((p \rightarrow q)\wedge \lnot q) \rightarrow \lnot p\) is a tautology. This can be done by constructing the following truth table. The truth table shows that the conclusion is always true, and thus verifies that the modus tollens is valid.

\(p\)

\(q\)

\(\overbrace{p\rightarrow q}^\text{A}\)

\(\overbrace{A \wedge \lnot q}^\text{B}\)

\(B \rightarrow \lnot p\)

0

0

1

1

1

0

1

1

0

1

1

0

0

0

1

1

1

1

0

1

To verify the validity of the Law of Syllogism, construct another truth table to show that \(((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)\) is also a tautology.

Solution to Exercise (2†)

Note that the following answers are example arguments, and that there exist many other valid answers.

  • Since it isn’t day, it must be night.

  • I have bread and I have cheese on top, so I have a cheese sandwich.

  • I have a cheese sandwich, so I have cheese.

  • Since I sing all the time, I am always singing or talking.

Solution to Exercise (3†)

For both arguments when \(p\) is false and \(q\) is true the premises hold but the conclusion does not.

  • When it rains the ground is wet. The ground is wet. Therefore it rains.

  • When I am on a boat i am not on land. I am not on a boat. Therefore I am on land.

Solution to Exercise (4†)

For this set of solutions, remember that you a slightly less formal method would be to use a truth table to prove the validity of arguments in propositional logic. If you can show that in all rows where all premises are true, the conclusion is also true, then the argument must be valid!

  1. Invalid. A counterexample for this argument is when \(p\) and \(q\) are false and \(s\) is true.

  2. Valid.

    \[\begin{split}\begin{align*} p\wedge q && \text{(premise)}\\ q && \text{(from 1)}\\ q\rightarrow (r\vee s) && \text{(premise)}\\ r\vee s && \text{(from 2 and 3 by *modus ponens*)}\\ \lnot r && \text{(premise)}\\ s && \text{(from 4 and 5)} \end{align*}\end{split}\]
  3. Valid.

    \[\begin{split}\begin{align*} p\vee q && \text{(premise)}\\ \lnot p && \text{(premise)}\\ q && \text{(from 1 and 2)}\\ q\rightarrow (r\wedge s)&&\text{(premise)}\\ r\wedge s&&\text{(from 3 and 4 by *modus ponens*)}\\ s&&\text{(from 5)} \end{align*}\end{split}\]
  4. Valid.

    \[\begin{split}\begin{align*} \lnot(q\vee t)&&\text{(premise)}\\ \lnot q\wedge\lnot t&&\text{(from 1 by *De Morgan*)}\\ \lnot t&&\text{(from 2)}\\ (\lnot p)\rightarrow t&&\text{(premise)}\\ \lnot(\lnot p)&&\text{(from 3 and 4 by *modus tollens*)}\\ p&&\text{(from 5)} \end{align*}\end{split}\]
  5. Invalid. A counterexample for this argument is when \(p\), \(r\) and \(s\) are true and \(q\) is false.

  6. Valid.

    \[\begin{split}\begin{align*} p&&\text{(premise)}\\ p\rightarrow(t\rightarrow s)&&\text{(premise)}\\ t\rightarrow s&&\text{(from 1 and 2 by *modus ponens*)}\\ q\rightarrow t&&\text{(premise)}\\ q\rightarrow s&&\text{(from 3 and 4 by *Law of Syllogism*)} \end{align*}\end{split}\]

Solution to Exercise (5†)

  1. Let \(s\) = “today is a Sunday”, \(r\) = “it rains today” and \(s\) = “it snows today”.

    \(s \rightarrow (r \vee s)\)

    \(s\)

    \(\lnot r\)

    \(\therefore s\)

    This argument is valid.

  2. Let \(h\) = “there is herring on the pizza”, \(n\) = “Jack doesn’t eat pizza”, \(a\) = “Jack is angry”.

    \(h \rightarrow n\)

    \(n \rightarrow a\)

    \(a\)

    \(\therefore h\)

    The argument is invalid since we can’t deduce anything from the fact that Jack is angry, there might be many more reasons for Jack to get angry.

    Note that this exercise becomes harder when we translate to predicate logic instead of propositional logic. For predicate logic, “a” pizza is translated differently than “the” pizza.

    This exercise in predicate logic would become:

    Let \(P(x)\) mean that \(x\) is a pizza, let \(H(x)\) mean that \(x\) is a herring, let \(On(x,y)\) mean that \(x\) is on \(y\), let \(E(x,y)\) mean \(x\) eats \(y\) and finally let \(A(x)\) mean that \(x\) is angry. Let j = Jack.

    \(P(a)\)

    \(\forall x((H(x) \wedge On(x,a)) \rightarrow \lnot E(j,a))\)

    \(\lnot \exists x((P(x) \wedge E(j,x)) \rightarrow A(j))\)

    \(A(j)\)

    \(\therefore \exists x (H(x) \wedge On(x,a))\)

    As an exercise for yourself, try to translate part c to predicate logic as well as propositional logic.

  3. Let \(a\) = “it is 8:00”, \(l\) = “Jane studies at the library” and \(h\) = “Jane works at home”.

    \(a \rightarrow (l \vee h)\)

    \(a\)

    \(\lnot l\)

    \(\therefore h\)

    This argument is valid.