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.
Asked
Active
Viewed 78 times
0
-
This question was asked here recently: http://math.stackexchange.com/questions/707337/every-boolean-function-is-constructed-from-wedges-and-vees#comment1501826_707337 – coffeemath Mar 19 '14 at 10:43
2 Answers
0
Hint: the Boolean functions constructed with only $\wedge$ and $\vee$ are nondecreasing in all variables.
bof
- 78,265
0
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$.
sas
- 3,117
- 1
- 17
- 29