Analyze the validity of the following reasoning without using truth tables

Question

I have to decide whether the following reasoning is valid or not:

$$\{\neg p\Rightarrow [(\neg s\Rightarrow \neg r)\;\wedge\;(\neg s\vee t)]\;\wedge\;\neg t\}\quad\Rightarrow\quad p.$$

I have no idea how to prove it. I tried different ways but I'm stuck.

For example, I separated it on premises:

$$\begin{array}{ll} P_1:&\neg p\Rightarrow [(\neg s\Rightarrow \neg r)\;\wedge\;(\neg s\vee t)] \\ P_2:&\neg t \end{array}$$

$\neg t$ must be $T$, so $t$ must be $F$. But by replacing its truth value in $P_1$ I can not assure anything of $p$. On the other hand, if I try to reduce the proposition, it does not give me guarantees of anything over $p$.

What demonstration method should be used? And how would you prove it without using truth tables?

Thanks!

Answer 1

You can do this using the 'short truth-table method'.

The idea here is that you try to see whether or not the statement can be false, and so, let's see what has to be the case when the statement is false. As such, we'll put $F$ under the main connective:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &&&&&&&&&&&&&&&&&&&&&&F\\ \end{array}

A conditional can only be false when the antecedent is true and the consequent is false:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &&&&&&&&&&&&&&&&&&T&&&&F&F\\ \end{array}

For the conjunction to be true, both conjuncts need to be true:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &&&T&&&&&&&&&&&&&&&T&T&&&F&F\\ \end{array}

If $\neg t$ is to be True, and $t$ should be False:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &&&T&&&&&&&&&&&&&&&T&T&F&&F&F\\ \end{array}

Copy the values of $p$ and $t$:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &&F&T&&&&&&&&&&&&&F&&T&T&F&&F&F\\ \end{array}

This means $\neg p$ is True:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&&&&&&&&&&&F&&T&T&F&&F&F\\ \end{array}

A true conditional with a true antecedent means the consequent is true:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&&&&&&T&&&&&F&&T&T&F&&F&F\\ \end{array}

Both conjuncts are true:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&&T&&&&T&&&&T&F&&T&T&F&&F&F\\ \end{array}

The disjunction is true, and with one disjunct false, the other one has to be true:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&&T&&&&T&&T&&T&F&&T&T&F&&F&F\\ \end{array}

So, $s$ is False:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&&T&&&&T&&T&F&T&F&&T&T&F&&F&F\\ \end{array}

Copy value of $s$:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&&F&T&&&&T&&T&F&T&F&&T&T&F&&F&F\\ \end{array}

Negate $s$ (of course you could have directly copied the value of $\neg s$ as well):

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&T&F&T&&&&T&&T&F&T&F&&T&T&F&&F&F\\ \end{array}

This means $\neg r$ has to be True:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&T&F&T&T&&&T&&T&F&T&F&&T&T&F&&F&F\\ \end{array}

And hence $r$ itself is False:

\begin{array}{cccccccccccccccccc} \{&\neg &p &\rightarrow &[(&\neg &s & \rightarrow &\neg &r&)&\land&(&\neg &s&\lor &t&)]&\land&\neg &t&\}&\rightarrow &p\\ &T&F&T&&T&F&T&T&F&&T&&T&F&T&F&&T&T&F&&F&F\\ \end{array}

OK, we filled out every truth-value ... and found no contradictions. So that tells us that the statement can indeed be made false, meaning it is not valid. And, as a bonus, we have our counterexample as well: set all variables to False. In fact, since everything was forced, we know this is the only counterexample.

Answer 2

You have reasoned that the argument is not valid.

More formally, you should show that accepting the premises $P_1$ and $P_2$, and making an assumption of $\neg p$, cannot lead to any contradictions in your proof system.   That is that the conclusion may be false while the premises are all true.