24.2.07

Laberintos (Parte 3)

(A la parte 2 - A la parte 4)

Teseo en el laberinto

El laberinto es un edificio cerrado y oscuro. Una persona, digamos que se llama Teseo, lo recorre buscando desesperadamente la salida. Por toda iluminación Teseo lleva una vela que apenas alumbra algunos centímetros alrededor por lo que sólo sabrá que ha llegado a la salida exactamente cuando llegue a ella (no podrá verla desde lejos) y sólo sabrá que ha llegado a un callejón sin salida cuando se encuentre cara a cara con la pared que lo cierra. Teseo lleva también un papel en el que va registrando lo que ha recorrido hasta el momento y además una tiza con la que puede hacer marcas y así reconocer si ya ha pasado por el punto del laberinto en el que se encuentre. Intentamos medir objetivamente la dificultad que tendrá Teseo en hallar la salida del laberinto.

Decíamos antes que todo laberinto estará representado por un grafo. Muchas veces evitaremos intermediaciones innecesarias y diremos simplemente que el laberinto es el grafo que lo representa. Teseo está en realidad dibujando un camino en el grafo (suponemos que no se vuelve atrás en medio de un eje, es decir, cuando comienza a sale de un nodo no cambia de dirección antes de llegar al nodo siguiente). Hallar la salida del laberinto equivale a encontrar un camino que conecte la entrada con la salida.

(A la parte 2 - A la parte 4)

21.2.07

Laberintos (Parte 2)

(A la parte 1 - A la parte 3)

¿Qué es un laberinto?

La pregunta del título no alude a la definición de la palabra “laberinto”, sino a la descripción matemática que adoptaremos. Todos sabemos qué es un laberinto, los hay esencialmente de dos tipos, aquellos que se resuelven con lápiz y papel, y aquellos que son construcciones que se resuelven desde adentro y en los que el diseño del laberinto es descubierto a medida que éste es recorrido. Nos interesan aquí los laberintos del segundo tipo, que describiremos matemáticamente mediante grafos.

Un grafo es un dibujo formado por puntos (o nodos) unidos mediante líneas (o ejes). Aunque puede darse una definición más formal de este concepto (como un conjunto finito de pares ordenados), la definición gráfica que hemos dado será más que suficiente para todos nuestros fines. Los siguientes son ejemplos de grafos, donde los nodos están destacados en azul:

Nótese que el hecho de que dos líneas se corten en un punto no transforma a éste necesariamente en un nodo (Figura 1) y que pude suceder que un eje conecte a un nodo consigo mismo (Figura 2).

Un camino en un grafo es un recorrido que comienza y termina en un nodo (eventualmente el mismo) y que va pasando de un nodo a otro a través de los ejes que los conectan (sólo puede cambiar de dirección en un nodo). Un camino puede pasar varias veces por un mismo eje o tocar varias veces un mismo nodo. Como antes, es posible dar una definición más formal de este concepto, pero a todos nuestros fines esta definición informal será más que suficiente. Un grafo es conexo si dado cualquier par de nodos siempre existe un camino que los conecte. Los dos grafos dibujados más arriba son conexos, pero el siguiente no lo es:

Todo laberinto se representará mediante un grafo conexo en el que se hayan destacado dos nodos, llamados entrada y salida. En los dibujos la entrada se marcará con rojo y la salida, con verde. Aquí abajo vemos un laberinto y uno de los grafos que lo representa (donde los nodos indican las bifurcaciones del laberinto):
En la tercera parte veremos otras definiciones referidas a los laberintos y a los grafos que los representan.

(A la parte 1 - A la parte 3)

17.2.07

Laberintos (Parte 1)

(A la parte 2)

Presentación

Nuestra intención es iniciar una serie de pequeñas entradas orientadas a resolver la siguiente cuestión: ¿Cómo puede medirse objetivamente la dificultad de un laberinto?

Así como en Matemáticas existen distintas maneras de medir distancias, habrá, como veremos, distintas maneras de medir la dificultad de un laberinto. En consecuencia, en primer lugar vamos a postular qué condiciones debería cumplir una medida cualquiera de la dificultad un laberinto, para luego proponer una manera concreta de medir esa dificultad.

