[Math] Qns on Propositional Logic – Inference Rules + Logical Equivalence

logicproof-theorypropositional-calculus

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.

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

Related Question