0
$\begingroup$

I was asked to prove the above. The teacher has assured me that they are indeed equivalent, but when drawing a truth table, I have not been able to show this.

For:

$P =$ F,

$Q =$ T,

$R =$ T.

I have the first portion as true but the second as false.

Would someone be able to confirm whether I have made an error or not?

If it my assertion is indeed wrong and I have messed up somewhere, please do not show me the final proof, as I do want to work it out, but just want to ensure that it is actually provable.

Thanks in advance


EDIT:

Thank both for your help. I just had one final question on the topic regarding semantics

for $$ P \land Q \Rightarrow R $$

JMoravitz, based on your answer, I suppose it should be treated as $$ (P \land Q) \Rightarrow R$$ as opposed to how I was originally viewing the problem$$P\land (Q \Rightarrow R)$$ I'm assuming that everything before an implication should ALWAYS be grouped together? Should everything after the implication also be grouped together regardless of what follows?

if not, how would you go about determining grouping?

$\endgroup$
  • $\begingroup$ Yes, they are equivalent. For $P = F$, $Q = R = T$, we have $P \land Q = F$, so the second statement is true as well. $\endgroup$ – user230734 Sep 6 '15 at 17:34
  • $\begingroup$ There is an order of operations in logic, just as in other fields. The usual order says that parentheses are handled first, then AND and OR (with equal priority), then implication. That much is pretty standard. Another common, but not universal, rule is that implications are right associative, so $P \to Q \to R$ means $P \to (Q \to R)$ instead of $(P \to Q) \to R$. This latter rule is motivated by the fact that $P \to (Q \to R)$ is more commonly encountered, since it is equivalent to $P \land Q \to R$. $\endgroup$ – Carl Mummert Sep 6 '15 at 18:07
  • $\begingroup$ AND and OR do not have equal priority. AND wins, especially since we often split into cases each of which is a conjunction of conditions. Also, NOT always goes first before them. $\endgroup$ – user21820 Oct 22 '15 at 12:22
0
$\begingroup$

Remember that $A\Rightarrow B$ is true whenever $A$ is false. So, for the first $P$ being false, it is false implies (something), therefore the implication is true.

For the second, it is (false and true) implies (something). false and true simplifies to simply false, so again we have false implies (something), and therefore the implication is true.

tldr: P:F, Q:T, R:T is not a counterexample


As a hint/reminder on how best to proceed, remember that $A\Rightarrow B$ is logically equivalent to $\neg A \vee B$

$\endgroup$
  • $\begingroup$ thanks for your help, would you be able to check my edit just for final clarification on my small question regarding semantics? $\endgroup$ – user3256725 Sep 6 '15 at 17:51
  • $\begingroup$ Ah, I see why you might have been confused. Indeed, it is somewhat ambiguous what was intended, but in my experience $P\wedge Q\Rightarrow R$ should generally be interpreted as $(P\wedge Q)\Rightarrow R$. There are certainly situations where the other interpretation might be useful however. Another user on the site was quoted once as saying "A wise person will use enough parenthesis so that the meaning is perfectly clear." $\endgroup$ – JMoravitz Sep 6 '15 at 17:54
  • $\begingroup$ @user3256725 As for a general rule, it is my interpretation that if an implication arrow ($\Rightarrow$) appears, unless parenthesis also appear, all terms on the left are grouped and all terms on the right are grouped: $P\wedge Q\Rightarrow R\wedge S$ would be interpreted as $(P\wedge Q)\Rightarrow (R\wedge S)$, but it might not necessarily be standard. Verifying this with your teacher would be good as well, and interpretation questions like "if things are grouped" are generally allowed during tests. $\endgroup$ – JMoravitz Sep 6 '15 at 17:56

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.