Cálculo proposicional

Ajustar Compartir Imprimir Citar

Rama de la lógica formal

El cálculo proposicional es una rama de la lógica. También se denomina lógica proposicional, lógica de enunciados, cálculo de oraciones, lógica de oraciones o, a veces, cero -orden lógica. Se ocupa de proposiciones (que pueden ser verdaderas o falsas) y relaciones entre proposiciones, incluyendo la construcción de argumentos basados en ellas. Las proposiciones compuestas se forman conectando proposiciones mediante conectivos lógicos. Las proposiciones que no contienen conectores lógicos se llaman proposiciones atómicas.

A diferencia de la lógica de primer orden, la lógica proposicional no trata con objetos no lógicos, predicados sobre ellos o cuantificadores. Sin embargo, toda la maquinaria de la lógica proposicional está incluida en la lógica de primer orden y en la lógica de orden superior. En este sentido, la lógica proposicional es el fundamento de la lógica de primer orden y de la lógica de orden superior.

Explicación

Los conectores lógicos se encuentran en los lenguajes naturales. En inglés, por ejemplo, algunos ejemplos son "y" (conjunción), "o" (disyunción), "no" (negación) y "si" (pero solo cuando se usa para denotar material condicional).

El siguiente es un ejemplo de una inferencia muy simple dentro del alcance de la lógica proposicional:

Premise 1: Si está lloviendo entonces está nublado.

Premise 2: Está lloviendo.

Conclusión: Está nublado.

Tanto las premisas como la conclusión son proposiciones. Las premisas se dan por supuestas y, con la aplicación del modus ponens (una regla de inferencia), se sigue la conclusión.

Como la lógica proposicional no se ocupa de la estructura de las proposiciones más allá del punto en el que ya no pueden descomponerse mediante conectivos lógicos, esta inferencia se puede reafirmar reemplazando esas declaraciones atómicas con declaraciones letras, que se interpretan como variables que representan declaraciones:

Premise 1:

Pto Q

Premise 2:

P

Conclusión:

Q

Lo mismo puede enunciarse sucintamente de la siguiente manera:

{displaystyle {frac {Pto Q,P}{Q}}}

Cuando $P$ se interpreta como "Está lloviendo" y $Q$ como "está nublado" Se puede ver que las expresiones simbólicas anteriores se corresponden exactamente con la expresión original en lenguaje natural. No sólo eso, sino que también se corresponderán con cualquier otra inferencia de esta forma, que será válida sobre la misma base que esta inferencia.

La lógica proposicional puede estudiarse a través de un sistema formal en el que las fórmulas de un lenguaje formal pueden interpretarse para representar proposiciones. Un sistema de axiomas y reglas de inferencia permite derivar ciertas fórmulas. Estas fórmulas derivadas se denominan teoremas y pueden interpretarse como proposiciones verdaderas. Una secuencia construida de tales fórmulas se conoce como derivación o prueba y la última fórmula de la secuencia es el teorema. La derivación puede interpretarse como prueba de la proposición representada por el teorema.

Cuando un sistema formal se utiliza para representar la lógica formal, sólo las cartas de declaración (normalmente mayúsculas mayúsculas tales como $P$ , $Q$ y $R$ ) están representados directamente. Las proposiciones de lenguaje natural que surgen cuando se interpretan están fuera del ámbito del sistema, y la relación entre el sistema formal y su interpretación está igualmente fuera del propio sistema formal.

En la lógica proposicional funcional de verdad clásica, las fórmulas se interpretan como si tuvieran exactamente uno de dos posibles valores de verdad, el valor de verdad de verdadero o el valor de verdad de falso. Se mantiene el principio de bivalencia y la ley del tercero excluido. La lógica proposicional funcional veritativa definida como tal y los sistemas isomorfos a ella se consideran lógica de orden cero. Sin embargo, también son posibles lógicas proposicionales alternativas. Para obtener más información, consulte Otros cálculos lógicos a continuación.

Historia

Aunque la lógica proposicional (que es intercambiable con el cálculo proposicional) había sido insinuada por filósofos anteriores, Crisipo la desarrolló en una lógica formal (lógica estoica) en el siglo III a. C. y la expandió su sucesor, los estoicos. La lógica se centró en las proposiciones. Este avance fue diferente de la lógica silogística tradicional, que se centró en los términos. Sin embargo, la mayoría de los escritos originales se perdieron y la lógica proposicional desarrollada por los estoicos ya no se entendió más tarde en la antigüedad. En consecuencia, el sistema fue esencialmente reinventado por Pedro Abelardo en el siglo XII.

La lógica proposicional finalmente se perfeccionó utilizando la lógica simbólica. Al matemático de los siglos XVII y XVIII Gottfried Leibniz se le atribuye ser el fundador de la lógica simbólica por su trabajo con el cálculo razonador. Aunque su trabajo fue el primero de su tipo, era desconocido para la comunidad lógica en general. En consecuencia, muchos de los avances logrados por Leibniz fueron recreados por lógicos como George Boole y Augustus De Morgan, completamente independientes de Leibniz.

Así como la lógica proposicional puede considerarse un avance de la lógica silogística anterior, la lógica de predicados de Gottlob Frege también puede considerarse un avance de la lógica proposicional anterior. Un autor describe la lógica de predicados como una combinación de "las características distintivas de la lógica silogística y la lógica proposicional". En consecuencia, la lógica de predicados marcó el comienzo de una nueva era en la historia de la lógica; sin embargo, los avances en la lógica proposicional aún se realizaron después de Frege, incluida la deducción natural, los árboles de verdad y las tablas de verdad. La deducción natural fue inventada por Gerhard Gentzen y Jan Łukasiewicz. Los árboles de la verdad fueron inventados por Evert Willem Beth. Sin embargo, la invención de las tablas de verdad es de atribución incierta.

Dentro de los trabajos de Frege y Bertrand Russell, hay ideas que influyeron en la invención de las tablas de verdad. La estructura tabular real (formateada como una tabla), en sí misma, generalmente se atribuye a Ludwig Wittgenstein o Emil Post (o a ambos, de forma independiente). Además de Frege y Russell, otros acreditados por tener ideas que preceden a las tablas de verdad incluyen a Philo, Boole, Charles Sanders Peirce y Ernst Schröder. Otros acreditados con la estructura tabular incluyen a Jan Łukasiewicz, Alfred North Whitehead, William 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 ser claro que una persona deba recibir el título de 'inventor' de tablas de verdad.".

Terminología

En términos generales, un cálculo es un sistema formal que consta de un conjunto de expresiones sintácticas (fórmulas bien formadas), un subconjunto distinguido de estas expresiones (axiomas), más un conjunto de expresiones formales reglas que definen una relación binaria específica, destinada a ser interpretada como equivalencia lógica, en el espacio de las expresiones.

Cuando se pretende que el sistema formal sea un sistema lógico, las expresiones deben interpretarse como declaraciones, y las reglas, que se conocen como reglas de inferencia, generalmente tienen la intención de preservar la verdad.. En esta configuración, las reglas, que pueden incluir axiomas, se pueden usar para derivar ("inferir") fórmulas que representan enunciados verdaderos, a partir de fórmulas dadas que representan enunciados verdaderos.

El conjunto de axiomas puede ser vacío, un conjunto finito no vacío o un conjunto infinito numerable (ver esquema de axioma). Una gramática formal define recursivamente las expresiones y fórmulas bien formadas del lenguaje. Además, se puede dar una semántica que define la verdad y las valoraciones (o interpretaciones).

El lenguaje de un cálculo proposicional consiste en

un conjunto de símbolos primitivos, varios denominados fórmulas atómicas, propietarios, Propuestas, o variables, y
un conjunto de símbolos de operador, diversos interpretados como operadores lógicos o conexiones lógicas.

Una fórmula bien formada es cualquier fórmula atómica, o cualquier fórmula que pueda construirse a partir de fórmulas atómicas mediante símbolos de operadores de acuerdo con las reglas de la gramática.

Los matemáticos a veces distinguen entre constantes proposicionales, variables proposicionales y esquemas. Las constantes proposicionales representan alguna proposición particular, mientras que las variables proposicionales abarcan el conjunto de todas las proposiciones atómicas. Sin embargo, los esquemas abarcan todas las proposiciones. Es común representar las constantes proposicionales mediante $A$ , $B$ y $C$ , variables proposicionales por $P$ , $Q$ y $R$ , y las letras esquemáticas suelen ser letras griegas, la mayoría de las veces $φ$ , $ψ$ , y $χ$ .

Conceptos básicos

A continuación se describe un cálculo proposicional estándar. Existen muchas formulaciones diferentes que son todas más o menos equivalentes, pero difieren en los detalles de:

su idioma (es decir, la colección particular de símbolos primitivos y símbolos de operadores),
el conjunto de axiomas, o fórmulas distinguidas, y
el conjunto de reglas de inferencia.

Cualquier proposición dada puede representarse con una letra llamada 'constante proposicional', de forma análoga a representar un número mediante una letra en matemáticas (p. ej., $a = 5$ ). Todas las proposiciones requieren exactamente uno de dos valores de verdad: verdadero o falso. Por ejemplo, sea $P$ la proposición de que está lloviendo afuera. Esto será verdadero ( $P$ ) si está lloviendo afuera, y falso en caso contrario ( $\neg P$ ).

