Lógica Matemática - LPred: Evaluación de fórmulas

EVALUACION DE LAS FORMULAS Y OTROS CONECTIVOS.

Otras conectivas: En l´ogica proposicional, a ^, _ y ¬ se les llama conectivas
l´ogicas. A menudo tambi´en se consideran otras conectivas, como!o$. Aqu´ý no
las hemos introducido porque son expresables mediante las tres conectivas dadas.
Por ejemplo, las f´ormulas F ! G y F $ G pueden verse como abreviaturas
de (¬F _ G) y de ((¬F _ G) ^ (¬G _ F)) respectivamente.
No ambig¨uedad, representaci´on en ´arbol: Las f´ormulas, vistas como una
cadena de s´ýmbolos (conectivas, s´ýmbolos de predicado y par´entesis), no son ambiguas:
existe una ´unica forma de entenderlas. Formalmente: para cada f´ormula
F existe un ´unico ´arbol que representa la construcci´on de F seg´un la definici´on
de la sintaxis de la l´ogica proposicional.
Por ejemplo, la f´ormula ((p ^ q) _ ¬(r ^ ¬q)) s´olo puede leerse como un _ de
la f´ormula (p ^ q) y de la f´ormula ¬(r ^ ¬q). ´Estas a su vez s´olo son legibles de
una ´unica manera, y as´ý sucesivamente. El ´arbol correspondiente es:
_
. &
^ ¬
. & # p q ^
. & r ¬
#q
Prioridades de conectivas y par´entesis: A veces podemos omitir par´entesis
innecesarios: quitarlos no introduce ambig¨uedad. Por ejemplo, podemos escribir
p ^ q en vez de (p ^ q). Adem´as se asumen las siguientes prioridades entre las
conectivas; de m´as prioritario a menos, tenemos: ¬ ^ _ ! $. As´ý, podemos
escribir p^q _r para referirnos a (p^q)_r, pero no podemos omitir par´entesis
en ¬(p ^ (q _ r)). N´otese la similitud con la suma, el producto, y el “−” unario
en aritm´etica: con −x_y+z nos referimos a ((−x) _y)+z y no a, por ejemplo,
−(x _ (y + z)), ni a (−x) _ (y + z) .
3
¿Qu´e cosas se modelan con esta l´ogica?: La idea intuitiva de esta l´ogica
es que sirve para modelar (y razonar formalmente sobre) situaciones de la vida
real en las que tratemos con enunciados o proposiciones que s´olo pueden ser o
bien ciertas o bien falsas.
Por ejemplo, si P es { llueve, hace sol , esta nublado }, cada interpretaci
´on I para esta P modela una situaci´on real del tiempo del estilo de “s´ý llueve,
no hace sol y no est´a nublado”, es decir, I(llueve) = 1, I(hace sol ) = 0,
I(esta nublado) = 0. Con esta interpretaci´on I, si F es la f´ormula
llueve ^ ¬(hace sol _ esta nublado)
entonces, por la definici´on de evalI , tenemos evalI (F) =
min( I(llueve), 1 − max( I(hace sol ), I(esta nublado) ) ) =
min( 1, 1 − max( 0, 0 ) ) = 1,
luego F es cierta en I, es decir, tenemos I |= F. Similarmente, si G es la f´ormula
¬llueve _ (hace sol _ esta nublado), entonces I no satisface G, es decir, I 6|= G.
Podemos listar todas las posibles interpretaciones y la evaluaci´on en cada
una de ellas de la f´ormula llueve ^ ¬(hace sol _ esta nublado) mediante una
tabla de verdad (escribiendo p, q, r en vez de llueve, hace sol , y esta nublado):
p q r p ^ ¬(q _ r)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0
y vemos que en este ejemplo s´olo hay una interpretaci´on que satisface la f´ormula,
que es cuando llueve, no hace sol y no est´a nublado.
4. Satisfacci´on, tautolog´ýa, consecuencia, y equivalencia
Ahora podemos introducir la siguiente nomenclatura b´asica. Estas nociones
no dependen de la l´ogica concreta. Se definen de manera id´entica en otras l´ogicas
distintas a la l´ogica proposicional, como la l´ogica de primer orden. Por eso no
se repetir´an cuando tratemos a la l´ogica de primer orden.
1. Una f´ormula F es satisfactible si tiene alg´un modelo, es decir, si existe
alguna interpretaci´on I tal que I |= F. Un f´ormula F es insatisfactible (o
es una contradicci´on) si no es satisfactible.
2. Una f´ormula F es una tautolog´ýa (o es v´alida), si toda interpretaci´on es
modelo de F, es decir, si para toda interpretaci´on I tenemos I |= F.
4
3. Sean F y G f´ormulas construidas sobre un vocabulario P.
Definimos: F es consecuencia l´ogica de G si todo modelo de G tambi´en
lo es de F, es decir, si para toda interpretaci´on I sobre P tal que I |= G
tenemos I |= F. Sobrecargando el operador “|=”, esto se denotar´a por
G |= F.
4. Sean F y G f´ormulas construidas sobre un vocabulario P.
Definimos: F y G son l´ogicamente equivalentes si tienen los mismos modelos,
es decir, si para toda interpretaci´on I sobre P tenemos I |= G si y
s´olo si I |= F. Esto se denotar´a por G _ F.
N´otese que el s´ýmbolo “|=” denota satisfacci´on cuando a su izquierda hay
una interpretaci´on I; en ese caso, I |= F denota que I satisface F. En cambio,
cuando a la izquierda hay una f´ormula G, el s´ýmbolo “|=” denota consecuencia
l´ogica; as´ý, G |= F denota que todo modelo de G satisface F.
Este tipo de propiedades (satisfactibilidad o tautolog´ýa de una f´ormula, consecuencia
l´ogica o equivalencia entre f´ormulas, etc.) se plantean en diversas aplicaciones
pr´acticas de una l´ogica. Por ejemplo, en Intel pueden estar interesados
en saber si dos circuitos (dos f´ormulas) son equivalentes, o saber si un circuito
F cumple cierta propiedad G (es decir, si F |= G).
La l´ogica proposicional es especialmente interesante porque todas estas propiedades
son decidibles: para cada una de ellas hay alg´un programa de ordenador
que siempre termina y nos da una respuesta correcta s´ý/no. Por ejemplo, para
saber si una f´ormula F dada es satisfactible, podemos construir su tabla de
verdad con la lista de todas las posibles interpretaciones I para el vocabulario
P sobre el que F est´a construido, y averiguar si hay alg´un 1 en la columna de
F, esto es, si evalI (F) = 1 para alguna I.
Similarmente, tenemos F |= G para dos f´ormulas F y G dadas si y s´olo si
en la tabla de verdad (para el vocabulario P de F y G), por cada fila con un 1
en la columna de F tambi´en hay un 1 en la columna de G.
Sin embargo, estos m´etodos basados en la tabla de verdad no son los m´as
eficientes. En los ejercicios veremos que cualquiera de estas propiedades se puede
expresar en t´erminos del problema de la satisfactibilidad (abreviado, SAT), esto
es, el de determinar si una f´ormula proposicional dada es satisfactible o no. Por
ejemplo, para dos f´ormulas F y G tenemos F |= G si, y s´olo si, F ^ ¬G es
insatisfactible. Por eso, para las aplicaciones pr´acticas se usa un SAT solver,
esto es, un programa de ordenador que, dada una f´ormula F, decide si F es
satisfactible o no.