0

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.

user376343
  • 8,311
Kit lai
  • 49

1 Answers1

1

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.

Rebecca J. Stones
  • 26,845
  • 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? – Kit lai Feb 28 '14 at 01:38
  • 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. – Rebecca J. Stones Feb 28 '14 at 01:39
  • [link]http://math.stackexchange.com/q/693420/132016 Sir, can you provide a feed back on this thanks. – Kit lai Mar 03 '14 at 00:50
  • @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)$? – Ittay Weiss Mar 03 '14 at 02:14
  • 1
    @IttayWeiss I can conclude that the two functions are not equal. – Kit lai Mar 03 '14 at 09:50