A continuación, definimos operadores funcionales de la verdad, comenzando con la negación. $\neg P$ representa la negación de $P$ , que se puede considerar como la negación de $P$ . En el ejemplo anterior, $\neg P$ expresa que no está lloviendo fuera, o por una lectura más estándar: "No es el caso que llueva afuera". Cuando $P$ es verdad, $\neg P$ es falso; y cuando $P$ es falso, $\neg P$ es verdad. Como resultado, $\neg P$ siempre tiene el mismo valor de la verdad $P$ .
La conjunción es un conector funcional de la verdad que forma una proposición de dos proposiciones más simples, por ejemplo, P y Q. La conjunción de P y Q escrito P ∧ Q, y expresa que cada uno es verdad. Leímos P ∧ Q como "P y Q". Para cualquier dos proposiciones, hay cuatro posibles asignaciones de valores de verdad:
1. $P$ es verdad y $Q$ es verdad
2. $P$ es verdad y $Q$ es falso
3. $P$ es falso $Q$ es verdad
4. $P$ es falso $Q$ es falso

La conjunción de

P

Q

es cierto en el caso 1, y es falso de lo contrario. Donde

P

es la proposición de que está lloviendo afuera y

Q

es la proposición de que un frente frío está sobre Kansas,

P \land Q

es cierto cuando está lloviendo afuera y Hay una frente fría sobre Kansas. Si no está lloviendo afuera, entonces

P \land Q

es falso; y si no hay frente al frío sobre Kansas, entonces

P \land Q

también es falso.

La disyunción se asemeja a la conjunción en que forma una proposición de dos proposiciones más simples. Lo escribimos $P Alternativa Q$ , y se lee " $P$ o $Q$ ". Expresa que $P$ o $Q$ es verdad. Así, en los casos enumerados anteriormente, la disyunción de $P$ con $Q$ es cierto en todos los casos - excepto caso 4. Usando el ejemplo anterior, la disyunción expresa que está lloviendo fuera, o hay un frente frío sobre Kansas. (Nota, se supone que este uso de la disyunción se asemeja al uso de la palabra inglesa "o". Sin embargo, es más como el "o" inclusivo inglés, que se puede utilizar para expresar la verdad de al menos una de dos proposiciones. No es como el "o" exclusivo inglés, que expresa la verdad de exactamente una de dos proposiciones. En otras palabras, el exclusivo "o" es falso cuando ambos $P$ y $Q$ son verdaderos (caso 1), y similarmente es falso cuando ambos $P$ y $Q$ son falsos (caso 4). Un ejemplo de la exclusiva o es: Usted puede tener un bagel o una pasta, pero no ambos. A menudo en lenguaje natural, dado el contexto apropiado, la adición "pero no ambas" se omite, pero implícita. En las matemáticas, sin embargo, "o" es siempre inclusivo o; si exclusivo o se quiere decir que será especificado, posiblemente por "xor".)
Material condicional también se une a dos proposiciones más simples, y escribimos $P \to Q$ , que se lee "si $P$ entonces $Q$ ". La proposición a la izquierda de la flecha se llama el antecedente, y la proposición a la derecha se llama el consiguiente. (No existe tal designación para conjunción o disyunción, ya que son operaciones conmutativas.) Expresa que $Q$ es verdad $P$ es verdad. Así $P \to Q$ es cierto en cada caso anterior excepto el caso 2, porque este es el único caso cuando $P$ es verdad pero $Q$ No lo es. Usando el ejemplo, si $P$ entonces $Q$ expresa que si está lloviendo afuera, entonces hay un frente frío sobre Kansas. El condicional material a menudo se confunde con causación física. El condicional material, sin embargo, sólo relaciona dos proposiciones por sus valores de verdad, que no es la relación de causa y efecto. Es contencioso en la literatura si la implicación material representa causación lógica.
Bicondicional se une a dos proposiciones más simples, y escribimos $P Administración Q$ , que se lee " $P$ si $Q$ ". Expresa que $P$ y $Q$ tienen el mismo valor de la verdad, y en los casos 1 y 4. ' $P$ es verdad si y sólo si $Q$ ' es cierto, y es falso de lo contrario.

Es muy útil mirar las tablas de verdad para estos diferentes operadores, así como el método de cuadros analíticos.

Cierre en operación

La lógica proposicional se cierra bajo los conectivos veritativo-funcionales. Es decir, para cualquier proposición $φ$ , $\neg φ$ es también una proposición. Del mismo modo, para cualquier proposición $φ$ y $ψ$ , $φ \land ψ$ es una proposición, y de manera similar para disyunción, condicional y bicondicional. Esto implica que, por ejemplo, $φ \land ψ$ es una proposición, por lo que puede unirse a otra proposición. Para representar esto, necesitamos usar paréntesis para indicar qué proposición se une a cuál. Por ejemplo, $P \land Q \land R$ no es una fórmula bien formada, porque no sabemos si estamos uniendo $P \land Q$ con $R$ o si estamos uniendo $P$ con $Q \land R$ . Por lo tanto, debemos escribir $(P \land Q) \land R$ para representar el primero, o $P \land (Q \land R)$ para representar este último. Al evaluar las condiciones de verdad, vemos que ambas expresiones tienen las mismas condiciones de verdad (serán verdaderas en los mismos casos), y además que cualquier proposición formada por conjunciones arbitrarias tendrá las mismas condiciones de verdad, independientemente de la ubicación de los paréntesis. Esto significa que la conjunción es asociativa, sin embargo, uno no debe asumir que los paréntesis nunca tienen un propósito. Por ejemplo, la oración $P \land (Q \lor R)$ no tiene el mismo condiciones de verdad de $(P \land Q) \lor R$ , por lo que son diferentes oraciones distinguidas solo por los paréntesis. Uno puede verificar esto mediante el método de la tabla de verdad mencionado anteriormente.

Nota: para cualquier número arbitrario de constantes proposicionales, podemos formar un número finito de casos que enumeren sus posibles valores de verdad. Una forma sencilla de generar esto es mediante tablas de verdad, en las que se escribe $P$ , $Q$ ,..., $Z$ , para cualquier lista de $k$ constantes proposicionales, es decir, cualquier lista de constantes proposicionales con $k$ entradas. Debajo de esta lista, uno escribe $2 k$ filas, y debajo $P$ uno completa la primera mitad de las filas con verdadero (o T) y la segunda mitad con falso (o F). Debajo de la $Q$ se rellena un cuarto de las filas con T, luego un cuarto con F, luego un cuarto con T y el último cuarto con F. La siguiente columna alterna entre verdadero y falso para cada octavo de los renglones, luego dieciseisavos, y así sucesivamente, hasta que la última constante proposicional varía entre V y F para cada renglón. Esto dará una lista completa de casos o asignaciones de valores de verdad posibles para esas constantes proposicionales.

Argumento

El cálculo proposicional luego define un argumento como una lista de proposiciones. Un argumento válido es una lista de proposiciones, la última de las cuales se deriva del resto, o está implícita en él. Todos los demás argumentos no son válidos. El argumento válido más simple es el modus ponens, un ejemplo del cual es la siguiente lista de proposiciones:

{begin{array}{rl}1.&Pto Q\2.&P\hline therefore &Qend{array}}

Esta es una lista de tres proposiciones, cada línea es una proposición, y la última sigue del resto. Las dos primeras líneas se llaman locales, y la última línea la conclusión. Decimos que cualquier propuesta $C$ de cualquier conjunto de propuestas $(P_{1},...,P_{n})$ , si $C$ debe ser verdad cuando cada miembro del set $(P_{1},...,P_{n})$ es verdad. En el argumento anterior, para cualquier $P$ y $Q$ , siempre $P \to Q$ y $P$ son verdaderas, necesariamente $Q$ es verdad. Note eso, cuando $P$ es cierto, no podemos considerar casos 3 y 4 (de la tabla de la verdad). Cuando $P \to Q$ es verdad, no podemos considerar caso 2. Esto deja sólo el caso 1, en el que $Q$ es también cierto. Así $Q$ está implícito por los locales.

Esto se generaliza esquemáticamente. Así, donde $φ$ y $ψ$ puede ser cualquier proposición,

{begin{array}{rl}1.&varphi to psi \2.&varphi \hline therefore &psi end{array}}

Otras formas de argumento son convenientes, pero no necesarias. Dado un conjunto completo de axiomas (ver más abajo para uno de esos conjuntos), modus ponens es suficiente para probar todas las demás formas de argumento en lógica proposicional, por lo que pueden considerarse un derivado. Tenga en cuenta que esto no es cierto para la extensión de la lógica proposicional a otras lógicas como la lógica de primer orden. La lógica de primer orden requiere al menos una regla de inferencia adicional para obtener la completitud.

El significado del argumento en la lógica formal es que uno puede obtener nuevas verdades de verdades establecidas. En el primer ejemplo anterior, dadas las dos premisas, la verdad $Q$ no se conoce ni se declara. Después del argumento, $Q$ está deducido. De esta manera, definimos un sistema de deducción para ser un conjunto de todas las proposiciones que puedan deducirse de otro conjunto de proposiciones. Por ejemplo, dada la serie de proposiciones ${displaystyle A={Plor Q,neg Qland R,(Plor Q)to R}}$ , podemos definir un sistema de deducción, $.$ , que es el conjunto de todas las proposiciones que siguen $A$ . Siempre se asume la reiteración, por lo que ${displaystyle Plor Q,neg Qland R,(Plor Q)to Rin Gamma }$ . Además, desde el primer elemento $A$ , último elemento, así como modus ponens, $R$ es una consecuencia, y así $Rin Gamma$ . Porque no hemos incluido suficientes axiomas completos, sin embargo, nada más puede ser deducido. Así, aunque la mayoría de los sistemas de deducción estudiados en la lógica proposicional son capaces de deducir ${displaystyle (Plor Q)leftrightarrow (neg Pto Q)}$ , este es demasiado débil para probar tal propuesta.

Descripción genérica de un cálculo proposicional

A cálculo proposicional es un sistema formal ${mathcal {L}}={mathcal {L}}left(mathrm {A} Omega mathrm {Z} mathrm {I} right)$ , donde:

El conjunto de alfa $mathrm {A}$ es un conjunto contablemente infinito de elementos llamados símbolos de proposición o variables proposición. Sintácticamente hablando, estos son los elementos más básicos del lenguaje formal ${mathcal {L}}$ , de otro modo denominado fórmulas atómicas o elementos terminales. En los ejemplos a seguir, los elementos $mathrm {A}$ son típicamente las letras $p$ , $q$ , $r$ , y así sucesivamente.
El omega set $Ω$ es un conjunto finito de elementos llamados símbolos de operador o conexiones lógicas. El set $Ω$ se divide en subconjuntos descomunales como sigue:
${displaystyle Omega =Omega _{0}cup Omega _{1}cup cdots cup Omega _{j}cup cdots cup Omega _{m}.}$
En esta partición, $Omega _{j}$ es el conjunto de símbolos del operador arity $j$ .
En el calculi proposición más familiar, $Ω$ normalmente se divide de la siguiente manera:
$Omega _{1}={lnot },$
$Omega _{2}subseteq {landlortoleftrightarrow }.$
Una convención adoptada frecuentemente trata los valores lógicos constantes como operadores de la aridad cero, por lo tanto:
${displaystyle Omega _{0}={bottop }.}$
Algunos escritores usan el tilde (~), o N, en lugar de $\neg$ ; y algunos uso v en lugar de $vee$ así como el ampersand, el K prefijo, o $cdot$ en lugar de $wedge$ . La notación varía aún más para el conjunto de valores lógicos, con símbolos como {falso, verdadero}, {F, T}, o {0, 1} todos siendo vistos en diversos contextos en lugar de ${bottop }$ .
El zeta set $mathrm {Z}$ es un conjunto finito de reglas de transformación que se llaman reglas de inferencia cuando adquieren aplicaciones lógicas.
El iota set $mathrm {I}$ es un conjunto contable puntos iniciales que se llaman axiomas cuando reciben interpretaciones lógicas.

El idioma de ${mathcal {L}}$ , también conocido como su conjunto de fórmulas, fórmulas bien formadas, se define inductivamente por las siguientes reglas:

Base: Cualquier elemento del conjunto alfa $mathrm {A}$ es una fórmula ${mathcal {L}}$ .
Si $p_{1},p_{2},ldotsp_{j}$ son fórmulas y $f$ está dentro $Omega _{j}$ , entonces ${displaystyle left(fp_{1}p_{2}ldots p_{j}right)}$ es una fórmula.
Cerrado: Nada más es una fórmula ${mathcal {L}}$ .

Las aplicaciones repetidas de estas reglas permiten la construcción de fórmulas complejas. Por ejemplo:

Por regla 1, $p$ es una fórmula.
Por regla 2 $neg p$ es una fórmula.
Por regla 1, $q$ es una fórmula.
Por regla 2 $(neg plor q)$ es una fórmula.

Ejemplo 1. Sistema de axiomas simples

Vamos ${mathcal {L}}_{1}={mathcal {L}}(mathrm {A}Omegamathrm {Z}mathrm {I})$ , donde $mathrm {A}$ , $Omega$ , $mathrm {Z}$ , $mathrm {I}$ se definen de la siguiente manera:

El set $mathrm {A}$ , el conjunto contablemente infinito de símbolos que sirven para representar proposiciones lógicas:
${displaystyle mathrm {A} ={p,q,r,s,t,u,p_{2},ldots }.}$
El conjunto funcionalmente completo $Omega$ de operadores lógicos (conectores y negación) es el siguiente. De los tres conectores para conjunción, disyunción e implicación ( $wedgelor$ , y $\to$ ), se puede tomar como primitivo y los otros dos se pueden definir en términos de ella y negación ( $\neg$ ). Alternativamente, todos los operadores lógicos pueden definirse en términos de un único operador suficiente, como el trazo Sheffer (nand). El bicondicional $aleftrightarrow b$ ) puede por supuesto ser definido en términos de conjunción e implicación como $(ato b)land (bto a)$ .
Adoptar la negación e implicación como las dos operaciones primitivas de un cálculo proposiciónl equivale a tener el conjunto de omega $Omega =Omega _{1}cup Omega _{2}$ partición como sigue:
$Omega _{1}={lnot },$
$Omega _{2}={to }.$

Entonces... $alor b$ se define como $neg ato b$ , y $aland b$ se define como $neg (ato neg b)$ .

El set I{displaystyle mathrm {I} $mathrm {I}$ (el conjunto de puntos iniciales de deducción lógica, es decir, axiomas lógicos) es el sistema de axioma propuesto por Jan Łukasiewicz, y utilizado como la parte proposición-calculus de un sistema Hilbert. Los axiomas son todos los casos de sustitución de:
- $pto (qto p)$
- ${displaystyle (pto (qto r))to ((pto q)to (pto r))}$
- ${displaystyle (neg pto neg q)to (qto p)}$
El set $mathrm {Z}$ de las reglas de transformación (reglas de inferencia) es la única regla modus ponens (es decir, de cualquier fórmula de la forma $varphi$ y ${displaystyle (varphi to psi)}$ , inferencia $psi$ ).

Este sistema se utiliza en la base de datos de prueba formal de Metamath set.mm.

Ejemplo 2. Sistema de deducción natural

Vamos ${mathcal {L}}_{2}={mathcal {L}}(mathrm {A}Omegamathrm {Z}mathrm {I})$ , donde $mathrm {A}$ , $Omega$ , $mathrm {Z}$ , $mathrm {I}$ se definen de la siguiente manera:

El conjunto de alfa $mathrm {A}$ , es un conjunto contablemente infinito de símbolos, por ejemplo:
${displaystyle mathrm {A} ={p,q,r,s,t,u,p_{2},ldots }.}$
El set de omega $Omega =Omega _{1}cup Omega _{2}$ particiones como sigue:
$Omega _{1}={lnot },$
$Omega _{2}={landlortoleftrightarrow }.$

En el siguiente ejemplo de un cálculo proposicional, las reglas de transformación pretenden interpretarse como las reglas de inferencia de un llamado sistema de deducción natural. El sistema particular presentado aquí no tiene puntos iniciales, lo que significa que su interpretación para aplicaciones lógicas deriva sus teoremas de un conjunto de axiomas vacío.

El conjunto de puntos iniciales está vacío, es decir, $mathrm {I} =varnothing$ .
El conjunto de reglas de transformación, $mathrm {Z}$ , se describe como sigue:

Nuestro cálculo proposicional tiene once reglas de inferencia. Estas reglas nos permiten derivar otras fórmulas verdaderas dado un conjunto de fórmulas que se supone que son verdaderas. Los diez primeros simplemente establecen que podemos inferir ciertas fórmulas bien formadas a partir de otras fórmulas bien formadas. Sin embargo, la última regla usa razonamiento hipotético en el sentido de que en la premisa de la regla asumimos temporalmente que una hipótesis (no comprobada) es parte del conjunto de fórmulas inferidas para ver si podemos inferir otra fórmula determinada. Dado que las primeras diez reglas no hacen esto, generalmente se describen como reglas no hipotéticas y la última como una regla hipotética.

Al describir las reglas de transformación, podemos introducir un símbolo de metalanguía $vdash$ . Es básicamente un cortocircuito conveniente para decir "inferir eso". El formato es $Gamma vdash psi$ , en que $.$ es un conjunto (posiblemente vacío) de fórmulas llamadas locales, y $↑$ es una fórmula llamada conclusión. La regla de transformación $Gamma vdash psi$ significa que si cada propuesta en $.$ es un teorema (o tiene el mismo valor de la verdad que los axiomas), entonces $↑$ es también un teorema. Tenga en cuenta que teniendo en cuenta la siguiente regla Introducción de Conjunción, lo sabremos cada vez que $.$ tiene más de una fórmula, siempre podemos reducirla de forma segura en una fórmula usando la conjunción. Así que, por poco, desde entonces podemos representar $.$ como una fórmula en lugar de un conjunto. Otra omisión para conveniencia es cuando $.$ es un conjunto vacío, en cuyo caso $.$ puede no aparecer.

Negation introduction: Desde $(pto q)$ y $(pto neg q)$ , inferencia $neg p$ .; Eso es, ${(pto q),(pto neg q)}vdash neg p$ .
Eliminación de la pobreza: Desde $neg p$ , inferencia $(pto r)$ .; Eso es, ${neg p}vdash (pto r)$ .
Eliminación de doble negación: Desde $neg neg p$ , inferencia $p$ .; Eso es, $neg neg pvdash p$ .
Introducción de la orden: Desde $p$ y $q$ , inferencia $(pland q)$ .; Eso es, ${p,q}vdash (pland q)$ .
Eliminación de la conjunción: Desde $(pland q)$ , inferencia $p$ .; Desde $(pland q)$ , inferencia $q$ .; Eso es, $(pland q)vdash p$ y $(pland q)vdash q$ .
Introducción a la disyunción: Desde $p$ , inferencia $(plor q)$ .; Desde $q$ , inferencia $(plor q)$ .; Eso es, $pvdash (plor q)$ y $qvdash (plor q)$ .
Eliminación de la disyunción: Desde $(plor q)$ y $(pto r)$ y $(qto r)$ , inferencia $r$ .; Eso es, ${plor q,pto r,qto r}vdash r$ .
Introducción bicondicional: Desde $(pto q)$ y $(qto p)$ , inferencia $(pleftrightarrow q)$ .; Eso es, ${pto q,qto p}vdash (pleftrightarrow q)$ .
Eliminación bicondicional: Desde $(pleftrightarrow q)$ , inferencia $(pto q)$ .; Desde $(pleftrightarrow q)$ , inferencia $(qto p)$ .; Eso es, $(pleftrightarrow q)vdash (pto q)$ y $(pleftrightarrow q)vdash (qto p)$ .
Modus ponens (eliminación condicional): Desde $p$ y $(pto q)$ , inferencia $q$ .; Eso es, ${p,pto q}vdash q$ .
Prueba condicional (introducción condicional): De [aceptar] $p$ permite una prueba de $q$ ], inferir $(pto q)$ .; Eso es, $(pvdash q)vdash (pto q)$ .

Formas argumentales básicas y derivadas

Nombre	Secuencia	Descripción
Modus Ponens	$((pto q)land p)vdash q$	Si $p$ entonces $q$ ; $p$ ; por consiguiente $q$
Modus Tollens	$((pto q)land neg q)vdash neg p$	Si $p$ entonces $q$ ; no $q$ ; por lo tanto no $p$
Syllogismo hipotético	$((pto q)land (qto r))vdash (pto r)$	Si $p$ entonces $q$ ; si $q$ entonces $r$ ; por lo tanto, si $p$ entonces $r$
Syllogismo disjuntivo	$((plor q)land neg p)vdash q$	Cualquiera $p$ o $q$ , o ambos; no $p$ ; por consiguiente, $q$
Constructive Dilemma	$((pto q)land (rto s)land (plor r))vdash (qlor s)$	Si $p$ entonces $q$ ; y si $r$ entonces $s$ ; pero $p$ o $r$ ; por consiguiente $q$ o $s$
Dilema destructivo	$((pto q)land (rto s)land (neg qlor neg s))vdash (neg plor neg r)$	Si $p$ entonces $q$ ; y si $r$ entonces $s$ ; pero no $q$ o no $s$ ; por lo tanto no $p$ o no $r$
Bidirectional Dilemma	$((pto q)land (rto s)land (plor neg s))vdash (qlor neg r)$	Si $p$ entonces $q$ ; y si $r$ entonces $s$ ; pero $p$ o no $s$ ; por consiguiente $q$ o no $r$
Simplificación	$(pland q)vdash p$	$p$ y $q$ son verdaderas; $p$ es verdad
Conjunción	$p,qvdash (pland q)$	$p$ y $q$ son verdaderas por separado; por lo tanto, son verdaderas
Adición	$pvdash (plor q)$	$p$ es verdad; por lo tanto la disyunción ( $p$ o $q$ ) es verdad
Composition	$((pto q)land (pto r))vdash (pto (qland r))$	Si $p$ entonces $q$ ; y si $p$ entonces $r$ ; por lo tanto si $p$ es cierto entonces $q$ y $r$ son verdaderos
Teorema de De Morgan (1)	$neg (pland q)vdash (neg plor neg q)$	La negación de ( $p$ y $q$ ) es equiv. a (no $p$ o no $q$ )
Teorema de De Morgan (2)	$neg (plor q)vdash (neg pland neg q)$	La negación de ( $p$ o $q$ ) es equiv. a (no $p$ y no $q$ )
Commutación (1)	$(plor q)vdash (qlor p)$	() $p$ o $q$ ) es equiv. a ( $q$ o $p$ )
Commutación (2)	$(pland q)vdash (qland p)$	() $p$ y $q$ ) es equiv. a ( $q$ y $p$ )
Commutación (3)	$(pleftrightarrow q)vdash (qleftrightarrow p)$	() $p$ es equiv. a $q$ ) es equiv. a ( $q$ es equiv. a $p$ )
Association (1)	$(plor (qlor r))vdash ((plor q)lor r)$	$p$ o $q$ o $r$ ) es equiv. a ( $p$ o $q$ ) o $r$
Association (2)	$(pland (qland r))vdash ((pland q)land r)$	$p$ y $q$ y $r$ ) es equiv. a ( $p$ y $q$ ) y $r$
Distribución (1)	$(pland (qlor r))vdash ((pland q)lor (pland r))$	$p$ y $q$ o $r$ ) es equiv. a ( $p$ y $q$ ) o ( $p$ y $r$ )
Distribución (2)	$(plor (qland r))vdash ((plor q)land (plor r))$	$p$ o $q$ y $r$ ) es equiv. a ( $p$ o $q$ ) y ( $p$ o $r$ )
Doble Negación	$pvdash neg neg p$ y $neg neg pvdash p$	$p$ es equivalente a la negación de no $p$
Transposición	$(pto q)vdash (neg qto neg p)$	Si $p$ entonces $q$ es equiv. a si no $q$ entonces no $p$
Implicación material	$(pto q)vdash (neg plor q)$	Si $p$ entonces $q$ es equiv. a no $p$ o $q$
Equivalencia material (1)	$(pleftrightarrow q)vdash ((pto q)land (qto p))$	() $p$ Sip $q$ ) es equiv. a (si $p$ es cierto entonces $q$ es cierto) y (si $q$ es cierto entonces $p$ es cierto)
Equivalencia material (2)	$(pleftrightarrow q)vdash ((pland q)lor (neg pland neg q))$	() $p$ Sip $q$ ) es equiv. a ambos ( $p$ y $q$ son ciertas) o (tanto $p$ y $q$ son falsos)
Equivalencia material (3)	$(pleftrightarrow q)vdash ((plor neg q)land (neg plor q))$	() $p$ Sip $q$ ) es equiv a, ambos ( $p$ o no $q$ es cierto) y (no $p$ o $q$ es cierto)
Exportación	$((pland q)to r)vdash (pto (qto r))$	de (si $p$ y $q$ son verdaderos entonces $r$ es verdad) podemos probar (si $q$ es cierto entonces $r$ es verdad, si $p$ es cierto)
Importación	$(pto (qto r))vdash ((pland q)to r)$	Si $p$ entonces (si $q$ entonces $r$ ) es equivalente a si $p$ y $q$ entonces $r$
Tautología (1)	$pvdash (plor p)$	$p$ es verdad es equiv. a $p$ es verdad o $p$ es verdad
Tautología (2)	$pvdash (pland p)$	$p$ es verdad es equiv. a $p$ es verdad y $p$ es verdad
Tercio non datur (Ley de Medio Excluido)	$vdash (plor neg p)$	$p$ o no $p$ es verdad
Law of Non-Contradiction	$vdash neg (pland neg p)$	$p$ y no $p$ es falso, es una verdadera declaración

Pruebas en cálculo proposicional

Uno de los usos principales de un cálculo proposicional, cuando se interpreta para aplicaciones lógicas, es determinar relaciones de equivalencia lógica entre fórmulas proposicionales. Estas relaciones se determinan mediante las reglas de transformación disponibles, cuyas secuencias se denominan derivaciones o pruebas.

En la discusión que sigue, una prueba se presenta como una secuencia de líneas numeradas, cada una de las cuales consta de una sola fórmula seguida de una razón o justificación para presentar esa fórmula. Cada premisa del argumento, es decir, una suposición introducida como hipótesis del argumento, se enumera al principio de la secuencia y se marca como "premisa" en lugar de otra justificación. La conclusión se enumera en la última línea. Una demostración es completa si cada línea se sigue de las anteriores mediante la aplicación correcta de una regla de transformación. (Para un enfoque contrastante, consulte los árboles de prueba).

Ejemplo de una prueba en sistema de deducción natural

Para ser demostrado que $A \to A$ .
Una posible prueba de esto (que, si bien es válida, contiene más pasos de lo necesario) puede ser dispuesta de la siguiente manera:

Ejemplo de una prueba
Número	Formula	Razón
1	$A$	premisa
2	$Alor A$	De (1) por introducción de disyunción
3	$(Alor A)land A$	De (1) y (2) por introducción conjunta
4	$A$	De (3) por eliminación conjunta
5	$Avdash A$	Resumen de (1A través de4)
6	$vdash Ato A$	De (5) por prueba condicional

Interpret $Avdash A$ como "Asumiendo $A$ , inferencia $A$ ". Leer $vdash Ato A$ como "Asumir nada, inferir que $A$ implicación $A$ ", o "Es una tautología que $A$ implicación $A$ ", o "Siempre es verdad que $A$ implicación $A$ ".

Ejemplo de una demostración en un sistema de cálculo proposicional clásico

Ahora probamos el mismo teorema. ${displaystyle Ato A}$ en el sistema axiomático de Jan Łukasiewicz descrito anteriormente, que es un ejemplo de un sistema deductivo estilo Hilbert para el cálculo proposición clásica.

Los axiomas son:

(A1)

(pto (qto p))

(A2)

((pto (qto r))to ((pto q)to (pto r)))

(A3)

((neg pto neg q)to (qto p))

Y la prueba es la siguiente:

${displaystyle Ato ((Bto A)to A)}$ (instancia de (A1))
${displaystyle (Ato ((Bto A)to A))to ((Ato (Bto A))to (Ato A))}$ (A2))
${displaystyle (Ato (Bto A))to (Ato A)}$ (de (1) y 2) por modus ponens)
${displaystyle Ato (Bto A)}$ (instancia de (A1))
${displaystyle Ato A}$ (de (4) y 3) por modus ponente)

Solicitud y exhaustividad de las normas

