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

Me pasó otra vez...

...Google insiste en confundirme con un bot. No se que es lo que confundirá a sus algoritmos de detección, aunque sospecho de mi tendencia a abrir múltiples pestañas cuando veo una lista de links :-)


Por si fuera poco, el CAPTCHA también me clasificó como "no humano", ya que realmente me resultaba difícil ver que es lo que decía. Tengo la sospecha de que navegar por Internet en el futuro va a ser realmente interesante...

spice3f5 para Visual C++

Acabo de agregar a la página de mi proyecto de Tesis una versión de spice3f5 compilable con Microsoft Visual C++ 2008. Esto permite realizar fácilmente análisis de una netlist cualquiera (aunque no incluye manual de uso :-)

Un problema de probabilidad

En un juego, se presentan a una persona dos sobres. Sabe que uno de ellos contiene una cantidad desconocida de dinero 'A', y que el otro contiene el doble de esa cantidad, pero el jugador desconoce "cuál es cual". Se le dice que puede llevarse solo uno de los sobres y que debe llevarse el último sobre que abra.

La pregunta es: después de haber elegido y abierto un sobre, le conviene cambiarlo por el otro?

La respuesta intuitiva es "no", ya que ver el contenido del sobre no nos permite discriminar entre el caso en que elegimos el sobre con la cantidad A y el caso en que elegimos el sobre con al cantidad 2A. Al no tener evidencia proveniente de ver el contenido del sobre, el intercambio nos sería indiferente.

Ahora supongamos que calculamos el valor esperado del contenido del sobre no abierto, al que denominaremos "sobre 2". Si llamamos B al contenido del sobre abierto, el sobre 2 puede tener contenido B/2 o 2B. Asumiendo la indiferencia mencionada anteriormente, el valor esperado del contenido del sobre 2 sería:

E(contenido sobre 2) = 1/2 B/2 + 1/2 2B = B/4 + B = 5/4 B

Esto implicaría que siempre nos sería conveniente realizar el intercambio!

Más detalles sobre el problema y sus implicaciones en Wikipedia...

Factories en C++

Las implementaciones normales de factories en C++ suelen introducir la necesidad de modificar la clase Factory o su inicialización para cada clase que se agrega. Los intentos de evadir esta centralización utilizando la inicialización estática suelen ser algo como lo que aparece en el ejemplo factory_mal (es claro que hay algo mal :-) .

Este ejemplo utiliza la inicialización de variables globales para realizar el registro de los factory methods. En muchos casos esto parece funcionar, de hecho me acaba de funcionar al probarlo, pero contiene un error grave: asume un orden de inicialización de objetos estáticos entre distintos archivos (bueno, "unidades de traducción").

El problema en que no puede suponerse que los distintos Registrators vayan a inicializarse después que Factory::cm_. Si los Registrators se inicializan primero, Factory::registrate() accederá a un map no inicializado, probablemente llevando a un segmentation fault.

La solución a esto es la misma que la aplicada en el Singleton de Meyers: utilizar una variable estática dentro de un método. De este modo podemos garantizar que el objeto estará inicializado cuando sea utilizado.

Obviamente esta solución no maneja los problemas con múltiples threads, ni arregla mágicamente los problemas de diseño que puedan ser provocados por el uso indebido de singletons, pero soluciona el problema de la inicialización.

Relatividad en 6 minutos

(Vía John Walker)
Sí, un video musical por Max Tegmark! No puedo imaginarme algo así en la FIUBA aunque, en realidad, tampoco lo imaginaba en el MIT :-D



El paper con la letra...

Un robot distinto

BigDog: un robot que parece "útil". Acostumbrado a ver la forma vacilante en que suelen caminar los robots me impresionó mucho la estabilidad y adaptabilidad que despliega BigDog. Tal vez hay razones para el optimismo en la robótica :-)