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?



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.

  • $\begingroup$ Thank you! First question: 1) Does the 'short truth-table method' has something to do with a- 'direct method', b-'absurd method' or c-'counterreproach method'? And 2) I don't understand the following: "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."; what do you mean by "everything was forced"? And how do you come to know that "this is the only counterexample"? $\endgroup$
    – manooooh
    Apr 8 '18 at 16:09
  • $\begingroup$ @manooooh Hmm, I am not sure I know what those 'methods' refer to ... especially the 'counterreproach method' ... do you have some description for each? And by 'everything is forced', I meant that every truth-value I put down was forced by the very first truth-value I put down. So, there is one and only one way to make the statement false, meaning that there is exactly one counterexample. $\endgroup$
    – Bram28
    Apr 8 '18 at 17:02
  • $\begingroup$ I start with the second answer: But do not we have to see what happens if we assume that the statement is true? (You did it for the false case). Or already to find a contradiction does not need to choose the other alternative? $\endgroup$
    – manooooh
    Apr 8 '18 at 19:34
  • 1
    $\begingroup$ @manooooh OK, then what I did is most closely related to the method of the absurd: once I assume the conditional was False, I was forced to assume the antecedent to be True and the consequent to be False ... and went from there. So that ends up as the same set-up as the method of the absurd ... but of course we did not end up with an absurdity, and hence no proof that the conditional is valid. In fact, we showed that it is definitely possible to have a true antecedent and false consequent, thus showing the statement is invalid. $\endgroup$
    – Bram28
    Apr 8 '18 at 19:37
  • 1
    $\begingroup$ Yay I understood $\endgroup$
    – manooooh
    Apr 8 '18 at 19:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.