I am new to Boolean Algebra and I'd just like to know: Is it possible to encode boolean logic into a matrix such that successive powers of that matrix perform logical computations?
For example, given $A$ and $A \Rightarrow B$, we can deduce $B$. Is it possible to have a matrix such that the information $A$ and $A \Rightarrow B$ are already present, then upon squaring this matrix it also shows that $B$ is true, and further powers do not change the information?
I suspect this is impossible, as posed above, but may be possible with some matrix operations other than powers or some structure other than a matrix, i.e. a tensor. If it is possible, how is this done?
Best Answer
I think it could be done using a 27 state Markov chain process.
I propose using 27 states to represent our knowledge at any given time about the following three: $A$, $B$, $A \implies B$.
$[QQQ]$ means that we do not know whether any of the three are true or false.
$[QTF]$ means that we do not know whether $A$ is true or false, we know that B is true and we know that $A \implies B$ is false.
The states are therefore: $[QQQ]$,$[QQT]$,$[QQF]$,$[QTQ]$,$[QTT]$,$[QTF]$,$[QFQ]$,$[QFT]$,$[QFF]$,$[TQQ]$,$[TQT]$,$[TQF]$,$[TTQ]$,$[TTT]$,$[TTF]$,$[TFQ]$,$[TFT]$,$[TFF]$,$[FQQ]$,$[FQT]$,$[FQF]$,$[FTQ]$,$[FTT]$,$[FTF]$,$[FFQ]$,$[FFT]$,$[FFF]$.
It would be possible to create a transition matrix showing the conclusion that can be drawn from the state you are in at the moment.
So if you start in $[QQQ]$ you will always be in $[QQQ]$. There will be a lot of states like that, where no further information can be gained.
But if you are in $[TQT]$ then you must move to $[TTT]$. And once you are in $[TTT]$ you will stay there for higher powers of the matrix.
States are:
The $27 \times 27$ matrix $M$ has entries $M_{ij}=1$ if being in State $i$ will allow you to move to State $j$.