Boolean functions built from $\wedge$ and $\vee$

79 Views Asked by At

Prove that not every Boolean function is equal to a Boolean function constructed by only $\wedge$ and $\vee$. Please can you help me giving some hint.

2

There are 2 best solutions below

0
On

Hint: the Boolean functions constructed with only $\wedge$ and $\vee$ are nondecreasing in all variables.

0
On

Both functions preserve $1$. So if you have some formula with variables $x_1 \ldots x_n$ and if all of them are equal to $1$, the result is also equal to $1$.