Las propiedades cruciales de este conjunto de reglas son que son sólidas y completas. Informalmente, esto significa que las reglas son correctas y que no se requieren otras reglas. Estas afirmaciones se pueden hacer más formales de la siguiente manera. Tenga en cuenta que las pruebas de la solidez y la integridad de la lógica proposicional no son en sí mismas pruebas en la lógica proposicional; estos son teoremas en ZFC utilizados como metateoría para probar propiedades de la lógica proposicional.

Definimos una asignación de verdad como una función que asigna variables proposicionales a verdadero o falso. De manera informal, tal asignación de verdad puede entenderse como la descripción de un posible estado de cosas (o mundo posible) donde ciertas declaraciones son verdaderas y otras no. La semántica de las fórmulas se puede formalizar definiendo para qué "estado de cosas" se consideran verdaderas, que es lo que hace la siguiente definición.

Definimos cuándo tal asignación de verdad $A$ satisface una cierta fórmula bien formada con las siguientes reglas:

$A$ satisfice la variable proposición $P$ si $A () P) = verdadero$
$A$ satisfizo $\neg φ$ si $A$ no satisface $φ$
$A$ satisfizo $() φ \land ↑)$ si $A$ satisfizo ambos $φ$ y $↑$
$A$ satisfizo $() φ Alternativa ↑)$ si $A$ satisfizo al menos uno de los dos $φ$ o $↑$
$A$ satisfizo $() φ \to ↑)$ si y sólo si no es el caso $A$ satisfizo $φ$ pero no $↑$
$A$ satisfizo $() φ Administración ↑)$ si $A$ satisfizo ambos $φ$ y $↑$ o satisfice a ninguno de ellos

Con esta definición, ahora podemos formalizar lo que significa que una fórmula $φ$ esté implícita en un determinado conjunto $S$ de fórmulas. Informalmente, esto es cierto si en todos los mundos que son posibles dado el conjunto de fórmulas $S$ la fórmula $φ$ también se cumple. Esto lleva a la siguiente definición formal: Decimos que un conjunto $S$ de fórmulas bien formadas implica semánticamente (o implica) una cierta fórmula bien formada $φ$ si todas las asignaciones de verdad que satisfacen todos los las fórmulas en $S$ también satisfacen $φ.$

Finalmente, definimos vinculación sintáctica tal que $φ$ está sintácticamente vinculado por $S$ si y solo si podemos derivarlo con las reglas de inferencia que se presentaron anteriormente en un número finito de pasos. Esto nos permite formular exactamente lo que significa que el conjunto de reglas de inferencia sea sólido y completo:

Solidez: Si el conjunto de fórmulas bien formadas $S$ sintácticamente implica la fórmula bien formada $φ$ luego $S$ semánticamente implica $φ$ .

Completitud: Si el conjunto de fórmulas bien formadas $S$ semánticamente implica la fórmula bien formada $φ$ luego $S$ sintácticamente implica $φ$ .

Para el conjunto de reglas anterior, este es el caso.

Bosquejo de una prueba de solidez

(Para la mayoría de los sistemas lógicos, esta es la dirección de prueba comparativamente "simple")

Convenciones de notación: Sea $G$ una variable que abarca conjuntos de oraciones. Sean $A, B$ y $C$ rango sobre oraciones. Para " $G$ implica sintácticamente $A$ " escribimos " $G$ demuestra $A$ ". Para " $G$ implica semánticamente $A$ " escribimos " $G$ implica $A$ ".

Queremos mostrar: $(A)(G)$ (si $G$ demuestra $A$ , luego $G$ implica $A$ ).

Observamos que " $G$ demuestra que $A$ " tiene una definición inductiva, y eso nos brinda los recursos inmediatos para demostrar afirmaciones de la forma "Si $G$ prueba $A$ , luego...". Así que nuestra prueba procede por inducción.

Basis. Mostrar: Si $A$ es miembro de $G$ , entonces $G$ implicación $A$ .
Basis. Mostrar: Si $A$ es un axioma, entonces $G$ implicación $A$ .
Paso inductivo (inducción n, la longitud de la prueba:
1. Assume for arbitrary $G$ y $A$ si $G$ prueba $A$ dentro $n$ o menos pasos, entonces $G$ implicación $A$ .
2. Para cada posible aplicación de una norma de inferencia a paso $n + 1$ , que conduce a un nuevo teorema $B$ , mostrar eso $G$ implicación $B$ .

Observe que el Paso básico II se puede omitir para los sistemas de deducción natural porque no tienen axiomas. Cuando se usa, el Paso II implica mostrar que cada uno de los axiomas es una verdad lógica (semántica).

Los pasos básicos demuestran que las oraciones comprobables más simples de $G$ también están implícitas en $G$ , para cualquier $G$ . (La prueba es simple, ya que el hecho semántico de que un conjunto implica cualquiera de sus miembros también es trivial). El paso inductivo cubrirá sistemáticamente todas las oraciones adicionales que podrían ser demostrables, considerando cada caso en el que podríamos llegar a una conclusión lógica. usando una regla de inferencia, y muestra que si una nueva oración es demostrable, también está lógicamente implícita. (Por ejemplo, podríamos tener una regla que nos diga que de " $A$ " podemos derivar &# 34; $A$ o $B$ ". En III.a asumimos que si $A$ es demostrable, está implícito. También sabemos que si $A$ es demostrable entonces " $A$ o $B$ " es demostrable. Tenemos que demostrar que entonces " $A$ o $B$ " también está implícito. Lo hacemos apelando a la definición semántica y la suposición que acabamos de hacer. $A$ es comprobable a partir de G, suponemos. Así que también está implícito en $G$ . Entonces, cualquier valoración semántica que haga que todo $G$ sea verdadero hace que $A$ cierto. Pero cualquier valoración que haga $A$ verdadera hace que " $A$ o $B$ " cierto, por la semántica definida para "o". Entonces, cualquier valoración que haga que todo $G$ sea verdadero hace que " $A$ o $B$ " verdadero. Entonces " $A$ o $B$ " está implícito.) Generalmente, el paso Inductivo consistirá en un extenso pero simple análisis caso por caso de todas las reglas de inferencia, mostrando que cada una "conserva" implicación semántica.

Según la definición de demostrabilidad, no hay oraciones demostrables que no sean por ser un miembro de $G$ , un axioma, o siguiendo una regla; entonces, si todo eso está implícito semánticamente, el cálculo de deducción es sólido.

Bosquejo de prueba de integridad

(Esta suele ser la dirección de prueba mucho más difícil).

Adoptamos las mismas convenciones de notación que arriba.

Queremos mostrar: Si $G$ implica $A$ , entonces $G$ demuestra $A$ . Procedemos por contraposición: mostramos en cambio que si $G$ no prueba $A$ entonces $G$ no implica $A$ . Si mostramos que hay un modelo en el que $A$ no se cumple a pesar de $G$ siendo verdadero, entonces obviamente $G$ no implica $A$ . La idea es construir un modelo de este tipo a partir de nuestra suposición de que $G$ no prueba $A$ .

$G$ no prueba $A$ . (Asunción)
Si G no prueba A, entonces podemos construir un (infinito) Juego máximo, G^Alternativa, que es un superset de G y que tampoco prueba A.
1. Realizar un pedido (con el tipo de orden ω) sobre todas las frases en el idioma (por ejemplo, el primero más corto, e igualmente largo en el orden alfabético ampliado), y numerarlas $() E 1, E 2,...)$
2. Define una serie G_n de conjuntos ()G₀, G₁,...) inductivamente:
  1. $G_{0}=G$
  2. Si $G_{k}cup {E_{k+1}}$ prueba $A$ , entonces $G_{k+1}=G_{k}$
  3. Si $G_{k}cup {E_{k+1}}$ ¿Sí? no prueba $A$ , entonces $G_{k+1}=G_{k}cup {E_{k+1}}$
3. Define $G Alternativa$ como la unión de todos los $G n$ . (Eso es, $G Alternativa$ es el conjunto de todas las oraciones que están en cualquier $G n$ .)
4. Se puede mostrar fácilmente que
  1. $G Alternativa$ contiene (es un superset de) $G$ (por b.i));
  2. $G Alternativa$ no prueba $A$ (porque la prueba sólo contiene muchas oraciones finitamente y cuando la última de ellas es introducida en algunos $G n$ , eso $G n$ prueba $A$ contra la definición de $G n$ ); y
  3. $G Alternativa$ es un conjunto máximo con respecto a $A$ : Si hay más frases a las que se añadieron $G Alternativa$ , eso probaría $A$ . (Porque si fuera posible añadir más frases, deberían haber sido agregadas cuando fueron encontradas durante la construcción de la $G n$ , de nuevo por definición)
