Have been working on this for the past 2 hours and still not getting any where. Any help will be much appreciated!

Consider the following argument

1) p
2) p v q
3) q → (r → s)
4) t → r

∴¬s → ¬t

Analyze the validity of the argument. If it is valid, show the proof with the inference rules & logical equivalence laws. If it is not valid, show a counterexample (which results in all premises being true but the condition being false).

I've tried using the basic inference rules (modus ponens/tollens, conjunctive simplification/addition, disjunctive addition/syllogism & hypotehtical syllogism) + the all the logical equivalence laws but am unable to derive an answer.


Proceed methodically: Suppose the premisses are true and conclusion false. So

$1.\quad p \quad \Rightarrow \quad T$

$2.\quad p \lor q \quad \Rightarrow \quad T$

$3.\quad q \to (r \to s) \quad \Rightarrow \quad T$

$4.\quad t \to r \quad \Rightarrow \quad T$

$5.\quad \neg s \to \neg t \quad \Rightarrow \quad F$

From the last, you know

$6.\quad \neg s \quad \Rightarrow \quad T$

$7.\quad \neg t \quad \Rightarrow \quad F$


$8.\quad s \quad \Rightarrow \quad F$

$9.\quad t \quad \Rightarrow \quad T$

4 and 9 give us

$10.\quad r \quad \Rightarrow \quad T$

So $r \to s$ is false, and hence, from (3)

$11.\quad q \quad \Rightarrow \quad F$.

So we've worked backwards to successfully find a valuation of all the variables (at lines 1, 8--11) which you can check makes all of 1 to 5 true, i.e. makes the premisses true and conclusion false.

Systematizing this "working backwards" method gives us the user-friendly method of "semantic tableaux" or "truth-trees" used in many textbooks (including mine, and Paul Teller's which is freely available online).

  • $\begingroup$ Could not believe it's this simple! Thanks for the clear explanation! $\endgroup$ – KillerKidz Sep 5 '13 at 14:49

It is false, since you can instantiate p=1, q=0, r=1, s=0, t=1, that verify all the premises but not the conclusion.

Moreover notice that the assumption 2 is useless, since it is direct consequence of assumption 1.


To show it is false, you need to show that $\neg s$ can be true while $\neg t$ can be false without contradicting the assumptions. In other words, $\neg s \land t$.

First, note that assumption $2$ doesn't tell us anything since it follows from $1$. Also, the assumptions $3$ and $4$ (and the argument) don't talk about $p$, so it is easy to make assumption $1$ true by setting $p$ true. Now, the easiest way to make assumption $3$ true is to set $q$ as false. Finally for $4$, since we want our $t$ to be true, set $r$ as true too.

So, $p=\text{True}, q=\text{False}, r=\text{True}, t=\text{True} \text{ and } s=\text{False}$ is a counterexample.

  • $\begingroup$ Would have voted up this ans if not for the lack of reputation score. Thanks a lot! $\endgroup$ – KillerKidz Sep 5 '13 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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