# Logic gates analyses

How to write the output of the gates not, and, or, xor, nand and nor in terms of their inputs, expressed as zeros and ones, using base 10 addition and multiplication.

-
Please do not deface the question. It orphans the answers that people have given. –  robjohn Feb 11 '13 at 18:36

Any gate could be expressed using $\mathtt{nand}$ and assuming you want $\mathtt{falsehood} = 0$ and $\mathtt{truth} = 1$, you can express $\mathtt{nand}$ as $$\mathtt{nand}(x,y) = 1-x\cdot y.$$

The nice way to look at the problem of expressing logic gates in terms of real numbers addition/multiplication is from the perspective of probability theory. The issue with logic gates is that they behave in a discrete, rather than continuous way. It is the same with sets, in fact logic gates are very similar to set operators, that is \begin{align} a \land b &\to A \cap B, \\ a \lor b &\to A\cup B, \\ \neg a &\to A^c, \end{align} and so on (it is not a coincidence those symbols are similar). But then instead of taking $x \in A$ we could write $P(x \in A)$, and as if by magic we moved from discrete world into a continuous one. Using this intuition we could write (for $A$ and $B$ independent):

\begin{align} P(A \cap B) &= P(A)\cdot P(B)\\ P(A \cup B) &= P(A)+P(B) - P(A \cap B) \\ P(A^c) &= 1-P(A) \\ \end{align} and therefore $\mathtt{nand}$ can be expressed as $$P\left((A \cap B)^c\right) = 1 - P(A)\cdot P(B).$$

Of course, the above formulas would give you much simpler way of expressing $\mathtt{and}$, $\mathtt{or}$, and others in terms of addition and multiplication that the proposed in the begging $\mathtt{nand}$ method. However, as I have done most of the work, I leave the rest for you ;-)

Cheers!

-
Thanks much!!!!! –  user60465 Feb 9 '13 at 10:04

Since $\neg$ and $\land$ are functionally complete (i.e., they together suffice to form all logical operators), it suffices to have the following:

$$\neg x := 1 - x \qquad x \land y := x \cdot y$$

(Possible) Definitions for the other logical operators can then be derived by expressing them in terms of $\neg$ and $\land$. E.g.: $$x \mathbin{\mathsf{NOR}} y = (\neg x) \land (\neg y) = (1-x)(1-y) = 1 + x y - x -y$$

-