Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$.

If p,q = (0,1)

(p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1

(p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0

Therefore (p$∧$q)$∨$q $≠$ (p$∧$q)$∨$~q.

Is my proof good enough? I realize that this question has been asked more than once here but I didn't quite understand the proofs that they gave. Any feedback will be greatly appreciated thanks!

  • $\begingroup$ No, it is not. You really have not proved anything related to the question. $\endgroup$ – Andrés E. Caicedo Apr 9 '14 at 6:13
  • $\begingroup$ @AndresCaicedo thanks. Which basically means I don't understand the question. If you're willing can you please explain to me what it is asking me to do? $\endgroup$ – JayS Apr 9 '14 at 6:35
  • 1
    $\begingroup$ You need to give an example of a Boolean function $f$ with the property that $f\ne g$ for all Boolean functions $g$ constructed using only $\land$ and $\lor$. $\endgroup$ – Andrés E. Caicedo Apr 9 '14 at 6:41
  • 1
    $\begingroup$ You could represent the function f such that f(x)=x using $\land$ and $\lor$ by using [x$\land$(x$\lor$y)]. There's a Boolean function "1" such that 1 (x, y)=1 for all x, y, which can represent every tautology. Can you make any tautologies using just $\land$ and $\lor$ and variables? $\endgroup$ – Doug Spoonwood Apr 9 '14 at 14:42

I don't think it's good enough because you are just showing that two particular boolean functions are not always equal. Hint: use a single variable, two is unnecessarily complicated.


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.