Sistemas de ecuaciones booleanos

Hace unos días un compañero de la facultad (hola Guille!) me comentaba sobre una clase de problemas que suelen aparecer en los parciales de Matemática Discreta (al menos en la FIUBA). Recordaba que estos problemas consistían en encontrar una función booleana que de como resultado 1 si y solo si los valores de sus parámetros satisfacen un sistema de ecuaciones booleano y eso me hizo recordar un "método" que había desarrollado cuando la había cursado (aunque creo que no tuve ocasión de usarlo en el parcial).

Nota: Las "barras" que se suelen utilizarse para indicar complemento no se expresan fácilmente en HTML. Esto puede resolverse utilizando el operador "¬". Las otras dos operaciones pueden expresarse por "∧" (AND) y "∨" (OR). Por simplicidad, podemos asumir que "∧" tiene prioridad sobre "∨".

Para empezar podemos demostrar que dada una variable y satisfaciendo x ∧ y = 0 y x ∨ y = 1 sabemos que y = ¬x (o sea la unicidad del complemento). Una forma es viendo que:

(1) x ∨ y = 1 (Hipótesis)
(2) ¬x ∧ (x ∨ y) = ¬x ∧ 1 (Aplico la misma operación a ambos miembros)
(3) ¬x ∧ (x ∨ y) = ¬x (Definición de 1)
(4) ¬x ∧ x ∨ ¬x ∧ y = ¬x (Propiedad distributiva)
(5) 0 ∨ ¬x ∧ y = ¬x (Definición de complemento)
(6) x ∧ y = 0 (Hipótesis)
(7) x ∧ y ∨ ¬x ∧ y = ¬x (Reemplazando 6 en 5)
(8) (x ∨ ¬x) ∧ y = ¬x (Propiedad distributiva)
(9) 1 ∧ y = ¬x (Definición de complemento)
(10) y = ¬x (Definición de 1)

Otro "lema" que es útil indica que dados x e y tales que x ∧ y = 1, puede decirse que x = 1 y que y = 1. Una forma de demostrarlo es la siguiente:

(1) x ∧ y = 1 (Hipótesis)
(2) x ∧ y ∨ x ∧ ¬y = 1 ∨ x ∧ ¬y (Aplico la misma operación a ambos miembros)
(3) x ∧ y ∨ x ∧ ¬y = 1 (Propiedad absorbente)
(4) x ∧ (y ∨ ¬y) = 1 (Propiedad distributiva)
(5) x ∧ 1 = 1 (Definición de complemento)
(6) x = 1 (Definición de 1)

Por simetría podemos ver que y = 1 y podemos evitar demostrar la propiedad absorbente para poder llegar alguna vez al tema a tratar :-)

Ahora, podemos ver a todo sistema de ecuaciones como una serie de igualdades entre funciones que requieren satisfacerse. Por ejemplo:

f1(x, y, ...) = g1(x, y, ...)
f2(x, y, ...) = g2(x, y, ...)
f3(x, y, ...) = g3(x, y, ...)
...

Ahora, como sabemos que x ∧ y = 0 y x ∨ y = 1 implican x = ¬y y que x ∧ y = 1 implica que tanto x como y son iguales a 1, podemos expresar una igualdad arbitraria a = b como ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 aplicando lo siguiente:

Ida

(1) a = b (Hipótesis)
(2) a = ¬(¬b) (Propiedad involutiva del complemento)
(3) a ∧ ¬b = 0 (Definición de complemento)
(4) a ∨ ¬b = 1 (Definición de complemento)
(5) ¬(a ∧ ¬b) = ¬0 (Aplico la misma operación a ambos miembros)
(6) ¬(a ∧ ¬b) = 1 (Aplico ¬0 = 1)
(7) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Aplico ∧ miembro a miembro sobre 4 y 6)

Vuelta

(1) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Hipótesis)
(2) ¬(a ∧ ¬b) = 1 (Propiedad demostrada anteriormente)
(3) a ∨ ¬b = 1 (De 1 por propiedad demostrada anteriormente)
(4) ¬¬(a ∧ ¬b) = ¬1 (Aplico la misma operación a ambos miembros)
(5) a ∧ ¬b = ¬1 (Propiedad involutiva del complemento)
(6) a ∧ ¬b = 0 (Aplico ¬1 = 0)
(7) a = ¬¬b (Aplico otra propiedad demostrada anteriormente sobre 3 y 6)
(8) a = b (Propiedad involutiva del complemento)

Si omitimos que no demostramos ni la propiedad involutiva del complemento ni que ¬0 = 1 (las demostraciones son simples, quedan como ejercicio para el lector :-), sabemos como transformar una ecuación arbitraria en una igualada a 1. Ahora podemos aplicar que x ∧ y = 1 implica que x = y = 1 para expresar el sistema de ecuaciones anterior como:

¬(f1(x, y, z, ...) ∧ ¬g1(x, y, z, ...)) ∧
(f1(x, y, z, ...) ∨ ¬g1(x, y, z, ...)) ∧
¬(f2(x, y, z, ...) ∧ ¬g2(x, y, z, ...)) ∧
(f2(x, y, z, ...) ∨ ¬g2(x, y, z, ...)) ∧
¬(f3(x, y, z, ...) ∧ ¬g3(x, y, z, ...)) ∧
(f3(x, y, z, ...) ∨ ¬g3(x, y, z, ...)) ∧
... = 1

Esto cumple en forma automática el objetivo del problema aunque puede ser algo tedioso...