Is XOR a combination of AND and NOT operators?

Yes. In fact, any logical operation can be built from the NAND operator, where

A NAND B = NOT(A AND B)

See for instance http://en.wikipedia.org/wiki/NAND_logic, which gives

A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))

Digression: There is a story about certain military devices being designed using only NAND gates, so that only one part needs to be certified, stocked as spares, etc. I don't know whether it's actually true.


enter image description here


Meanwhile, let me add the fact that XOR is not expressible by any expression whose operations use only AND, OR, IMPLIES, ConverseImplies and IFF.

To see this, observe merely that True XOR True is False, but the other operations always take True input to True output, a feature that would be inductively preserved in complex expressions.

Tags:

Logic

Boolean Algebra

Related

No uncountable ordinals without the axiom of choice? "Standard" ways of telling if an irreducible quartic polynomial has Galois group C_4? Connections between metrics, norms and scalar products (for understanding e.g. Banach and Hilbert spaces) Exact values of $\cos(2\pi/7)$ and $\sin(2\pi/7)$ Distinguishing between symmetric, Hermitian and self-adjoint operators Methods for showing three points in $\mathbb{R}^2$ are colinear (or not) Countable compact spaces as ordinals Are all extensions of finite fields cyclic? When is $\mathrm{Hom}(A,R) \otimes B =\mathrm{Hom}(A,B)$? $G\rtimes_\phi H \cong G\rtimes_\psi H$ when certain automorphisms exist If $X$ is a connected metric space, then a locally constant function $f: X \to $ M, $M $ a metric space, is constant Intuition for a relationship between volume and surface area of an $n$-sphere

Recent Posts