I have an old exam-question but don't know how to solve this type of problems. So If someone could give me a hint it would be much appreciated.

Is the following entailment valid?

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

If I assume that the right handside is false$(\neg t)$ and show that the left handside holds, then the entailment is not valid. But how?


For $$ \neg r \land \neg s  $$ to be true then both  r and s must be false. And if r is false then $$(p \rightarrow q)$$ must be false.  And since $$(q \rightarrow p)$$ must be true, then p is true and q is false.

When t is negated, all premises is satisfiable and therefor the entailment is not valid. Am I right?

  • $\begingroup$ Have you made any progress? $\endgroup$ – Graham Kemp Aug 21 '18 at 2:14
  • $\begingroup$ Oh. Thanks for asking. Not really. I'm I a making it more complicated when adding a negation to 't'(right hand side)? $\endgroup$ – Lars Logik Oct 14 '18 at 16:23
  • $\begingroup$ Yes, indeed; since the conclusion may be false with all premises satisfied, therefore $t$ is not entailed by those premises. $\endgroup$ – Graham Kemp Oct 14 '18 at 21:14
  • $\begingroup$ I have now tried this when assuming t is false and when t is true. Both times all premises is true if p is true and q is false. Is it then correct to say that the entailment is not valid but satisfiable? $\endgroup$ – Lars Logik Oct 16 '18 at 11:52
  • $\begingroup$ Yes, and therefore.... $\endgroup$ – Graham Kemp Oct 16 '18 at 11:56

If all of the premises and the negation of the conclusion can be satisfied, then the conclusion is not a logical entailment of the premises.

$$\{(p \rightarrow q) \rightarrow r, \neg r\land \neg s, (q \rightarrow p) \lor t, t \rightarrow (r \lor p), \neg t\}$$

Clearly, the negation of the conclusion may be satisfied when $t$ is false. That also satisfies the fourth premise, but the third premise would then only be satisfied when $q$ implies $p$.

$$\{(p \rightarrow q) \rightarrow r, \neg r\land \neg s, (q \rightarrow p) \lor \bot, \bot \rightarrow (r \lor p), \neg \bot\}$$

Carry on..

| cite | improve this answer | |
  • $\begingroup$ When you say it also satisfies the fourth premise, do you mean that (r v p) could be either true or false here? $\endgroup$ – Lars Logik Oct 14 '18 at 16:35
  • $\begingroup$ Yes, @LarsLogik . $t\to(r\vee p)$ is satisfied when $\lnot t$ is; so that does not fix $r$ or $p$. For that, look to the second premise, $\lnot r\land\lnot s$. $\endgroup$ – Graham Kemp Oct 14 '18 at 21:07

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.