Tip:
Highlight text to annotate it
X
Vamos a modelizar un sistema complejo
como es un sudoku,
tan complejo que realmente vamos simplemente
a modelizar las restricciones que ocurren
en uno de los nueve cuadrados que componen el sudoku.
Bien, si se recuerdan estas restricciones,
en esos nueve cuadrados
deben aparecer números del 1 al 9 sin repetir.
Esto da lugar a una combinatoria posible
de relleno distinto de los cuadrados,
que es la que vamos a intentar modelizar
con fórmulas de lógica proposicional.
Para expresar estas restricciones complejas,
tenemos que preguntarnos qué es lo mínimo, mínimo,
cuáles nuestras fórmulas atómicas,
que es lo mínimo que podemos decir
sobre este sudoku.
Y va a ser que, en la casilla X está el número Y.
En concreto, por ejemplo,
que en la casilla que se obtiene entrando por la fila 1
y por la columna 3, hay un 9.
Para eso escogeremos una letra proposicional cualquiera,
que, para simplificarnos la vida,
lo que hacemos son un conjunto de trazos,
lo que sería una letra proposicional,
pero que dejan ver un poco la estructura de la fórmula,
es decir, en la fila 1, columna 3,
hay un 9, que es lo que aparece en el superíndice.
De tal manera que esta otra fórmula
lo que dice es que hay un 8,
exactamente entrando por la fila 3, columna 2.
Bien, podemos apreciar
que con este esquema de codificación,
nos salen 3 filas, por 3 columnas, por 9 opciones:
81 fórmulas atómicas distintas.
Y vamos a construir fórmulas más complejas
a partir de estas 81 fórmulas atómicas.
Cualquiera de esas fórmulas más complejas,
para evaluarla exhaustivamente, para evaluar su tabla de verdad,
hay que recordar que constará de 2 elevado a 81 líneas,
muchos millones de líneas,
por lo tanto aunque nos hemos restringido mucho
en el problema del sudoku,
sigue siendo esta restricción en concreto, pequeña,
sigue siendo un problema tremendamente complejo,
si se quiere evaluar con tablas de verdad.
Veremos que el esquema que usamos
es el que hemos mencionado, p sub i, j,
es que en la fila i, columna j, está el número k.
Bien, puestos a empezar a modelizar esto,
centrémonos en esta casilla, lo que queremos expresar
es que ahí va a aparecer un número del 1 al 9,
y no otro número.
Es decir, exactamente algún número del 1 al 9.
Como no podemos todavía, hasta que no usemos la igualdad,
decir que va a haber exactamente un número,
vamos a hacer una aproximación de otra manera.
Primero diremos con esta fórmula tan extensa,
que en esa casilla, en la 1-3,
o bien hay un 1, o hay un 2, o hay un 3, o hay un 9.
Esta fórmula ya lo que hace es
que sea solamente válida
cuando al menos una de esas nueve opciones
es cierta, es decir,
puesto que estamos en nueve proposiciones distintas,
estaríamos en una tabla de verdad de 2 elevado a 9,
de 512 elementos, 512 lineas.
Sólo en una de las líneas esta fórmula no es cierta,
y es aquella en la que en esa casilla
no hay ningún número del 1 al 9.
Esto lo queremos evitar, lo queremos obviar,
y nos quedamos en las otras 511 líneas,
es decir, afirmamos que se debe cumplir esa restricción
y por lo tanto sabemos que ahí va a haber algún número del 1 al 9.
Ahora bien, esta fórmula no excluye
que haya más de un número.
No será otro, pero a lo mejor ahí
hay un 2, un 3, un 5, un 7.
Para evitarlo,
tenemos que añadir otras restricciones.
En concreto, esta que ponemos ahora
lo que indica es, que si en esa casilla
hubiera un 1, entonces en esa misma casilla
ni hay un 2, ni hay un 3, ni hay un 9.
Esta fórmula,
esta restricción, este condicional se hace verdadero
incluso aunque no haya un 1 en esa casilla.
No se viola esta restricción.
Porque esta fórmula condicional
no está exigiendo que haya un 1.
Sólo dice que, si hubiera un 1, si es verdad el antecedente,
para que la fórmula siga siendo verdadera,
no puede ser falso el consecuente,
es decir, se tiene que cumplir lo que dice el consecuente.
Por lo tanto, si hay un 1 ahí,
no hay el resto de los números posibles.
O bien, si hay un 2 ahí,
no hay el resto de los otros ocho números.
O bien, si hay un 9 ahí,
no hay el resto de los ocho números restantes.
Con estas diez fórmulas,
la primera que dice que los números van del 1 al 9,
aunque quizá haya más de uno, y las otras nueve fórmulas
que nos dicen que si hay un determinado número,
no hay el resto, con estas diez fórmulas,
cuando estas diez fórmulas son ciertas a la vez,
son verdad, se satisfacen, en esa configuración,
sólo podríamos poner un determinado número,
el que queramos, del 1 al 9.
No violaría estas restricciones.
Bien, si repetimos lo mismo para otra casilla,
tendríamos de nuevo que establecer
estas diez fórmulas exactamente para esa casilla.
Es decir, si uno ve la letra pequeña de este vídeo,
lo que verá es que hemos cortado y pegado
lo que dijimos para la casilla primera que analizamos,
pero habría que particularizarlo para esa casilla 2-1.
Bien, tenemos 90 fórmulas,
y estas 90 fórmulas simplemente lo son
para que en cada casilla haya un número del 1 al 9,
y no más de un número.
Ahora, hay otras restricciones aquí.
En concreto, si en una determinada casilla
hay un 3, en otra no debe haber un 3.
Podríamos decir que, como se señala en el diagrama,
si en la casilla 2-1 hubiera un 3,
en el resto de las ocho casillas restantes
no va a haber un 3.
De nuevo, este condicional no obliga
a que haya un 3 en el 2-1,
ahora bien, si es verdadero que hay un 3,
para cumplir esta fórmula,
no puede haber un 3 en otras casillas.
Bien, como se verá,
el proceso de ir poniendo todas las restricciones
es bastante latoso, daría lugar a bastantes fórmulas,
pero en principio ya se ha visto cómo se podrían poner
todas las restricciones que faltan,
y lo que tenemos es, digamos,
en términos de lógica proposicional,
las reglas del juego.
Éstas son nuestras fórmulas que definen exactamente
cuáles son las restricciones sobre ese fragmento del sudoku.
Con estas restricciones hay muchas posibilidades,
uno puede empezar a rellenar por un lado, por otro,
poner unos números u otros cumpliendo las restricciones.
Uno no puede repetir el 3 varias veces,
ni en una casilla poner un 5 y un 9.
Si fuéramos rellenando, si decidiéramos, por ejemplo,
que en un paso intermedio
de nuestra resolución del sudoku
colocamos un 9 ahí, y un 8 ahí,
lo que estaríamos diciendo es, además de todas estas fórmulas
-vamos a, por poner un ejemplo, suponer
que las restricciones son 200 fórmulas-,
además de las 200 fórmulas de las restricciones,
hay otras dos, estas en concreto,
que hay un 9 en esa determinada casilla
y hay un 8 en esa determinada casilla,
que tienen que ser verdad
al tiempo que las 200 fórmulas que restringen.
Es decir, ahora tenemos 202 fórmulas
que supuestamente tienen que poder ser verdad
en alguna configuración.
Como veremos en más de una configuración,
porque hay muchas maneras ahora de rellenar el resto de las casillas.
Lo que tendríamos que ir haciendo,
conforme rellenemos el resto de las casillas,
es ir añadiendo la fórmula correspondiente,
y nuestra pregunta es si lo que hemos hecho no viola
las 200 restricciones que teníamos
más las fórmulas que implican
los hechos sobre el sistema aparte de las restricciones.
Esto es una idea aproximada
de cómo se modela un sistema mínimamente complejo.
Los sistemas de hardware, los sistemas de software,
de análisis de elementos industriales,
que tengan una serie de estados, etc.,
se están ahora mismo analizando
mediante este tipo de técnicas, pero da lugar
a una enorme cantidad de letras proposicionales,
a un número muy elevado de fórmulas que deben cumplir,
y por tanto, no ya sólo su resolución
necesita un sistema automático,
sino casi incluso su planteamiento.
Es decir, generar las dos, tres mil, cinco mil fórmulas
que necesita un sistema para ser definida,
también necesita un cierto apoyo
de un sistema que nos guíe para hacer eso.
Afortunadamente no es el objeto de este primer curso de lógica,
hay otras muchas cosas que podemos modelizar
con muchas menos variables y muchas menos fórmulas,
como algunos razonamientos sencillos,
algunos sistemas sencillos.
Pero era bueno ver un primer sistema
más o menos complejo, de ejemplo.