Georges Boole: l matemático que inventó la forma en que hoy busca Google

 

Cada vez que haces una simple búsqueda en Google, o en cualquier otro buscador informático, entre los mecanismos de programación que hacen posible que encuentres lo que buscas hay unos principios de lógica que fueron concebidos hace más de 150 años.

Fue el matemático inglés George Boole quien inventó un sistema de álgebra que es clave para la programación de hoy en día.

La álgebra de Boole, o álgebra booleana, es una estructura algebraica que esquematiza las operaciones lógicas, y está presente en todas partes a nuestro alrededor: desde la programación detrás de los videojuegos a los que jugamos, hasta el código de las aplicaciones que usamos y los programas de las computadoras que utilizamos.

Se puede decir que los ladrillos con los que se construye la programación, que son los comandos o instrucciones que se le da a un sistema informático, están todos basados en la lógica de Boole.

"Si eres un programador no te puedes escapar del término booleano", dice Michael Dunn de Gospelweare, una compañía desarrolladora de iOS y Android.

AND, OR y NOT

Durante los últimos 17 años de su vida George Boole estableció el concepto de lógica algebraica en matemáticas y simplificó el mundo en enunciados básicos que tenían por respuesta Sí o No, utilizando para ello aritmética binaria.

"Las interpretaciones respectivas de los símbolos 0 y 1 en el sistema de lógica son Nada y Universo", dijo.

Este concepto, que introdujo en 1847 y expandió siete años más tarde, es lo que está presente en los programas informáticos actuales.

"Hay un enunciado booleano casi cada dos líneas de un programa informático", dice Dunn.
"No es algo sobre lo que reflexiones, porque es una parte totalmente integral de la programación".
Boole utilizó el concepto de puertas lógicas, o preguntas, que exploran un enunciado.

Las puertas lógicas más básicas son, en el lenguaje original de Boole, AND, OR o NOT. Es decir, Y, O o No en español.

Después, estas tres puertas se pueden combinar para crear enunciados más complejos.

Así que cuando buscas en internet "Miley Cyrus" hay un uso implícito de la lógica booleana del comando AND para combinar las dos palabras, "Miley" y "Cyrus".

Mucho antes de Google, durante los primeros años en que se hacían búsquedas, era frecuente usar los comandos AND, OR y NOT para filtrar los resultados.

Hoy, los avances en la tecnología de búsquedas hace que muchas se puedan realizar utilizando un lenguaje más natural.

Aún así, Google todavía le permite a los usuarios escribir OR o incluir el símbolo de sustracción - para afinar los resultados.

Juventud prolífica

Boole murió hace 150 años, cuando tenía 49.

En 1864 enfermó gravemente tras mojarse bajo la lluvia mientras caminaba hasta el aula donde daba clase.

Murió el 8 de diciembre de ese año de un derrame pleural o pleuresía, acumulación de agua en los pulmones.

Él mismo tenía cierta noción del impacto histórico que su sistema de lógica podría tener.

En 1851 le dijo a un amigo que la lógica booleana podría ser "la contribución más valiosa, si no la única, que he hecho o que probablemente haga a la ciencia y el motivo por el que desearía que me recuerden, si es que me van a recordar, póstumamente".

Y así fue.

Fuente:

BBC Ciencia

Los sistemas de numeración y los números binarios

Los sistemas de numeración son símbolos y reglas para denotar cantidades  Muchas civilizaciones inventaron los suyos, por ejemplo, los romanos usaron la notación I, II, III, IV, .. etcétera.

En nuestros tiempos, el sistema de numeración que usamos cotidianamente se llama sistema de numeración posicional en base 10 (o simplemente sistema decimal).  Es decimal pues se usan diez símbolos (a saber  0, 1, 2, 3, 4, 5, 6, 7, 8, 9) y depende de la posición pues no es lo mismo 12 (uno dos) que 21 (dos uno).

*	**	***	****	*****	***** *	***** **	***** ***	***** ****	***** *****
1	2	3	4	5	6	7	18	9	10
***** ***** *	***** ***** **	***** ***** ***	***** ***** ****	***** ***** *****	***** ***** ***** *	***** ***** ***** **	***** ***** ***** ***	***** ***** ***** ****	***** ***** ***** *****
11	12	13	14	15	16	17	18	19	20

