# Discrete Mathematics - are Boolean functions equal?

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.

• note that I improved your type-setting a bit so you can learn how to do it yourself. – Ittay Weiss Mar 3 '14 at 2:18
• @IttayWeiss Thank you – 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.

• 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 1: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 1:39
• [link]math.stackexchange.com/q/693420/132016 Sir, can you provide a feed back on this thanks. – Kit lai Mar 3 '14 at 0: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 3 '14 at 2:14
• @IttayWeiss I can conclude that the two functions are not equal. – Kit lai Mar 3 '14 at 9:50