Logic gates analyses

Question

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!!!

Answer 1

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!

Answer 2

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$$