Si G^Alternativa es un conjunto máximo con respecto a A, entonces es verdad-como. Esto significa que contiene C si y sólo si lo hace no contener ¬; Si contiene C y contiene "Si C entonces B"entonces también contiene B; y así sucesivamente. Para mostrar esto, hay que demostrar que el sistema axiomático es suficientemente fuerte para lo siguiente:
- Para cualquier fórmula $C$ y $D$ , si prueba ambos $C$ y $\neg$ , entonces prueba $D$ . De esto sigue, que un conjunto máximo con respecto a $A$ no puede probar ambos $C$ y $\neg$ , como de otro modo probaría $A$ .
- Para cualquier fórmula $C$ y $D$ , si prueba ambos $C$ → $D$ y $\neg$ → $D$ , entonces prueba $D$ . Esto se utiliza, junto con el teorema de deducción, para demostrar que para cualquier fórmula, ya sea ella o su negación está en $G Alternativa$ # $B$ ser una fórmula no $G Alternativa$ ; entonces $G Alternativa$ con la adición de $B$ prueba $A$ . Así, desde el teorema de deducción sigue que $G Alternativa$ prueba $B$ → $A$ . Pero supongo $\negB$ no estaban $G Alternativa$ , entonces por la misma lógica $G Alternativa$ también prueba $\negB$ → $A$ ; pero entonces $G Alternativa$ prueba $A$ , que ya hemos demostrado ser falsos.
- Para cualquier fórmula $C$ y $D$ , si lo demuestra $C$ y $D$ , entonces prueba $C$ → $D$ .
- Para cualquier fórmula $C$ y $D$ , si lo demuestra $C$ y $\negD$ , entonces demuestra ¬( $C$ → $D$ ).
- Para cualquier fórmula $C$ y $D$ , si lo demuestra $\neg$ , entonces prueba $C$ → $D$ .
Si el funcionamiento lógico adicional (como la conjunción y/o la disyunción) también son parte del vocabulario, entonces hay requisitos adicionales en el sistema axiomático (por ejemplo, que si prueba C y D, también probaría su conjunción).
Si $G Alternativa$ es verdad, como si hubiera una $G Alternativa$ - Valoración canónica del idioma: una que hace cada oración en $G Alternativa$ verdadero y todo fuera $G Alternativa$ falso mientras sigue obedeciendo las leyes de la composición semántica en el lenguaje. Tenga en cuenta que el requisito de que sea como la verdad es necesario para garantizar que las leyes de la composición semántica en el lenguaje serán satisfechas por esta asignación de la verdad.
A $G Alternativa$ - valoración canónica hará nuestro conjunto original $G$ todo verdadero, y hacer $A$ falso.
Si hay una valoración sobre la cual $G$ son verdaderos $A$ es falso, entonces $G$ no implica (semántica) $A$ .

Por lo tanto, todo sistema que tenga modus ponens como regla de inferencia y demuestre los siguientes teoremas (incluidas sus sustituciones) es completo:

${displaystyle pto (neg pto q)}$
${displaystyle (pto q)to ((neg pto q)to q)}$
${displaystyle pto (qto (pto q))}$
${displaystyle pto (neg qto neg (pto q))}$
$neg pto (pto q)$
${displaystyle pto p}$
$pto (qto p)$
${displaystyle (pto (qto r))to ((pto q)to (pto r))}$

Los cinco primeros se utilizan para satisfacer las cinco condiciones de la etapa III anterior y los tres últimos para probar el teorema de deducción.

Ejemplo

Como ejemplo, se puede demostrar que, como cualquier otra tautología, los tres axiomas del sistema clásico de cálculo proposicional descrito anteriormente pueden ser probados en cualquier sistema que satisfaga lo anterior, a saber, que tiene modus ponens como regla de inferencia, y prueba los ocho teoremas anteriores (incluyendo sus sustituciones). De los ocho teoremas, los dos últimos son dos de los tres axiomas; el tercer axioma, ${displaystyle (neg qto neg p)to (pto q)}$ , puede ser probado también, como ahora mostramos.

Para la prueba, podemos usar el teorema del silogismo hipotético (en la forma relevante para este sistema axiomático), ya que solo se basa en los dos axiomas que ya están en el conjunto anterior de ocho teoremas. La prueba entonces es la siguiente:

${displaystyle qto (pto q)}$ (instancia del 7o teorema)
${displaystyle (qto (pto q))to ((neg qto neg p)to (qto (pto q)))}$ (instancia del 7o teorema)
${displaystyle (neg qto neg p)to (qto (pto q))}$ (de (1) y 2) por modus ponens)
${displaystyle (neg pto (pto q))to ((neg qto neg p)to (neg qto (pto q)))}$ (sustancia de la hipotética teorema de silogismo)
${displaystyle (neg pto (pto q))}$ (Posición del 5to teorema)
${displaystyle (neg qto neg p)to (neg qto (pto q))}$ (de (5) y (4) por modus ponens)
${displaystyle (qto (pto q))to ((neg qto (pto q))to (pto q))}$ (la posición del segundo teorema)
${displaystyle ((qto (pto q))to ((neg qto (pto q))to (pto q)))to ((neg qto neg p)to ((qto (pto q))to ((neg qto (pto q))to (pto q))))}$ (instancia del 7o teorema)
${displaystyle (neg qto neg p)to ((qto (pto q))to ((neg qto (pto q))to (pto q)))}$ (de 7) y (8) por modus ponens)
${displaystyle ((neg qto neg p)to ((qto (pto q))to ((neg qto (pto q))to (pto q))))to }$
${displaystyle (((neg qto neg p)to (qto (pto q)))to ((neg qto neg p)to ((neg qto (pto q))to (pto q))))}$ (la posición del 8o teorema)
${displaystyle ((neg qto neg p)to (qto (pto q)))to ((neg qto neg p)to ((neg qto (pto q))to (pto q)))}$ (de (9) y (10) por modus ponente)
${displaystyle (neg qto neg p)to ((neg qto (pto q))to (pto q))}$ (de (3) y (11) por modus ponens)
${displaystyle ((neg qto neg p)to ((neg qto (pto q))to (pto q)))to (((neg qto neg p)to (neg qto (pto q)))to ((neg qto neg p)to (pto q)))}$ (la posición del 8o teorema)
${displaystyle ((neg qto neg p)to (neg qto (pto q)))to ((neg qto neg p)to (pto q))}$ (de (12) y (13) por modus ponens)
${displaystyle (neg qto neg p)to (pto q)}$ (de (6) y (14) por modus ponens)

Verificación de la integridad del sistema de cálculo proposicional clásico

Ahora verificamos que el sistema de cálculo proposicional clásico descrito anteriormente puede probar los ocho teoremas requeridos mencionados anteriormente. Usamos varios lemas probados aquí:

(DN1)

{displaystyle neg neg pto p}

- Doble negación (una dirección)

(DN2)

{displaystyle pto neg neg p}

- Doble negación (otra dirección)

(HS1)

{displaystyle (qto r)to ((pto q)to (pto r))}

- una forma de silogismo hipotético

(HS2)

{displaystyle (pto q)to ((qto r)to (pto r))}

- otra forma de silogismo hipotético

(TR1)

{displaystyle (pto q)to (neg qto neg p)}

- Transposición

(TR2)

{displaystyle (neg pto q)to (neg qto p)}

- otra forma de transposición.

(L1)

{displaystyle pto ((pto q)to q)}

(L3)

{displaystyle (neg pto p)to p}

También usamos el método del metateorema del silogismo hipotético como abreviatura de varios pasos de demostración.

p→ → ()¬ ¬ p→ → q){displaystyle pto (neg pto q)} ${displaystyle pto (neg pto q)}$ - Prueba:
1. ${displaystyle pto (neg qto p)}$ (instancia de (A1))
2. ${displaystyle (neg qto p)to (neg pto neg neg q)}$ (instancia de (TR1))
3. ${displaystyle pto (neg pto neg neg q)}$ (de (1) y (2) usando el metateorema hipotético del silogismo)
4. ${displaystyle neg neg qto q}$ (instancia de (DN1))
5. ${displaystyle (neg neg qto q)to ((neg pto neg neg q)to (neg pto q))}$ (instance of (HS1))
6. ${displaystyle (neg pto neg neg q)to (neg pto q)}$ (de (4) y (5) utilizando modus ponens)
7. ${displaystyle pto (neg pto q)}$ (de (3) y (6) usando el metateorema hipotético del silogismo)
()p→ → q)→ → ()()¬ ¬ p→ → q)→ → q){displaystyle (pto q)to (neg pto q)to q)} ${displaystyle (pto q)to ((neg pto q)to q)}$ - Prueba:
1. ${displaystyle (pto q)to ((neg qto p)to (neg qto q))}$ (instance of (HS1))
2. ${displaystyle (neg qto q)to q}$ (instancia de (L3))
3. ${displaystyle ((neg qto q)to q)to (((neg qto p)to (neg qto q))to ((neg qto p)to q))}$ (instance of (HS1))
4. ${displaystyle ((neg qto p)to (neg qto q))to ((neg qto p)to q)}$ (de 2) y 3) por modus ponente)
5. ${displaystyle (pto q)to ((neg qto p)to q)}$ (de (1) y (4) usando el metateorema hipotético del silogismo)
6. ${displaystyle (neg pto q)to (neg qto p)}$ (instancia de (TR2))
7. ${displaystyle ((neg pto q)to (neg qto p))to (((neg qto p)to q)to ((neg pto q)to q))}$ (instancia de (HS2))
8. ${displaystyle ((neg qto p)to q)to ((neg pto q)to q)}$ (de (6) y (7) utilizando modus ponens)
9. ${displaystyle (pto q)to ((neg pto q)to q)}$ (de (5) y (8) usando el metateorema hipotético del silogismo)
p→ → ()q→ → ()p→ → q)){displaystyle pto (qto (pto q)} ${displaystyle pto (qto (pto q))}$ - Prueba:
1. ${displaystyle qto (pto q)}$ (instancia de (A1))
2. ${displaystyle (qto (pto q))to (pto (qto (pto q)))}$ (instancia de (A1))
3. ${displaystyle pto (qto (pto q))}$ (de (1) y (2) utilizando modus ponens)
p→ → ()¬ ¬ q→ → ¬ ¬ ()p→ → q)){displaystyle pto (neg qto neg (pto q)} ${displaystyle pto (neg qto neg (pto q))}$ - Prueba:
1. ${displaystyle pto ((pto q)to q)}$ (instancia de (L1))
2. ${displaystyle ((pto q)to q)to (neg qto neg (pto q))}$ (instancia de (TR1))
3. ${displaystyle pto (neg qto neg (pto q))}$ (de (1) y (2) usando el metateorema hipotético del silogismo)
¬ ¬ p→ → ()p→ → q){displaystyle neg pto (pto q)} $neg pto (pto q)$ - Prueba:
1. ${displaystyle neg pto (neg qto neg p)}$ (instancia de (A1))
2. ${displaystyle (neg qto neg p)to (pto q)}$ (instancia de (A3))
3. ${displaystyle neg pto (pto q)}$ (de (1) y (2) usando el metateorema hipotético del silogismo)
${displaystyle pto p}$ - la prueba dada en el ejemplo anterior
$pto (qto p)$ - axioma (A1)
${displaystyle (pto (qto r))to ((pto q)to (pto r))}$ - axioma (A2)

