Cálculo proposicional

Branch of logic

El cálculo proposicional ^[a] es una rama de la lógica . ^[1] También se denomina lógica proposicional , ^[2] lógica de enunciados , ^[1] cálculo oracional , ^[3] lógica oracional , ^[1] o, a veces , lógica de orden cero . ^{[4] [5]} Se ocupa de proposiciones ^[1] (que pueden ser verdaderas o falsas ) ^[6] y de las relaciones entre proposiciones, ^[7] incluida la construcción de argumentos basados ​​en ellas. ^[8] Las proposiciones compuestas se forman conectando proposiciones mediante conectivos lógicos que representan las funciones de verdad de conjunción , disyunción , implicación , bicondicional y negación . ^{[9] [10] [11] [12]} Algunas fuentes incluyen otros conectivos, como en la siguiente tabla.

A diferencia de la lógica de primer orden , la lógica proposicional no se ocupa de 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 las lógicas de orden superior. En este sentido, la lógica proposicional es la base de la lógica de primer orden y la lógica de orden superior.

La lógica proposicional se estudia típicamente con un lenguaje formal , en el que las proposiciones se representan mediante letras, que se denominan variables proposicionales . Estas se utilizan luego, junto con símbolos para conectivos, para formar proposiciones compuestas. Debido a esto, las variables proposicionales se denominan fórmulas atómicas de un lenguaje formal de orden cero. ^{[10] [2]} Si bien las proposiciones atómicas se representan típicamente con letras del alfabeto , ^[10] existe una variedad de notaciones para representar los conectivos lógicos. La siguiente tabla muestra las principales variantes de notación para cada uno de los conectivos en la lógica proposicional.

La rama más investigada de la lógica proposicional es la lógica proposicional veritativo-funcional clásica , ^[1] en la que las fórmulas se interpretan como si tuvieran precisamente uno de dos valores de verdad posibles , el valor de verdad de verdadero o el valor de verdad de falso . ^[15] Se mantienen el principio de bivalencia y la ley del tercio excluido . En comparación con la lógica de primer orden , la lógica proposicional veritativo-funcional se considera lógica de orden cero . ^{[4] [5]}

Historia

Aunque la lógica proposicional (también llamada cálculo proposicional) había sido insinuada por filósofos anteriores, fue desarrollada en una lógica formal ( lógica estoica ) por Crisipo en el siglo III a. C. ^[16] y ampliada por sus sucesores estoicos . La lógica se centraba en proposiciones . Esto era diferente de la lógica silogística tradicional , que se centraba en términos . Sin embargo, la mayoría de los escritos originales se perdieron ^[17] y, en algún momento entre el siglo III y el VI d. C., la lógica estoica cayó en el olvido, para resucitar solo en el siglo XX, a raíz del (re)descubrimiento de la lógica proposicional. ^[18]

La lógica simbólica , que llegaría a ser importante para refinar la lógica proposicional, fue desarrollada por primera vez por el matemático de los siglos XVII y XVIII Gottfried Leibniz , cuyo cálculo razonador era, sin embargo, 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. ^[19]

La lógica de predicados de Gottlob Frege se basa en la lógica proposicional y se ha descrito como una combinación de "las características distintivas de la lógica silogística y la lógica proposicional". ^[20] En consecuencia, la lógica de predicados marcó el comienzo de una nueva era en la historia de la lógica; sin embargo, después de Frege se hicieron avances en la lógica proposicional, incluyendo la deducción natural , los árboles de verdad y las tablas de verdad . La deducción natural fue inventada por Gerhard Gentzen y Stanisław Jaśkowski . Los árboles de verdad fueron inventados por Evert Willem Beth . ^[21] Sin embargo, la invención de las tablas de verdad es de atribución incierta.

En los trabajos de Frege ^[22] y Bertrand Russell [ ^23] se encuentran 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 ambos, independientemente). ^[22] Además de Frege y Russell, otros a quienes se les atribuyen ideas anteriores a las tablas de verdad incluyen a Philo, Boole, Charles Sanders Peirce [ ^24] y Ernst Schröder . Otros a quienes se les atribuye la estructura tabular incluyen a Jan Łukasiewicz , Alfred North Whitehead , William Stanley Jevons , John Venn y Clarence Irving Lewis . ^[23] En última instancia, algunos han concluido, como John Shosky, que "está lejos de estar claro que a una persona se le deba dar el título de 'inventor' de las tablas de verdad". ^[23]

Oraciones

La lógica proposicional, tal como se estudia actualmente en las universidades, es una especificación de un estándar de consecuencia lógica en el que solo se consideran los significados de los conectivos proposicionales al evaluar las condiciones de verdad de una oración, o si una oración se sigue lógicamente de alguna otra oración o grupo de oraciones. ^[2]

Oraciones declarativas

La lógica proposicional se ocupa de enunciados , que se definen como oraciones declarativas que tienen valor de verdad. ^{[25] [1]} Algunos ejemplos de enunciados pueden incluir:

• Wikipedia es una enciclopedia libre en línea que cualquiera puede editar.
• Londres es la capital de Inglaterra .
• Todos los editores de Wikipedia hablan al menos tres idiomas .

Las oraciones declarativas contrastan con preguntas , como "¿Qué es Wikipedia?", y declaraciones imperativas , como "Agregue citas para respaldar las afirmaciones de este artículo". ^{[26] [27]} Estas oraciones no declarativas no tienen valor de verdad , ^[28] y solo se tratan en lógicas no clásicas , llamadas lógicas erotéticas e imperativas .

Oraciones compuestas con conectores

En lógica proposicional, un enunciado puede contener uno o más enunciados como partes. ^[1] Las oraciones compuestas se forman a partir de oraciones más simples y expresan relaciones entre las oraciones constituyentes. ^[29] Esto se hace combinándolas con conectivos lógicos : ^{[29] [30]} los principales tipos de oraciones compuestas son negaciones , conjunciones , disyunciones , implicaciones y bicondicionales , ^[29] que se forman utilizando los conectivos correspondientes para conectar proposiciones. ^{[31] [32]} En inglés , estos conectivos se expresan mediante las palabras "y" ( conjunción ), "o" ( disyunción ), "no" ( negación ), "si" ( condicional material ) y "si y solo si" ( bicondicional ). ^{[1] [9]} Ejemplos de tales oraciones compuestas podrían incluir:

• Wikipedia es una enciclopedia libre en línea que cualquiera puede editar, y millones de personas ya lo han hecho . (conjunción)
• No es cierto que todos los editores de Wikipedia hablen al menos tres idiomas. (negación)
• O bien Londres es la capital de Inglaterra, o bien Londres es la capital del Reino Unido , o ambas. (disyunción) ^[b]

Si las oraciones carecen de conectores lógicos, se denominan oraciones simples , ^[1] u oraciones atómicas ; ^[30] si contienen uno o más conectores lógicos, se denominan oraciones compuestas , ^[29] u oraciones moleculares . ^[30]

Los conectivos oracionales son una categoría más amplia que incluye conectivos lógicos. ^{[2] [30]} Los conectivos oracionales son partículas lingüísticas que unen oraciones para crear una nueva oración compuesta, ^{[2] [30]} o que flexionan una sola oración para crear una nueva oración. ^[2] Un conectivo lógico , o conectivo proposicional , es un tipo de conectivo oracional con el rasgo característico de que, cuando las oraciones originales sobre las que opera son (o expresan) proposiciones , la nueva oración que resulta de su aplicación también es (o expresa) una proposición . ^[2] Los filósofos no están de acuerdo sobre qué es exactamente una proposición, ^{[6] [2]} así como sobre qué conectivos oracionales en los lenguajes naturales deben contarse como conectivos lógicos. ^{[30] [2]} Los conectivos oracionales también se denominan funtores oracionales , ^[33] y los conectivos lógicos también se denominan funtores de verdad . ^[33]

Argumentos

Un argumento se define como un par de cosas, a saber, un conjunto de oraciones, llamadas premisas , ^[c] y una oración, llamada conclusión . ^{[34] [30] [33]} Se afirma que la conclusión se sigue de las premisas, ^[33] y se afirma que las premisas respaldan la conclusión. ^[30]

Ejemplo de argumento

El siguiente es un ejemplo de un argumento dentro del ámbito de la lógica proposicional:

Premisa 1: Si llueve, entonces está nublado.

Premisa 2: Está lloviendo.

Conclusión: Está nublado.

La forma lógica de este argumento se conoce como modus ponens , ^[35] que es una forma clásicamente válida . ^[36] Por lo tanto, en la lógica clásica, el argumento es válido , aunque puede ser sólido o no , dependiendo de los hechos meteorológicos en un contexto dado. Este argumento de ejemplo se reutilizará al explicar el § Formalización.

Validez y solidez

Un argumento es válido si, y sólo si, es necesario que, si todas sus premisas son verdaderas, su conclusión sea verdadera. ^{[34] [37] [38]} Alternativamente, un argumento es válido si, y sólo si, es imposible que todas las premisas sean verdaderas mientras que la conclusión sea falsa. ^{[38] [34]}

La validez se contrasta con la solidez . ^[38] Un argumento es sólido si, y sólo si, es válido y todas sus premisas son verdaderas. ^{[34] [38]} De lo contrario, es erróneo . ^[38]

