Lógica Proposicional

La lógica proposicional 

o

 Lógica de orden cero

Es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.

La lógica proposicional trata con sistemas lógicos que carecen de cuantificadores, o variables interpretables como entidades. En lógica proposicional si bien no hay signos para variables de tipo entidad, sí existen signos para variables proposicionales (es decir, que pueden ser interpretadas como proposiciones con un valor de verdad de definido), de ahí el nombre proposicional. La lógica proposicional incluye además de variables interpretables como proposiciones simples signos para conectivas lógicas, por lo que dentro de este tipo de lógica puede analizarse la inferencia lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.

Ejemplo:

Considérese el siguiente argumento:

1. Mañana es miércoles o mañana es jueves.
2. Mañana no es jueves.
3. Por lo tanto, mañana es miércoles.

Es un argumento válido. Quiere decir que es imposible que las premisas sean verdaderas y la conclusión falsa. Esto no quiere decir que la conclusión sea verdadera. Si las premisas son falsas, entonces la conclusión también podría serlo. Pero si las premisas son verdaderas, entonces la conclusión también lo es. La validez de este argumento no se debe al significado de las expresiones «mañana es miércoles» y «mañana es jueves», porque éstas podrían cambiarse por otras y el argumento permanecer válido. Por ejemplo:

1. Está soleado o está nublado.
2. No está nublado.
3. Por lo tanto, está soleado.

En cambio, la validez de estos dos argumentos depende del significado de las expresiones «o» y «no». Si alguna de estas expresiones se cambiara por otra, entonces podría ser que los argumentos dejaran de ser válidos. Por ejemplo:

1. Ni está soleado ni está nublado.
2. No está nublado.
3. Por lo tanto, está soleado.

Las expresiones de las que depende la validez de los argumentos se llaman constantes lógicas. La lógica proposicional estudia el comportamiento de algunas de estas expresiones, llamadas conectivas lógicas. En cuanto a las expresiones como "está nublado" o "mañana es jueves", lo único que importa de ellas es que tengan un valor de verdad. Es por esto que se las reemplaza por simples letras, cuya intención es simbolizar una expresión con valor de verdad cualquiera. A estas letras se las llama variables proposicionales, y en general se toman del alfabeto latino, empezando por la letra p, luego q, r, s, etc. Así, los dos primeros argumentos de esta sección podrían reescribirse así:

1. p o q
2. No q
3. Por lo tanto, p

Y el tercer argumento, a pesar de no ser válido, puede reescribirse así:

1. Ni p ni q
2. No q
3. Por lo tanto, p

Conectivas lógicas

A continuación hay una tabla que despliega todas las conectivas lógicas que ocupan a la lógica proposicional, incluyendo ejemplos de su uso en el lenguaje natural y los símbolos que se utilizan para representarlas en lenguaje formal:

En la lógica proposicional, las conectivas lógicas se tratan como funciones de verdad. Es decir, como funciones que toman conjuntos de valores de verdad y devuelven valores de verdad. Por ejemplo, la conectiva lógica «no» es una función que si toma el valor de verdad V, devuelve F, y si toma el valor de verdad F, devuelve V. Por lo tanto, si se aplica la función «no» a una letra que represente una proposición falsa, el resultado será algo verdadero. Si es falso que «está lloviendo», entonces será verdadero que «no está lloviendo».

El significado de las conectivas lógicas no es nada más que su comportamiento como funciones de verdad. Cada conectiva lógica se distingue de las otras por los valores de verdad que devuelve frente a las distintas combinaciones de valores de verdad que puede recibir. Esto quiere decir que el significado de cada conectiva lógica puede ilustrarse mediante una tabla que despliegue los valores de verdad que la función devuelve frente a todas las combinaciones posibles de valores de verdad que puede recibir.

Leyes notables en lógica

Entre las reglas de la lógica proposicional clásica algunas de la más notables son listadas a continuación:

1.    Ley de doble negación

2.    Leyes de idempotencia

3.    Leyes asociativas

4.    Leyes conmutativas

5.    Leyes distributivas

6.    Leyes de De Morgan

Otras leyes como el principio del tercero excluido son admisibles en lógica clásica, pero en lógica intuicionista y con fines a sus aplicaciones matemáticas no existe un equivalente del tercero excluido, por ejemplo.

Límites de la lógica proposicional

La maquinaria de la lógica proposicional permite formalizar y teorizar sobre la validez de una gran cantidad de argumentos. Sin embargo, también existen argumentos que son intuitivamente válidos, pero cuya validez no puede ser probada por la lógica proposicional. Por ejemplo, considérese el siguiente argumento:

1.    Todos los hombres son mortales.

2.    Sócrates es un hombre.

3.    Por lo tanto, Sócrates es mortal.

Como este argumento no contiene ninguna de las conectivas «no», «y», «o», etc., según la lógica proposicional, su formalización será la siguiente:

1.    p

2.    q

3.    Por lo tanto, r

Pero esta es una forma de argumento inválida, y eso contradice nuestra intuición de que el argumento es válido. Para teorizar sobre la validez de este tipo de argumentos, se necesita investigar la estructura interna de las variables proposicionales. De esto se ocupa la lógica de primer orden. Otros sistemas formales permiten teorizar sobre otros tipos de argumentos. Por ejemplo la lógica de segundo orden, la lógica modal y la lógica temporal.

Dos sistemas formales de lógica proposicional

A continuación se presentan dos sistemas formales estándar para la lógica proposicional. El primero es un sistema axiomático simple, y el segundo es un sistema sin axiomas, de deducción natural.

Sistema axiomático

Alfabeto

El alfabeto de un sistema formal es el conjunto de símbolos que pertenecen al lenguaje del sistema. Si L es el nombre de este sistema axiomático de lógica proposicional, entonces el alfabeto de L consiste en:

·         Una cantidad finita pero arbitrariamente grande de variables proposicionales. En general se las toma del alfabeto latino, empezando por la letra p, luego q, r, etc., y utilizando subíndices cuando es necesario o conveniente. Las variables proposicionales representan proposiciones como "está lloviendo" o "los metales se expanden con el calor".

·         Un conjunto de operadores lógicos: 

·         Dos signos de puntuación: los paréntesis izquierdo y derecho. Su única función es desambiguar ciertas expresiones ambiguas, en exactamente el mismo sentido en que desambiguan la expresión 2 + 2 ÷ 2, que puede significar tanto (2 + 2) ÷ 2, como 2 + (2 ÷ 2).

Gramática

Una vez definido el alfabeto, el siguiente paso es determinar qué combinaciones de símbolos pertenecen al lenguaje del sistema. Esto se logra mediante una gramática formal. La misma consiste en un conjunto de reglas que definen respectivamente las cadenas de caracteres que pertenecen al lenguaje. A las cadenas de caracteres construidas según estas reglas se las llama fórmulas bien formadas. Las reglas del sistema L son:

1.    Las variables proposicionales del alfabeto de L son fórmulas bien formadas.

2.    Si  es una fórmula bien formada de L, entonces también lo es.

3.    Si  y son fórmulas bien formadas de L, entonces ,   ,  y  también lo son.

4.    Sólo las expresiones que pueden ser generadas mediante las cláusulas 1 a 3 en un número finito de pasos son fórmulas bien formadas de L.

Axiomas

Los axiomas de un sistema formal son un conjunto de fórmulas bien formadas que se toman como punto de partida para demostraciones ulteriores. Un conjunto de axiomas estándar es el que descubrió Jan Łukasiewicz:

Reglas de inferencial

Una regla de inferencia es una función que va de conjuntos de fórmulas a fórmulas. Al conjunto de fórmulas que la función toma como argumento se lo llama premisas, mientras que a la fórmula que devuelve como valor se la llama conclusión. En general se busca que las reglas de inferencia transmitan la verdad de las premisas a la conclusión. Es decir, que sea imposible que las premisas sean verdaderas y la conclusión falsa. En el caso de L, la única regla de inferencia es el modus ponens, el cual dice:

Recordando que y no son fórmulas, sino meta variables que pueden ser reemplazadas por cualquier fórmula bien formada.

Lenguaje formal en la notación BNF

El lenguaje formal de la lógica proposicional se puede generar con la gramática formal descrita usando la notación BNF como sigue:

 La gramática anterior define la precedencia de operadores de la siguiente manera:

1.     Negación ()

2.     Conjunción ( )

3.     Disyunción ()

4.     Condicional material ( )

5.     Bicondicional ()

 Semántica

Una interpretación para un sistema de lógica proposicional es una asignación de valores de verdad para cada variable proposicional, sumada a la asignación usual de significados para los operadores lógicos. A cada variable proposicional se le asigna uno de dos posibles valores de verdad: o V (verdadero) o F (falso). Esto quiere decir que si hay n variables proposicionales en el sistema, el número de interpretaciones distintas es de 2n.

