Artículo sobre el libro: Tratado sobre Satisfacibilidad Lógica
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 |
Ley 2ª | Ley de la |
Ley 3ª y Ley | Leyes de la |
Ley 5ª y Ley | Leyes |
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.