Discrete Mathematics - are Boolean functions equal?

233 Views Asked by At

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.

1

There are 1 best solutions below

5
On

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.