En la próxima entrada comenzaremos definiendo qué es exactamente un laberinto.

Agradecimiento: Mi agradecimiento al Grupo de los Lunes, pues la inquietud de buscar una medida para la dificultad de los laberintos ha nacido de muchas y fructíferas discusiones sostenidas en su seno.

(A la parte 2)

15.2.07

Ni verdadero, ni falso (Parte 3 de 3)

(A la parte 2)

Verdad y mentira

Volvamos ahora al terreno de la lógica y preparémonos para afrontar el desafío de hallar una solución positiva para la paradoja del mentiroso. Observemos en primer lugar las siguientes frases a las cuales, para abreviar, llamaremos frase P y frase Q.

P = “Dos más dos es cuatro”.
Q = “La frase P es falsa”.

Tenemos frases, como P, que se refieren a cuestiones aritméticas. Por otro lado tenemos frases, como Q, que se refieren a otras frases. Concretamente, la frase Q se refiere a P. Hasta aquí no hay conflicto, la frase P es verdadera y la frase Q es falsa (ya que afirma erróneamente que P es falsa).

Una abreviatura comúnmente usada consiste en simbolizar la veracidad de una frase con el número 1 y su falsedad con el número 0. Diremos entonces que una frase verdadera tiene valor de verdad 1 y que una frase falsa tiene valor de verdad 0. Si llamamos “x” al valor de verdad de la frase P e “y” al valor de verdad de la frase Q, entonces x = 1 e y = 0.

Pasemos a considerar ahora un nuevo sistema de frases:

P = “Dos más dos es cinco”.
Q = “La frase P es falsa”.

Si adoptamos las mismas notaciones que en el ejemplo anterior (x = valor de verdad de la frase P; y = valor de verdad de la frase Q), entonces x = 0 (P es falsa) e y = 1 (Q es verdadera).

Es importante notar que si P es una frase cualquiera cuyo valor de verdad es “x” y Q, cuyo valor de verdad llamaremos “y”, es la frase que afirma que P es falsa, entonces entre “x” e “y” se verifica siempre la siguiente relación: y = 1 – x.

Ataquemos, ahora sí, el problema de la paradoja del mentiroso. Para ello pasemos a considerar la frase R:

R = “Esta frase es falsa”

Que podemos rescribir:

R = “R es falsa”

Según hemos visto, esta frase no puede ser considerada ni verdadera ni falsa. En otras palabras, no se le puede asignar de modo coherente el valor de verdad 0 ni el valor de verdad 1. La solución negativa, según vimos, consiste simplemente en no considerarla una frase admisible. Para hallar la solución positiva a este problema, debemos dejarnos guiar por el desarrollo que hemos esbozado en el ejemplo de las ecuaciones cuadráticas. Cuando el conjunto de los números reales resultó insuficiente para dar solución a todas las ecuaciones, se creó el conjunto de los números complejos. Éste contiene y amplía el conjunto de los números reales y permite hallar solución para todas las ecuaciones cuadráticas.

Nuestra propuesta para resolver la paradoja del mentiroso consiste en actuar ahora de modo similar. Si el conjunto {0,1} es insuficiente para dar un valor de verdad a la frase R entonces ampliaremos el espectro de los valores de verdad posibles. Admitiremos como posible que una frase tenga como valor de verdad cualquier número real entre 0 y 1. En consecuencia, además de frases con valor de verdad 0 o 1, tendremos también frases con valor de verdad 0,5 o 0,23. La lógica tradicional se mueve en un rígido marco donde sólo son admisibles la verdad absoluta y la falsedad absoluta. Se trata ahora de introducir una lógica de “grises” o, como suele decirse, una lógica “borrosa” en la que tengan cabida expresiones como “a medias verdadero” o “casi cierto”.

Esbozo de un sistema

Hemos planteado la idea global de nuestra solución para la paradoja del mentiroso. Esta solución consiste en ampliar el espectro de valores de verdad posibles para dar cabida a todos los valores intermedios entre 0 y 1. Sin embargo, para que esta solución resulte admisibles y útil, la asignación de valores de verdad debe hacerse de modo coherente y sistemático. Abusando una vez más de la analogía con las ecuaciones cuadráticas observemos que los números complejos resultan útiles porque tienen una estructura, es decir, hay reglas que nos dicen cómo operar con ellos. Del mismo modo, necesitamos una forma estructurada de trabajar con la lógica borrosa de las frases autorreferentes.

Para comenzar a estudiar este método de trabajo, volvamos la frase:

R = “Esta frase es falsa”.

Que también hemos escrito:

R = “R es falsa”.

Recordemos que si i P es una frase con valor de verdad “x” y Q (cuyo valor de verdad llamamos “y”) es la frase que afirma que P es falsa entonces y = 1 – x.

Llamemos “z” al valor de verdad de la frase R. Si Q fuera la afirmación “R es falsa” entonces y = 1 - z. Ahora bien, “R es falsa” es justamente la afirmación que hace la propia frase R; luego Q = R. Por lo tanto z = 1 – z. Entonces z = 0,5. La frase “Esta frase es falsa” tendrá, en nuestra lógica borrosa, un valor de verdad de 0,5.

Queda esbozado de esta manera el método general para trabajar con frases autorreferentes. A cada una de estas frases le corresponderá una ecuación y el valor de verdad de la frase se obtendrá simplemente resolviendo dicha ecuación. Para construir la ecuación que corresponde a la frase “Esta frase es falsa” hemos observado qué relación aritmética existe entre el valor de verdad de la frase P y el valor de verdad de la frase Q = “P es falsa”.

Un estudio aritmético similar permite asignar valores de verdad a otras frases autorreferentes. Como nuevo ejemplo analicemos la frase “Esta frase es verdadera y falsa”. Debido a su condición de autorreferente la lógica tradicional relegaría a esta frase al limbo de las pseudofrases carentes de significado. Veamos qué tiene que decir al respecto la lógica borrosa.

Llamemos S a la frase “Esta frase es verdadera y falsa”. Es decir:

S = “Esta frase es verdadera y falsa”.

Que podemos rescribir como:

S = “S es verdadera y falsa”. (*)

Sea “w” el valor de verdad de la frase S.

Supongamos que tuviésemos una frase P (con valor de verdad “x”) y una frase Q (con valor de verdad “y”) y que construimos con ellas la frase R:

R = “P es verdadera y Q es falsa”. (**)

Si “z” es el valor de verdad de la frase R, entonces el lector podrá verificar fácilmente que entre los valores “x”, “y”, “z” existe la siguiente relación:

z = x(1 – y) (***)

En el caso de la frase S, ella misma juega el papel de P, Q y R simultáneamente. En efecto, si en (**) se sustituyen P, Q y R por S entonces se obtiene (*). Realizando en (***) la operación análoga, es decir, sustituyendo “x”, “y”, “z” por “w”, obtenemos:

w = w(1 – w)

Esta es la ecuación que corresponde a la frase S. El lector podrá verificar fácilmente que la única solución de esta ecuación es w = 0. Por lo tanto la frase S es falsa.

Es interesante acotar que si hiciéramos para la frase “Esta frase es verdadera y falsa” un análisis similar al que hicimos al inicio de la primera parte para “Esta frase es falsa” llegaríamos exactamente a la misma conclusión.

Aunque no hemos desarrollado sistemáticamente el método de la lógica borrosa de frases autorreferentes, confiamos en que los ejemplos aquí expuestos servirán para que el lector se haga una clara idea del funcionamiento del mismo.

Bibliografía:

N. Falleta; Paradojas y juegos - Ed. Gedisa, México, 1989.
P. Hughes - G. Brecht; Círculos viciosos y paradojas; Juegos & Co. Buenos Aires, 1994.

A. Kaufmann; Introducción a la teoría de los subconjuntos borrosos; Editorial continental; México, 1982.

