Are the boolean functions $(p\wedge \neg q)\vee (\neg r\wedge q)$ and $(p\vee \neg q)\wedge (r \vee \neg q)$ equal? Explain your answer.

Here my solution, please give me a feedback on this solution, I'm very eager to learn more on my mistakes, Thanks (I'm a slow learner bear with me if I dont really understand your points driving to me)

For the first expression:
$(p \wedge \neg q) \vee (\neg r \wedge q)\quad \quad \quad 0\;0\;1\;0\;1\;1\;1\;0$

For the second:
$(p \vee \neg q) \wedge (r \vee \neg q)\quad \quad \quad 1\;1\;0\;0\;1\;1\;0\;1$

Conclusion: No, the two functions are not equal.

  • $\begingroup$ note that I improved your type-setting a bit so you can learn how to do it yourself. $\endgroup$ – Ittay Weiss Mar 3 '14 at 2:18
  • $\begingroup$ @IttayWeiss Thank you $\endgroup$ – Kit lai Mar 3 '14 at 9:50

The best way to prove these are not equal is to find an explicit counter-example. (This may be what you're attempting, but it's hard to read.)

$$(p \wedge \neg q) \vee (\neg r \wedge q)$$ $$(p \vee \neg q) \wedge (r \vee \neg q)$$

In the second expression, we see that if $q$ is FALSE, then the expression is TRUE regardless of $p$ and $q$.

It is possible to find $p$ and $r$ such that the first expression is FALSE when $q$ is FALSE.

This provides a counter-example.

  • $\begingroup$ Sorry for that, I'm still learning on how to use proper symbols too. Can I ask how do you actually determine which one is either True or False in one of the variables? $\endgroup$ – Kit lai Feb 28 '14 at 1:38
  • $\begingroup$ If the two expressions are equal, then they are equal for all assignments of TRUE/FALSE to the variables. Therefore, if there is a single way of assigning TRUE/FALSE to the variables in which the two expressions are not equal, then they are not equal in general. This is the counter-example; it shows they're not always equal. $\endgroup$ – Rebecca J. Stones Feb 28 '14 at 1:39
  • $\begingroup$ [link]math.stackexchange.com/q/693420/132016 Sir, can you provide a feed back on this thanks. $\endgroup$ – Kit lai Mar 3 '14 at 0:50
  • $\begingroup$ @Kitlai remember that boolean expressions as the ones above are actually functions. You can write $f=(p\wedge ~q)\vee (~r\wedge q)$. Then you can evaluate $f(0,0,0)$ and get some value (you computed that value and more above). Similarly, you can call the second expression $g$ and evaluate $g(0,0,0)$. What can you conclude if you see that $f(0,0,0)\ne g(0,0,0)$? $\endgroup$ – Ittay Weiss Mar 3 '14 at 2:14
  • 1
    $\begingroup$ @IttayWeiss I can conclude that the two functions are not equal. $\endgroup$ – Kit lai Mar 3 '14 at 9:50

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.