Cálculo proposicional

La lógica proposicional, también llamada lógica de enunciados, lógica de orden cero o cálculo proposicional, es un sistema formal cuyos elementos más simples representan proposiciones o enunciados, y cuyas constantes lógicas, llamadas conectivas lógicas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.^[1]​

Las lógicas proposicionales carecen de cuantificadores o variables de individuo, pero tienen variables proposicionales (es decir, que se pueden interpretar como proposiciones con un valor de verdad definido), de ahí el nombre proposicional. Los sistemas de lógica proposicional incluyen además conectivas lógicas, por lo que dentro de este tipo de lógica se puede analizar la inferencia lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.^[2]​

Como las lógicas proposicionales no tienen cuantificadores o variables de individuo, cualquier secuencia de signos que constituya una fórmula bien formada admite una valoración en la proposición es verdadera o falsa dependiendo del valor de verdad asignado a las proposiciones que la compongan. Esto implica que cualquier fórmula bien formada define una función proposicional. Por tanto, cualquier sistema lógico basado en la lógica proposicional es decidible y en un número finito de pasos se puede determinar la verdad o falsedad semántica de una proposición. Esto hace que la lógica proposicional sea completa y con una semántica muy sencilla.

Introducción

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 (1) y (2) sean verdaderas y la conclusión (3) falsa.

Sin embargo, a pesar de que el argumento sea válido, esto no quiere decir que la conclusión sea verdadera. En otras palabras, 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 del argumento no depende del significado de las expresiones «mañana es miércoles» ni «mañana es jueves», sino de la estructura misma del argumento. Estas premisas podrían cambiarse por otras y el argumento permanecería válido. Por ejemplo:

1. Hoy está soleado o está nublado.
2. Hoy no está nublado.
3. Por lo tanto, hoy está soleado.

La validez de los dos argumentos anteriores depende del significado de las expresiones «o» y «no». Si alguna de estas expresiones se cambia por otra, entonces los argumentos podrían dejar de ser válidos. Por ejemplo, considérese el siguiente argumento inválido:

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

Estas expresiones como «o» y «no», de las que depende la validez de los argumentos, se llaman conectivas lógicas. En cuanto a expresiones como «está nublado» y «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 (de «proposición») luego q, r, s, etc. Es así que los dos primeros argumentos de esta sección se podrían reescribir así:

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

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

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

Conectivas lógicas

Artículo principal: Conectiva lógica

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.

Conectiva	Expresión en el lenguaje natural	Ejemplo	Símbolo en este artículo	Símbolos alternativos
Negación	no	No está lloviendo.	${\displaystyle \neg \,}$	${\displaystyle \sim \,}$
Conjunción	y	Está lloviendo y está nublado.	${\displaystyle \land }$	&
Disyunción	o	Está lloviendo o está soleado.	${\displaystyle \lor }$	|
Condicional material	si... entonces	Si está soleado, entonces es de día.	${\displaystyle \to \,}$	${\displaystyle \supset }$
Bicondicional	si y solo si	Está nublado si y solo si hay nubes visibles.	${\displaystyle \leftrightarrow }$	${\displaystyle \equiv \,}$
Disyunción opuesta	ni... ni	Ni está soleado ni está nublado.	${\displaystyle \downarrow \,}$
Disyunción exclusiva	o bien... o bien	O bien está soleado, o bien está nublado.	${\displaystyle \nleftrightarrow }$	${\displaystyle \oplus ,\not \equiv ,W}$

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.

Negación	Conjunción	Disyunción	Condicional	Bicondicional	Disyunción exclusiva
${\displaystyle {\begin{array}{c||c}\phi &\neg \phi \\\hline F&V\\V&F\\\end{array}}}$	${\displaystyle {\begin{array}{c|c||c}\phi &\psi &\phi \land \psi \\\hline V&V&V\\F&V&F\\V&F&F\\F&F&F\\\end{array}}}$	${\displaystyle {\begin{array}{c|c||c}\phi &\psi &\phi \lor \psi \\\hline V&V&V\\F&V&V\\V&F&V\\F&F&F\\\end{array}}}$	${\displaystyle {\begin{array}{c|c||c}\phi &\psi &\phi \to \psi \\\hline V&V&V\\F&V&V\\V&F&F\\F&F&V\\\end{array}}}$	${\displaystyle {\begin{array}{c|c||c}\phi &\psi &\phi \leftrightarrow \psi \\\hline V&V&V\\F&V&F\\V&F&F\\F&F&V\\\end{array}}}$	${\displaystyle {\begin{array}{c|c||c}\phi &\psi &\phi \nleftrightarrow \psi \\\hline V&V&F\\F&V&V\\V&F&V\\F&F&F\\\end{array}}}$

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:

• Ley de doble negación
• Leyes de idempotencia
• Leyes Asociatividad (Buscar 'Lógica Preposicional' dentro del artículo)
• 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.

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 se puede probar 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: ${\displaystyle \neg ,\land ,\lor ,\to ,\leftrightarrow }$
• 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 recursivamente 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 ${\displaystyle \phi \,}$ es una fórmula bien formada de L, entonces ${\displaystyle \neg \phi \,}$ también lo es.
3. Si ${\displaystyle \phi \,}$ y ${\displaystyle \psi \,}$ son fórmulas bien formadas de L, entonces ${\displaystyle (\phi \land \psi )}$, ${\displaystyle (\phi \lor \psi )}$, ${\displaystyle (\phi \to \psi )\,}$ y ${\displaystyle (\phi \leftrightarrow \psi )}$ también lo son.
4. Solo 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.

Según estas reglas, las siguientes cadenas de caracteres son ejemplos de fórmulas bien formadas:

${\displaystyle p\,}$

${\displaystyle \neg \neg \neg q\,}$

${\displaystyle (p\land q)}$

${\displaystyle \neg (p\land q)}$

${\displaystyle (p\leftrightarrow \neg p)}$

${\displaystyle ((p\to q)\land p)}$

${\displaystyle (\neg (p\land (q\lor r))\lor s)}$

Y los siguientes son ejemplos de fórmulas mal formadas^{[cita requerida]}:

Fórmula	Error	Corrección
${\displaystyle (p)\,}$	Sobran paréntesis	${\displaystyle p\,}$
${\displaystyle \neg (p)\,}$	Sobran paréntesis	${\displaystyle \neg p\,}$
${\displaystyle (\neg p)\,}$	Sobran paréntesis	${\displaystyle \neg p\,}$
${\displaystyle p\to q\,}$	Faltan paréntesis	${\displaystyle (p\to q)\,}$
${\displaystyle (p\land q\to r)}$	Faltan paréntesis	${\displaystyle ((p\land q)\to r)\,}$

Por otra parte, dado que la única función de los paréntesis es desambiguar las fórmulas, en general se acostumbra omitir los paréntesis externos de cada fórmula, ya que estos no cumplen ninguna función. Así por ejemplo, las siguientes fórmulas generalmente se consideran bien formadas:

${\displaystyle p\land q}$

${\displaystyle \neg p\to q\,}$

${\displaystyle (p\land q)\lor \neg q}$

${\displaystyle (p\leftrightarrow q)\leftrightarrow (q\leftrightarrow p)}$

Otra convención acerca del uso de los paréntesis es que las conjunciones y las disyunciones tienen «menor jerarquía» que los condicionales materiales y los bicondicionales. Esto significa que dada una fórmula sin paréntesis, las conjunciones y las disyunciones deben agruparse antes que los condicionales materiales y los bicondicionales. Por ejemplo:

Fórmula	Lectura correcta	Lectura incorrecta
${\displaystyle p\land q\to r\,}$	${\displaystyle (p\land q)\to r\,}$	${\displaystyle p\land (q\to r)\,}$
${\displaystyle \neg p\leftrightarrow q\lor r\,}$	${\displaystyle \neg p\leftrightarrow (q\lor r)\,}$	${\displaystyle (\neg p\leftrightarrow q)\lor r\,}$
${\displaystyle p\land q\leftrightarrow r\lor s\,}$	${\displaystyle (p\land q)\leftrightarrow (r\lor s)\,}$	${\displaystyle (p\land (q\leftrightarrow r))\lor s\,}$

Estas convenciones son análogas a las que existen en el álgebra elemental, donde la multiplicación y la división siempre deben resolverse antes que la suma y la resta. Así por ejemplo, la ecuación 2 + 2 × 2 podría interpretarse como (2 + 2) × 2 o como 2 + (2 × 2). En el primer caso el resultado sería 8, y en el segundo caso sería 6. Pero como la multiplicación siempre debe resolverse antes que la suma, el resultado correcto en este caso es 6, no 8.

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:

• ${\displaystyle (\phi \to (\psi \to \phi ))\,}$
• ${\displaystyle ((\phi \to (\psi \to \chi ))\to ((\phi \to \psi )\to (\phi \to \chi )))\,}$
• ${\displaystyle ((\neg \phi \to \neg \psi )\to (\psi \to \phi ))\,}$

Reglas de inferencia

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:

${\displaystyle (\phi \to \psi ),\phi \vdash \psi }$

Recordando que ${\displaystyle \phi \,}$ y ${\displaystyle \psi \,}$ no son fórmulas, sino metavariables que pueden ser reemplazadas por cualquier fórmula bien formada.

Deducción natural

Artículo principal: Deducción natural

Sea ${\displaystyle {\mathcal {L}}_{2}={\mathcal {L}}(\mathrm {A} ,\Omega ,\mathrm {Z} ,\mathrm {I} )}$, donde ${\displaystyle \mathrm {A} }$, ${\displaystyle \Omega }$, ${\displaystyle \mathrm {Z} }$, ${\displaystyle \mathrm {I} }$, se define como:

• El conjunto Alfa ${\displaystyle \mathrm {A} }$ es un conjunto finito de símbolos que es lo suficientemente grande como para satisfacer las necesidades de una discusión dada, por ejemplo:

  ${\displaystyle \mathrm {A} =\{p,q,r,s,t,u\}.}$

• El conjunto Omega ${\displaystyle \Omega =\Omega _{1}\cup \Omega _{2}}$ como partición de :

  ${\displaystyle \Omega _{1}=\{\lnot \},}$

  ${\displaystyle \Omega _{2}=\{\land ,\lor ,\to ,\leftrightarrow \}.}$

En el siguiente ejemplo es de un cálculo proposicional, las reglas presentadas de transformación tienen que ser interpretadas como reglas de inferencia de un sistema de deducción natural. El sistema particular aquí presentado no tiene puntos iniciales, lo que significa que su interpretación para las aplicaciones lógicas deriva de un teorema de conjuntos de axiomas vacíos.

*El conjunto de puntos iniciales está vacío, este es ${\displaystyle \mathrm {I} =\varnothing }$.

*El conjunto de reglas de transformación ${\displaystyle \mathrm {Z} }$ se describe como :

Nuestro cálculo proposicional tiene diez reglas de inferencia. Estas reglas nos permiten derivar otras fórmulas verdaderas dado un conjunto de fórmulas que se supone que son verdaderas. Las primeros nueve simplemente declaran que podemos inferir ciertas fórmulas bien formadas de otras fórmulas bien formadas; y la última regla utiliza el razonamiento hipotético en el sentido de que la premisa de la regla asuma temporalmente una hipótesis( no probada) para formar parte del conjunto de fórmulas deducidas para ver si podemos inferir alguna otra fórmula. Dado que las primeras nueve reglas no son hipotéticas , usualmente se describirían como reglas no hipotéticas, y la última regla como una regla hipotética.

Al describir las reglas de transformación, podemos introducir un símbolo de metalenguaje ${\displaystyle \vdash }$. Es básicamente una taquigrafía conveniente para decir " inferir que ". El formato es ${\displaystyle \Gamma \vdash \psi }$, en el cual Γ es un conjunto de fórmulas llamadas premisas, y ψ es una fórmula para hallar la conclusión. La regla de tranformacíon ${\displaystyle \Gamma \vdash \psi }$ significa que si toda proposición enΓ es un teorema ( o tiene el mismo valor de verdad que los axiomas ), entonces ψ es también un teorema. Tenga en cuenta que teniendo en cuenta la siguiente regla la introducción de conjunción Γ tiene más de una fórmula, siempre podemos reducirla con seguridad en una fórmula usando una conjunción. Así que para abreviar, a partir de ese momento podemos representar Γ como una fórmula en lugar de un conjunto. Otra omisión por conveniencia es cuando Γ es un conjunto vacío, en cuyo caso Γ puede no aparecer.

Un sistema de lógica proposicional también puede construirse a partir de un conjunto vacío de axiomas. Para ello se especifican una serie de reglas de inferencia que intentan capturar el modo en que naturalmente razonamos acerca de las conectivas lógicas.

Introducción de la negación

De ${\displaystyle (p\to q)}$ y ${\displaystyle (p\to \neg q)}$, se infiere ${\displaystyle \neg p}$.

Esto es, ${\displaystyle \{(p\to q),(p\to \neg q)\}\vdash \neg p}$.

Eliminación de la negación

De ${\displaystyle \neg p}$, se infiere ${\displaystyle (p\to r)}$.

Esto es, ${\displaystyle \{\neg p\}\vdash (p\to r)}$.

Eliminación de la doble negación

De ${\displaystyle \neg \neg p}$, se infiere ${\displaystyle p}$.

Esto es, ${\displaystyle \neg \neg p\vdash p}$.

Introducción de la conjunción

De ${\displaystyle p}$ y ${\displaystyle q}$, se infiere ${\displaystyle (p\land q)}$.

Esto es, ${\displaystyle \{p,q\}\vdash (p\land q)}$.

Eliminación de la conjunción

De ${\displaystyle (p\land q)}$, se infiere ${\displaystyle p}$.

De ${\displaystyle (p\land q)}$, se infiere ${\displaystyle q}$.

Esto es, ${\displaystyle (p\land q)\vdash p}$ y ${\displaystyle (p\land q)\vdash q}$.

Introducción de la disyunción

De ${\displaystyle p}$, se infiere ${\displaystyle (p\lor q)}$.

Esto es, ${\displaystyle p\vdash (p\lor q)}$ y ${\displaystyle q\vdash (p\lor q)}$.

Eliminación de la disyunción

De ${\displaystyle (p\lor q)}$ y ${\displaystyle (p\to r)}$ y ${\displaystyle (q\to r)}$, se infiere ${\displaystyle r}$.

Esto es, ${\displaystyle \{p\lor q,p\to r,q\to r\}\vdash r}$.

Introducción del bicondicional

De ${\displaystyle (p\to q)}$ y ${\displaystyle (q\to p)}$, se infiere ${\displaystyle (p\leftrightarrow q)}$.

Esto es, ${\displaystyle \{p\to q,q\to p\}\vdash (p\leftrightarrow q)}$.

Eliminación del bicondicional

De ${\displaystyle (p\leftrightarrow q)}$, se infiere ${\displaystyle (p\to q)}$.

De ${\displaystyle (p\leftrightarrow q)}$, se infiere ${\displaystyle (q\to p)}$.

Esto es, ${\displaystyle (p\leftrightarrow q)\vdash (p\to q)}$ y ${\displaystyle (p\leftrightarrow q)\vdash (q\to p)}$.

Modus ponens (eliminación del condicional)

De ${\displaystyle p}$ y ${\displaystyle (p\to q)}$, se infiere ${\displaystyle q}$.

Esto es, ${\displaystyle \{p,p\to q\}\vdash q}$.

Prueba condicional (introducción del condicional)

De [aceptando que ${\displaystyle p}$ permite una prueba de ${\displaystyle q}$], se infiere ${\displaystyle (p\to q)}$.

Esto es, ${\displaystyle (p\vdash q)\vdash (p\to q)}$.

Formas de argumentos básicas y derivadas

