Artículo sobre el libro: Tratado sobre Satisfacibilidad Lógica
Enviado por José Francisco Rivera Romualdo
Prefacio
El presente artículo trata el problema de Satisfacibilidad. Dicho problema se enuncia de la siguiente forma:
Dada una expresión conteniendo variables, paréntesis y operadores lógicos, ¿existe una combinación de valores de las variables que la satisfacen?
Es decir, hemos de encontrar si existe, el valor uno, encendido o, valor de verdad, ó no existe, valor cero, apagado, o valor de falsedad; sobre el dominio de discurso de una determinada expresión lógica.
Tomaremos el dominio de discurso gracias a una base generadora. A su vez podremos pasar de la base generadora que cumple la expresión a la base generadora que no satisface la expresión (base complementaria).
En el presente artículo actuaremos sobre las primera y segunda formas canónicas de lógica de proposiciones.
Formas canónicas[1]
Como sabemos, toda expresión lógica se puede representar en las cuatro formas canónicas. En este artículo vamos a centrarnos en la primera y segunda forma canónica.
La primera forma canónica corresponde a una suma de productos; mientras que la segunda forma canónica, al producto de sumas.
Por ejemplo:
Ejemplo en la 1ª Forma canónica
Sea la expresión:
Podemos desarrollar su tabla de verdad obteniendo:
A | b | c | d | a"bc" | b"d | a"d" | P1 | |||
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | |||
0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||
0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | |||
0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | |||
0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||
0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | |||
0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | |||
0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | |||
1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |||
1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | |||
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |||
1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | |||
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | |||
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||
Con lo cual el dominio de discurso de P1, que le asigna el valor verdadero resulta ser:
a | b | c | d |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
Mientras que los estados, valores de las variables, que le asignan un valor falso a la proposición P1 son:
a | b | c | d |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
El tiempo de complejidad de la resolución de la satisfacibilidad lógica en la 1ª forma canónica la obtengo en:
Siendo s el número de sumas.
Como podemos observar no depende del número de variables, y su actuación sobre el número de sumas es lineal.
Valores de una Proposición
Hemos calculado la base 1 generadora de cualquier proposición en su primera forma canónica. Para calcular la base 0 generadora de una proposición tan sólo hay que negar dicha proposición y aplicar las leyes de Morgan. Este proceso nos da la segunda forma canónica si partimos de la primera forma canónica y, análogamente, la primera forma canónica si partimos de la segunda forma canónica.
Por ejemplo:
En el Tratado sobre Satisfacibilidad Lógica defino una serie de parámetros, bases, operaciones, reglas, funciones, leyes… que llevan a su solución en dicho tiempo de complejidad.
Base Independiente
Leyes de contracción
Clasifico las leyes de contracción de la siguiente forma:
Ley 1ª | Ley de la Identidad |
Ley 2ª | Ley de la Unión |
Ley 3ª y Ley 4ª | Leyes de la Absorción |
Ley 5ª y Ley 6ª | Leyes Doble |
Podemos contraer dos vectores, es decir: Sean dos vectores, con ciertos requisitos, podemos expresar su dominio de discurso con un único vector.
Orden cero
Para el orden cero tenemos una única ley:
Ejemplo:
Como podemos observar corresponde a la Ley de la Identidad.
Expansión de una base
Llamamos Expansión de una base a la expansión de todos los vectores de la base.
Número de expansión
Base Irreducible
Como hemos observado en los ejemplos de P4 y Q, la base independiente no es única.
Proposición 2
Base Cardenasiana
Corolario
Epílogo
Estamos en condiciones de poder encontrar el dominio de discurso para cualquier proposición lógica.
Podemos utilizar también la tercera y cuarta forma canónica para encontrar dicho dominio de discurso, únicamente tendríamos que definir sus particularidades y, su resultado sería una base que podríamos transformarla en base cardenasiana.
La base cardenasiana, aun no siendo única para una proposición, es la representación del dominio de discurso más sencilla de todas las posibles. Siempre podemos encontrar una base cardenasiana para cualquier proposición.
Si la base que nos resulta de una forma canónica tuviere como resultado soluciones triples o superiores, tendríamos que utilizar la expresión de Lunar tantas veces como soluciones existiese menos una.
Las reglas de la interferencia y diferencia, las leyes de la contracción y la expansión, son leyes o reglas que actúan sobre el dominio de discurso; se diferencian claramente de las leyes de proposiciones, pues éstas actúan directamente sobre la proposición.
José Francisco Rivera Romualdo
Huelva
Jueves, quince de agosto de dos mil trece
Referencias
Fundamentos de Lógica Matemática y Computación [2006] Ed.: Sanz y Torres
Autor:
José Francisco Rivera Romualdo
[1] Véase páginas 60 a 72 de la referencia bibliográfica.