La lógica, en general, tiene como objetivo especificar con precisión argumentos válidos. ^[30] Esto se hace definiendo un argumento válido como uno en el que su conclusión es una consecuencia lógica de sus premisas, ^[30] lo que, cuando esto se entiende como consecuencia semántica , significa que no hay ningún caso en el que las premisas sean verdaderas pero la conclusión no lo sea ^[30] – ver § Semántica más abajo.

Formalización

La lógica proposicional se estudia típicamente a través de un sistema formal en el que las fórmulas de un lenguaje formal se interpretan para representar proposiciones . Este lenguaje formal es la base de los sistemas de prueba , que permiten derivar una conclusión de las premisas si, y solo si, es una consecuencia lógica de ellas. Esta sección mostrará cómo funciona esto formalizando el argumento de ejemplo §. El lenguaje formal para un cálculo proposicional se especificará completamente en § Lenguaje, y se dará una descripción general de los sistemas de prueba en § Sistemas de prueba.

Variables proposicionales

Dado que 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, ^{[35] [1]} se estudia típicamente reemplazando dichas declaraciones atómicas (indivisibles) con letras del alfabeto, que se interpretan como variables que representan declaraciones ( variables proposicionales ). ^[1] Con variables proposicionales, el argumento de ejemplo § se simbolizaría entonces de la siguiente manera:

Premisa 1: ${\displaystyle P\to Q}$

Premisa 2: ${\displaystyle P}$

Conclusión: ${\displaystyle Q}$

Cuando P se interpreta como “está lloviendo” y Q como “está nublado”, estas expresiones simbólicas 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 con la misma forma lógica .

Cuando se utiliza un sistema formal para representar la lógica formal, solo se representan directamente las letras de los enunciados (normalmente letras romanas mayúsculas como , y ). Las proposiciones en lenguaje natural que surgen cuando se interpretan quedan fuera del ámbito del sistema, y ​​la relación entre el sistema formal y su interpretación queda asimismo fuera del propio sistema formal. ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle R}$

Notación Gentzen

Si asumimos que la validez del modus ponens ha sido aceptada como un axioma , entonces el mismo argumento de ejemplo también se puede representar así:

${\displaystyle {\frac {P\to Q,P}{Q}}}$

Este método de mostrarlo es la notación de Gentzen para la deducción natural y el cálculo consecuente . ^[39] Las premisas se muestran sobre una línea, llamada línea de inferencia , ^[11] separadas por una coma , que indica una combinación de premisas. ^[40] La conclusión se escribe debajo de la línea de inferencia. ^[11] La línea de inferencia representa la consecuencia sintáctica , ^[11] a veces llamada consecuencia deductiva , ^[41] que también se simboliza con ⊢. ^{[42] [41]} Por lo tanto, lo anterior también se puede escribir en una línea como . ^[d] ${\displaystyle P\to Q,P\vdash Q}$

La consecuencia sintáctica se contrasta con la consecuencia semántica , ^[43] que se simboliza con ⊧. ^{[42] [41]} En este caso, la conclusión se sigue sintácticamente porque se ha asumido la regla de inferencia de deducción natural del modus ponens . Para obtener más información sobre las reglas de inferencia, consulte las secciones sobre sistemas de prueba a continuación.

Idioma

El lenguaje (comúnmente llamado ) ^{[44] [45] [30]} de un cálculo proposicional se define en términos de: ^{[2] [10]} ${\displaystyle {\mathcal {L}}}$

1. un conjunto de símbolos primitivos, llamados fórmulas atómicas , oraciones atómicas , ^{[35] [30]} átomos, ^[46] marcadores de posición , fórmulas primos , ^[46] letras de proposición , letras de oración , ^[35] o variables , y
2. un conjunto de símbolos operadores, llamados conectivos , ^{[14] [1] [47]} conectivos lógicos , ^[1] operadores lógicos , ^[1] conectivos veritativo-funcionales, ^[1] functores de verdad , ^[33] o conectivos proposicionales . ^[2]

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 operadores de acuerdo con las reglas de la gramática. El lenguaje , entonces, se define como idéntico a su conjunto de fórmulas bien formadas, ^[45] o como que contiene ese conjunto (junto con, por ejemplo, su conjunto de conectivos y variables). ^{[10] [30]} ${\displaystyle {\mathcal {L}}}$

Por lo general, la sintaxis de se define recursivamente mediante unas pocas definiciones, como se ve a continuación; algunos autores incluyen explícitamente paréntesis como signos de puntuación al definir la sintaxis de su lenguaje, ^{[30] [48]} mientras que otros los usan sin comentarios. ^{[2] [10]} ${\displaystyle {\mathcal {L}}}$

Sintaxis

Dado un conjunto de variables proposicionales atómicas , , , ..., y un conjunto de conectivos proposicionales , , , ... , , , , ..., , , , ..., una fórmula de lógica proposicional se define recursivamente mediante estas definiciones: ^{[2] [10] [47] [e]} ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{3}}$ ${\displaystyle c_{1}^{1}}$ ${\displaystyle c_{2}^{1}}$ ${\displaystyle c_{3}^{1}}$ ${\displaystyle c_{1}^{2}}$ ${\displaystyle c_{2}^{2}}$ ${\displaystyle c_{3}^{2}}$ ${\displaystyle c_{1}^{3}}$ ${\displaystyle c_{2}^{3}}$ ${\displaystyle c_{3}^{3}}$

Definición 1 : Las variables proposicionales atómicas son fórmulas.

Definición 2 : Si es un conectivo proposicional, y A, B, C, … es una secuencia de m fórmulas, posiblemente pero no necesariamente atómicas, posiblemente pero no necesariamente distintas, entonces el resultado de aplicar a A, B, C, … es una fórmula. ${\displaystyle c_{n}^{m}}$ ${\displaystyle \langle }$ ${\displaystyle \rangle }$ ${\displaystyle c_{n}^{m}}$ ${\displaystyle \langle }$ ${\displaystyle \rangle }$

Definición 3: Nada más es una fórmula.

Escribiendo el resultado de aplicar a A, B, C, … en notación funcional, como (A, B, C, …), tenemos los siguientes como ejemplos de fórmulas bien formadas: ${\displaystyle c_{n}^{m}}$ ${\displaystyle \langle }$ ${\displaystyle \rangle }$ ${\displaystyle c_{n}^{m}}$

• ${\displaystyle p_{5}}$
• ${\displaystyle c_{3}^{2}(p_{2},p_{9})}$
• ${\displaystyle c_{3}^{2}(p_{1},c_{2}^{1}(p_{3}))}$
• ${\displaystyle c_{1}^{3}(p_{4},p_{6},c_{2}^{2}(p_{1},p_{2}))}$
• ${\displaystyle c_{4}^{2}(c_{1}^{1}(p_{7}),c_{3}^{1}(p_{8}))}$
• ${\displaystyle c_{2}^{3}(c_{1}^{2}(p_{3},p_{4}),c_{2}^{1}(p_{5}),c_{3}^{2}(p_{6},p_{7}))}$
• ${\displaystyle c_{3}^{1}(c_{1}^{3}(p_{2},p_{3},c_{2}^{2}(p_{4},p_{5})))}$

Lo que se dio como Definición 2 anteriormente, que es responsable de la composición de fórmulas, es referido por Colin Howson como el principio de composición . ^{[35] [f]} Es esta recursión en la definición de la sintaxis de un lenguaje lo que justifica el uso de la palabra "atómico" para referirse a variables proposicionales, ya que todas las fórmulas en el lenguaje se construyen a partir de los átomos como bloques de construcción últimos. ^[2] Las fórmulas compuestas (todas las fórmulas además de los átomos) se llaman moléculas , ^[46] u oraciones moleculares . ^[30] (Esta es una analogía imperfecta con la química , ya que una molécula química a veces puede tener solo un átomo, como en los gases monoatómicos ). ^[46] ${\displaystyle {\mathcal {L}}}$

La definición de que "nada más es una fórmula", dada anteriormente como Definición 3 , excluye cualquier fórmula del lenguaje que no sea específicamente requerida por las otras definiciones en la sintaxis. ^[33] En particular, excluye que las fórmulas infinitamente largas estén bien formadas . ^[33]

Gramática CF en BNF

Una alternativa a las definiciones de sintaxis dadas anteriormente es escribir una gramática libre de contexto (CF) para el lenguaje en forma Backus-Naur (BNF). ^{[50] [51]} Esto es más común en informática que en filosofía . ^[51] Se puede hacer de muchas maneras, ^[50] de las cuales una particularmente breve, para el conjunto común de cinco conectivos, es esta única cláusula: ^{[51] [52]} ${\displaystyle {\mathcal {L}}}$

${\displaystyle \phi ::=a_{1},a_{2},\ldots ~|~\neg \phi ~|~\phi ~\&~\psi ~|~\phi \vee \psi ~|~\phi \rightarrow \psi ~|~\phi \leftrightarrow \psi }$

Esta cláusula, debido a su naturaleza autorreferencial (ya que se encuentra en algunas ramas de la definición de ), también actúa como una definición recursiva y, por lo tanto, especifica todo el lenguaje. Para expandirla y agregar operadores modales , solo es necesario agregar …  al final de la cláusula. ^[51] ${\displaystyle \phi }$ ${\displaystyle \phi }$ ${\displaystyle |~\Box \phi ~|~\Diamond \phi }$

Constantes y esquemas