R. Smullyan; ¿Cómo se llama este libro? ; Ediciones Cátedra; Madrid, 1991.

(A la parte 2)

2.2.07

Ni verdadero, ni falso (Parte 2 de 3)

(A la parte 1 - A la parte 3)

Números complejos

Salgamos por un momento del ámbito de la pura lógica y entremos en el mundo de las ecuaciones cuadráticas. Consideremos como primer ejemplo la ecuación: x^2 - 4x + 4 = 0. En la que “x” simboliza algún número real desconocido y x^2 es ese número al cuadrado.

Como es bien sabido, para resolver la ecuación hay que hallar todos los números reales que reemplazados por “x” dejan una correcta igualdad numérica. En el ejemplo precedente x = 2 resulta ser la única solución de la ecuación. Podemos decir que a la ecuación x^2 - 4x + 4 = 0 le corresponde el número 2.

Analicemos un nuevo ejemplo: x^2 - 3x + 2 = 0. A diferencia de la precedente, esta ecuación tiene dos soluciones. En efecto, “x” puede ser reemplazada por x = 1 o x = 2 y en ambos casos se obtendrá una igualdad correcta. A la ecuación x^2 - 3x + 2 = 0 le corresponden entonces dos números reales: 1 y 2.

Veamos todavía un tercer ejemplo: x^2 + 1 = 0. Como el lector podrá verificar fácilmente, a diferencia de las dos anteriores, esta ecuación no tiene soluciones reales. A esta ecuación no le corresponde ningún número real. ¿Cómo debemos tratar esta situación? ¿Cómo podemos admitir la existencia de ecuaciones sin solución? ¿No sería preferible que a toda ecuación le correspondiera al menos un número? Una posibilidad sería adoptar la “solución negativa” y considerar que las ecuaciones que no tienen solución (es decir, las ecuaciones que no representan ningún número) son “pseudoecuaciones”, expresiones carentes de significado y que deben ser excluidas de la teoría (1).

Todas las ecuaciones “aceptables” quedarían entonces dentro del seguro cerco de la resolubilidad y las demás serían relegadas al limbo de las pseudoecuaciones. La solución que los matemáticos han adoptado para esta situación es, en cambio, completamente diferente. La solución consiste en ampliar el conjunto de los números existentes mediante la creación un nuevo conjunto numérico: el conjunto de los números complejos (2). Este conjunto, que contiene dentro de sí mismo al viejo conjunto de los números reales, permite resolver todas las ecuaciones cuadráticas.

Es importante destacar que las ecuaciones cuadráticas con coeficientes reales que tenían soluciones reales no ganan ni pierden nada con la ampliación del sistema de números.
La “solución negativa” encerraría a las ecuaciones con soluciones reales dentro del seguro cerco de la resolubilidad y dejaría fuera a todas las demás.

La “solución positiva”, en cambio, amplía el conjunto de los números existentes y nos permite estudiar en pie de igualdad todas las situaciones. Incidentalmente los números complejos han resultado ser una herramienta matemática tan poderosa (en campos completamente alejados de las cauciones cuadráticas) que hoy en día a nadie se le ocurriría prescindir de ellos. Las soluciones positivas crean nuevas formas para resolver problemas. Las negativas en cambio se reducen a definir cuidadosamente el campo de acción con el fin de evitar las situaciones conflictivas. Las soluciones positivas atacan de frente el problema y resultan mucho más estimulantes para la imaginación, son más creativas y motivadoras.

Una ventaja adicional de las soluciones positivas es que las nuevas respuestas que hallemos en un área pueden resultar útiles también para la resolución de problemas completamente alejados de la cuestión original.

Notas:

(1) Niels Abel tenía una opinión similar acerca de las series divergentes. El “anatema de Abel” (1828) dice: “Las series divergentes son una invención del diablo y es vergonzoso que haya quien se base en ellas al hacer cualquier demostración. ”

(2) Los números complejos se definen como expresiones de la forma a + bi, donde a y b son números reales e “i” es un símbolo con la propiedad de que i^2 = -1.

(A la parte 1 - A la parte 3)