1
$\begingroup$

I have this awesome PDF about Logic in Action which I need for my premaster at the University of Amsterdam for Software Engineering.

The PDF can be found here

I am at page 2-21 exercise 2.19:

Exercise 2.19

Show using a truth table that:

  • the inference from $p \to (q \land r)$, $\lnot q$ to $\lnot p$ is valid and
  • the inference from $p \to (q \lor r)$, $\lnot q$ to $\lnot p$ is not valid.

So what I did is the following, I made a truth table for $p \to (q \land r)$

╔═══╦═══╦═══╦═══╦═══╦════╦═══╦════╗
║ p ║ q ║ r ║ p ║ → ║ (q ║ ∧ ║ r) ║
╠═══╬═══╬═══╬═══╬═══╬════╬═══╬════╣
║ 0 ║ 0 ║ 0 ║ 0 ║ 1 ║  0 ║ 1 ║  0 ║
║ 0 ║ 0 ║ 1 ║ 0 ║ 1 ║  0 ║ 0 ║  1 ║
║ 0 ║ 1 ║ 0 ║ 0 ║ 1 ║  1 ║ 0 ║  0 ║
║ 0 ║ 1 ║ 1 ║ 0 ║ 1 ║  1 ║ 1 ║  1 ║
║ 1 ║ 0 ║ 0 ║ 1 ║ 0 ║  0 ║ 1 ║  0 ║
║ 1 ║ 0 ║ 1 ║ 1 ║ 0 ║  0 ║ 0 ║  1 ║
║ 1 ║ 1 ║ 0 ║ 1 ║ 1 ║  1 ║ 0 ║  0 ║
║ 1 ║ 1 ║ 1 ║ 1 ║ 1 ║  1 ║ 1 ║  1 ║
╚═══╩═══╩═══╩═══╩═══╩════╩═══╩════╝

I went ahead to check my answer in the same PDF at page B-4, B-5 Only to find that the PDF has a very different implementation of the truth table:

Truth Table

So my question is, what am I missing? Am I doing the Truth table wrong?

ps. The link does not work for me

$\endgroup$
5
  • $\begingroup$ $(q \land r)$ must be True only when both $p$ and $q$ are True. $\endgroup$ Commented Jun 19, 2017 at 11:40
  • $\begingroup$ so (q∧r) where q = 0 and r = 0 is ∧ = 0 and not 1 as in my truth table... how would you go about finding a solution? $\endgroup$
    – Igoranze
    Commented Jun 19, 2017 at 11:45
  • $\begingroup$ Firts, you have to fix the column under $\land$ and then fix accordingly the column under $\to$. $\endgroup$ Commented Jun 19, 2017 at 11:51
  • $\begingroup$ Then you have to add columns for $\lnot p$ and $\lnot q$ (very easy to compute...). $\endgroup$ Commented Jun 19, 2017 at 11:53
  • 1
    $\begingroup$ You can see Proving validity with Truth Table. $\endgroup$ Commented Jun 19, 2017 at 11:55

1 Answer 1

1
$\begingroup$

What you're missing may lie in the interpretation of the question. The inference to prov is one where $p\rightarrow (q\land r)$ and $\neg q$ are premises and $\neg p$ is the consequence. Writing the premises in one formula would be $(p\rightarrow (q\land r)) \land (\neg q)$ and the thing to prove would be $$((p\rightarrow (q\land r)) \land (\neg q)) \rightarrow \neg p$$

But you only made a truth table for $p\rightarrow (q\land r)$.

I think it's a typo in the solution as they wrote $\neg r$ instead of $\neg q$, but that is actually of no importance since it's just a renaming of the variables since we can replace $q\land r$ with $r\land q$. The correct truth table should have been:

$$\begin{matrix} p & q & r & ((p&\rightarrow (&q&\land& r)) &\land (&\neg &q)) &\rightarrow &\neg &p \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \end{matrix}$$

The second task is in similar way to prove that

$$((p\rightarrow (q\lor r)\land(\neg q))\rightarrow \neg p$$

is an invalid inference, that is the statement does not always hold (note we're not to show that it's generally false, but only that it's occationally false which makes it an invalid inference). The truth table then becomes

$$\begin{matrix} p & q & r & ((p&\rightarrow (&q&\lor& r)) &\land (&\neg &q)) &\rightarrow &\neg &p \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & \bbox[red]{\color{white}{0}} & 0 & 1\\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \end{matrix}$$

Here we see that for $p$ and $r$ being true and $q$ is false the inference fails which makes the inference invalid.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, so if I would create the second formula it would be: $((p\rightarrow (q\lor r)) \land (\neg q)) \rightarrow \neg p$ yes? The second one is $p \to (q \lor r)$, $\lnot q$ where q OR r instead of q AND r. I still have trouble understanding how this all works. If i would create the Truth table for the first formula as in your answer, how would i go about proving that not-q and not-p are valid? $\endgroup$
    – Igoranze
    Commented Jun 19, 2017 at 12:05
  • $\begingroup$ Thank you, this is exactly what I need for a better understanding! $\endgroup$
    – Igoranze
    Commented Jun 19, 2017 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .