Lógica Proposicional
Resumen
Se presentan conceptos asocidados a la lógica proposicional, cuyos elementos fundamentales son sentencias, que pueden ser evaluadas como falsas o verdaderas; se introduce el concepto de fórmula bien formada y de su deducción a partir de expresiones en lenguaje natural, así como la contrucción de fórmulas en sus formas normales. También se muestra la forma de construir circuitos lógicos equivalentes a fórmulas de la lógica proposicional.
1 Introducción
La lógica proposicional trabaja con sentencias u oraciones a las cuales se les puede asociar un valor de verdad (cierto o falso); estas sentencias se conocen como sentencias declarativas o, simplemente, proposiciones. Existen proposiciones que son simples, así como proposiciones que están construidas por otras proposiciones usando elementos (conectivas lógicas) que las asocian. Al construir una proposición, se debe garantizar que esta puede ser evaluada (fórmula bien formada); de la misma forma, podemos construir proposiciones usando solo un grupo de conectivas, produciendo fórmulas que se dice están en su forma normal. Las formas normales son importantes por el hecho que permiten definir esquemas generales para el tratamiento de estas fórmulas (GSAT, por ejemplo).
Otro aspecto importante es el de determinar si una proposición esta construida (o puede ser deducida) a partir de un conjunto de proposiciones, es decir, si es una consecuencia lógica de dicho conjunto.
Finalmente, existen varias formas de representar una fórmula de la lógica proposicional; aquí se introduce el concepto de circuitos lógicos, donde se asocia a las conectivas lógicas un símbolo gráfico.
2 Objetivos
Los objetivos que se persiguen dentro de este módulo son los siguientes:
El alumno distinguirá fórmulas bien formadas a partir de oraciones en lenguaje natural para especificar y definir formalmente un conjunto de sentencias.
El alumno probará consecuencias lógicas (CL) para un conjunto de fórmulas bien formadas, a partir de los teoremas 1 y 2 para distinguir cuando un enunciado es verdadero ante un conjunto de axiomas, o sigue de ellos.
3 Proposiciones
Al escuchar algo como La rosa es una flor o El cocodrilo es un mamífero, fácilmente se puede determinar si estas sentencias son ciertas o falsas; sin embargo, al escuchar No seas flojo! o Quién ganará las elecciones?, no es posible asociar a ellas un valor de verdad. Sentencias como las primeras dos son los elementos fundamentales con los que trabaja la lógica proposicional.
La lógica proposicional (o cálculo proposicional) tiene el propósito de simbolizar cualquier tipo de razonamiento para su análisis y tratamiento. Específicamente, para simbolizar razonamiento, la lógica proposicional usa sentencias declarativas a las que se puede asociar un valor de verdad (cierto o falso); es decir, usa proposiciones.
No existe una notación generalmente utilizada para representar proposiciones, pero en este curso se identifica a cada una de ellas con una letra mayúscula (o una cadena de letras mayúsculas).
Ejemplo: P y Q son proposiciones:
P : La rosa es una flor
Q : El cocodrilo es un mamífero
La asociación de proposiciones produce otras proposiciones conocidas como compuestas, por lo que es posible diferenciar a las proposiciones simples llamándolas fórmulas atómicas o, simplemente átomos y a las compuestas llamándolas fórmulas compuestas. Del ejemplo, P y Q son átomos.
4 Conectivas lógicas
La construcción de fórmulas compuestas requiere del uso de elementos que permitan establecer una relación entre los átomos que la forman; estos elementos se conocen como conectivas lógicas. En la proposición ''El agua esta fría y el calentador está descompuesto'' se tienen dos átomos (El agua esta fria, el calentador está descompuesto), unidos por la partícula ''y'' la cual se dice que es una conectiva lógica. Otro ejemplo sería ''Si Luis es ingeniero, entonces Luis es inteligente'', donde la conectiva lógica es ''Si ... entonces''.
Las conectivas lógicas usadas en la lógica proposicional son cinco y son representadas simbólicamente de varias formas, como se muestra en la tabla 1.
|
Conectiva |
Símbolos asociados |
|
Negación (No) |
~, ¬ , - |
|
Conjunción (Y) |
Ù, &, * |
|
Disyunción (O) |
Ú, |, + |
|
Condicional (Si ... entonces) |
® |
|
Bicondicional (Si y solo si) |
« , = |
Tabla 1: Conectivas Lógicas.
Así, para los ejemplos mencionados, se tendría la siguiente representación:
Ejemplo: C: ''El agua esta fría y el calentador está descompuesto'', se representa por AÙB.
donde:
A: El agua esta fría.
B: El calentador esta descompuesto.
Ejemplo: R: ''Si Luis es ingeniero, entonces Luis es inteligente'', se representa por P® Q.
donde:
P: Luis es ingeniero.
Q: Luis es inteligente.
Como es posible determinar si una proposición es cierta o falsa, al encontrarse con proposiciones unidas por conectivas lógicas, es necesario conocer cuales son las reglas que se aplican para determinar si la proposición completa es cierta o falsa. La tabla 2 señala los valores resultantes para la evaluación de proposiciones compuestas a partir de las diferentes combinaciones de valores de verdad de sus átomos. En esta tabla P y Q son los átomos y se utiliza V para un valor cierto y F para uno falso.
|
P |
Q |
¬ P
|
PÙQ |
PÚQ |
P® Q |
P« Q |
|
V |
V |
F |
V |
V |
V |
V |
|
V |
F |
F |
F |
V |
F |
F |
|
F |
V |
V |
F |
V |
V |
F |
|
F |
F |
V |
F |
F |
V |
V |
Tabla 2: Valores de verdad de proposiciones compuestas.
Ejemplo: Si P tiene un valor V, Q tiene un valor F y R es V, el valor de P® R es V y el valor de P® Q es F.
5 Fórmulas bien formadas
Como se ha explicado, las proposiciones compuestas son agrupaciones de átomos unidos por conectivas lógicas; es importante aclarar que al construir proposiciones, se requiere seguir una serie de reglas que establecen si una fórmula esta bien formada. De acuerdo a lo anterior, una formula bien formada (fbf) es aquella que cumple los siguientes cuatro puntos:
Un átomo es una fórmula bien formada.
Si P es una fórmula bien formada, ¬ P también es una fórmula bien formada.
Si P y Q son fórmulas bien formadas, PÙQ, PÚQ, P® Q y P« Q son fórmulas bien formadas.
Todas las fórmulas bien formadas se obtienen aplicando las reglas 1, 2 y 3.
De lo anterior, se puede decir que fórmulas están bien formadas y que fórmulas no lo están:
Ejemplo: Las siguientes son fórmulas bien formadas:
PÚ¬ Q
PÚ¬ Q® S
Ejemplo: Las siguientes no son fórmulas bien formadas:
® S
ÚP¬
P¬ R
6 Jerarquía de conectivas
Como se estableció anteriormente, para determinar el valor de verdad de una proposición compuesta, es necesario conocer cuales son las reglas que se aplican para determinar si la proposición completa es cierta o falsa; asimismo, al tener fórmulas con dos o más conectivas, se deben conocer las reglas de precedencia y asociatividad de las conectivas para asegurar que la evaluación es correcta. Aún cuando existen algunas diferencias en la determinación de una jerarquía de conectivas, en este texto se utilizará el siguiente orden:
¬ , Ù, Ú, ® , «
donde ¬ (negación) es el operador con mayor jerarquía en la secuencia y « (bicondicional) es el operador con el menor peso.
Ejemplo: El orden de evaluación de ¬PÚQÙR es, utilizando paréntesis, ( (¬ P) Ú( QÙR) ) ; es decir, primero se evalúa ¬ P, posteriormente QÙR, y finalmente se aplica Ú al resultado de ambas evaluaciones.
Al tener una fórmula con la presencia de dos o mas conectivas iguales, el orden de asociatividad siempre es de izquierda a derecha.
Ejemplo: El orden de evaluación de P® Q® R es ( ( P® Q) ® R) .
7 Interpretación de fórmulas
Una interpretación de una fórmula es una asignación de valores de verdad a un conjunto de átomos; para una fórmula con dos átomos se tienen dos posibles interpretaciones, para una con tres se tienen ocho interpretaciones, y en general para una fórmula con n átomos de tienen 2n interpretaciones.
Considerando las condiciones discutidas anteriormente, es posible determinar el valor de verdad cualquier una fórmula de la lógica proposicional.
Ejemplo: Teniendo que P es V, Q es F, R es V y S es V, la interpretación para la fórmula ¬ ( P® Q) ® ( RÙS) es:
|
P |
Q |
R |
S |
P® Q |
¬ ( P® Q) |
RÙS |
¬ ( P® Q) ® ( RÙS) |
|
V |
F |
V |
V |
F |
V |
V |
V |
En general, para evaluar una fórmula, se deben considerar todas sus posibles interpretaciones.
Ejemplo: La evaluación de ¬ ( P® Q) ® ( RÙS) es:
|
P |
Q |
R |
S |
P® Q |
¬ ( P® Q) |
RÙS |
¬ ( P® Q) ® ( RÙS) |
|
V |
V |
V |
V |
V |
F |
V |
V |
|
V |
V |
V |
F |
V |
F |
F |
V |
|
V |
V |
F |
V |
V |
F |
F |
V |
|
V |
V |
F |
F |
V |
F |
F |
V |
|
V |
F |
V |
V |
F |
V |
V |
V |
|
V |
F |
V |
F |
F |
V |
F |
F |
|
V |
F |
F |
V |
F |
V |
F |
F |
|
V |
F |
F |
F |
F |
V |
F |
F |
|
F |
V |
V |
V |
V |
F |
V |
V |
|
F |
V |
V |
F |
V |
F |
F |
V |
|
F |
V |
F |
V |
V |
F |
F |
V |
|
F |
V |
F |
F |
V |
F |
F |
V |
|
F |
F |
V |
V |
V |
F |
V |
V |
|
F |
F |
V |
F |
V |
F |
F |
V |
|
F |
F |
F |
V |
V |
F |
F |
V |
|
F |
F |
F |
F |
V |
F |
F |
V |
De la evaluación de una fórmula, se pueden definir los siguientes conceptos:
Tautología o fórmula válida: Una fórmula es una tautología si es verdadera para todas sus posibles interpretaciones. Una tautología también se conoce como una fórmula válida.
Contradicción, fórmula inconsistente o fórmula insatisfactible: Una fórmula es una contradicción si es falsa para todas sus posibles interpretaciones. Una contradicción también se conoce como una fórmula inconsistente o una fórmula insatisfactible.
Fórmula consistente o fórmula satisfactible: Una fórmula que al menos tiene una interpretación verdadera se conoce como una fórmula consistente o satisfactible.
Fórmula inválida: Una fórmula es inválida si es falsa para al menos una interpretación.
Ejemplo: La fórmula ( P® Q) ÚP es una tautología, ya que todas sus interpretaciones son verdaderas.
|
P |
Q |
P® Q |
( P® Q) ÚP |
|
V |
V |
V |
V |
|
V |
F |
F |
V |
|
F |
V |
V |
V |
|
F |
F |
V |
V |
Ejemplo: La fórmula ( P® Q) Ù¬ P es consistente, ya que de sus interpretaciones, dos son verdaderas.
|
P |
Q |
¬ P
|
P® Q |
( P® Q) Ù¬ P |
|
V |
V |
F |
V |
F |
|
V |
F |
F |
F |
F |
|
F |
V |
V |
V |
V |
|
F |
F |
V |
V |
V |
Como consecuencia de las definiciones anteriores, se tiene que:
Una fórmula es válida si y solo si su negación es inconsistente.
Una fórmula es inconsistente si y solo si su negación es válida.
Una fórmula es inválida si y solo si existe por lo menos una interpretación sobre la cual la fórmula es falsa.
Una fórmula es consistente si y solo si existe por lo menos una interpretación sobre la cual la fórmula es verdadera.
Si una fórmula es válida, entonces es consistente, pero no viceversa.
Si una fórmula es inconsistente, entonces es inválida, pero no viceversa.
8 Fórmulas equivalentes
Al evaluar las fórmulas P® Q y ¬ PÚQ se observa que todas sus interpretaciones son iguales, por lo que se dice que ambas fórmulas son equivalentes.
Ejemplo: P® Q y ¬ PÚQ son fórmulas equivalentes:
|
P |
Q |
¬ P
|
P® Q |
¬ PÚQ |
|
V |
V |
F |
V |
V |
|
V |
F |
F |
F |
F |
|
F |
V |
V |
V |
V |
|
F |
F |
V |
V |
V |
Existen varias equivalencias entre fórmulas de la lógica proposicional, las cuales se conocen como leyes de equivalencia. La tabla 3 muestra estas leyes. Se utiliza el símbolo Tautología para indicar una tautología y el símbolo Contradicción para indicar una contradicción.
|
Ley de equivalencia |
Fórmula |
|
Doble Implicación |
F«G = (F® G)Ù(G® H) |
|
Implicación |
F® G = ¬ FÚG |
|
Distribución |
FÚ(GÙH) = (FÚG)Ù(FÚH) |
|
|
FÙ(GÚH) = (FÙG)Ú(FÙH) |
|
Asociación |
(FÚG)ÚH = FÚ(GÚH) |
|
|
(FÙG)ÙH = FÙ(GÙH) |
|
Complementación |
FÙ¬ F = Contradicción |
|
|
FÚ¬ F = Tautología |
|
|
¬ ¬ F = F |
|
Conmutación |
FÚG = GÚF |
|
|
FÙG = GÙF |
|
Cero |
FÚTautología = Tautología |
|
|
FÙContradicción = Contradicción |
|
Identidad |
FÚContradicción = F |
|
|
FÙTautología = F |
|
Idempotencia |
FÚF = F |
|
|
FÙF = F
|
|
Absorción |
FÚFÙQ = F |
|
|
FÙ(FÚQ) = F |
|
|
FÚ¬ FÙQ = FÚQ |
|
Leyes de Morgan |
¬ (FÚQÚH) = ¬ FÙ¬ QÙ¬ H |
|
|
¬ (FÙQÙH) = ¬ FÚ¬ QÚ¬ H |
Tabla 3: Leyes de equivalencias para fórmulas
lógicas.
9 Formas normales
Las leyes de equivalencia permiten transformar fórmulas de la lógica proposicional en otras fórmulas más simples de evaluar o que estén escritas en alguna forma que sea útil para su manipulación. En lógica proposicional existen dos formas para presentar fórmulas que son importantes ya que permiten definir métodos genéricos de evaluación y análisis; estas formas se conocen como formas normales, y en particular: forma normal conjuntiva y forma normal disyuntiva.
Forma Normal Conjuntiva: Una fórmula está en su forma normal conjuntiva (FNC) si es una conjunción de disyunciones, es decir, tiene la forma: F1ÙF2Ù...ÙFn, en la cual Fn es una fórmula construida por una agrupación de átomos unidos por disyunciones; esto es Fn es P1ÚP2Ú...ÚPm. En ambos casos n y m pueden ser mayores o iguales a 1.
Forma Normal Disyuntiva: Una fórmula está en su forma normal disyuntiva (FND) si es una disyunción de conjunciones, es decir, tiene la forma: F1ÚF2Ú...ÚFn , en la cual Fn es una fórmula construida por una agrupación de átomos unidos por conjunciones; esto es Fn es P1ÙP2Ù...ÙPm.
Ejemplo: La fórmula ( PÚQÚR) Ù( ¬ PÚR)ÙR está en su forma normal conjuntiva construida de tres funciones F1:PÚQÚR, F2:¬ PÚR y F3:R. Cada función es una agrupación de átomos unidos por disyunciones.
Ejemplo: La fórmula ( PÙQÚR) Ù( ¬ PÚR)ÙR no está en su forma normal conjuntiva.
Para poder transformar cualquier fórmula a su forma normal (conjuntiva o disyuntiva), es necesario aplicar la siguiente secuencia de operaciones de equivalencia sobre la fórmula original:
Sustituir todas las ocurrencias de conectivas ® y « en la fórmula usando las correspondientes leyes de equivalencia.
Asegurarse que las negaciones afecten solo a átomos, usando las leyes de Morgan y la eliminación de dobles negaciones.
Aplicar las otras leyes para encontrar la forma normal (las principales leyes que se aplican son las distributivas).
Ejemplo: La forma normal conjuntiva de P® Q® S es ( PÚS) Ù( ¬ QÚS) ya que aplicando las reglas anteriores:
Se eliminan las condicionales P® Q por ¬ PÚQ y ( ¬ PÚQ) ® S por ¬ ( ¬ PÚQ) ÚS.
Se pasan las negaciones a los átomos usando leyes de Morgan produciendo ¬ ¬ PÙ¬ QÚS.
Se elimina la doble negación resultando PÙ¬ QÚS.
Como la conjunción tiene mayor prioridad, se distribuye la disyunción, quedando ( PÚS) Ù( ¬ QÚS) , que ya esta en la forma normal conjuntiva.
Ejemplo: La forma normal disyuntiva de P® Q® S es PÙ¬ QÚS.
10 Consecuencias lógicas
Otro concepto importante en la lógica proposicional es el de consecuencia lógica. Uno de los aspectos a analizar en la lógica proposicional es el de determinar la validez de argumentos representados por fórmulas bien formadas. Un argumento esta formado por las premisas, axiomas o postulados y por una conclusión, objetivo o consecuencia lógica. Las premisas son proposiciones que son base para la deducción de una conclusión o consecuencia.
Así, en términos de la lógica proposicional, una consecuencia lógica es aquella fórmula (G) que es derivada de un grupo de fórmulas (F) cumpliendo la restricción de ser verdadera para todas las interpretaciones verdaderas del grupo de fórmulas (F). Esto es, G es una consecuencia lógica de las premisas F, si y solo si, al ser verdaderas las premisas, G siempre es verdadera.
Para probar si una fórmula es una consecuencia lógica de un grupo de fórmulas se tienen dos métodos, que se producen a partir de los conceptos de validez e inconsistencia. Estos métodos se conocen en forma de teoremas:
Teorema 1: Teniendo un grupo de fórmulas F1, F2,...,Fn y otra llamada G, G es una consecuencia lógica de F1, F2,...,Fn si y solo si la fórmula ( F1ÙF2Ù¼ÙFn) ® G es válida.
Teorema 2: Teniendo un grupo de fórmulas F1, F2,...,Fn y otra llamada G, G es una consecuencia lógica de F1, F2,...,Fn si y solo si la fórmula F1ÙF2Ù¼ÙFnÙ¬ G es inconsistente.
Para demostrar si G es una consecuencia lógica se pueden usar tablas de verdad o aplicar las leyes de equivalencia para encontrar su forma normal.
Ejemplo: U es una consecuencia lógica de ( ¬ PÚS) Ù( ¬ SÚU) ÙP ya que:
Definición de consecuencia lógica:
Aplicando la definición de consecuencia lógica y aplicando tablas de verdad se tiene que:
|
P |
S |
U |
¬ P |
¬ S |
¬ PÚS |
¬ SÚU |
( ¬ PÚS) Ù( ¬ SÚU)ÙP |
|
V |
V |
V |
F |
F |
V |
V |
V |
|
V |
V |
F |
F |
F |
V |
F |
F |
|
V |
F |
V |
F |
V |
F |
V |
F |
|
V |
F |
F |
F |
V |
F |
V |
F |
|
F |
V |
V |
V |
F |
V |
V |
F |
|
F |
V |
F |
V |
F |
V |
F |
F |
|
F |
F |
V |
V |
V |
V |
V |
F |
|
F |
F |
F |
V |
V |
V |
V |
F |
Se observa que U es verdadero para la única interpretación verdadera de ( ¬ PÚS)Ù( ¬ SÚU) ÙP.
1. Teorema 1:
Usando tablas de verdad la fórmula ( ( ¬PÚS) Ù( ¬ SÚU) ÙP) ® U es una fórmula válida.
|
( ¬ PÚS) Ù( ¬ SÚU) ÙP |
U |
( ( ¬PÚS) Ù( ¬ SÚU) ÙP) ® U |
|
V |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
Otra forma es transformando la fórmula original en su forma normal disyuntiva:
|
( ( ¬ PÚS) Ù( ¬SÚU) ÙP) ® U |
|
|
¬ ( ( ¬ PÚS) Ù( ¬ SÚU) ÙP) ÚU |
eliminado condicional |
|
( ¬ ( ¬ PÚS) Ú¬ ( ¬ SÚU) Ú¬ P) ÚU |
aplicando De Morgan |
|
( ( ¬ ¬ PÙ¬ S) Ú( ¬ ¬ SÙ¬ U) Ú¬ P) ÚU |
aplicando De Morgan |
|
( ( PÙ¬ S) Ú( SÙ¬ U) Ú¬ P) ÚU |
aplicando De Morgan |
|
( PÙ¬ S) Ú( SÙ¬ U) Ú¬ PÚU |
eliminando paréntesis innecesarios |
|
( PÙ¬ S) Ú¬ PÚ( SÙ¬ U) ÚU |
aplicando la ley conmutativa |
|
( ( PÚ¬ P) Ù( ¬ SÚ¬ P) ) Ú( SÙ¬ U) ÚU |
distribuyendo ¬ P en PÙ¬ S |
|
( Tautología Ù( ¬ SÚ¬ P) ) Ú( SÙ¬ U) ÚU |
aplicando complementación en PÚ¬ P |
|
( ¬ SÚ¬ P) Ú( SÙ¬ U) ÚU |
aplicando identidad en Tautología Ù( ¬ SÚ¬ P) |
|
( ¬ SÚ¬ P) Ú( ( SÚU) Ù( ¬ UÚU) ) |
distribuyendo U en SÙ¬ U |
|
( ¬ SÚ¬ P) Ú( ( SÚU) ÙTautología ) |
aplicando complementación en ¬ UÚU |
|
( ¬ SÚ¬ P) Ú( SÚU) |
aplicando identidad en ( SÚU) ÙTautología |
|
¬ SÚ¬ PÚSÚU |
eliminando paréntesis innecesarios |
|
Tautología Ú¬ PÚU |
aplicando complementación en ¬ SÚS |
|
Tautología |
aplicando complementación en Tautología Ú¬ PÚU |
2. Teorema 2:
Usando tablas de verdad la fórmula ( ( ¬PÚS) Ù( ¬ SÚU) ÙP) Ù¬ U es una fórmula inconsistente.
|
( ¬ PÚS) Ù( ¬ SÚU) ÙP |
U |
¬ U |
(( ¬ PÚS) Ù( ¬ SÚU) ÙP) Ù¬ U |
|
V |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
F |
F |
V |
F |
11 Circuitos Lógicos
Debido a que una proposición puede ser evaluada y resultar solo verdadera o falsa, se puede deducir alguna equivalencia con el álgebra booleana, que maneja solamente dos valores (0 y 1). Las propiedades del cálculo proposicional son equivalentes a las del álgebra desarrollada por Boole.
En el álgebra booleana, una proposición es equivalente a una variables, y las conectivas lógicas se utilizan como compuertas lógicas. La figura 1 muestra las compuestas lógicas más representativas de esta álgebra. Los esquemas que resultan de aplicar las compuertas lógicas se conocen como circuitos lógicos.
Figura 1: Compuertas Lógicas.
Una fórmula del cálculo proposicional se puede representar gráficamente usando compuertas lógicas. Como se observa, para representar fórmulas con condicionales o bicondicionales se debe transformar la fórmula para eliminarlas.
Ejemplo: La representación en circuito lógico de ( ¬ PÚQ) Ù( ¬ QÚR) es: