Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The instruction of this question is:

Encode the following arguments and show whether they are valid or not. If not valid give countermodels i.e., truth assignments to the propositions which make them false.

If the investigation continues, then new evidence is brought to light. If new evidence is brought to light, then several leading citizens are implicated. If several leading citizens are implicated, then the newspapers stop publicizing the case. If continuation of the investigation implies that the newspapers stop publicizing the case, then bringing to light of new evidence implies that the investigation continues. The investigation does not continue. Therefore, new evidence is not brought to light.

My attempt:

Let $p$ denote "the investigation continues"
$\quad \space \space q$ denote "new evidence is brought to light"
$\quad \space \space r$ denote "several leading citizens are implicated"
$\quad \space \space s$ denote "the newspapers stop publicizing the case"

So, the premises are:
$p \to q $
$q \to r $
$r \to s $
$(p \to s) \to (q \to p)$
$\neg p$

$\therefore \neg q$

I am very much a beginner in logic so I am not sure if this is correct so far or how to prove or disprove this using the standard rules of inference. Any ideas?

share|cite|improve this question
up vote 2 down vote accepted

Here's a simplification of Zhen Lin's argument. We know $$ \tag A (p \to s) \to (q \to p)$$ Contrapose this: $$ \tag B (q\land\neg p) \to (p\land \neg s)$$ Now I'm going to prove $q\to p$ by contradiction. We assume its negation $$ \tag C q\land \neg p $$ and from this and (B) by modus ponens we can then conclude $ p\land \neg s $ and in particular $p$. However (C) also trivially implies $\neg p$ which is a contradiction.

Thus, given (A) I have proved $$\tag D q\to p$$ (And in contrast to Zhen I didn't even need the $\neg p$ premise to do so. On the other hand, my proof is not intuitionistically valid).

Now the story explicitly tells us $\neg p$. Therefore, by modus tollens and (D), we have $\neg q$. Q.E.D.

share|cite|improve this answer

looks like you missed a couple.

The fourth statement should be:

(p -> s) -> (q -> p)

So we have:


So by the first three primitives we have p->s. Hence q -> p. So not p implies not q.

I think this checks out, but I my formal logic training is a little weak.

share|cite|improve this answer

You meant, for the fourth premiss, $$(p \to s) \to (q \to r)$$ Which might help! Intuitively, the first three premisses in PL give you $$p \to s$$ Modus ponens with the corrected fourth premiss yields $$q \to r$$ Modus tollens with the fifth premiss gives the conclusion. So it is just a question of following these steps in your preferred formal system.

A general point about such questions in elementary logic texts, however. You should always ask yourself, when translations involving conditionals or "implies" are concerned, whether the validity of the supposed rendering into PL shows (i) that the original argument is valid, or (ii) that the material conditional is here a bad translation of the intuitive content of the original. (After all, you are being asked whether the original argument is valid, and showing a certain rendering of it into PL is valid only settles the matter if the rendering is a good one: and where vernacular conditionals are involved, things can easily go wrong. So you should always, when answering, indicate whether you think that showing the PL argument is valid establishes what is asked.)

share|cite|improve this answer

Edit. I assume you meant $(p \to s) \to (q \to p)$ in your fourth premise – but it doesn't actually matter, as we shall see.

  1. Ex falso quodlibet, so $$\lnot p, p \vdash s$$ and by conditional proof, $$\lnot p \vdash (p \to s)$$

  2. By modus ponens, $$\lnot p, ((p \to s) \to (q \to p)) \vdash (q \to p)$$

  3. By contraposition, $$\lnot p, (q \to p) \vdash \lnot q$$

  4. Putting it all together, $$\lnot p, ((p \to s) \to (q \to p)) \vdash \lnot q$$

So it turns out the other premises $p \to q, q \to r, r \to s$ are irrelevant for this deduction.

share|cite|improve this answer
+1 Sneaky! ${}{}$ – Henning Makholm Sep 11 '12 at 8:50
On the other hand, what this sneaky reasoning suggests to me is that perhaps $(p\to s)\to(q\to p)$ doesn't fully represent the meaning of "If continuation of the investigation implies that the newspapers stop publicizing the case, then bringing to light of new evidence implies that the investigation continues." The more I stare at that sentence the less sure am I what it is intended to convey. (I'm attempting to pretend here that it's not just a back-translation of a propositional formula). Perhaps this natural-language use of "implies" is better modeled as something like $\Box(p\to s)$? – Henning Makholm Sep 11 '12 at 9:16
I agree – there's something very unsatisfactory about a proof that starts with ex falso quodlibet, but it was the first one that came to mind after playing with boolean valuations. On the other hand we can instead substitute $(p \to q), (q \to r), (r \to s) \vdash (p \to s)$ and deduce $q \to p$ by modus ponens. The story makes little sense, in any case. – Zhen Lin Sep 11 '12 at 9:23
The implication chain $p\to q\to r\to s$ is doubtlessly what the exercise poser had in mind -- since it is what you get if you strive to conclude something new immediately when you get a new piece of information and use each premise only once. Your solution is better, I think, because it highlights the semantic trouble with the story. – Henning Makholm Sep 11 '12 at 9:35

The text of the problem does not state that you have to use the rules of interference. To show that $\neg q$ holds when $\neg p$ and $(p \rightarrow s)\rightarrow(q \rightarrow p)$ holds you can also use truth tables. The lines were $\neg p$ and $(p \rightarrow s)\rightarrow(q \rightarrow p)$ holds are the lines 1,2,3,4. For these lines the last column is 1 so $\neg q$ is true.

$$ \begin{array}{ccccccccccccc} &n&p&q&r&s&p \rightarrow q&q \rightarrow r&r \rightarrow s&(p \rightarrow s)\rightarrow(q \rightarrow p)& \neg p& \neg q\\\hline &1&0&0&0&0&1&1&1&1&1&1\\ &2&0&0&0&1&1&1&1&1&1&1\\ &3&0&0&1&0&1&1&0&1&1&1\\ &4&0&0&1&1&1&1&1&1&1&1\\ &5&0&1&0&0&1&0&1&0&1&0\\ &6&0&1&0&1&1&0&1&0&1&0\\ &7&0&1&1&0&1&1&0&0&1&0\\ &8&0&1&1&1&1&1&1&0&1&0\\ &9&1&0&0&0&0&1&1&1&0&1\\ &10&1&0&0&1&0&1&1&1&0&1\\ &11&1&0&1&0&0&1&1&1&0&1\\ &12&1&0&1&1&0&1&1&1&0&1\\ &13&1&1&0&0&1&0&1&1&0&0\\ &14&1&1&0&1&1&0&1&1&0&0\\ &15&1&1&1&0&1&1&1&1&0&0\\ &16&1&1&1&1&1&1&1&1&0&0 \end{array} $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.