# Matrix Representation for logical gates?

I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ where:

$$\begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} X \oplus \neg X, \ 0 \oplus \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} 1, \ \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix}$$ $$= Y \oplus (\neg X \neg Y) = X \Rightarrow Y$$

Note that the juxtaposition of two variables without an operator corresponds to conjunction i.e. $$XY = X \wedge Y$$ and of course $$1 \wedge X = X$$ and $$0 \wedge X = 0$$ and are written accordingly. Actually all of the propositional logical operators can be done with a unique binary $$2 \times 2$$ matrix - it is fascinating.

Yes, "all of the propositional logical operators can be done with a unique binary 2×2 matrix".

In fact, every possible map $$g: \{0,1\}\times\{0,1\}\to\{0,1\}$$ can be done with a unique binary 2x2 matrix.

Here is a proof.

\begin{align} &\quad \begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\&= \begin{bmatrix} XA \oplus \neg XC, \ XB \oplus \neg XD \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\ &= XAY \oplus \neg XCY \oplus XB\neg Y \oplus \neg XD\neg Y\\ \end{align}

• Suppose the above expression equals $$g(X,Y)$$.
• Let $$X=0, Y=0$$, we get $$0\oplus0\oplus0\oplus D=D=g(0,0)$$.
• Let $$X=0, Y=1$$, we get $$0\oplus C\oplus0\oplus 0=C=g(0,1)$$.
• Let $$X=1, Y=0$$, we get $$0\oplus0\oplus B\oplus 0=B=g(1,0)$$.
• Let $$X=1, Y=1$$, we get $$A\oplus0\oplus0\oplus 0=A=g(1,1)$$.
• Conversely, if we have $$A= g(1,1)$$, $$B= g(1,0)$$, $$C=g(0,1)$$ and $$D=g(0,0)$$, the above expression can be verified to be equal to $$g(X,Y)$$ for all $$X, Y$$.

So we have proved that

$$\begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = g(X,Y) \\ \Leftrightarrow A= g(1,1),\ B= g(1,0),\ C=g(0,1),\ D=g(0,0)$$

If we use in-fix notation for $$g$$, we have $$\begin{bmatrix} X, \ \neg X \end{bmatrix} \begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = XgY,$$ or $$\begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix} \equiv g.$$ In particular, we can substitute $$g$$ by anyone of $$\land, \lor, \oplus, \odot, \Rightarrow, \Leftarrow, \equiv$$.

For more related concepts and computation, please check boolean rings.

• Wow, I really appreciate this, I will add it to a paper I am working and and cite this answer. – Relative0 Jan 16 '19 at 23:30
• For the paper I am working on I originally posted this question to find if something similar had been discovered so as to give credit where it is due and cite it in my paper. – Relative0 Jan 16 '19 at 23:32
• You are welcome and thanks. If you are asking for the origin, I cannot recall whether I have read my answer before or not. It looks like folklore to me. – John L. Jan 16 '19 at 23:40