0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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]$ $\endgroup$ – Ben Crossley May 21 at 11:46
  • $\begingroup$ 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. $\endgroup$ – tomi May 21 at 12:05
  • $\begingroup$ 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? $\endgroup$ – Ben Crossley May 21 at 12:14
  • $\begingroup$ It's worse than that! I'll expand on my answer. $\endgroup$ – tomi May 21 at 13:11
  • $\begingroup$ I didn't initially clock that you were using a Markov chain. $\endgroup$ – Ben Crossley May 21 at 13:59

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.