Los matemáticos a veces distinguen entre constantes proposicionales, variables proposicionales y esquemas. Las constantes proposicionales representan alguna proposición particular, ^[53] mientras que las variables proposicionales abarcan el conjunto de todas las proposiciones atómicas. ^[53] Sin embargo, los esquemas, o letras esquemáticas , abarcan todas las fórmulas. ^{[33] [1]} (Las letras esquemáticas también se denominan metavariables ). ^[34] Es común representar las constantes proposicionales por A , B y C , las variables proposicionales por P , Q y R , y las letras esquemáticas suelen ser letras griegas, más frecuentemente φ , ψ y χ . ^{[33] [1]}

Sin embargo, algunos autores reconocen sólo dos "constantes proposicionales" en su sistema formal: el símbolo especial , llamado "verdad", que siempre evalúa a Verdadero , y el símbolo especial , llamado "falsedad", que siempre evalúa a Falso . ^{[54] [55] [56]} Otros autores también incluyen estos símbolos, con el mismo significado, pero los consideran "functores de verdad de lugar cero", ^[33] o equivalentemente, " conectivos nulares ". ^[47] ${\displaystyle \top }$ ${\displaystyle \bot }$

Semántica

Para servir como modelo de la lógica de un lenguaje natural dado , un lenguaje formal debe ser interpretado semánticamente. ^[30] En la lógica clásica , todas las proposiciones evalúan exactamente uno de dos valores de verdad : Verdadero o Falso . ^{[1] [57]} Por ejemplo, " Wikipedia es una enciclopedia en línea gratuita que cualquiera puede editar" evalúa a Verdadero , ^[58] mientras que "Wikipedia es una enciclopedia en papel " evalúa a Falso . ^[59]

En otros aspectos, la siguiente semántica formal puede aplicarse al lenguaje de cualquier lógica proposicional, pero las suposiciones de que solo hay dos valores semánticos ( bivalencia ), que solo uno de los dos se asigna a cada fórmula en el lenguaje ( no contradicción ), y que a cada fórmula se le asigna un valor ( tercero excluido ), son características distintivas de la lógica clásica. ^{[57] [60] [33]} Para aprender sobre lógicas no clásicas con más de dos valores de verdad, y su semántica única, uno puede consultar los artículos sobre " Lógica de muchos valores ", " Lógica de tres valores ", " Lógica de valores finitos " y " Lógica de valores infinitos ".

Interpretación (caso) y argumentación

Para un lenguaje dado , una interpretación , ^[61] valoración , ^[48] o caso , ^{[30] [g]} es una asignación de valores semánticos a cada fórmula de . ^[30] Para un lenguaje formal de lógica clásica, un caso se define como una asignación , a cada fórmula de , de uno u otro, pero no ambos, de los valores de verdad , a saber, verdad ( T , o 1) y falsedad ( F , o 0). ^{[62] [63]} Una interpretación que sigue las reglas de la lógica clásica a veces se denomina valoración booleana . ^{[48] [64]} Una interpretación de un lenguaje formal para lógica clásica a menudo se expresa en términos de tablas de verdad . ^{[65] [1]} Dado que a cada fórmula solo se le asigna un único valor de verdad, una interpretación puede verse como una función , cuyo dominio es , y cuyo rango es su conjunto de valores semánticos , ^[2] o . ^[30] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {V}}=\{{\mathsf {T}},{\mathsf {F}}\}}$ ${\displaystyle {\mathcal {V}}=\{1,0\}}$

Para símbolos proposicionales distintos hay distintas interpretaciones posibles. Para cualquier símbolo particular , por ejemplo, hay posibles interpretaciones: o bien se le asigna T , o bien se le asigna F . Y para el par , hay posibles interpretaciones: o bien se le asigna T a ambos , o bien se le asigna F a ambos , o bien se le asigna T y se le asigna F , o bien se le asigna F y se le asigna T . ^[65] Puesto que tiene , es decir, una cantidad numerable de símbolos proposicionales, hay , y por lo tanto una cantidad incontable de posibles interpretaciones distintas de como un todo. ^[65] ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle a}$ ${\displaystyle 2^{1}=2}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 2^{2}=4}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle 2^{\aleph _{0}}={\mathfrak {c}}}$ ${\displaystyle {\mathcal {L}}}$

Donde es una interpretación y y representan fórmulas, la definición de un argumento , dada en § Argumentos, puede entonces enunciarse como un par , donde es el conjunto de premisas y es la conclusión. La definición de la validez de un argumento , es decir, su propiedad de que , puede entonces enunciarse como su ausencia de un contraejemplo , donde un contraejemplo se define como un caso en el que las premisas del argumento son todas verdaderas pero la conclusión no es verdadera. ^{[30] [35]} Como se verá en § Verdad semántica, validez, consecuencia, esto es lo mismo que decir que la conclusión es una consecuencia semántica de las premisas. ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle }$ ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$ ${\displaystyle \psi }$ ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$ ${\displaystyle \psi }$

Semántica conectiva proposicional

Una interpretación asigna valores semánticos a fórmulas atómicas directamente. ^{[61] [30]} A las fórmulas moleculares se les asigna una función del valor de sus átomos constituyentes, según el conectivo utilizado; ^{[61] [30]} los conectivos se definen de tal manera que el valor de verdad de una oración formada a partir de átomos con conectivos depende de los valores de verdad de los átomos a los que se aplican, y solo de ellos. ^{[61] [30]} Colin Howson se refiere a esta suposición como la suposición de la funcionalidad de verdad de los conectivos . ^[35]

Semántica a través de tablas de verdad

Dado que los conectivos lógicos se definen semánticamente solo en términos de los valores de verdad que toman cuando las variables proposicionales a las que se aplican toman cualquiera de los dos posibles valores de verdad, ^{[1] [30]} la definición semántica de los conectivos generalmente se representa como una tabla de verdad para cada uno de los conectivos, ^{[1] [30] [66]} como se ve a continuación:

Esta tabla cubre cada uno de los cinco conectivos lógicos principales : ^{[9] [10] [11] [12]} conjunción (aquí notada p ∧ q), disyunción (p ∨ q), implicación (p → q), bicondicional (p ↔ q) y negación , (¬p, o ¬q, según sea el caso). Es suficiente para determinar la semántica de cada uno de estos operadores. ^{[1] [67] [30]} Para más tablas de verdad para más tipos diferentes de conectivos, vea el artículo " Tabla de verdad ".

Semántica mediante expresiones de asignación

Algunos autores (es decir, todos los autores citados en esta subsección) escriben la semántica de los conectivos utilizando una lista de enunciados en lugar de una tabla. En este formato, donde es la interpretación de , los cinco conectivos se definen como: ^{[33] [48]} ${\displaystyle {\mathcal {I}}(\varphi )}$ ${\displaystyle \varphi }$

• ${\displaystyle {\mathcal {I}}(\neg P)={\mathsf {T}}}$Si, y sólo si, ${\displaystyle {\mathcal {I}}(P)={\mathsf {F}}}$
• ${\displaystyle {\mathcal {I}}(P\land Q)={\mathsf {T}}}$si, y sólo si, y ${\displaystyle {\mathcal {I}}(P)={\mathsf {T}}}$ ${\displaystyle {\mathcal {I}}(Q)={\mathsf {T}}}$
• ${\displaystyle {\mathcal {I}}(P\lor Q)={\mathsf {T}}}$si, y sólo si, o ${\displaystyle {\mathcal {I}}(P)={\mathsf {T}}}$ ${\displaystyle {\mathcal {I}}(Q)={\mathsf {T}}}$
• ${\displaystyle {\mathcal {I}}(P\to Q)={\mathsf {T}}}$si, y sólo si, es cierto que, si , entonces ${\displaystyle {\mathcal {I}}(P)={\mathsf {T}}}$ ${\displaystyle {\mathcal {I}}(Q)={\mathsf {T}}}$
• ${\displaystyle {\mathcal {I}}(P\leftrightarrow Q)={\mathsf {T}}}$si, y sólo si, es cierto que si, y sólo si, ${\displaystyle {\mathcal {I}}(P)={\mathsf {T}}}$ ${\displaystyle {\mathcal {I}}(Q)={\mathsf {T}}}$

En lugar de , la interpretación de puede escribirse como , ^{[33] [68]} o, para definiciones como la anterior, puede escribirse simplemente como la oración en inglés " se le da el valor ". ^[48] Sin embargo, otros autores ^{[69] [70]} pueden preferir hablar de un modelo tarskiano para el lenguaje, de modo que en su lugar utilizarán la notación , que es equivalente a decir , donde es la función de interpretación para . ^[70] ${\displaystyle {\mathcal {I}}(\varphi )}$ ${\displaystyle \varphi }$ ${\displaystyle |\varphi |}$ ${\displaystyle {\mathcal {I}}(\varphi )={\mathsf {T}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathsf {T}}}$ ${\displaystyle {\mathfrak {M}}}$ ${\displaystyle {\mathfrak {M}}\models \varphi }$ ${\displaystyle {\mathcal {I}}(\varphi )={\mathsf {T}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathfrak {M}}}$

Métodos de definición conectivos

Algunas de estas conectivas pueden definirse en términos de otras: por ejemplo, la implicación, p → q, puede definirse en términos de disyunción y negación, como ¬p ∨ q; ^[71] y la disyunción puede definirse en términos de negación y conjunción, como ¬(¬p ∧ ¬q). ^[48] De hecho, un sistema verdad-funcionalmente completo ^{, [h]} en el sentido de que todas y solo las tautologías proposicionales clásicas son teoremas, puede derivarse usando solo disyunción y negación (como lo hicieron Russell , Whitehead y Hilbert ), ^[2] o usando solo implicación y negación (como lo hizo Frege ), ^[2] o usando solo conjunción y negación, ^[2] o incluso usando solo una única conectiva para "no y" (el trazo de Sheffer ), ^{[3] [2]} como lo hizo Jean Nicod . ^[2] Un conectivo de negación conjunta ( NOR lógico ) también será suficiente, por sí solo, para definir todos los demás conectivos, ^[48] pero ningún otro conectivo tiene esta propiedad. ^[48]

Algunos autores, a saber, Howson ^[35] y Cunningham ^[73], distinguen la equivalencia del bicondicional. (En cuanto a la equivalencia, Howson la llama "equivalencia veritativo-funcional", mientras que Cunningham la llama "equivalencia lógica"). La equivalencia se simboliza con ⇔ y es un símbolo del metalenguaje, mientras que un bicondicional se simboliza con ↔ y es un conectivo lógico en el lenguaje objeto . Independientemente de esto, una equivalencia o un bicondicional es verdadero si, y solo si, a las fórmulas conectadas por él se les asigna el mismo valor semántico bajo cada interpretación. Otros autores a menudo no hacen esta distinción y pueden usar la palabra "equivalencia", ^[11] y/o el símbolo ⇔, ^[74] para denotar el conectivo bicondicional de su lenguaje objeto. ${\displaystyle {\mathcal {L}}}$

Verdad semántica, validez, consecuencia

Dados y como fórmulas (u oraciones) de un lenguaje , y como una interpretación (o caso) ^[i] de , entonces se aplican las siguientes definiciones: ^{[65] [63]} ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {L}}}$

• Verdad en un caso: ^[30] Una oración de es verdadera bajo una interpretación si asigna el valor de verdad T a . ^{[63] [65]} Si es verdadera bajo , entonces se llama un modelo de . ^[65] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$
• Falsedad en un caso: ^[30] es falsa bajo una interpretación si, y solo si, es verdadera bajo . ^{[65] [75] [30]} Esta es la definición de "verdad de negación" de falsedad en un caso. ^[30] La falsedad en un caso también puede definirse por la definición de "complemento": es falsa bajo una interpretación si, y solo si, no es verdadera bajo . ^{[63] [65]} En lógica clásica , estas definiciones son equivalentes, pero en lógicas no clásicas , no lo son. ^[30] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$
• Consecuencia semántica: Una oración de es una consecuencia semántica ( ) de una oración si no hay interpretación bajo la cual es verdadera y no es verdadera. ^{[63] [65] [30]} ${\displaystyle \psi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$
• Fórmula válida (tautología): Una oración de es lógicamente válida ( ), ^[j] o una tautología , ^{[76] [77] [48]} si es verdadera bajo cualquier interpretación, ^{[63] [65]} o verdadera en todos los casos. ^[30] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \models \varphi }$
• Oración consistente: Una oración de es consistente si es verdadera bajo al menos una interpretación. Es inconsistente si no es consistente. ^{[63] [65]} Una fórmula inconsistente también se llama autocontradictoria , ^[1] y se dice que es una autocontradicción , ^[1] o simplemente una contradicción , ^{[78] [79] [80]} aunque este último nombre a veces se reserva específicamente para enunciados de la forma . ^[1] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle (p\land \neg p)}$

Para las interpretaciones (casos) de , a veces se dan estas definiciones: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {L}}}$

• Caso completo: Un caso es completo si, y sólo si, o bien es verdadero en o bien es verdadero en , para cualquier en . ^{[30] [81]} ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$
• Caso consistente: Un caso es consistente si, y sólo si, no existe en tal que tanto y sean verdaderos en . ^{[30] [82]} ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \varphi }$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$

Para la lógica clásica , que supone que todos los casos son completos y consistentes, ^[30] se aplican los siguientes teoremas:

• Para cualquier interpretación dada, una fórmula dada es verdadera o falsa según ella. ^{[65] [75]}
• Ninguna fórmula es a la vez verdadera y falsa bajo la misma interpretación. ^{[65] [75]}
• ${\displaystyle \varphi }$es verdadero bajo si, y sólo si, es falso bajo ; ^{[65] [75]} es verdadero bajo si, y sólo si, no es verdadero bajo . ^[65] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$
• Si y son ambos verdaderos bajo , entonces es verdadero bajo . ^{[65] [75]} ${\displaystyle \varphi }$ ${\displaystyle (\varphi \to \psi )}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \psi }$ ${\displaystyle {\mathcal {I}}}$
• Si y , entonces . ^[65] ${\displaystyle \models \varphi }$ ${\displaystyle \models (\varphi \to \psi )}$ ${\displaystyle \models \psi }$
• ${\displaystyle (\varphi \to \psi )}$es verdadera bajo si, y sólo si, o bien no es verdadera bajo , o bien es verdadera bajo . ^[65] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \psi }$ ${\displaystyle {\mathcal {I}}}$
• ${\displaystyle \varphi \models \psi }$si, y sólo si, es lógicamente válido , es decir, si, y sólo si, . ^{[65] [75]} ${\displaystyle (\varphi \to \psi )}$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \models (\varphi \to \psi )}$

Sistemas de prueba

Los sistemas de prueba en lógica proposicional pueden clasificarse ampliamente en sistemas de prueba semánticos y sistemas de prueba sintácticos , ^{[83] [84] [85]} según el tipo de consecuencia lógica en la que se basan: los sistemas de prueba semánticos se basan en la consecuencia semántica ( ), ^[86] mientras que los sistemas de prueba sintácticos se basan en la consecuencia sintáctica ( ). ^[87] La ​​consecuencia semántica se ocupa de los valores de verdad de las proposiciones en todas las interpretaciones posibles, mientras que la consecuencia sintáctica se refiere a la derivación de conclusiones a partir de premisas basadas en reglas y axiomas dentro de un sistema formal. ^[88] Esta sección ofrece una breve descripción general de los tipos de sistemas de prueba, con enlaces a las secciones relevantes de este artículo sobre cada uno, así como a los artículos separados de Wikipedia sobre cada uno. ${\displaystyle \varphi \models \psi }$ ${\displaystyle \varphi \vdash \psi }$

Sistemas de prueba semánticos

Ejemplo de una tabla de verdad

Una representación gráfica de un cuadro proposicional parcialmente construido

Los sistemas de prueba semántica se basan en el concepto de consecuencia semántica, simbolizado como , que indica que si es verdadero, entonces también debe ser verdadero en cada interpretación posible. ^[88] ${\displaystyle \varphi \models \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$

Tablas de verdad

Una tabla de verdad es un método de prueba semántica utilizado para determinar el valor de verdad de una expresión de lógica proposicional en cada escenario posible. ^[89] Al enumerar exhaustivamente los valores de verdad de sus átomos constituyentes, una tabla de verdad puede mostrar si una proposición es verdadera, falsa, tautológica o contradictoria. ^[90] Véase § Prueba semántica mediante tablas de verdad.

Cuadros semánticos

Un cuadro semántico es otra técnica de prueba semántica que explora sistemáticamente la verdad de una proposición. ^[91] Construye un árbol donde cada rama representa una posible interpretación de las proposiciones involucradas. ^[92] Si cada rama conduce a una contradicción, la proposición original se considera una contradicción y su negación se considera una tautología . ^[35] Véase § Prueba semántica mediante cuadros.

Sistemas de prueba sintácticos

Reglas para el cálculo proposicional secuencial LK, en notación Gentzen

Los sistemas de prueba sintácticos, por el contrario, se centran en la manipulación formal de los símbolos de acuerdo con reglas específicas. La noción de consecuencia sintáctica, , significa que puede derivarse del uso de las reglas del sistema formal. ^[88] ${\displaystyle \varphi \vdash \psi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi }$

Sistemas axiomáticos

Un sistema axiomático es un conjunto de axiomas o suposiciones de los cuales se derivan lógicamente otras afirmaciones (teoremas). ^[93] En lógica proposicional, los sistemas axiomáticos definen un conjunto base de proposiciones consideradas como evidentemente verdaderas, y los teoremas se prueban aplicando reglas de deducción a estos axiomas. ^[94] Véase § Prueba sintáctica mediante axiomas.

Deducción natural

La deducción natural es un método sintáctico de prueba que enfatiza la derivación de conclusiones a partir de premisas mediante el uso de reglas intuitivas que reflejan el razonamiento ordinario. ^[95] Cada regla refleja un conectivo lógico particular y muestra cómo puede introducirse o eliminarse. ^[95] Véase § Prueba sintáctica mediante deducción natural.

Cálculo secuencial

El cálculo secuencial es un sistema formal que representa deducciones lógicas como secuencias o "secuencias" de fórmulas. ^[96] Desarrollado por Gerhard Gentzen , este enfoque se centra en las propiedades estructurales de las deducciones lógicas y proporciona un marco poderoso para probar afirmaciones dentro de la lógica proposicional. ^{[96] [97]}

Prueba semántica mediante tablas de verdad

Aprovechando el concepto semántico de validez (verdad en cada interpretación), es posible probar la validez de una fórmula utilizando una tabla de verdad , que da cada interpretación posible (asignación de valores de verdad a las variables) de una fórmula. ^{[90] [46] [33]} Si, y solo si, todas las líneas de una tabla de verdad resultan verdaderas, la fórmula es semánticamente válida (verdadera en cada interpretación). ^{[90] [46]} Además, si (y solo si) es válida, entonces es inconsistente. ^{[78] [79] [80]} ${\displaystyle \neg \varphi }$ ${\displaystyle \varphi }$

Por ejemplo, esta tabla muestra que " p → (q ∨ r → (r → ¬p)) " no es válido: ^[46]

El cálculo de la última columna de la tercera línea se puede mostrar de la siguiente manera: ^[46]

Además, utilizando el teorema de que si, y solo si, es válido, ^{[65] [75]} podemos utilizar una tabla de verdad para demostrar que una fórmula es una consecuencia semántica de un conjunto de fórmulas: si, y solo si, podemos producir una tabla de verdad que resulte completamente verdadera para la fórmula (es decir, si ). ^{[98] [99]} ${\displaystyle \varphi \models \psi }$ ${\displaystyle (\varphi \to \psi )}$ ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi }$ ${\displaystyle \left(\left(\bigwedge _{i=1}^{n}\varphi _{i}\right)\rightarrow \psi \right)}$ ${\displaystyle \models \left(\left(\bigwedge _{i=1}^{n}\varphi _{i}\right)\rightarrow \psi \right)}$

Prueba semántica mediante cuadros

Como las tablas de verdad tienen 2 ⁿ líneas para n variables, pueden ser tediosas de largas para valores grandes de n. ^[35] Las tablas analíticas son un método de prueba semántica más eficiente, pero no por ello menos mecánico, ^[66] ; aprovechan el hecho de que "no aprendemos nada sobre la validez de la inferencia al examinar las distribuciones de valores de verdad que hacen que las premisas sean falsas o la conclusión verdadera: las únicas distribuciones relevantes al considerar la validez deductiva son claramente sólo aquellas que hacen que las premisas sean verdaderas o la conclusión falsa". ^[35]

Los cuadros analíticos para la lógica proposicional están completamente especificados por las reglas que se exponen en forma esquemática a continuación. ^[48] Estas reglas utilizan "fórmulas con signo", donde una fórmula con signo es una expresión o , donde es una fórmula (sin signo) del lenguaje . ^[48] (De manera informal, se lee " es verdadero", y se lee " es falso".) ^[48] Su definición semántica formal es que "bajo cualquier interpretación, una fórmula con signo se llama verdadera si es verdadera, y falsa si es falsa, mientras que una fórmula con signo se llama falsa si es verdadera, y verdadera si es falsa". ^[48] ${\displaystyle TX}$ ${\displaystyle FX}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle TX}$ ${\displaystyle X}$ ${\displaystyle FX}$ ${\displaystyle X}$ ${\displaystyle TX}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle FX}$ ${\displaystyle X}$ ${\displaystyle X}$

${\displaystyle {\begin{aligned}&1)\quad {\frac {T\sim X}{FX}}\quad &&{\frac {F\sim X}{TX}}\\{\phantom {spacer}}\\&2)\quad {\frac {T(X\land Y)}{\begin{matrix}TX\\TY\end{matrix}}}\quad &&{\frac {F(X\land Y)}{FX|FY}}\\{\phantom {spacer}}\\&3)\quad {\frac {T(X\lor Y)}{TX|TY}}\quad &&{\frac {F(X\lor Y)}{\begin{matrix}FX\\FY\end{matrix}}}\\{\phantom {spacer}}\\&4)\quad {\frac {T(X\supset Y)}{FX|TY}}\quad &&{\frac {F(X\supset Y)}{\begin{matrix}TX\\FY\end{matrix}}}\end{aligned}}}$

En esta notación, la regla 2 significa que produce tanto , mientras que se ramifica en . La notación debe entenderse de manera análoga para las reglas 3 y 4. ^[48] A menudo, en tablas para lógica clásica , la notación de fórmula con signo se simplifica de modo que se escribe simplemente como , y como , lo que explica el nombre de la regla 1 como " Regla de la doble negación ". ^{[35] [66]} ${\displaystyle T(X\land Y)}$ ${\displaystyle TX,TY}$ ${\displaystyle F(X\land Y)}$ ${\displaystyle FX,FY}$ ${\displaystyle T\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle F\varphi }$ ${\displaystyle \neg \varphi }$

Se construye un cuadro para un conjunto de fórmulas aplicando las reglas para producir más líneas y ramas de árbol hasta que se haya usado cada línea, produciendo un cuadro completo . En algunos casos, una rama puede llegar a contener tanto y para algunos , es decir, una contradicción. En ese caso, se dice que la rama se cierra . ^[35] Si cada rama en un árbol se cierra, se dice que el árbol mismo se cierra. ^[35] En virtud de las reglas para la construcción de cuadros, un árbol cerrado es una prueba de que la fórmula original, o conjunto de fórmulas, utilizado para construirlo era en sí mismo autocontradictorio y, por lo tanto, falso. ^[35] A la inversa, un cuadro también puede probar que una fórmula lógica es tautóloga : si una fórmula es tautóloga, su negación es una contradicción, por lo que un cuadro construido a partir de su negación se cerrará. ^[35] ${\displaystyle TX}$ ${\displaystyle FX}$ ${\displaystyle X}$

Para construir una tabla para un argumento , primero se escribe el conjunto de fórmulas de premisas, , con una fórmula en cada línea, firmada con (es decir, para cada una en el conjunto); ^[66] y junto con esas fórmulas (el orden no es importante), también se escribe la conclusión, , firmada con (es decir, ). ^[66] Luego se produce un árbol de verdad (tabla analítica) usando todas esas líneas de acuerdo con las reglas. ^[66] Un árbol cerrado será una prueba de que el argumento era válido, en virtud del hecho de que si, y solo si, es inconsistente (también escrito como ). ^[66] ${\displaystyle \langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle }$ ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$ ${\displaystyle T}$ ${\displaystyle T\varphi }$ ${\displaystyle T\varphi }$ ${\displaystyle \psi }$ ${\displaystyle F}$ ${\displaystyle F\psi }$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \{\varphi ,\sim \psi \}}$ ${\displaystyle \varphi ,\sim \psi \models }$

Lista de formas de argumentos clásicamente válidos

Utilizando métodos de comprobación semántica, como tablas de verdad o cuadros semánticos, para comprobar tautologías y consecuencias semánticas, se puede demostrar que, en lógica clásica, las siguientes formas de argumento clásicas son semánticamente válidas, es decir, se cumplen estas tautologías y consecuencias semánticas. ^[33] Usamos ⟚ para denotar la equivalencia de y , es decir, como una abreviatura tanto para y ; ^[33] como ayuda para leer los símbolos, se da una descripción de cada fórmula. La descripción lee el símbolo ⊧ (llamado el "doble torniquete") como "por lo tanto", que es una lectura común del mismo, ^{[33] [100]} aunque muchos autores prefieren leerlo como "implica", ^{[33] [101]} o como "modelos". ^[102] ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi \models \varphi }$

Prueba sintáctica por deducción natural

La deducción natural , dado que es un método de prueba sintáctica, se especifica proporcionando reglas de inferencia (también llamadas reglas de prueba ) ^[34] para un lenguaje con el conjunto típico de conectivos ; no se utilizan otros axiomas además de estas reglas. ^[105] Las reglas se tratan a continuación y luego se da un ejemplo de prueba. ${\displaystyle \{-,\&,\lor ,\to ,\leftrightarrow \}}$

Estilos de notación

Los distintos autores varían hasta cierto punto en cuanto a las reglas de inferencia que dan, lo que se señalará. Sin embargo, lo que resulta más llamativo para la apariencia de una prueba es la variación en los estilos de notación. La notación § Gentzen, que se trató anteriormente para un argumento corto, en realidad se puede apilar para producir grandes pruebas de deducción natural en forma de árbol ^{[39] [11]} —no debe confundirse con los "árboles de verdad", que es otro nombre para los cuadros analíticos . ^[66] También hay un estilo debido a Stanisław Jaśkowski , donde las fórmulas en la prueba se escriben dentro de varios cuadros anidados, ^[39] y hay una simplificación del estilo de Jaśkowski debido a Fredric Fitch ( notación Fitch ), donde los cuadros se simplifican a simples líneas horizontales debajo de las introducciones de suposiciones y líneas verticales a la izquierda de las líneas que están debajo de la suposición. ^[39] Por último, está el único estilo de notación que realmente se utilizará en este artículo, que se debe a Patrick Suppes , ^[39] pero fue muy popularizado por EJ Lemmon y Benson Mates . ^[106] Este método tiene la ventaja de que, gráficamente, es el menos intensivo de producir y mostrar, lo que lo convirtió en una elección natural para el editor que escribió esta parte del artículo, que no entendía los complejos comandos LaTeX que se requerirían para producir pruebas en los otros métodos.

Una prueba , entonces, dispuesta de acuerdo con el estilo de notación de Suppes-Lemmon , ^[39] es una secuencia de líneas que contienen oraciones, ^[34] donde cada oración es una suposición o el resultado de aplicar una regla de prueba a oraciones anteriores en la secuencia. ^[34] Cada línea de prueba se compone de una oración de prueba , junto con su anotación , su conjunto de suposiciones y el número de línea actual . ^[34] El conjunto de suposiciones enumera las suposiciones de las que depende la oración de prueba dada, a las que se hace referencia mediante los números de línea. ^[34] La anotación especifica qué regla de prueba se aplicó y a qué líneas anteriores para producir la oración actual. ^[34] Véase el ejemplo de prueba de deducción natural §.

Reglas de inferencia

