# Boolean Algebra (Matrix?)

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?

• Yes, it is possible. – tomi May 21 at 11:10
• @tomi do you know how this is done? – Ben Crossley May 21 at 11:15
• Not really! I think it could be done using a 27 state Markov chain process. – tomi May 21 at 11:18

## 1 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:

1. $$[QQQ]$$
2. $$[QQT]$$
3. $$[QQF]$$
4. $$[QTQ]$$
5. $$[QTT]$$
6. $$[QTF]$$
7. $$[QFQ]$$
8. $$[QFT]$$
9. $$[QFF]$$
10. $$[TQQ]$$
11. $$[TQT]$$
12. $$[TQF]$$
13. $$[TTQ]$$
14. $$[TTT]$$
15. $$[TTF]$$
16. $$[TFQ]$$
17. $$[TFT]$$
18. $$[TFF]$$
19. $$[FQQ]$$
20. $$[FQT]$$
21. $$[FQF]$$
22. $$[FTQ]$$
23. $$[FTT]$$
24. $$[FTF]$$
25. $$[FFQ]$$
26. $$[FFT]$$
27. $$[FFF]$$

The $$27 \times 27$$ matrix $$M$$ has entries $$M_{ij}=1$$ if being in State $$i$$ will allow you to move to State $$j$$.

• But if you are in $\left[TQT\right]$ then you must move to $\left[TTT\right]$. I agree that you must move there, but how are you performing this calculation? What operation have you performed or function have you applied on $\left[TQT\right]$ to get the answer $\left[TTT\right]$ – Ben Crossley May 21 at 11:46
• You will have a vector $x_0$ that will tell you what state you start in. You will have a transition matrix $M$ that describes the movements from state to state. You calculate $x_n = M^nx_0$ to find the state after $n$ steps. – tomi May 21 at 12:05
• Ok, I think I'm following. I need to predefine all of the transitions by finding the correct matrix. I'm going to use $1$ as $T$, $0$ as $Q$ and $-1$ as $F$. so I need to find a matrix $M$ such that all of the mappings are correct. I.e. $\left[\begin{matrix} 1 & 1 & 1 \end{matrix}\right] = M \left[\begin{matrix} 1 & 1 & 0 \end{matrix}\right]$ and $\left[\begin{matrix} 1 & 0 & 0 \end{matrix}\right] = M \left[\begin{matrix} 1 & 0 & 0 \end{matrix}\right]$ for all possible transitions. Are you sure such a matrix exists? – Ben Crossley May 21 at 12:14
• It's worse than that! I'll expand on my answer. – tomi May 21 at 13:11
• I didn't initially clock that you were using a Markov chain. – Ben Crossley May 21 at 13:59