Otro esquema para una prueba de integridad

Si una fórmula es una tautología, entonces existe una tabla de verdad que muestra que cada valoración arroja el valor verdadero de la fórmula. Considere tal valoración. Por inducción matemática sobre la longitud de las subfórmulas, demuestre que la verdad o falsedad de la subfórmula se sigue de la verdad o falsedad (según sea apropiado para la valoración) de cada variable proposicional en la subfórmula. Luego combine las líneas de la tabla de verdad de dos en dos usando "( $P$ is true implica $S$ ) implica (( $P$ es false implica $S$ ) implica $S)". Siga repitiendo esto hasta que se hayan eliminado todas las dependencias de las variables proposicionales. El resultado es que hemos probado la tautología dada. Dado que toda tautología es demostrable, la lógica es completa.$

Interpretación de un cálculo proposicional veritativo-funcional

An interpretación de un cálculo proposición-funcional de la verdad ${mathcal {P}}$ es una asignación a cada símbolo proposición de ${mathcal {P}}$ de uno o el otro (pero no ambos) de la verdad valora la verdad (T) y falsedad (F), y una asignación a los símbolos conectivos de ${mathcal {P}}$ de sus significados funcionales de verdad habituales. También se puede expresar una interpretación de un cálculo proposición-funcional de verdad en términos de tablas de verdad.

Para $n$ distintos símbolos proposiciónles hay $2^{n}$ distintas interpretaciones posibles. Para cualquier símbolo particular $a$ , por ejemplo, hay $2^{1}=2$ posibles interpretaciones:

$a$ se asigna T, o
$a$ se asigna F.

Para el par $a$ , $b$ hay $2^{2}=4$ posibles interpretaciones:

ambos asignados T,
ambos asignados F,
$a$ se asigna T y $b$ se asigna F, o
$a$ se asigna F y $b$ se asigna T.

Desde ${mathcal {P}}$ tiene $aleph _{0}$ , es decir, sin duda muchos símbolos proposiciónles, hay $2^{aleph _{0}}={mathfrak {c}}$ , y por lo tanto, incontablemente muchas interpretaciones distintas posibles ${mathcal {P}}$ .

Interpretación de una oración de lógica proposicional veritativo-funcional

Si $φ$ y $↑$ son fórmulas de ${mathcal {P}}$ y ${mathcal {I}}$ es una interpretación de ${mathcal {P}}$ entonces se aplican las siguientes definiciones:

Una frase de la lógica proposicional es fiel a una interpretación ${mathcal {I}}$ si ${mathcal {I}}$ asigna el valor de la verdad T a esa frase. Si una frase es verdadera bajo una interpretación, entonces esa interpretación se llama modelo de esa frase.
$φ$ es falso bajo una interpretación ${mathcal {I}}$ si $φ$ no es cierto ${mathcal {I}}$ .
Una frase de la lógica proposicional es lógicamente válida si es verdad bajo cada interpretación.
$models$ $φ$ significa que $φ$ es lógicamente válido.
A sentence $↑$ de la lógica proposicional es una consecuencia semántica de una sentencia $φ$ si no hay interpretación en virtud de la cual $φ$ es verdad y $↑$ es falso.
Una frase de la lógica proposicional es coherente si es cierto bajo al menos una interpretación. Es inconsistente si no es consistente.

Algunas consecuencias de estas definiciones:

Para cualquier interpretación dada una fórmula dada es verdadera o falsa.
Ninguna fórmula es verdadera y falsa bajo la misma interpretación.
$φ$ es falso para una interpretación dada sif $neg phi$ es verdad para esa interpretación; y $φ$ es cierto bajo una interpretación sif $neg phi$ es falso bajo esa interpretación.
Si $φ$ y $(phi to psi)$ ambos son verdaderos bajo una interpretación dada, entonces $↑$ es cierto bajo esa interpretación.
Si $models _{mathrm {P} }phi$ y $models _{mathrm {P} }(phi to psi)$ , entonces $models _{mathrm {P} }psi$ .
$neg phi$ es verdad ${mathcal {I}}$ Sip $φ$ no es cierto ${mathcal {I}}$ .
$(phi to psi)$ es verdad ${mathcal {I}}$ o $φ$ no es cierto ${mathcal {I}}$ o $↑$ es verdad ${mathcal {I}}$ .
A sentence $↑$ de la lógica proposicional es una consecuencia semántica de una frase $φ$ Sip $(phi to psi)$ es lógicamente válido, es decir, $phi models _{mathrm {P} }psi$ Sip $models _{mathrm {P} }(phi to psi)$ .

Cálculo alternativo

Es posible definir otra versión del cálculo proposicional, que define la mayor parte de la sintaxis de los operadores lógicos por medio de axiomas, y que usa solo una regla de inferencia.

Axiomas

Sea $φ$ , $χ$ y $ψ$ representan fórmulas bien formadas. (Las fórmulas bien formadas en sí mismas no contendrían letras griegas, sino solo letras romanas mayúsculas, operadores conectivos y paréntesis). Entonces los axiomas son los siguientes:

Axiomas
Nombre	Axiom Schema	Descripción
THEN-1	$phi to (chi to phi)$	Agregar hipótesis $χ$ , introducción de implicaciones
THEN-2	$(phi to (chi to psi))to ((phi to chi)to (phi to psi))$	Distribuir hipótesis $phi$ sobre la implicación
Y-1	$phi land chi to phi$	Eliminar la conjunción
AND-2	$phi land chi to chi$
Y 3	$phi to (chi to (phi land chi))$	Introducción
OR-1	$phi to phi lor chi$	Introducción
OR-2	$chi to phi lor chi$
OR-3	$(phi to psi)to ((chi to psi)to (phi lor chi to psi))$	Eliminar la disyunción
NO-1	$(phi to chi)to ((phi to neg chi)to neg phi)$	Introducción
NO-2	$phi to (neg phi to chi)$	Eliminar la negación
NO-3	$phi lor neg phi$	Lógica clásica e intermedia
IFF-1	$(phi leftrightarrow chi)to (phi to chi)$	Eliminar la equivalencia
IFF-2	$(phi leftrightarrow chi)to (chi to phi)$
IFF-3	$(phi to chi)to ((chi to phi)to (phi leftrightarrow chi))$	Introducir equivalencia

Axiom THEN-2 puede ser considerado como una "propiedad distributiva de implicación con respecto a la implicación".
Axiomas Y-1 y AND-2 corresponde a "la eliminación de conjunción". La relación entre Y-1 y AND-2 refleja la conmutación del operador de conjunción.
Axiom Y 3 corresponde a "introducción de conjunción".
Axiomas OR-1 y OR-2 corresponde a "introducción de disyunciones". La relación entre OR-1 y OR-2 refleja la conmutación del operador de disyunción.
Axiom NO-1 corresponde a "reductio ad absurdum".
Axiom NO-2 dice que "todo se puede deducir de una contradicción".
Axiom NO-3 se llama "tertium non-datur" (Latín: "un tercio no se da") y refleja la valoración semántica de las fórmulas proposicionales: una fórmula puede tener un valor de verdad de verdadero o falso. No hay un tercer valor de la verdad, al menos no en la lógica clásica. Los lógicas intuitionistas no aceptan el axioma NO-3.

Regla de inferencia

La regla de inferencia es modus ponens:

{displaystyle {frac {phi phi to chi }{chi }}}

Regla de metainferencia

Represente una demostración mediante una secuencia, con las hipótesis a la izquierda del torniquete y la conclusión a la derecha del torniquete. Entonces el teorema de la deducción puede enunciarse de la siguiente manera:

Si la secuencia

phi _{1}, phi _{2},..., phi _{n}, chi vdash psi

ha sido demostrado, entonces también es posible demostrar la secuencia

phi _{1}, phi _{2},..., phi _{n}vdash chi to psi

Este teorema de deducción (DT) no está formulado en sí mismo con cálculo proposicional: no es un teorema de cálculo proposicional, sino un teorema sobre cálculo proposicional. En este sentido, es un meta-teorema, comparable a los teoremas sobre la solidez o completitud del cálculo proposicional.

Por otro lado, DT es tan útil para simplificar el proceso de prueba sintáctica que se puede considerar y utilizar como otra regla de inferencia, acompañando al modus ponens. En este sentido, DT corresponde a la regla de inferencia de prueba condicional natural que forma parte de la primera versión de cálculo proposicional presentada en este artículo.

El inverso de DT también es válido:

Si la secuencia

phi _{1}, phi _{2},..., phi _{n}vdash chi to psi

ha sido demostrado, entonces también es posible demostrar la secuencia

phi _{1}, phi _{2},..., phi _{n}, chi vdash psi

de hecho, la validez de la inversa de DT es casi trivial en comparación con la de DT:

phi _{1},..., phi _{n}vdash chi to psi

entonces

