Una fórmula no es verdadera ni falsa: lo es en una estructura y con una asignación.
«x es el máximo» es una frase en castellano. La Guía 6 pide escribirla en un lenguaje que tiene ≤, =, los nexos ∧, ∨, ¬, →, ↔ y los dos cuantificadores ∀ y ∃, y nada más. Y después pregunta si lo que escribiste dice lo mismo.
La pregunta tiene trampa, porque una fórmula sola no dice nada. (x ≤ y) no es verdadera ni falsa: es verdadera en una estructura y con una asignación que le dé un valor a x y a y. Cambiá cualquiera de las dos y el valor de verdad se mueve. La palabra queda igual.
Por eso «acertar» no puede ser que la fórmula se te parezca a la frase. Es otra cosa, y se puede medir: agarrás un puñado de estructuras, recorrés sus elementos de a uno, anotás dónde tu fórmula da verdadero y dónde la propiedad se cumple de verdad, y comparás los dos renglones. Si coinciden en todos los elementos de todas las estructuras, tu fórmula dice esa propiedad — al menos ahí.
Eso es lo que hay abajo. Elegís un objetivo, armás una fórmula tocando la paleta, y el banco de estructuras te dice renglón por renglón dónde las dos se separan.
La fórmula se arma sin escribir: tocás un □ y después un botón de la paleta, que lo reemplaza por el símbolo con sus propios huecos. Lo que estás armando es un árbol, y la palabra que ves se genera desde él. Tocá cualquier pedazo ya escrito para volver a elegirlo.
Empezá por el objetivo fácil: «x es el mínimo» sale con ∀y(x ≤ y), que es la respuesta que la guía da por buena. Después seguí con los otros tres, y no borres la fórmula al cambiar de objetivo: la misma fórmula contra otra propiedad es la parte interesante.
La guía también da por buena ¬∃z((x ≤ z) ∧ ¬(z = x)) para «x es maximal», y se lee sola: no hay ningún z que esté por encima de x y sea distinto de x. Armala en el widget con el objetivo «x es maximal» y vas a ver los ocho renglones alineados.
Ahora, sin tocar la fórmula, cambiá el objetivo a «x es el máximo». En los divisores de 12 y en la cadena no pasa nada: los dos renglones siguen coincidiendo. En la anticadena se pone todo rojo.
Y tiene que ponerse. En la anticadena los tres elementos son maximales — ninguno tiene nada por encima, porque ninguno se compara con nadie — y ninguno es el máximo, porque para ser el máximo hay que estar por encima de todos. La fórmula de la guía no se equivocó: dice «maximal», que es exactamente lo que le pidieron. Somos nosotros los que leímos «máximo» donde decía otra cosa.
Las dos frases se confunden porque en los ejemplos que uno tiene en la cabeza coinciden. En un reticulado finito siempre hay máximo —es el supremo de todos los elementos— y ahí el único maximal es el máximo. Hace falta un orden donde falte el techo para que las dos frases se separen, y por eso el banco tiene dos que no son reticulados.
La que sí dice «máximo» es ∀y(y ≤ x), que es la del mínimo dada vuelta. Eso ya dice algo de lo que viene: dar vuelta los símbolos de una fórmula no la deja diciendo algo parecido.
Antes de dar vuelta nada hay que mirar dónde termina un cuantificador, porque es lo que decide qué variables quedaron sueltas. La Guía 6 lo marca como observación importante: la negación y los cuantificadores no agregan paréntesis. ∀xφ es ∀xφ, sin nada que lo encierre.
La consecuencia es que el alcance de un cuantificador llega hasta donde llega la subfórmula que le sigue, y ni un símbolo más. Estas dos tienen los mismos símbolos en el mismo orden y difieren en un par de paréntesis:
∃z((a ≤ z) ∧ (b ≤ z))(∃z(a ≤ z) ∧ (b ≤ z))
Abajo tocás cualquier ∀ o ∃ y se te subraya en azul hasta dónde llega, con las ocurrencias que liga pintadas del mismo azul. Lo que queda con subrayado punteado es una ocurrencia libre: nadie la ligó.
Elegí las dos de arriba, una después de la otra, y mirá la lectura de abajo. Después movéle el valor a lo que haya quedado libre.
La primera es una sentencia: no tiene ninguna variable libre, así que la estructura sola decide si es verdadera. La segunda no. Al no encerrar la conjunción entre paréntesis, el ∃z se queda con (a ≤ z) y nada más — el segundo z le queda afuera, libre, y su valor lo pone la asignación. Por eso el veredicto se mueve cuando movés el selector, y por eso hablar del «valor de verdad» de la segunda, a secas, no significa nada.
El tercer ejemplo es el que la guía usa para definir «variable libre», y es más raro de lo que parece: en ((x ≤ a) ∧ ∀x(b ≤ x)) la variable x ocurre tres veces y dos de esas ocurrencias están acotadas por el ∀x. Y sin embargo x es una variable libre de la fórmula, porque alcanza con que una sola ocurrencia lo esté. Libre y acotada no son propiedades de la variable: son propiedades de cada ocurrencia, y la fórmula hereda «libre» si le queda al menos una.
Con el alcance a la vista ya se puede hacer la pregunta que importa. Tomá ∀x∃y(x ≤ y) y escribí los mismos símbolos cambiando de lugar los dos cuantificadores: ∃y∀x(x ≤ y). Misma relación, mismas variables, mismas letras. ¿Dicen lo mismo?
Abajo el orden lo armás vos: tocás un nodo y después otro, y la arista entre los dos aparece o desaparece. El primero queda abajo. El botón da vuelta los dos cuantificadores sin tocar nada más.
Dos cosas para probar. Una: dejá la fórmula como arranca y tratá de hacerla falsa — sacale todas las aristas si hace falta. Dos: dala vuelta y tratá de hacerla verdadera.
La primera no se puede romper. ∀x∃y(x ≤ y) es verdadera en cualquier orden, incluso en el que no tiene ninguna arista, porque el y que el ∃ tiene que producir puede ser el mismo x: todo elemento está por debajo de sí mismo. Es una fórmula que parece decir algo y no dice nada.
Dada vuelta pasa lo contrario. En ∃y∀x(x ≤ y) el y se elige antes de saber contra qué x lo van a comparar, así que tiene que servir para todos a la vez. Eso ya no es «cada uno tiene algo arriba»: es «hay un techo», y es falsa cada vez que le sacás el techo al orden.
El orden de los cuantificadores no es puntuación. Es quién elige primero, y eso cambia la afirmación entera.
Las dos cosas que encontraste son la misma cosa. ¬∃z((x ≤ z) ∧ ¬(z = x)) se separa de «x es el máximo» exactamente en las estructuras sin techo, y ∀x∃y(x ≤ y) se separa de ∃y∀x(x ≤ y) exactamente en las estructuras sin techo. No es casualidad: las dos confusiones son la misma, escrita de dos maneras. «Nada por encima mío» es local, se chequea elemento por elemento; «por encima de todos» es global, y exige que uno solo sirva para todo el conjunto.
Y acá hay un detalle de método que conviene anotar. La guía ilustra que los cuantificadores no conmutan con (N, máx, mín, ≤), que es infinito, y no es por gusto: en un reticulado finito esto no se puede mostrar. Un reticulado finito siempre tiene máximo —el supremo de todos sus elementos— y con máximo las dos fórmulas dan lo mismo. Lo que sí alcanza, y cabe en la pantalla, es un orden parcial finito sin máximo. Por eso el widget de arriba te deja sacar aristas hasta que el orden deje de ser un reticulado: ahí es donde las dos fórmulas se despegan.
Queda una advertencia sobre el primer widget. Que los dos renglones coincidan en las cuatro estructuras del banco no demuestra que tu fórmula diga la propiedad: demuestra que ninguna de esas cuatro la rompe. Un banco más grande podría. Es la misma asimetría de siempre — un contraejemplo cierra la discusión y mil ejemplos no—, y es exactamente por eso que la anticadena está en el banco: es un contraejemplo esperando.
Sirve para los ejercicios 3, 5 y 6 de la Guía 6 y para los ejercicios 1 y 2 de la Guía 7.