finding a boolean function with specific property

Question

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$.

My solution is $$\left(p\wedge\thicksim q\right) \vee\left(\thicksim r\wedge q\right)$$

Please i want some feedback if my work is correct or not and some hints to improve my answer.

Answer 1

the solution you gave above is, at best, obscure. Think about what you need to do: You need to first exhibit a boolean function about which you intend to claim that it can't be written only using conjunction and disjunction. Then, you actually need to give an argument why that is the case. Hint: if a boolean function is written using only conjunction and disjunction, what will happen when you evaluate it when all its variables are equal to $1$? Can you now think of a function that can't possibly be expressed only with conjunction and disjunction?

Answer 2

Hint:

• We have that $\land$ and $\lor$ are monotone (projections and similar are monotone as well).
• Composition of monotone function is monotone.
• Boolean functions do not need to be monotone in general.

I hope this helps $\ddot\smile$

Answer 3

An unary negation function $$x\mapsto \lnot x$$ can't be written with $\lor$ and $\land$ only (because $x\lor x = x\land x = x$ while $\lnot x \ne x$), so such function exists.