Las reglas de inferencia de deducción natural, debidas en última instancia a Gentzen , se dan a continuación. ^[105] Hay diez reglas primitivas de prueba, que son la regla de suposición , más cuatro pares de reglas de introducción y eliminación para los conectivos binarios, y la regla reductio ad adbsurdum . ^[34] El silogismo disyuntivo se puede utilizar como una alternativa más fácil a la ∨-eliminación adecuada, ^[34] y MTT y DN son reglas dadas comúnmente, ^[105] aunque no son primitivas. ^[34]

Ejemplo de prueba de deducción natural

La prueba a continuación ^[34] se deriva de y utiliza solo MPP y RAA , lo que demuestra que MTT no es una regla primitiva, ya que puede derivarse de esas otras dos reglas. ${\displaystyle -P}$ ${\displaystyle P\to Q}$ ${\displaystyle -Q}$

Prueba sintáctica mediante axiomas

Es posible realizar pruebas axiomáticamente, lo que significa que ciertas tautologías se toman como evidentes y varias otras se deducen de ellas usando modus ponens como regla de inferencia , así como una regla de sustitución , que permite reemplazar cualquier fórmula bien formada con cualquier instancia de sustitución de la misma. ^[108] Alternativamente, se utilizan esquemas axiomáticos en lugar de axiomas, y no se utiliza ninguna regla de sustitución. ^[108]

En esta sección se presentan los axiomas de algunos sistemas axiomáticos históricamente notables para la lógica proposicional. Para más ejemplos, así como teoremas metalógicos específicos de dichos sistemas axiomáticos (como su completitud y consistencia), consulte el artículo Sistema axiomático (lógica) .

De FregeEscritura de constitución

Aunque la prueba axiomática se ha utilizado desde el famoso libro de texto griego antiguo , Elementos de geometría de Euclides , en lógica proposicional se remonta a la Begriffsschrift de Gottlob Frege de 1879. ^{[33] [108]} El sistema de Frege usaba solo la implicación y la negación como conectivos, ^[2] y tenía seis axiomas, ^[108] que eran estos: ^{[109] [110]}

• Proposición 1: ${\displaystyle a\supset (b\supset a)}$
• Proposición 2: ${\displaystyle (c\supset (b\supset a))\supset ((c\supset b)\supset (c\supset a))}$
• Proposición 8: ${\displaystyle (d\supset (b\supset a))\supset (b\supset (d\supset a))}$
• Proposición 28: ${\displaystyle (b\supset a)\supset (\neg a\supset \neg b)}$
• Proposición 31: ${\displaystyle \neg \neg a\supset a}$
• Proposición 41: ${\displaystyle a\supset \neg \neg a}$

These were used by Frege together with modus ponens and a rule of substitution (which was used but never precisely stated) to yield a complete and consistent axiomatization of classical truth-functional propositional logic.^[109]

Łukasiewicz's P2

Jan Łukasiewicz showed that, in Frege's system, "the third axiom is superfluous since it can be derived from the preceding two axioms, and that the last three axioms can be replaced by the single sentence ${\displaystyle CCNpNqCpq}$".^[110] Which, taken out of Łukasiewicz's Polish notation into modern notation, means ${\displaystyle (\neg p\rightarrow \neg q)\rightarrow (p\rightarrow q)}$. Hence, Łukasiewicz is credited^[108] with this system of three axioms:

• ${\displaystyle p\to (q\to p)}$
• ${\displaystyle (p\to (q\to r))\to ((p\to q)\to (p\to r))}$
• ${\displaystyle (\neg p\to \neg q)\to (q\to p)}$

Just like Frege's system, this system uses a substitution rule and uses modus ponens as an inference rule.^[108] The exact same system was given (with an explicit substitution rule) by Alonzo Church,^[111] who referred to it as the system P₂^[111][112] and helped popularize it.^[112]

Schematic form of P₂

One may avoid using the rule of substitution by giving the axioms in schematic form, using them to generate an infinite set of axioms. Hence, using Greek letters to represent schemata (metalogical variables that may stand for any well-formed formulas), the axioms are given as:^[33][112]

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

The schematic version of P₂ is attributed to John von Neumann,^[108] and is used in the Metamath "set.mm" formal proof database.^[112] It has also been attributed to Hilbert,^[113] and named ${\displaystyle {\mathcal {H}}}$ in this context.^[113]

Proof example in P₂

As an example, a proof of ${\displaystyle A\to A}$ in P₂ is given below. First, the axioms are given names:

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

(A2) ${\displaystyle ((p\to (q\to r))\to ((p\to q)\to (p\to r)))}$

(A3) ${\displaystyle ((\neg p\to \neg q)\to (q\to p))}$

And the proof is as follows:

1. ${\displaystyle A\to ((B\to A)\to A)}$       (instance of (A1))
2. ${\displaystyle (A\to ((B\to A)\to A))\to ((A\to (B\to A))\to (A\to A))}$       (instance of (A2))
3. ${\displaystyle (A\to (B\to A))\to (A\to A)}$       (from (1) and (2) by modus ponens)
4. ${\displaystyle A\to (B\to A)}$       (instance of (A1))
5. ${\displaystyle A\to A}$       (from (4) and (3) by modus ponens)

Solvers

One notable difference between propositional calculus and predicate calculus is that satisfiability of a propositional formula is decidable.^[114] Deciding satisfiability of propositional logic formulas is an NP-complete problem. However, practical methods exist (e.g., DPLL algorithm, 1962; Chaff algorithm, 2001) that are very fast for many useful cases. Recent work has extended the SAT solver algorithms to work with propositions containing arithmetic expressions; these are the SMT solvers.

See also

• Philosophy portal

Higher logical levels

• First-order logic
• Second-order propositional logic
• Second-order logic
• Higher-order logic

Related topics

• Boolean algebra (logic)
• Boolean algebra (structure)
• Boolean algebra topics
• Boolean domain
• Boolean function
• Boolean-valued function
• Categorical logic
• Combinational logic
• Combinatory logic
• Conceptual graph
• Disjunctive syllogism
• Entitative graph
• Equational logic
• Existential graph
• Implicational propositional calculus
• Intuitionistic propositional calculus
• Jean Buridan
• Laws of Form
• List of logic symbols
• Logical graph
• Logical NOR
• Logical value
• Mathematical logic
• Operation (mathematics)
• Paul of Venice
• Peirce's law
• Peter of Spain (author)
• Propositional formula
• Symmetric difference
• Tautology (rule of inference)
• Truth function
• Truth table
• Walter Burley
• William of Sherwood

Notes

1. Many sources write this with a definite article, as the propositional calculus, while others just call it propositional calculus with no article.
2. The "or both" makes it clear^[30] that it's a logical disjunction, not an exclusive or, which is more common in English.
3. The set of premises may be the empty set;^[33][34] an argument from an empty set of premises is valid if, and only if, the conclusion is a tautology.^[33][34]
4. The turnstile, for syntactic consequence, is of lower precedence than the comma, which represents premise combination, which in turn is of lower precedence than the arrow, used for material implication; so no parentheses are needed to interpret this formula.^[40]
5. A very general and abstract syntax is given here, following the notation in the SEP,^[2] but including the third definition, which is very commonly given explicitly by other sources, such as Gillon,^[10] Bostock,^[33] Allen & Hand,^[34] and many others. As noted elsewhere in the article, languages variously compose their set of atomic propositional variables from uppercase or lowercase letters (often focusing on P/p, Q/q, and R/r), with or without subscript numerals; and in their set of connectives, they may include either the full set of five typical connectives, ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$, or any of the truth-functionally complete subsets of it. (And, of course, they may also use any of the notational variants of these connectives.)
6. Note that the phrase "principle of composition" has referred to other things in other contexts, and even in the context of logic, since Bertrand Russell used it to refer to the principle that "a proposition which implies each of two propositions implies them both."^[49]
7. The name "interpretation" is used by some authors and the name "case" by other authors. This article will be indifferent and use either, since it is collaboratively edited and there is no consensus about which terminology to adopt.
8. A truth-functionally complete set of connectives^[2] is also called simply functionally complete, or adequate for truth-functional logic,^[35] or expressively adequate,^[72] or simply adequate.^[35][72]
9. Some of these definitions use the word "interpretation", and speak of sentences/formulas being true or false "under" it, and some will use the word "case", and speak of sentences/formulas being true or false "in" it. Published reliable sources (WP:RS) have used both kinds of terminological convention, although usually a given author will use only one of them. Since this article is collaboratively edited and there is no consensus about which convention to use, these variations in terminology have been left standing.
10. Conventionally ${\displaystyle \models \varphi }$, with nothing to the left of the turnstile, is used to symbolize a tautology. It may be interpreted as saying that ${\displaystyle \varphi }$ is a semantic consequence of the empty set of formulae, i.e., ${\displaystyle \{\}\models \varphi }$, but with the empty brackets omitted for simplicity;^[33] which is just the same as to say that it is a tautology, i.e., that there is no interpretation under which it is false.^[33]
11. To simplify the statement of the rule, the word "denial" here is used in this way: the denial of a formula ${\displaystyle \varphi }$ that is not a negation is ${\displaystyle -\varphi }$, whereas a negation, ${\displaystyle -\varphi }$, has two denials, viz., ${\displaystyle \varphi }$ and ${\displaystyle --\varphi }$.^[34]

References

1. "Propositional Logic | Internet Encyclopedia of Philosophy". Retrieved 22 March 2024.
2. Franks, Curtis (2023), "Propositional Logic", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Fall 2023 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
3. Weisstein, Eric W. "Propositional Calculus". mathworld.wolfram.com. Retrieved 22 March 2024.
4. Bělohlávek, Radim; Dauben, Joseph Warren; Klir, George J. (2017). Fuzzy logic and mathematics: a historical perspective. New York, NY, United States of America: Oxford University Press. p. 463. ISBN 978-0-19-020001-5.
5. Manzano, María (2005). Extensions of first order logic. Cambridge tracts in theoretical computer science (Digitally printed first paperback version ed.). Cambridge: Cambridge University Press. p. 180. ISBN 978-0-521-35435-6.
6. McGrath, Matthew; Frank, Devin (2023), "Propositions", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Winter 2023 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
7. "Predicate Logic". www3.cs.stonybrook.edu. Retrieved 22 March 2024.
8. "Philosophy 404: Lecture Five". www.webpages.uidaho.edu. Retrieved 22 March 2024.
9. "3.1 Propositional Logic". www.teach.cs.toronto.edu. Retrieved 22 March 2024.
10. Davis, Steven; Gillon, Brendan S., eds. (2004). Semantics: a reader. New York: Oxford University Press. ISBN 978-0-19-513697-5.
11. Plato, Jan von (2013). Elements of logical reasoning (1. publ ed.). Cambridge: Cambridge University press. pp. 9, 32, 121. ISBN 978-1-107-03659-8.
12. "Propositional Logic". www.cs.miami.edu. Retrieved 22 March 2024.
13. Plato, Jan von (2013). Elements of logical reasoning (1. publ ed.). Cambridge: Cambridge University press. p. 9. ISBN 978-1-107-03659-8.
14. Weisstein, Eric W. "Connective". mathworld.wolfram.com. Retrieved 22 March 2024.
15. "Propositional Logic | Brilliant Math & Science Wiki". brilliant.org. Retrieved 20 August 2020.
16. Bobzien, Susanne (1 January 2016). "Ancient Logic". In Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University – via Stanford Encyclopedia of Philosophy.
17. "Propositional Logic | Internet Encyclopedia of Philosophy". Retrieved 20 August 2020.
18. Bobzien, Susanne (2020), "Ancient Logic", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Summer 2020 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
19. Peckhaus, Volker (1 January 2014). "Leibniz's Influence on 19th Century Logic". In Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University – via Stanford Encyclopedia of Philosophy.
20. Hurley, Patrick (2007). A Concise Introduction to Logic 10th edition. Wadsworth Publishing. p. 392.
21. Beth, Evert W.; "Semantic entailment and formal derivability", series: Mededlingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde, Nieuwe Reeks, vol. 18, no. 13, Noord-Hollandsche Uitg. Mij., Amsterdam, 1955, pp. 309–42. Reprinted in Jaakko Intikka (ed.) The Philosophy of Mathematics, Oxford University Press, 1969
22. Truth in Frege
23. "Russell: the Journal of Bertrand Russell Studies".
24. Anellis, Irving H. (2012). "Peirce's Truth-functional Analysis and the Origin of the Truth Table". History and Philosophy of Logic. 33: 87–97. doi:10.1080/01445340.2011.621702. S2CID 170654885.
25. "Part2Mod1: LOGIC: Statements, Negations, Quantifiers, Truth Tables". www.math.fsu.edu. Retrieved 22 March 2024.
26. "Lecture Notes on Logical Organization and Critical Thinking". www2.hawaii.edu. Retrieved 22 March 2024.
27. "Logical Connectives". sites.millersville.edu. Retrieved 22 March 2024.
28. "Lecture1". www.cs.columbia.edu. Retrieved 22 March 2024.
29. "Introduction to Logic - Chapter 2". intrologic.stanford.edu. Retrieved 22 March 2024.
30. Beall, Jeffrey C. (2010). Logic: the basics (1. publ ed.). London: Routledge. pp. 6, 8, 14–16, 19–20, 44–48, 50–53, 56. ISBN 978-0-203-85155-5.
31. "Watson". watson.latech.edu. Retrieved 22 March 2024.
32. "Introduction to Theoretical Computer Science, Chapter 1". www.cs.odu.edu. Retrieved 22 March 2024.
33. Bostock, David (1997). Intermediate logic. Oxford : New York: Clarendon Press ; Oxford University Press. pp. 4–5, 8–13, 18–19, 22, 27, 29, 191, 194. ISBN 978-0-19-875141-0.
34. Allen, Colin; Hand, Michael (2022). Logic primer (3rd ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-54364-4.
35. Howson, Colin (1997). Logic with trees: an introduction to symbolic logic. London ; New York: Routledge. pp. ix, x, 5–6, 15–16, 20, 24–29, 38, 42–43, 47. ISBN 978-0-415-13342-5.
36. Stojnić, Una (2017). "One's Modus Ponens: Modality, Coherence and Logic". Philosophy and Phenomenological Research. 95 (1): 167–214. doi:10.1111/phpr.12307. ISSN 0031-8205. JSTOR 48578954.
37. Dutilh Novaes, Catarina (2022), "Argument and Argumentation", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Fall 2022 ed.), Metaphysics Research Lab, Stanford University, retrieved 5 April 2024
38. "Validity and Soundness | Internet Encyclopedia of Philosophy". Retrieved 5 April 2024.
39. Pelletier, Francis Jeffry; Hazen, Allen (2024), "Natural Deduction Systems in Logic", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Spring 2024 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
40. Restall, Greg (2018), "Substructural Logics", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Spring 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
41. "Compactness | Internet Encyclopedia of Philosophy". Retrieved 22 March 2024.
42. "Lecture Topics for Discrete Math Students". math.colorado.edu. Retrieved 22 March 2024.
43. Paseau, Alexander; Pregel, Fabian (2023), "Deductivism in the Philosophy of Mathematics", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Fall 2023 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
44. "Compactness | Internet Encyclopedia of Philosophy". Retrieved 22 March 2024.
45. Demey, Lorenz; Kooi, Barteld; Sack, Joshua (2023), "Logic and Probability", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Fall 2023 ed.), Metaphysics Research Lab, Stanford University, retrieved 22 March 2024
46. Kleene, Stephen Cole (2002). Mathematical logic (Dover ed.). Mineola, N.Y: Dover Publications. ISBN 978-0-486-42533-7.
47. Humberstone, Lloyd (2011). The connectives. Cambridge, Mass: MIT Press. pp. 118, 702. ISBN 978-0-262-01654-4. OCLC 694679197.
48. Smullyan, Raymond M. (1995). First-order logic. New York: Dover. pp. 5, 10–11, 14. ISBN 978-0-486-68370-6.
49. Russell, Bertrand (2010). Principles of mathematics. Routledge classics. London: Routledge. p. 17. ISBN 978-0-415-48741-2.
50. Hodges, Wilfrid (1977). Logic. Harmondsworth ; New York: Penguin. pp. 80–85. ISBN 978-0-14-021985-2.
51. Hansson, Sven Ove; Hendricks, Vincent F. (2018). Introduction to formal philosophy. Springer undergraduate texts in philosophy. Cham: Springer. p. 38. ISBN 978-3-030-08454-7.
52. Ayala-Rincón, Mauricio; de Moura, Flávio L.C. (2017). Applied Logic for Computer Scientists. Undergraduate Topics in Computer Science. Springer. p. 2. doi:10.1007/978-3-319-51653-0. ISBN 978-3-319-51651-6.
53. Lande, Nelson P. (2013). Classical logic and its rabbit holes: a first course. Indianapolis, Ind: Hackett Publishing Co., Inc. p. 20. ISBN 978-1-60384-948-7.
54. Goldrei, Derek (2005). Propositional and predicate calculus: a model of argument. London: Springer. p. 69. ISBN 978-1-85233-921-0.
55. "Propositional Logic". www.cs.rochester.edu. Retrieved 22 March 2024.
56. "Propositional calculus". www.cs.cornell.edu. Retrieved 22 March 2024.
57. Shramko, Yaroslav; Wansing, Heinrich (2021), "Truth Values", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Winter 2021 ed.), Metaphysics Research Lab, Stanford University, retrieved 23 March 2024
58. Metcalfe, David; Powell, John (2011). "Should doctors spurn Wikipedia?". Journal of the Royal Society of Medicine. 104 (12): 488–489. doi:10.1258/jrsm.2011.110227. ISSN 0141-0768. PMC 3241521. PMID 22179287.
59. Ayers, Phoebe; Matthews, Charles; Yates, Ben (2008). How Wikipedia works: and how you can be a part of it. San Francisco: No Starch Press. p. 22. ISBN 978-1-59327-176-3. OCLC 185698411.
60. Shapiro, Stewart; Kouri Kissel, Teresa (2024), "Classical Logic", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Spring 2024 ed.), Metaphysics Research Lab, Stanford University, retrieved 25 March 2024
61. Landman, Fred (1991). "Structures for Semantics". Studies in Linguistics and Philosophy. 45: 127. doi:10.1007/978-94-011-3212-1. ISBN 978-0-7923-1240-6. ISSN 0924-4662.
62. Nascimento, Marco Antonio Chaer (2015). Frontiers in quantum methods and applications in chemistry and physics: selected proceedings of QSCP-XVIII (Paraty, Brazil, December, 2013). Progress in theoretical chemistry and physics. International Workshop on Quantum Systems in Chemistry and Physics. Cham: Springer. p. 255. ISBN 978-3-319-14397-2.
63. Chowdhary, K.R. (2020). "Fundamentals of Artificial Intelligence". SpringerLink: 31–34. doi:10.1007/978-81-322-3972-7. ISBN 978-81-322-3970-3.
64. Restall, Greg; Standefer, Shawn (3 January 2023). Logical Methods. MIT Press. p. 76. ISBN 978-0-262-54484-9.
65. Hunter, Geoffrey (1971). Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press. ISBN 0-520-02356-0.
66. Restall, Greg (2010). Logic: an introduction. Fundamentals of philosophy. London: Routledge. pp. 5, 36–41, 55–60, 69. ISBN 978-0-415-40068-8.
67. Aloni, Maria (2023), "Disjunction", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Spring 2023 ed.), Metaphysics Research Lab, Stanford University, retrieved 23 March 2024
68. Makridis, Odysseus (2022). Symbolic logic. Palgrave philosophy today. Cham, Switzerland: Palgrave Macmillan. p. 119. ISBN 978-3-030-67395-6.
69. Burgess, John P. (2009). Philosophical logic. Princeton foundations of contemporary philosophy. Princeton: Princeton University Press. p. 5. ISBN 978-0-691-13789-6. OCLC 276141382.
70. Beall, J. C.; Restall, Greg (2006). Logical Pluralism. Clarendon Press. p. 38. ISBN 978-0-19-928840-3.
71. Levin, Oscar. Propositional Logic.
72. Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
73. Cunningham, Daniel W. (2016). Set theory: a first course. Cambridge mathematical textbooks. New York, NY: Cambridge University Press. ISBN 978-1-107-12032-7.
74. Genesereth, Michael; Kao, Eric J. (2017). Introduction to Logic. Synthesis Lectures on Computer Science. Cham: Springer International Publishing. p. 18. doi:10.1007/978-3-031-01801-5. ISBN 978-3-031-00673-9.
75. Rogers, Robert L. (1971). Mathematical Logic and Formalized Theories. Elsevier. pp. 38–39. doi:10.1016/c2013-0-11894-6. ISBN 978-0-7204-2098-2.
76. "6. Semantics of Propositional Logic — Logic and Proof 3.18.4 documentation". leanprover.github.io. Retrieved 28 March 2024.
77. "Knowledge Representation and Reasoning: Basics of Logics". www.emse.fr. Retrieved 28 March 2024.
78. "1.4: Tautologies and contradictions". Mathematics LibreTexts. 9 September 2021. Retrieved 29 March 2024.
79. Sylvestre, Jeremy. EF Tautologies and contradictions.
80. DeLancey, Craig; Woodrow, Jenna (2017). Elementary Formal Logic (1 ed.). Pressbooks.
81. Dix, J.; Fisher, Michael; Novak, Peter, eds. (2010). Computational logic in multi-agent systems: 10th international workshop, CLIMA X, Hamburg, Germany, September 9-10, 2009: revised selected and invited papers. Lecture notes in computer science. Berlin ; New York: Springer. p. 49. ISBN 978-3-642-16866-6. OCLC 681481210.
82. Prakken, Henry; Bistarelli, Stefano; Santini, Francesco; Taticchi, Carlo, eds. (2020). Computational models of argument: proceedings of comma 2020. Frontiers in artificial intelligence and applications. Washington: IOS Press. p. 252. ISBN 978-1-64368-106-1.
83. Awodey, Steve; Arnold, Greg Frost-, eds. (2024). Rudolf carnap: studies in semantics: the collected works of rudolf carnap, volume 7. New York: Oxford University Press. pp. xxvii. ISBN 978-0-19-289487-8.
84. Harel, Guershon; Stylianides, Andreas J., eds. (2018). Advances in Mathematics Education Research on Proof and Proving: An International Perspective. ICME-13 Monographs (1st ed. 2018 ed.). Cham: Springer International Publishing : Imprint: Springer. p. 181. ISBN 978-3-319-70996-3.
85. DeLancey, Craig (2017). "A Concise Introduction to Logic: §4. Proofs". Milne Publishing. Retrieved 23 March 2024.
86. Ferguson, Thomas Macaulay; Priest, Graham (23 June 2016), "semantic consequence", A Dictionary of Logic, Oxford University Press, doi:10.1093/acref/9780191816802.001.0001, ISBN 978-0-19-181680-2, retrieved 23 March 2024
87. Ferguson, Thomas Macaulay; Priest, Graham (23 June 2016), "syntactic consequence", A Dictionary of Logic, Oxford University Press, doi:10.1093/acref/9780191816802.001.0001, ISBN 978-0-19-181680-2, retrieved 23 March 2024
88. Cook, Roy T. (2009). A dictionary of philosophical logic. Edinburgh: Edinburgh University Press. pp. 82, 176. ISBN 978-0-7486-2559-8.
89. "Truth table | Boolean, Operators, Rules | Britannica". www.britannica.com. 14 March 2024. Retrieved 23 March 2024.
90. "MathematicalLogic". www.cs.yale.edu. Retrieved 23 March 2024.
91. "Analytic Tableaux". www3.cs.stonybrook.edu. Retrieved 23 March 2024.
92. "Formal logic - Semantic Tableaux, Proofs, Rules | Britannica". www.britannica.com. Retrieved 23 March 2024.
93. "Axiomatic method | Logic, Proofs & Foundations | Britannica". www.britannica.com. Retrieved 23 March 2024.
94. "Propositional Logic". mally.stanford.edu. Retrieved 23 March 2024.
95. "Natural Deduction | Internet Encyclopedia of Philosophy". Retrieved 23 March 2024.
96. Weisstein, Eric W. "Sequent Calculus". mathworld.wolfram.com. Retrieved 23 March 2024.
97. "Interactive Tutorial of the Sequent Calculus". logitext.mit.edu. Retrieved 23 March 2024.
98. Lucas, Peter; Gaag, Linda van der (1991). Principles of expert systems (PDF). International computer science series. Wokingham, England ; Reading, Mass: Addison-Wesley. p. 26. ISBN 978-0-201-41640-4.
99. Bachmair, Leo (2009). "CSE541 Logic in Computer Science" (PDF). Stony Brook University.
100. Lawson, Mark V. (2019). A first course in logic. Boca Raton: CRC Press, Taylor & Francis Group. pp. example 1.58. ISBN 978-0-8153-8664-3.
101. Dean, Neville (2003). Logic and language. Basingstoke: Palgrave Macmillan. p. 66. ISBN 978-0-333-91977-4.
102. Chiswell, Ian; Hodges, Wilfrid (2007). Mathematical logic. Oxford texts in logic. Oxford: Oxford university press. p. 3. ISBN 978-0-19-857100-1.
103. Hodges, Wilfrid (2001). Logic (2 ed.). London: Penguin Books. pp. 130–131. ISBN 978-0-14-100314-6.
104. Toida, Shunichi (2 August 2009). "Proof of Implications". CS381 Discrete Structures/Discrete Mathematics Web Course Material. Department of Computer Science, Old Dominion University. Retrieved 10 March 2010.
105. Lemmon, Edward John (1998). Beginning logic. Boca Raton, FL: Chapman & Hall/CRC. pp. passim, especially 39-40. ISBN 978-0-412-38090-7.
106. "Natural Deduction Systems in Logic > Notes (Stanford Encyclopedia of Philosophy)". plato.stanford.edu. Retrieved 19 April 2024.
107. Arthur, Richard T. W. (2017). An introduction to logic: using natural deduction, real arguments, a little history, and some humour (2nd ed.). Peterborough, Ontario: Broadview Press. ISBN 978-1-55481-332-2. OCLC 962129086.
108. Smullyan, Raymond M. (23 July 2014). A Beginner's Guide to Mathematical Logic. Courier Corporation. pp. 102–103. ISBN 978-0-486-49237-7.
109. Mendelsohn, Richard L. (10 January 2005). The Philosophy of Gottlob Frege. Cambridge University Press. p. 185. ISBN 978-1-139-44403-3.
110. Łukasiewicz, Jan (1970). Jan Lukasiewicz: Selected Works. North-Holland. p. 136.
111. Church, Alonzo (1996). Introduction to Mathematical Logic. Princeton University Press. p. 119. ISBN 978-0-691-02906-1.
112. "Proof Explorer - Home Page - Metamath". us.metamath.org. Retrieved 2 July 2024.
113. Walicki, Michał (2017). Introduction to mathematical logic (Extended ed.). New Jersey: World Scientific. p. 126. ISBN 978-981-4719-95-7.
114. W. V. O. Quine, Mathematical Logic (1980), p.81. Harvard University Press, 0-674-55451-5

Further reading

• Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY.
• Chang, C.C. and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
• Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978.
• Korfhage, Robert R. (1974), Discrete Computational Structures, Academic Press, New York, NY.
• Lambek, J. and Scott, P.J. (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK.
• Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.

Related works

• Hofstadter, Douglas (1979). Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books. ISBN 978-0-465-02656-2.

External links

• Klement, Kevin C. (2006), "Propositional Logic", in James Fieser and Bradley Dowden (eds.), Internet Encyclopedia of Philosophy, Eprint.
• Formal Predicate Calculus, contains a systematic formal development with axiomatic proof
• forall x: an introduction to formal logic, by P.D. Magnus, covers formal semantics and proof theory for sentential logic.
• Chapter 2 / Propositional Logic from Logic In Action
• Propositional sequent calculus prover on Project Nayuki. (note: implication can be input in the form !X|Y, and a sequent can be a single formula prefixed with > and having no commas)
• Propositional Logic - A Generative Grammar
• A Propositional Calculator that helps to understand simple expressions