Nombre	Consecuente	Descripción
Modus ponens	${\displaystyle ((p\to q)\land p)\vdash q}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y ${\displaystyle p}$; por lo tanto ${\displaystyle q}$
Modus tollens	${\displaystyle ((p\to q)\land \neg q)\vdash \neg p}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y no ${\displaystyle q}$; por lo tanto no ${\displaystyle p}$
Silogismo hipotético	${\displaystyle ((p\to q)\land (q\to r))\vdash (p\to r)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y si ${\displaystyle q}$ entonces ${\displaystyle r}$; por lo tanto, si ${\displaystyle p}$ entonces ${\displaystyle r}$
Silogismo disyuntivo	${\displaystyle ((p\lor q)\land \neg p)\vdash q}$	Si ${\displaystyle p}$ o ${\displaystyle q}$; y no ${\displaystyle p}$; por lo tanto, ${\displaystyle q}$
Dilema constructivo	${\displaystyle ((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y si ${\displaystyle r}$ entonces ${\displaystyle s}$; pero ${\displaystyle p}$ o ${\displaystyle r}$; por lo tanto ${\displaystyle q}$ o ${\displaystyle s}$
Dilema destructivo	${\displaystyle ((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y si ${\displaystyle r}$ entonces ${\displaystyle s}$; pero no ${\displaystyle q}$ o no ${\displaystyle s}$; por lo tanto no ${\displaystyle p}$ o no ${\displaystyle r}$
Dilema bidireccional	${\displaystyle ((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y si ${\displaystyle r}$ entonces ${\displaystyle s}$; pero ${\displaystyle p}$ o no ${\displaystyle s}$; por lo tanto ${\displaystyle q}$ o no ${\displaystyle r}$
Simplificación	${\displaystyle (p\land q)\vdash p}$	${\displaystyle p}$ y ${\displaystyle q}$ son verdaderos; por lo tanto ${\displaystyle p}$ es verdadero
Conjunción	${\displaystyle p,q\vdash (p\land q)}$	${\displaystyle p}$ y ${\displaystyle q}$ son verdaderos separadamente; entonces son verdaderos conjuntamente.
Adición	${\displaystyle p\vdash (p\lor q)}$	${\displaystyle p}$ es verdadero; por lo tanto la disyunción (${\displaystyle p}$ o ${\displaystyle q}$) es verdadera
Composición	${\displaystyle ((p\to q)\land (p\to r))\vdash (p\to (q\land r))}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$; y si ${\displaystyle p}$ entonces ${\displaystyle r}$; por lo tanto si ${\displaystyle p}$ es verdadero entonces ${\displaystyle q}$ y ${\displaystyle r}$ son verdaderos
Ley de De Morgan (1)	${\displaystyle \neg (p\land q)\vdash (\neg p\lor \neg q)}$	La negación de (${\displaystyle p}$ y ${\displaystyle q}$) es equivalente a (no ${\displaystyle p}$ o no ${\displaystyle q}$)
Ley de De Morgan (2)	${\displaystyle \neg (p\lor q)\vdash (\neg p\land \neg q)}$	La negación de (${\displaystyle p}$ o ${\displaystyle q}$) es equivalente a (no ${\displaystyle p}$ y no ${\displaystyle q}$)
Conmutación (1)	${\displaystyle (p\lor q)\vdash (q\lor p)}$	(${\displaystyle p}$ o ${\displaystyle q}$) es equivalente a (${\displaystyle q}$ o ${\displaystyle p}$)
Conmutación (2)	${\displaystyle (p\land q)\vdash (q\land p)}$	(${\displaystyle p}$ y ${\displaystyle q}$) es equivalente a (${\displaystyle q}$ y ${\displaystyle p}$)
Conmutación (3)	${\displaystyle (p\leftrightarrow q)\vdash (q\leftrightarrow p)}$	(${\displaystyle p}$ es equivalente a ${\displaystyle q}$) es equivalente a (${\displaystyle q}$ es equivalente a ${\displaystyle p}$)
Asociación (1)	${\displaystyle (p\lor (q\lor r))\vdash ((p\lor q)\lor r)}$	${\displaystyle p}$ o (${\displaystyle q}$ o ${\displaystyle r}$) es equivalente a (${\displaystyle p}$ o ${\displaystyle q}$) o ${\displaystyle r}$
Asociación (2)	${\displaystyle (p\land (q\land r))\vdash ((p\land q)\land r)}$	${\displaystyle p}$ y (${\displaystyle q}$ y ${\displaystyle r}$) es equivalente a (${\displaystyle p}$ y ${\displaystyle q}$) y ${\displaystyle r}$
Distribución (1)	${\displaystyle (p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))}$	${\displaystyle p}$ y (${\displaystyle q}$ o ${\displaystyle r}$) es equivalente a (${\displaystyle p}$ y ${\displaystyle q}$) o (${\displaystyle p}$ y ${\displaystyle r}$)
Distribución (2)	${\displaystyle (p\lor (q\land r))\vdash ((p\lor q)\land (p\lor r))}$	${\displaystyle p}$ o (${\displaystyle q}$ y ${\displaystyle r}$) es equivalente a (${\displaystyle p}$ o ${\displaystyle q}$) y (${\displaystyle p}$ o ${\displaystyle r}$)
Doble negación	${\displaystyle p\vdash \neg \neg p}$	${\displaystyle p}$ es equivalente a la negación de no ${\displaystyle p}$
Transposición	${\displaystyle (p\to q)\vdash (\neg q\to \neg p)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$ es equivalente a si no ${\displaystyle q}$ entonces no ${\displaystyle p}$
Implicación material	${\displaystyle (p\to q)\vdash (\neg p\lor q)}$	Si ${\displaystyle p}$ entonces ${\displaystyle q}$ es equivalente a no ${\displaystyle p}$ o ${\displaystyle q}$
Equivalencia material (1)	${\displaystyle (p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))}$	(${\displaystyle p}$ si y solo si ${\displaystyle q}$) es equivalente a (si ${\displaystyle p}$ es verdadero entonces ${\displaystyle q}$ es verdadero) y (si ${\displaystyle q}$ es verdadero entonces ${\displaystyle p}$ es verdadero)
Equivalencia material (2)	${\displaystyle (p\leftrightarrow q)\vdash ((p\land q)\lor (\neg p\land \neg q))}$	(${\displaystyle p}$ si ${\displaystyle q}$) es equivalente a cualquiera de los dos (${\displaystyle p}$ y ${\displaystyle q}$ son verdaderos) o (tanto ${\displaystyle p}$ como ${\displaystyle q}$ son falsos)
Equivalencia material (3)	${\displaystyle (p\leftrightarrow q)\vdash ((p\lor \neg q)\land (\neg p\lor q))}$	(${\displaystyle p}$ si ${\displaystyle q}$) es equivalente a: tanto (${\displaystyle p}$ como no ${\displaystyle q}$ son verdaderos) y (no ${\displaystyle p}$ o ${\displaystyle q}$ es verdadero)
Exportación^[3]​	${\displaystyle ((p\land q)\to r)\vdash (p\to (q\to r))}$	desde (si ${\displaystyle p}$ y ${\displaystyle q}$ son verdaderos, entonces ${\displaystyle r}$ es verdadero) se puede probar que (si ${\displaystyle q}$ es verdadero entonces ${\displaystyle r}$ es verdadero, si ${\displaystyle p}$ es verdadero)
Importación	${\displaystyle (p\to (q\to r))\vdash ((p\land q)\to r)}$	${\displaystyle p}$ implica que ${\displaystyle q}$ implica ${\displaystyle r}$ es equivalente a que ${\displaystyle p}$ y ${\displaystyle q}$ implican ${\displaystyle r}$
Tautología (1)	${\displaystyle p\vdash (p\lor p)}$	${\displaystyle p}$ es verdadero es equivalente a ${\displaystyle p}$ es verdadero o ${\displaystyle p}$ es verdadero
Tautología (2)	${\displaystyle p\vdash (p\land p)}$	${\displaystyle p}$ es verdadero es equivalente a ${\displaystyle p}$ es verdadero y ${\displaystyle p}$ es verdadero
Principio del tercero excluido	${\displaystyle \vdash (p\lor \neg p)}$	${\displaystyle p}$ o no ${\displaystyle p}$ es verdadero
Principio de no contradicción	${\displaystyle \vdash \neg (p\land \neg p)}$	${\displaystyle p}$ y no ${\displaystyle p}$ es falso

Ejemplo de una demostración

Demostrar: ${\displaystyle A\to A\,}$

Una posible prueba de esto (que, aunque válida, pasa a contener más pasos de los necesarios) se puede disponer de la siguiente manera:

Paso	Fórmula	Razón
1	${\displaystyle A}$	Premisa.
2	${\displaystyle A\lor A}$	Desde (1) por introducción de la disyunción.
3	${\displaystyle (A\lor A)\land A}$	Desde (1) y (2) por introducción de la conjunción.
4	${\displaystyle A}$	Desde (3) por eliminación de la conjunción.
5	${\displaystyle A\vdash A}$	Resumen de (1) hasta (4).
6	${\displaystyle \vdash A\to A}$	Desde (5) por introducción del condicional. QED

Interpretar ${\displaystyle A\vdash A}$ como: "Asumiendo que ${\displaystyle A}$, inferire ${\displaystyle A}$". Leer ${\displaystyle \vdash }$ ${\displaystyle A\to A}$ como "Suponiendo nada, inferir que ${\displaystyle A}$ implica ${\displaystyle A}$", o "Es una tautología que ${\displaystyle A}$ implica ${\displaystyle A}$", o "Siempre es cierto que ${\displaystyle A}$ implica ${\displaystyle A}$".

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:

${\displaystyle {\begin{array}{rcl}{\rm {\langle Bicondicional\rangle }}&::=&{\rm {\langle Condicional\rangle \leftrightarrow \langle Bicondicional\rangle \mid \langle Condicional\rangle }}\\{\rm {\langle Condicional\rangle }}&::=&{\rm {\langle Conjunci{\acute {o}}n\rangle \rightarrow \langle Condicional\rangle \mid \langle Conjunci{\acute {o}}n\rangle }}\\{\rm {\langle Conjunci{\acute {o}}n\rangle }}&::=&{\rm {\langle Disyunci{\acute {o}}n\rangle \vee \langle Conjunci{\acute {o}}n\rangle \mid \langle Disyunci{\acute {o}}n\rangle }}\\{\rm {\langle Disyunci{\acute {o}}n\rangle }}&::=&{\rm {\langle Literal\rangle \wedge \langle Disyunci{\acute {o}}n\rangle \mid \langle Literal\rangle }}\\{\rm {\langle Literal\rangle }}&::=&{\rm {\langle {\acute {A}}tomo\rangle \mid \neg \langle {\acute {A}}tomo\rangle }}\\{\rm {\langle {\acute {A}}tomo\rangle }}&::=&{\rm {\top \mid \bot \mid \langle Letra\rangle \mid \langle Agrupaci{\acute {o}}n\rangle }}\\{\rm {\langle Agrupaci{\acute {o}}n\rangle }}&::=&{\rm {(\langle Bicondicional\rangle )\mid [\langle Bicondicional\rangle ]\mid \{\langle Bicondicional\rangle \}}}\end{array}}}$

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

1. Negación (${\displaystyle \neg \,}$)
2. Conjunción (${\displaystyle \land \,}$)
3. Disyunción (${\displaystyle \lor \,}$)
4. Condicional material (${\displaystyle \to \,}$)
5. Bicondicional (${\displaystyle \leftrightarrow }$)

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

Partiendo de esto es posible definir una cantidad de nociones semánticas. Si A y B son fórmulas cualquiera de un lenguaje L, ${\displaystyle \Gamma }$ es un conjunto de fórmulas de L, y M es una interpretación de L, entonces:

• A es verdadera bajo la interpretación M si y solo si M asigna el valor de verdad V a A.
• A es falsa bajo la interpretación M si y solo si M asigna el valor de verdad F a A.
• A es una tautología (o una verdad lógica) si y solo si para toda interpretación M, M asigna el valor de verdad V a A.
• A es una contradicción si y solo si para toda interpretación M, M asigna el valor de verdad F a A.
• A es satisfacible (o consistente) si y solo si existe al menos una interpretación M que asigne el valor de verdad V a A.
• ${\displaystyle \Gamma }$ es consistente si y solo si existe al menos una interpretación que haga verdaderas a todas las fórmulas en ${\displaystyle \Gamma }$.
• A es una consecuencia semántica de un conjunto de fórmulas ${\displaystyle \Gamma }$ si y solo si no existe interpretación en la que todas las fórmulas que pertenecen a ${\displaystyle \Gamma }$ sean verdaderas y A sea falsa. Cuando A es una consecuencia semántica de ${\displaystyle \Gamma }$ en un lenguaje L, se escribe: ${\displaystyle \Gamma \models _{L}A}$.
• A es una verdad lógica si y solo si A es una consecuencia semántica del conjunto vacío. Cuando A es una verdad lógica de un lenguaje L, se escribe: ${\displaystyle \models _{L}A}$.

Tablas de verdad

Artículo principal: 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 ${\displaystyle \neg (p\lor q)\to (p\to r)}$ es:

${\displaystyle {\begin{array}{c|c|c||c|c|c|c}p&q&r&(p\lor q)&\neg (p\lor q)&(p\to r)&\neg (p\lor q)\to (p\to r)\\\hline V&V&V&V&F&V&V\\V&V&F&V&F&F&V\\V&F&V&V&F&V&V\\V&F&F&V&F&F&V\\F&V&V&V&F&V&V\\F&V&F&V&F&V&V\\F&F&V&F&V&V&V\\F&F&F&F&V&V&V\\\end{array}}}$

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.

Formas normales

A menudo es necesario transformar una fórmula en otra, sobre todo transformar una fórmula a su forma normal. Esto se consigue transformando la fórmula en otra equivalente y repitiendo el proceso hasta conseguir una fórmula que solo use los conectivos básicos (${\displaystyle \land ,\lor ,\neg }$). Para lograr esto se utilizan las equivalencias lógicas:

${\displaystyle (p\to q)\leftrightarrow (\neg p\lor q)}$

${\displaystyle (p\leftrightarrow q)\leftrightarrow [(\neg p\lor q)\land (\neg q\lor p)]}$

Por ejemplo, considérese la siguiente fórmula:

${\displaystyle (p\to q)\land (\neg q\leftrightarrow p)}$

La misma puede desarrollarse así:

${\displaystyle (\neg p\lor q)\land (q\lor p)\land (\neg p\lor \neg q)}$

Se dice que una fórmula está en forma normal disyuntiva (FND) si y solo si tiene la siguiente forma:

${\displaystyle A_{1}\lor A_{2}\lor ...\lor A_{n}}$

donde cada A es una conjunción de fórmulas. Por ejemplo, la siguiente fórmula está en forma normal disyuntiva:

${\displaystyle p\lor (q\land s)\lor (\neg q\land p)}$

Se dice que una fórmula está en forma normal conjuntiva (FNC) si y solo si tiene la siguiente forma:

${\displaystyle A_{1}\land A_{2}\land ...\land A_{n}}$

donde cada A es una disyunción de fórmulas. Por ejemplo, la siguiente fórmula está en forma normal conjuntiva:

${\displaystyle p\land (q\lor s)\land (\neg q\lor p)}$

Por las leyes de De Morgan, es posible pasar de una forma normal disyuntiva a una forma normal conjuntiva y viceversa:

${\displaystyle \neg (A\lor B)\leftrightarrow (\neg A\land \neg B)}$

${\displaystyle \neg (A\land B)\leftrightarrow (\neg A\lor \neg B)}$

Las FNC y FND son mutuamente duales. La demostración hace uso de las leyes de De Morgan y de la propiedad distributiva de la conjunción y la disyunción. Se debe cumplir que:

${\displaystyle \neg [(A_{1}\land B_{1})\lor (A_{2}\land B_{2})\lor ...\lor (A_{n}\land B_{n})]\leftrightarrow [(\neg A_{1}\lor \neg B_{1})\land (\neg A_{2}\lor \neg B_{2})\land ...\land (\neg A_{n}\lor \neg B_{n})]}$

Y viceversa:

${\displaystyle \neg [(A_{1}\lor B_{1})\land (A_{2}\lor B_{2})\land ...\land (A_{n}\lor B_{n})]\leftrightarrow [(\neg A_{1}\land \neg B_{1})\lor (\neg A_{2}\land \neg B_{2})\lor ...\lor (\neg A_{n}\land \neg B_{n})]}$

Historia

Artículo principal: Historia de la lógica

La lógica es conocida como una de las ciencias más antiguas, tanto es así que se le atribuye a Aristóteles la paternidad de esta disciplina. Partiendo de que corresponde a Aristóteles haber sido el primero en tratar con todo detalle la lógica, se le considera su fundador. En un principio se llamó Analítica, en virtud del título de las obras en que trató los problemas lógicos. Más tarde los escritos de Aristóteles relativos a estos eventos fueron recopilados por sus discípulos con el título de Órganon, por considerar que la lógica era un instrumento para el conocimiento de la verdad.

Aristóteles se planteó cómo es posible probar y demostrar que un conocimiento es verdadero, es decir, que tiene una validez universal. Aristóteles encuentra el fundamento de la demostración en la deducción, procedimiento que consiste en derivar un hecho particular de algo universal. La forma en que se afecta esa derivación es el silogismo, por cuya razón la silogística llega a ser el centro de la lógica aristotélica.

Aunque la lógica proposicional (que es intercambiable con el cálculo proposicional) había sido insinuada por los filósofos anteriores, fue desarrollada como un sistema formal por el filósofo estoico Crisipo en el siglo III a. C. y ampliada por sus sucesores de la misma escuela. La lógica proposicional se centró en proposiciones. Este avance fue diferente de la lógica silogística tradicional que se centró en los términos. Sin embargo, más tarde en la antigüedad, la lógica proposicional desarrollada por los estoicos no se comprendía. En consecuencia de ello, el sistema fue reinventado esencialmente por Pedro Abelardo en el siglo XII.

La lógica proposicional fue finalmente refinada usando la lógica simbólica, se acreditó ser el fundador de la lógica simbólica el matemático Gottfried Leibniz siglo XVII/XVIII, por su trabajo ratiocinator del cálculo. Aunque su trabajo era unos de los primeros, era desconocido para la comunidad lógica más grande. En consecuencia, muchos de los avances logrados por Leibniz fueron recreados por lógicos como George Boole y Augustus De Morgan completamente independientes a Leibniz.

Así como la lógica proposicional puede considerarse un avance de la lógica silogísta anterior, la lógica de predicados de Gottlob Frege era un avance de la lógica proposicional anterior. Un autor describe esta lógica como la combinación de los rasgos distintivos de la lógica silogística y la lógica proposicional. Por lo tanto, la lógica predicativa marcó el comienzo de una nueva era en la historia de la lógica; sin embargo, los avances en la lógica proposicional se hicieron aún después de Frege, incluyendo Deducción Natural, Árboles de la Verdad y Tablas de Verdad. La deducción natural fue inventada por Gerhard Gentzen y Jan Lukasiewicz. Los árboles de la verdad fueron inventados por Evert Willem Beth. La invención de las tablas de la verdad, sin embargo, es de atribución controvertida.

Dentro de las obras de Frege y Bertrand Russell, hay ideas que influyen en la invención de las tablas de la verdad. La estructura tabular real se acredita generalmente a Ludwig Wittgenstein o a Emil Post ( o ambos independientemente). Adeám de Frege y Russell, otros acreditados con ideas anteriores a las tablas de la verdad incluyen a Philo, Boole, Charles Sanders Peirce. Otros acreditados de la estructura tabular incluyen Lukasiewicz, Alfred North Whitehead, Guillermo Stanley Jevons, John Venn, y Clarence Irving Lewis. En última instancia, algunos han llegado a la conclusión, como John Shosky, de que " está lejos de estar claro que a cualquier persona se le debe dar el título de 'inventor' de las tablas de la verdad".

Véase también

• Álgebra de Boole
• Cálculo lógico
• Cálculo proposicional de Frege
• Gráficos existenciales
• Lógica matemática
• Lógica de primer orden
• Lógica modal
• Tabla de verdad
• Teoría de grafos
• Silogismo
• Valor de verdad
• Razonamiento diagramático

Referencias

1. Simon Blackburn (ed.). «propositional calculus». Oxford Dictionary of Philosophy (en inglés). Oxford University Press. Consultado el 13 de agosto de 2009. 
2. Klement, Kevin C. «Propositional Logic». Internet Encyclopedia of Philosophy (en inglés). Consultado el 6 de febrero de 2012. 
3. Toida, Shunichi (2 de agosto de 2009). «Proof of Implications». CS381 Discrete Structures/Discrete Mathematics Web Course Material (en inglés). Department Of Computer Science, Old Dominion University. Consultado el 10 de marzo de 2010. 

Bibliografía

• Enderton, H. B. (1972). A Mathematical Introduction to Logic. Academic Press. 
• Hamilton, A. G. (1981). Lógica para matemáticos. Paraningo. 
• Mendelson, E. (1997). Introduction to Mathematical Logic (4ª edición). Chapman and May. 
• Pla, J. (1991). Lliçons de lógica matemática. P.P.U. 
• Badesa, C.; Jané, I.; Jansana, R. (1998). Elementos de lógica formal. Ariel. 
• Barnes, D. W.; Mack, J. M. (1978). Una introducción algebraica a la lógica matemática. Eunibar. 
• Bridge, J. (1977). Beginning Model Theory. Oxford University Pres. 
• Ershov, Y.; Paliutin, E. (1990). Lógica matemática. Mir. 
• Hofstadter, D. (1987). Gödel, Escher, Bach: un Eterno y Grácil Bucle. Tusquets Editores. 
• Jané, I. (1989). Álgebras de Boole y lógica. Publicaciones U.B. 
• Monk, J. D. (1976). Mathematical Logic. Springer-Verlag. 
• Nidditch, P. H. (1978). El desarrollo de la lógica matemática. Cátedra. 
• Van Dalen, D. (1983). Logic and Structure (2ª edición). Universitext, Springer-Verlag. 

Enlaces externos

• Wikiversidad alberga proyectos de aprendizaje sobre Lógica proposicional.
• Introducción a la lógica proposicional