phi _{1},..., phi _{n}, chi vdash chi to psi

phi _{1},..., phi _{n}, chi vdash chi

y de 1) y 2) se pueden deducir

phi _{1},..., phi _{n}, chi vdash psi

por medio de modus ponens, Q.E.D.

Lo contrario de DT tiene poderosas implicaciones: puede usarse para convertir un axioma en una regla de inferencia. Por ejemplo, por el axioma AND-1 tenemos,

{displaystyle vdash phi wedge chi to phi}

que se puede transformar mediante el inverso del teorema de deducción en

{displaystyle phi wedge chi vdash phi}

lo que nos dice que la regla de inferencia

{displaystyle {frac {phi wedge chi }{phi }}}

es admisible. Esta regla de inferencia es la eliminación de conjunciones, una de las diez reglas de inferencia utilizadas en la primera versión (en este artículo) del cálculo proposicional.

Ejemplo de una prueba

El siguiente es un ejemplo de una demostración (sintáctica), que involucra solo los axiomas ENTONCES-1 y ENTONCES-2:

Probar: $Ato A$ (Reflexividad de implicación).

Prueba:

$(Ato ((Bto A)to A))to ((Ato (Bto A))to (Ato A))$
Axiom THEN-2 con $phi =A,chi =Bto A,psi =A$
$Ato ((Bto A)to A)$
Axiom THEN-1 con $phi =A,chi =Bto A$
$(Ato (Bto A))to (Ato A)$
De (1) y (2) por modus ponens.
$Ato (Bto A)$
Axiom THEN-1 con $phi =A,chi =B$
$Ato A$
De (3) y (4) por modus ponens.

Equivalencia a lógica ecuacional

El cálculo alternativo anterior es un ejemplo de un sistema de deducción estilo Hilbert. En el caso de los sistemas proposicionales los axiomas son términos construidos con conectivos lógicos y la única regla de inferencia es el modus ponens. La lógica ecuacional, tal como se usa informalmente de manera estándar en el álgebra de la escuela secundaria, es un tipo diferente de cálculo de los sistemas de Hilbert. Sus teoremas son ecuaciones y sus reglas de inferencia expresan las propiedades de la igualdad, a saber, que es una congruencia de términos que admite sustitución.

Clásico cálculo proposiciónl como se describe anteriormente es equivalente al álgebra boo, mientras que el cálculo proposición intuitionista es equivalente a álgebra Heyting. La equivalencia se muestra por traducción en cada dirección de los teoremas de los respectivos sistemas. Teoremas $phi$ de cálculo proposición clásica o intuitionista se traducen como ecuaciones $phi =1$ de álgebra Boolean o Heyting respectivamente. Teoremas transversales $x=y$ de álgebra booleana o Heyting se traducen como teoremas $(xto y)land (yto x)$ de cálculo clásico o intuitivo respectivamente, para el cual $xequiv y$ es una abreviatura estándar. En el caso del álgebra booleana $x=y$ también se puede traducir como $(xland y)lor (neg xland neg y)$ , pero esta traducción es incorrecta intuitivamente.

En álgebra booleana y Heyting, desigualdad $xleq y$ se puede utilizar en lugar de igualdad. La igualdad $x=y$ es expresible como un par de desigualdades $xleq y$ y $yleq x$ . Por el contrario, la desigualdad $xleq y$ es expresible como la igualdad $xland y=x$ , o como $xlor y=y$ . La importancia de la desigualdad para los sistemas de estilo Hilbert es que corresponde a la deducción o símbolo de implicación de este último $vdash$ . Una implicación

phi _{1}, phi _{2}, dots phi _{n}vdash psi

se traduce en la versión de desigualdad del marco algebraico como

phi _{1} land phi _{2} land dots land phi _{n} leq psi

Por el contrario, la desigualdad algebraica $xleq y$ se traduce como la implicación

x vdash y

La diferencia entre implicación $xto y$ y desigualdad o implicación $xleq y$ o $x vdash y$ es que el primero es interno a la lógica mientras que el segundo es externo. La implicación interna entre dos términos es otro término del mismo tipo. La inclusión como implicación externa entre dos términos expresa una metatrulla fuera del lenguaje de la lógica, y se considera parte de la sustancia metálica. Incluso cuando la lógica en estudio es intuitionista, la implicación se entiende generalmente clásicamente como dos valores: o el lado izquierdo implica, o es menos o igual a, el lado derecho, o no lo es.

Son posibles traducciones similares pero más complejas hacia y desde la lógica algebraica para los sistemas de deducción natural descritos anteriormente y para el cálculo secuente. Las implicaciones de este último pueden interpretarse como de dos valores, pero una interpretación más perspicaz es como un conjunto, cuyos elementos pueden entenderse como pruebas abstractas organizadas como los morfismos de una categoría. En esta interpretación la regla de corte del cálculo secuente corresponde a la composición en la categoría. Las álgebras booleanas y de Heyting entran en esta imagen como categorías especiales que tienen como máximo un morfismo por homset, es decir, una prueba por implicación, lo que corresponde a la idea de que la existencia de pruebas es todo lo que importa: cualquier prueba servirá y no tiene sentido distinguirlas..

Cálculos gráficos

Es posible generalizar la definición de un lenguaje formal a partir de un conjunto de secuencias finitas sobre una base finita para incluir muchos otros conjuntos de estructuras matemáticas, siempre que se construyan por medios finitos a partir de materiales finitos. Además, muchas de estas familias de estructuras formales son especialmente adecuadas para su uso en lógica.

Por ejemplo, hay muchas familias de gráficos que son análogos lo suficientemente cercanos a los lenguajes formales como para que el concepto de cálculo se les extienda con bastante facilidad y naturalidad. Muchas especies de gráficos surgen como gráficos de análisis sintáctico en el análisis sintáctico de las familias correspondientes de estructuras de texto. Las exigencias de la computación práctica en lenguajes formales exigen con frecuencia que las cadenas de texto se conviertan en representaciones de estructuras de punteros de gráficos de análisis, simplemente como una cuestión de verificar si las cadenas son fórmulas bien formadas o no. Una vez hecho esto, se pueden obtener muchas ventajas al desarrollar el análogo gráfico del cálculo en cadenas. La asignación de cadenas a gráficos de análisis se denomina análisis y la asignación inversa de gráficos de análisis a cadenas se logra mediante una operación que se denomina recorrido del gráfico.

Otros cálculos lógicos

El cálculo proposicional es el tipo de cálculo lógico más simple que se usa actualmente. Se puede extender de varias maneras. (El cálculo "silogístico" aristotélico, que en gran medida ha sido suplantado en la lógica moderna, es en algunas formas más simple, pero en otras formas más complejo, que el cálculo proposicional.) La forma más inmediata de desarrollar un cálculo lógico más complejo es introducir reglas que sean sensibles a detalles más finos de las oraciones que se utilizan.

La lógica de primer orden (también conocida como lógica de predicados de primer orden) resulta cuando las "frases atómicas" de la lógica proposicional se dividen en términos, variables, predicados y cuantificadores, todos manteniendo las reglas de la lógica proposicional con algunas nuevas introducidas. (Por ejemplo, de 'Todos los perros son mamíferos' podemos inferir 'Si Rover es un perro, entonces Rover es un mamífero'.) Con las herramientas de la lógica de primer orden es posible formular una serie de teorías, ya sea con axiomas explícitos o mediante reglas de inferencia, que pueden tratarse como cálculos lógicos. La aritmética es la más conocida de ellas; otros incluyen la teoría de conjuntos y la mereología. La lógica de segundo orden y otras lógicas de orden superior son extensiones formales de la lógica de primer orden. Por lo tanto, tiene sentido referirse a la lógica proposicional como "lógica de orden cero", al compararla con estas lógicas.

La lógica modal también ofrece una variedad de inferencias que no se pueden capturar en el cálculo proposicional. Por ejemplo, desde "Necesariamente $p$ " podemos inferir que $p$ . De $p$ podemos inferir "Es posible que $p$ ". La traducción entre lógica modal y lógica algebraica atañe a la lógica clásica e intuicionista pero con la introducción de un operador unario en las álgebras booleanas o de Heyting, diferente de las operaciones booleanas, que interpreta la modalidad de posibilidad, y en el caso del álgebra de Heyting un segundo operador que interpreta la necesidad (para el álgebra booleana esto es redundante ya que la necesidad es el dual de posibilidad de De Morgan). El primer operador conserva el 0 y la disyunción mientras que el segundo conserva el 1 y la conjunción.

Las lógicas multivaluadas son aquellas que permiten que las oraciones tengan valores distintos de verdadero y falso. (Por ejemplo, ninguno y ambos son "valores adicionales" estándar; la "lógica continua" permite que cada oración tenga cualquiera de número infinito de 'grados de verdad' entre verdadero y falso.) Estas lógicas a menudo requieren dispositivos de cálculo bastante distintos del cálculo proposicional. Cuando los valores forman un álgebra booleana (que puede tener más de dos o incluso infinitos valores), la lógica de muchos valores se reduce a la lógica clásica; Por lo tanto, las lógicas de muchos valores solo tienen un interés independiente cuando los valores forman un álgebra que no es booleana.

Resolvedores

Decidir la satisfacibilidad de fórmulas de lógica proposicional es un problema NP-completo. Sin embargo, existen métodos prácticos (por ejemplo, algoritmo DPLL, 1962; algoritmo Chaff, 2001) que son muy rápidos para muchos casos útiles. El trabajo reciente ha ampliado los algoritmos de resolución de SAT para trabajar con proposiciones que contienen expresiones aritméticas; estos son los solucionadores de SMT.