¿Pero por qué usamos este sistema? ¿Y por qué se eligieron diez símbolos? Pues la respuesta está en la historia; el sistema decimal desciende de los números usados por los árabes.

Pero si nos vamos a la lógica matemática, no hay razón para usar exactamente diez símbolos; podríamos emplear cuantos quisiéramos y usar las reglas que queramos. Por ejemplo, los mayas usaron 3 símbolos y ponían símbolos arriba de otros.

Pero ya no tenemos que irnos al pasado para encontrar otros sistemas de numeración. En la actualidad, se emplea el sistema de numeración hexadecimal posicional (de dieciséis símbolos 0, 1, 2, …, 9, A, B, …, F ) para encriptar contraseñas o para denotar colores. ¿Sí los han visto no?

En decimal	En hexadecimal	Color
10, 354 714	9E001A	_______________
7, 556 367	734D0F	_______________

La relación al uso del sistema hexadecimal en los lenguajes computacionales tiene que ver en gran medida a que la información se guarda en bloques de potencia de dos (2n). Y pues el 16 es una potencia de dos: 24.

Pero el sistema de numeración que me parece más impresionante es el que tiene la menor cantidad de símbolos, el binario; con tan sólo dos símbolos (el 0 y el 1).

El sistema binario

El sistema binario es impresionante de entrada por tener tan pocos símbolos. Pues con sólo dos símbolos puedes escribir todos los números, incluyendo al cero. Pero además, aprovecha de la posición para reducir la cantidad de dígitos (como se hace en el sistema decimal).

Para los lectores que no estén familiarizados con el sistema binario, en la siguiente tabla se muestran los primeros diez números. Intenten descubrir el patrón de cómo se construyen estas representaciones y escribe los cinco números faltantes.

*	**	***	****	*****	******	*******	********
1	10	11	100	101	110	111	1000
******** *	******** **	******** ***	******** ****	******** *****	******** ******	******** *******	******** ********
1001	1010

Si lograron entender la sucesión, quedará evidente que podemos seguir este proceso indefinidamente, por lo que a cualquier cantidad (número) le podemos asociar su lista de unos y ceros; llamada notación binaria del número.

Una primera pregunta que podemos hacernos de la notación decimal es la siguiente, ¿qué cantidad representa la notación 100...00 (un uno con muchos)? Pues la respuesta es más o menos la misma que lo que ocurre en la notación decimal, vean la siguiente tabla.

Binario 10 2 100 2×2=22 1000 2×2×2=23 10000 24

Decimal 10 10 100 10×10=102 1000 103 10000 104

La simple existencia de esta notación y este parecido a la notación decimal puede parecer no muy motivante, pero tal vez la siguiente observación les resulte más impresionante.

Todo número entero es una potencia de dos o suma de potencias de dos. Por ejemplo, 6=21+22.

Para ver esto, basta con observar que la notación de binaria se transforma a una suma de potencias de dos, por ejemplo, 

43=(101011)2=25+0×24+1×23+0×22+1×21+1×20=25+23+21+20=32+8+2+1

Esto es similar a lo que muchos hemos visto en las clases de primaria para el sistema decimal: 

1235=103+2×102+3×101+5×100

Si aún no se sienten muy impresionados con el sistema binario, no se preocupen, es normal; no a todos nos da gusto acordarnos de la primaria.

Voy hacer el esfuerzo de hacérselos más interesantes, a continuación les presento unos contextos donde sin el sistema binario, no se podrían comprender tan fácilmente.

Los binarios y las monedas

El contexto que veremos es el de la elección de la denominación de las monedas.  Para hacerlo más interesante, se los dejo en forma de problema.

En un remoto país, tienen monedas de denominación distintas a las que usualmente conocemos (Por ejemplo, tienen una moneda de 32 pesos). Una maravilla de su sistema de monedas, es que una persona sólo necesita tener 8 monedas para pagar exactamente cualquier cantidad (sin centavos) desde 1 peso hasta 255 pesos, es decir, sin necesidad de que le den cambio, ¿de qué denominación son las 8 monedas?

¿Ya lo resolvieron? Bueno, si no lo han resuelto la respuesta está en lo que hemos visto, potencias de dos (1, 2, 4, 8, 16, 32 y 64 pesos). Y la justificación a esta respuesta está en lo que vimos sobre el sistema binario y sumas de potencias de dos.

