¿Cómo resolver estas ecuaciones booleanas?

Question

Tengo una ecuación booleana que se describe a continuación, $$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$ en el que $\mathbf{M}$ es un $n\times n$ matriz booleana, y $\mathbf{x}$ es un $n\times 1$ Vector de columnas booleano. El producto de dos matrices booleanas $A_{m\times k}$ y $B_{k\times n}$ es $C_{m\times n}$ definido por $$c_{ij}=\bigvee_{h=1}^{k}(a_{ih}\wedge b_{hj})$$

Ahora, teniendo en cuenta $\mathbf{M}$ La tarea consiste en encontrar todas las soluciones de las ecuaciones.

¿Quiere darme alguna idea?

Answer 1

Como he señalado en el comentario, si se considera que los valores booleanos son el campo de dos elementos $\Bbb F_2$ entonces tus matrices booleanas son simplemente matrices regulares sobre ese campo. $\vee$ se convierte en una adición modulo $2$ y $\wedge$ se convierte en una multiplicación módulo $2$ . Su definición de multiplicación matricial booleana es simplemente una multiplicación ordinaria entre matrices. Por lo tanto, sus matrices son operadores lineales sobre $\Bbb F_2^n$ lo que significa que $$M(a\mathbf x + b\mathbf y) = aM\mathbf x + bM\mathbf y.$$ Así que su ecuación se convierte en $$\mathbf 1 - \mathbf x = M(\mathbf 1 - M\mathbf x) = M\mathbf 1 - M^2\mathbf x$$ $$M^2\mathbf x - \mathbf x = M\mathbf 1 - \mathbf 1$$ $$(M^2 - I)\mathbf x = (M - I)\mathbf 1$$ $$(M - I)(M + I)\mathbf x = (M - I)\mathbf 1$$ Si $M - I$ es invertible, entonces $$(M + I)\mathbf x =\mathbf 1$$ Si $M + I$ también es invertible, entonces $$\mathbf x = (M + I)^{-1}\mathbf 1$$