# Qns on Propositional Logic - Inference Rules + Logical Equivalence

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$

Whence

$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).

• Could not believe it's this simple! Thanks for the clear explanation! – 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.

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