Construct XNOR with only OR gates

Question

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND and NOT gates using only OR which I do not believe is possible. I've played around with the truth tables for a while now and I'm not getting anywhere, but I'm also not sure how to prove this isn't possible. Any help is appreciated. Thanks.

Answer 1

Let us say that a logical circuit with $n$ inputs and one output, say $f(x_1,\ldots,x_n)$, is “false-preserving” if its output is false whenever all its inputs are false; that is if $$\def\f{\operatorname{false}}f(\f,\f,\ldots,\f) = \f.$$ For example, $\lor$ is false-preserving because $\f\lor\f = \f$, and $\land$ is false-preserving because $\f\land\f = \f$.

We can prove by induction on the number of gates that any circuit composed entirely of of false-preserving gates is also false-preserving. (I omit the proof, which is straightforward.)

Any circuit composed only of $\lor$ gates is composed entirely of false-preserving gates and is therefore false-preserving.

However, XNOR is not false-preserving, and so is not a composition of $\lor$ gates.

Answer 2

Any circuit constructed using only OR gates is monotonic, by which I mean that flipping inputs from FALSE to TRUE can only make the output "truer". XNOR does not have this property.

Answer 3

OR means that if at least one of the inputs qualifies as true, then the output will qualify as true. NOT has the property that if the input is true, then the output is false. In that case, at least one of the inputs of "NOT" qualifies as true, but the output is false. Thus, there is no way to represent NOT using just OR.