Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Thanks much in advance!!!

share|cite|improve this question
Please do not deface the question. It orphans the answers that people have given. – robjohn Feb 11 '13 at 18:36
up vote 0 down vote accepted

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 ;-)


share|cite|improve this answer
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$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.