$(\neg p\land q)\land(r\to p)\land(\neg r\to s)\land(s\to t)\implies t$

Question

Use rules of inference and laws of logical equivalence to prove $$(\neg p\land q)\land(r\to p)\land(\neg r\to s)\land(s\to t)\implies t$$

Writing this in a truth table confirmed to me that it was not a tautology nor a contradiction, but I don't know the ideal way to use these rules to break it down. Any help would be great.

Answer 1

• LHS false

This is realized as soon as one of the clause is false. For instance if $q=0$ then whole expression is false independently of the values taken by the other variables.

False LHS can imply any RHS, so this is ok.

• LHS true

Then all clauses should be true

$\begin{array}{ll} c_1 \implies p=0,q=1 &\text{to have }1\land 1=1\\ c_2 \implies r=0\ & \text{only false can imply false}\\ c_3 \implies s=1 & \text{true implies true}\\ c_4 \implies t=1 & \text{true implies true}\\ \end{array}$

True LHS can only imply true RHS, since $t=1$ is forced this is ok.

Answer 2

To prove that $A$ implies $B$ one often checks the unsatisfiability of $A \wedge \neg B$. In our case, $\neg B$ is $\neg t$. Noting that $A \rightarrow B$ is equivalent to $\neg B \rightarrow \neg A$, with a little rewriting of the left-hand side we get

$$ \neg t \wedge (\neg t \rightarrow \neg s) \wedge (\neg s \rightarrow r) \wedge (r \rightarrow p) \wedge \neg p \wedge q \enspace. $$

A few applications of modus ponens show that our formula implies $p \wedge \neg p$ and is therefore unsatisfiable. Hence, the implication holds.

Answer 3

$(\neg p\land q)\land(r\to p)\land(\neg r\to s)\land(s\to t)\implies t$

Break down all of the implications using De Morgan's Law...

$(\neg p\land q)\land(\neg r\lor p)\land(r\lor s)\land(\neg s \lor t)\implies t$

Reorder within to notice a the relationship...

$(q \land \neg p )\land(p\lor \neg r)\land(r\lor s)\land(\neg s \lor t)\implies t$

The distributive law can be then used with the and statements...

$((q\land\neg p\land p) \lor (q\land\neg p\land\neg r))\land(r\lor s)\land(\neg s\lor t)\implies t$

This simplifies the first part because $p \land \neg p $ cannot be satisfied

$(q\land\neg p\land\neg r)\land(r\lor s)\land(\neg s\lor t)\implies t$

Distributing again, we see yet another contradiction...

$((q\land\neg p\land\neg r \land r)\lor (q\land\neg p\land\neg r \land s))\land (\neg s\lor t)\implies t $

Getting rid of the first contradiction $\neg r \land r$ ...

$(q\land\neg p\land\neg r \land s)\land (\neg s\lor t)\implies t $

Distributing again, there is a contradiction with $\neg s \land s$ ...

$(q\land\neg p\land\neg r \land s \land \neg s)\lor (q\land\neg p\land\neg r \land s \land t ) \implies t $

Getting rid of the first part which cannot be satisfied, we are left with

$(q\land\neg p\land\neg r \land s \land t) \implies t $

Using Demorgan's Law again we have...

$\neg(q\land\neg p\land\neg r \land s \land t) \lor t $

Distributing the Negative...

$(\neg q\lor p \lor r \lor \neg s \lor \neg t) \lor t $

I may have missed an and or an or along the line because this comes out to a tautology with the t but that's apparently not the case. Check my work and make use of the distribution property and demorgan's law to pick out all of the points where it's ...or contradiction...

Answer 4

Lets use conditional proof to prove $$(\neg p\land q)\land(r\to p)\land(\neg r\to s)\land(s\to t)\implies t$$

What we need to do is to make 4 assumptions and then derive $t$ from them.

$1\quad\{1\}\quad \neg p\land q\quad$ Premise

$2\quad\{2\}\quad r\to p\quad$ Premise

$3\quad\{3\}\quad \neg r\to s\quad$ Premise

$4\quad\{4\}\quad s\to t\quad$ Premise

$5\quad\{1\}\quad \neg p\quad$ (1) Simplification

$6\quad\{3,4\}\quad \neg r \to t\quad$ (3,4) Hypothetical Syllogism

$7\quad\{2\}\quad \neg p \to \neg r\quad$ (2) Contraposition

$8\quad\{1,2\}\quad \neg r\quad$ (5,7) Law of Detachment

$9\quad\{1,2,3,4\}\quad t\quad$ (6,8) Law of Detachment

$10\ (\neg p\land q)\land(r\to p)\land(\neg r\to s)\land(s\to t)\to t\quad$ (9) Conditional Proof

Numbers in the second column correspond to the premises on which that lines depends. Numbers on the right correspond to lines that were used in the derivation of the current line. Notation is based on Patrick Suppes book Introduction to Logic.