0

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?

Ben Crossley
  • 2,544

1 Answers1

1

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

tomi
  • 9,594
  • 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 '19 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 '19 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 '19 at 12:14
  • It's worse than that! I'll expand on my answer. – tomi May 21 '19 at 13:11
  • I didn't initially clock that you were using a Markov chain. – Ben Crossley May 21 '19 at 13:59
  • Whilst I appreciate your answer, it doesn't actually perform the task I'd like it to perform. You have encoded the state of the system into a separate vector whereas I want to encode the entire system into the matrix, the current state included. – Ben Crossley May 21 '19 at 14:04
  • That can probably be added in... just makes things more awkward. – tomi May 21 '19 at 14:13
  • I was also looking for a far more condensed way of doing this. My aim (for myself) was to solve a 4x4 Sudoku using boolean algebra. So I want to let propositions A, B, C etc be A = cell A1 is 1, B = cell A1 is 2, C = cell A1 = 3 and so on... This way every cell has 4 propositions, each of which is true or false resulting in 64 T/F propositions that have an underlying implication structure.

    For example, $A \Rightarrow \bar{E}$ if E = cell A2 is 1 and $\bar{E}$ is not E

    I want to then put a starting sudoku into this algebra and for the solution to drop out.

     – Ben Crossley May 21 '19 at 14:23
  • I think you will still need to separate the process from the initial data. In my case the process is the transition matrix and the vector is the initial data. The vector that gets created is the solution. Moving away from Maths a bit now, but I suspect that most programming architectures distinguish between the input, the program and the output. – tomi May 21 '19 at 14:33