Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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.

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

Your Answer

 
discard

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.