0
$\begingroup$

I'm asking this in the context of a logical programming language similar to Prolog.

Say I have the rule $P ⇒ (Q ∨ S)$ . How would I go about proving the truth value of $Q$, assuming I know the values of $S$ and $P$, and possibly other information.

I've thought about it and found that I could prove that $Q$ is True for $(P ∧ ¬S)$ , in other words $Q$ must be True if $P$ is True and $S$ is False. However I can't seem to figure out what to do if $S$ is True.

Any help is appreciated !

edit : thanks @ervx for pointing out $P ⇒ Q ∨ S$ vs $P ⇒ (Q ∨ S)$

$\endgroup$
  • $\begingroup$ I assume you want $P\implies (Q\vee S)$ above. $\endgroup$ – ervx Apr 21 '16 at 20:19
1
$\begingroup$

Note that $P\implies (Q\vee S)$ is equivalent, as you pointed out, to $(\neg P\vee S)\vee Q$. Thus, to show that $Q$ is true, given only this information, you must show that $(\neg P\vee S)$ is false; i.e., that $P$ is true and $S$ is false. Without any more information, there is not way to conclude for sure that $Q$ is true. If $P$ and $S$ are true, then $Q$ could indeed be false and the statement $P\implies (Q\vee S)$ would still be true.

$\endgroup$
1
$\begingroup$

A more compact way of seeing this is simply that $\bot \lor S \iff S$. So $P \Rightarrow S$ is equivalent to $P \Rightarrow (\bot \lor S)$ which is to say $Q$ need not be true if $P \Rightarrow S$ holds (though, of course, $Q$ still could be true).

$\endgroup$

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.