Tablas de verdad

La tabla de verdad de una fórmula es una tabla en la que se presentan todas las posibles interpretaciones de las variables proposicionales que constituye la fórmula y el valor de verdad de la fórmula completa para cada interpretación. Por ejemplo, la tabla de verdad para la fórmula sería:

Como se ve, esta fórmula tiene 2ⁿ interpretaciones posibles —una por cada línea de la tabla—, donde n es el número de variables proposicionales (en este caso 3, es decir p, q, r) , y resulta ser una tautología, es decir que bajo todas las interpretaciones posibles de las variables proposicionales, el valor de verdad de la fórmula completa termina siendo V.

Tablas de verdad

En un sistema de lógica proposicional, una interpretación no es más que una función que asigna un único valor de verdad a todas las fórmulas atómicas bajo consideración. Diferentes interpretaciones, por lo tanto, difieren sólo en las asignaciones de valores de verdad que hacen. Una tautología es una fórmula bien formada que bajo cualquier interpretación de sus componentes atómicos, tiene valor de verdad 1 (verdadero). Por lo tanto, para determinar si una fórmula cualquiera es una tautología, basta con considerar todas las posibles interpretaciones de las fórmulas atómicas, y calcular el valor de verdad del todo. Esto se logra mediante una tabla de verdad. Por ejemplo, considérese la fórmula p ∧q. Como a cada fórmula atómica puede asignársele uno de dos posibles valores de verdad, hay en total 2² = 4 posibles combinaciones de valores de verdad. Es decir, cuatro interpretaciones posibles: o ambas son verdaderas; o p es verdadera y q falsa; o p es falsa y q verdadera; o ambas son falsas. Esto puede presentarse mediante una simple tabla:

Para cada una de estas interpretaciones, puede calcularse el valor de verdad de la fórmula p ∧ q. Los resultados pueden presentarse nuevamente mediante una tabla:

 Esta es la tabla de verdad de la fórmula p ∧ q. Como se ve, esta fórmula sólo es verdadera bajo una interpretación: aquella en la que ambas fórmulas atómicas son verdaderas. Una tautología es una fórmula cuyo valor de verdad es 1 para todas las interpretaciones posibles de las fórmulas atómicas. Por lo tanto, p ∧ q no es una tautología. En cambio, la siguiente tabla de verdad muestra una fórmula que sí lo es:

Si una fórmula tiene n fórmulas atómicas, entonces tiene 2ⁿ interpretaciones posibles. En muchos casos, por lo tanto, las tablas de verdad pueden ser muy grandes. Lo importante, sin embargo, es que dado que la lógica proposicional no admite fórmulas infinitas, el número de interpretaciones posibles siempre será un número finito, y por lo tanto siempre será posible decidir si una fórmula cualquiera es una tautología o no.

Tautología
En lógica, una tautología (del griego ταυτολογία, "decir lo mismo") es una fórmula bien formada de un sistema de lógica proposicional que resulta verdadera para cualquier interpretación; es decir, para cualquier asignación de valores de verdad que se haga a sus fórmulas atómicas. La construcción de una tabla de verdad es un método efectivo para determinar si una fórmula cualquiera es una tautología o no.

Contradicción

En lógica, una contradicción es una incompatibilidad entre dos o más proposiciones. Por ejemplo, las oraciones «llueve y no llueve» y «ni llueve ni truena, pero llueve y truena» expresan contradicciones.

En lógica proposicional, una contradicción se define como una fórmula que resulta falsa para cualquier interpretación, es decir para cualquier asignación de valores de verdad que se haga a sus fórmulas atómicas.

Consistencia
En lógica, la consistencia o consistencia lógica es una propiedad que pueden tener los conjuntos de fórmulas. Intuitivamente, un conjunto de fórmulas es consistente cuando no contiene una contradicción o ambigüedad. La consistencia puede ser definida tanto en términos semánticos como en términos sintácticos. En términos semánticos, un conjunto de fórmulas es consistente si y sólo si tiene un modelo. Es decir, si existe al menos una interpretación que haga verdaderas a todas las fórmulas del conjunto. En términos sintácticos, un conjunto de fórmulas es consistente si y sólo si para toda fórmula A, no es posible deducir tanto A como ￢A (i.e. la negación lógica de A) a partir del conjunto de fórmulas.

.