SEP                                DGIT                    SEIT

     INSTITUTO  TECNOLÓGICO  DE  MINATITLAN

Lógica Proposicional

Hasta aquí hemos visto la lógica tradicional. Vamos a ver ahora la lógica proposicional, desarrollada a partir del siglo XVIII por autores como Boole, Frege, Peano, Russell, Wittgenstein, Peirce, Cantor y otros.

A cualquier proposición, sea que tenga la forma sujeto-predicado o no, se le puede asignar un valor de verdad y se puede en poner en relación lógica con otras proposiciones. Por supuesto, esto complica un poco las cosas, porque la proposición puede ser muy compleja, y sin embargo su valor de verdad solamente es uno: verdadera o falsa.

Podemos, sin embargo, descomponer estas proposiciones. Por ejemplo, si decimos “Julio y Aura se fueron al cine”, estamos diciendo que

            Julio fue al cine.

            y

            Aura fue al cine.

Estas proposiciones “atómicas” se juntan para formar una más compleja. En lógica proposicional se trata de descubrir el valor de verdad de las proposiciones moleculares, a partir del valor de verdad de las proposiciones atómicas y de los conectivos lógicos (y, o, entonces, si y solo si, no). Por ejemplo, si sabemos que es verdad que Julio fue al cine, y que es verdad que Aura fue al cine, podemos afirmar que es verdad que Julio fue al cine y Aura fue al cine (es decir, que Julio y Aura fueron al cine).

La lógica proposicional se basa en tres nociones clave: valor de verdad, operadores lógicos y variables. Cada uno de estos conceptos puede ser simbolizado: V o F, >, P. La simbolización hace que a esta lógica se le conozca también como lógica matemática.

Cada enunciado es o verdadero o falso. En el lenguaje ordinario, por supuesto, admitimos cierto grado de verdad, o de indeterminación. Puede que algo no sea ni verdadero ni falso. Pero en lógica proposicional no hay lugar para “tal vez”, o “es probable”, o “no se sabe”. Cada proposición tiene un valor de verdad: o es verdadera, o es falsa. Si su valor de verdad es indeterminado, no se le pude considerar una proposición atómica. Esto quiere decir que la lógica proposicional es una lógica binaria. Es la misma que la que emplean las computadoras: 1-0, verdadero-falso, pasa-no pasa. También se le llama álgebra booleana, en honor a George Boole.

La lógica proposicional hace uso de los operadores lógicos, esto es, símbolos que indican la relación sintáctica precisa entre las proposiciones. Normalmente, se usan cinco operadores lógicos, que corresponden a las relaciones de conjunción, disyunción, condicionalidad, bicondicionalidad y negación.

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) .

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 2ⁿ 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:

En general, para evaluar una fórmula, se deben considerar todas sus posibles interpretaciones.

Ejemplo: La evaluación de ¬ ( P® Q) ® ( RÙS) es:

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.

Ejemplo: La fórmula ( P® Q) Ù¬ P es consistente, ya que de sus interpretaciones, dos son verdaderas.

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.

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:

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.

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: F₁ÙF₂Ù...ÙF_n, en la cual F_n es una fórmula construida por una agrupación de átomos unidos por disyunciones; esto es F_n es P₁ÚP₂Ú...ÚP_m. 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: F₁ÚF₂Ú...ÚF_n , en la cual F_n es una fórmula construida por una agrupación de átomos unidos por conjunciones; esto es F_n es P₁ÙP₂Ù...ÙP_m.

Ejemplo: La fórmula ( PÚQÚR) Ù( ¬ PÚR)ÙR está en su forma normal conjuntiva construida de tres funciones F₁:PÚQÚR, F₂:¬ PÚR y F₃: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:

1. Sustituir todas las ocurrencias de conectivas ® y « en la fórmula usando las correspondientes leyes de equivalencia.

    

2. Asegurarse que las negaciones afecten solo a átomos, usando las leyes de Morgan y la eliminación de dobles negaciones.

    

3. 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.

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 F₁, F₂,...,F_n y otra llamada G, G es una consecuencia lógica de F₁, F₂,...,F_n si y solo si la fórmula ( F₁ÙF₂Ù¼ÙF_n) ® G es válida.

Teorema 2: Teniendo un grupo de fórmulas F₁, F₂,...,F_n y otra llamada G, G es una consecuencia lógica de F₁, F₂,...,F_n si y solo si la fórmula F₁ÙF₂Ù¼ÙF_nÙ¬ 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:

1) Definición de consecuencia lógica:

Aplicando la definición de consecuencia lógica y aplicando tablas de verdad se tiene que:

Se observa que U es verdadero para la única interpretación verdadera de ( ¬ PÚS)Ù( ¬ SÚU) ÙP.

2) Teorema 1:

Usando tablas de verdad la fórmula ( ( ¬PÚS) Ù( ¬ SÚU) ÙP) ® U es una fórmula válida.

Otra forma es transformando la fórmula original en su forma normal disyuntiva:

2) Teorema 2:

Usando tablas de verdad la fórmula ( ( ¬PÚS) Ù( ¬ SÚU) ÙP) Ù¬ U es una fórmula inconsistente.