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:

Con lo cual el dominio de discurso de
P1, que le asigna el valor verdadero resulta
ser:

Mientras que los estados, valores de las
variables, que le asignan un valor falso a la
proposición P1 son:

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:

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.