En principio no parece tan práctico tener una moneda de 32 pesos. Pero veamos lo que pasa en nuestro sistema de monedas. Si nos dieran a escoger ocho monedas, no podríamos pagar muchas cantidades. Con 5 monedas y 3 billetes sólamente podríamos pagar desde  1 pesos hasta 110 pesos. Pueden ver la siguiente tabla, para la descripción detallada de las 8 monedas. Y les dejo de ejercicio verificar que podemos pagar de 1 hasta 110.

Cantidad	1	2	1	1	2	1
Denomincación	$1	$2	$5	$10	$20	$50

 
Entonces, ciertamente nuestro sistema de denominaciones es más ineficiente que en aquel remoto país del problema. Pues en aquél, con las misma cantidad de ocho monedas, se pueden pagar más del doble de cantidades.

Pero la razón por la cuál no se usa el sistema de denominaciones de aquél lejano país, es que sería mucho más trabajoso saber con cuántas y con cuáles monedas pagar. Por ejemplo, intente pagar 90 pesos con las siguientes monedas:

Para que este conjunto de monedas fuera más natural y fácil de usar, es necesario que todos usaramos binario en lugar del decimal; escribieramos, nombráramos, operarámos los números en binarios de forma cotidiana. ¿Se imaginan? Hasta las tablas de multiplicar serían más fáciles: uno por cero, cero; uno por uno, uno; ¡y se acabó!.

Un truco de magia

Un mago le pide a la audiencia, que piensen un número del 1 al 15. Después le muestra las siguientes cuatro cartas y pregunta, “¿En cuál o cuáles cartas aparece el número que pensó?”

A 1       3        5        7 9      11      13     15

B 2       3       6        7 10     11     14     15

C 4       5       6       7 12     13     14     15

D 8      9      10      11 12    13     14      15

Una vez indicadas las cartas, el mago inmediatamente dice cuál es el número. 

Ell truco del mago es sumar los primeros números de cada carta elegida por la persona. Por ejemplo, si la persona pensó “13”, entonces indica al mago que  su número está en las cartas A, C y D. Entonces, el mago suma 1 + 4 +8 =13 para saber cuál es el número.

Les dejo como ejercicio averiguar la relación de este truco, con el sistema de numeración binario y las potencias de dos.

Una observación más avanzada

Pues ya vimos que todo número se escribe como sumas de potencias de 2, pero qué pasará si en lugar de 2 ponemos -2. ¿Todo número se escribirá como sumas de potencias de -2?

La respuesta es que sí e inesperadamente esto incluye a los negativos. Todo número entero (incluyendo negativos) se podrá escribir de forma única como suma de potencias de -2.

La prueba formalmente tendría que hacerse con el uso de inducción matemática, pero para no espantar a los novatos, sólo escribo los primeros casos, los expertos podrán hacer la formalización si quieren.

• Paso -1: El número 0 no se podrá construir como sumas de potencias de -2. Así que para poder construir todos, será necesario incluirlo a la lista de generadores, es decir, vamos a generar todos los enteros usando el 0, 1, -2, 4, -8, 16, -32, …
• Paso 0: La potencia cero no da (−2)0=1, por lo que podemos generar ahora sólamente el 0 y el 1.
• Paso 1: La potencia uno, es el -2. Por lo que podemos generar, el 1, -2 y el 1+(-2)=-1, Es decir, podemos obtener desde el -2 hasta al 1 como suma de 1 y -2 (y el cero).
• Paso 2: (-2)^2 =4. Entonces, el paso anterior podemos obtener del -2 al 1 (cuatro números), por si a esos números les sumamos 4, obtendremos cuatro números más: 2, 3, 4 y 5. Entonces, ahora podemos construir desde el -2 hasta el 5, en total 8 números.
• Paso 3. (-2)^3 = -8. Al sumarle -8 a los ocho números del -2 al 5, obtendrémos otros nuevos 8 números; del -10 hasta el -3. En total, ahora podemos construir 16 números, del -10 hasta el 5.

Y así sucesivamente. podremos construir un intervalo de números enteros que tiene tamaño 2n. Y el número que vamos a sumar será (−2)n, así que duplicaremos la cantidad de números que se pueden generar como potencias de -2. Y dependiendo del signo de (−2)n el intervalo crece hacia los negativos o hacia los positivos.

Fuente:

Mate Tam