3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, I really appreciate this, I will add it to a paper I am working and and cite this answer. $\endgroup$ – Relative0 Jan 16 at 23:30
  • $\begingroup$ 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. $\endgroup$ – Relative0 Jan 16 at 23:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Jan 16 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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