Lógica de primer orden

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de junio de 2021; las comprobaciones requieren 2 ediciones .

La lógica de primer orden es un cálculo formal que permite afirmaciones sobre variables , funciones fijas y predicados . Extiende la lógica proposicional .

Además de la lógica de primer orden, también existen lógicas de orden superior , en las que los cuantificadores se pueden aplicar no solo a las variables, sino también a los predicados. Los términos lógica de predicados y cálculo de predicados pueden significar tanto lógica de primer orden como lógica de primer orden y lógica de orden superior juntas; en el primer caso, a veces se habla de pura lógica de predicados o puro cálculo de predicados .

Definiciones básicas

El lenguaje de la lógica de primer orden se construye sobre la base de una firma que consta de un conjunto de símbolos de funcióny un conjunto de símbolos de predicado. Cada símbolo de función y predicado tiene asociada una aridad , es decir, el número de argumentos posibles. Se permiten tanto los símbolos funcionales como los predicados de aridad 0. Los primeros a veces se separan en un conjunto separado de constantes . Además, se utilizan los siguientes caracteres adicionales: ${\ matemáticas {F}}$ ${\ matemáticas {P}}$

símbolos variables (generalmente , , , , , , , , etc.); $X$ $y$ $z$ $x_{1}$ $y_1$ $z_{1}$ $x_{2}$ $y_2$ $z_{2}$
operaciones lógicas:

Símbolo	Sentido
$\neg$	negativo (no)
$\tierra$	Conjunción ("y")
$\lor$	Disyunción ("o")
$\a$	Implicación ("si..., entonces...")

cuantificadores :

Símbolo	Sentido
$\para todos$	cuantificador universal
$\existe$	Cuantificador de existencia

caracteres de servicio: corchetes y coma .

Los símbolos enumerados junto con los símbolos de y forman el alfabeto de la lógica de primer orden . Las construcciones más complejas se definen inductivamente . ${\ matemáticas {P}}$ ${\ matemáticas {F}}$

Un término es un símbolo de una variable, o tiene la forma , donde es un símbolo funcional de aridad y son términos. $f(t_{1},\ldots,t_{n})$ $F$ $norte$ $t_{1},\ldots,t_{n}$
Un átomo (fórmula atómica) tiene la forma , donde es el símbolo de aridad del predicado , y son términos. $p(t_{1},\ldots,t_{n})$ $pags$ $norte$ $t_{1},\ldots,t_{n}$
- Por ejemplo, esta es una fórmula atómica que se cumple para cualquier número real . La fórmula consta de un predicado 2-ario , cuyos argumentos son términos y 0. Al mismo tiempo, el término consta de la constante 1 (que puede considerarse una función 0-aria), una variable y símbolos binarios (2 -ary) funciones + y ×. $(x+1)\times (x+1)\geqslant 0$ $X$ $\geqslant$ ${\ estilo de visualización (x + 1) \ veces (x + 1)}$ ${\ estilo de visualización (x + 1) \ veces (x + 1)}$ $X$
Una fórmula es un átomo o una de las siguientes construcciones: , , , , , , donde son funciones y es una variable. $\neg F$ $F_{1}\lor F_{2}$ $F_{1}\land F_{2}$ $F_{1}\a F_{2}$ $\para todo xF$ $\existe xF$ ${\ Displaystyle F, F_{1}, F_{2))$ $X$

Una variable se llama ligada en una fórmula si tiene la forma , o se puede representar en una de las formas , , , y ya está ligada en , y . Si no está ligado en , se llama libre en . Una fórmula sin variables libres se llama fórmula cerrada o oración . Una teoría de primer orden es cualquier conjunto de proposiciones. $X$ $F$ $F$ $\para todos xG$ $\existe xG$ $\neg H$ $F_{1}\lor F_{2}$ $F_{1}\land F_{2}$ $F_{1}\a F_{2}$ $X$ $H$ $F_{1}$ $F_{2}$ $X$ $F$ $F$

Axiomática y demostración de fórmulas

El sistema de axiomas lógicos de la lógica de primer orden consta de los axiomas del cálculo proposicional complementados por dos nuevos axiomas:

$\forall xA\to A[t/x]$ ,
$A[t/x]\a\existe xA$ ,

donde es la fórmula obtenida al sustituir el término por cada variable libre que aparece en la fórmula . ${\ estilo de visualización A [t/x]}$ $t$ $X$ $A$

La lógica de primer orden utiliza dos reglas de inferencia:

Modus ponens (esta regla también se usa en lógica proposicional): ${\frac {A,A\to B}{B}}$
Regla de generalización : ${\frac{A}{\forall xA}}$

Interpretación

En el caso clásico, la interpretación de las fórmulas lógicas de primer orden se da sobre el modelo de primer orden , que viene determinado por los siguientes datos:

juego de transporte , $\mathcal{D}$
Visualización de funciones semánticas $\sigma$
- cada símbolo de función -aria de a función -aria , $norte$ $F$ ${\ matemáticas {F}}$ $norte$ $\sigma (f)\dos puntos \,{\mathcal {D}}\times \ldots \times {\mathcal {D}}\rightarrow {\mathcal {D}}$
- cada símbolo de predicado -ario de la relación -ario . $norte$ $pags$ ${\ matemáticas {P}}$ $norte$ $\sigma (p)\subseteq {\mathcal {D}}\times \ldots \times {\mathcal {D}}$

Suele aceptarse identificar el conjunto de portadores y el propio modelo, lo que implica una función semántica implícita, si esto no genera ambigüedad. $\mathcal{D}$

Supongamos que es una función que asigna cada variable a algún elemento de , al que llamaremos sustitución . La interpretación del término on con respecto a la sustitución se da inductivamente : $s$ $\mathcal{D}$ $[\![t]\!]_{s}$ $t$ $\mathcal{D}$ $s$

$[\![x]\!]_{s}=s(x)$ , si es una variable, $X$
$[\![f(x_1,\ldots,x_n)]\!]_s = \sigma(f)([\!\![\,x_1]\!]_s,\ldots,[\![x_n]\ !]_s)$

En el mismo espíritu, se define la relación de la verdad de las fórmulas sobre relativamente : $\modelos_{s}$ $\mathcal{D}$ $s$

${\ matemáticas {D}} \ modelos _ {s} p (t_ {1}, \ ldots, t_ {n})$ , si y solo si , $\sigma(p)([\!\![\,t_1]\!]_s,\ldots,[\![t_n]\!]_s)$
${\ matemáticas {D}} \ modelos _ {s} \ neg \ phi$ , si y solo si - es falso, ${\ matemáticas {D}} \ modelos _ {s} \ phi$
${\ matemáticas {D}} \ modelos _ {s} \ phi \ tierra \ psi$ , si y sólo si y son verdaderas, ${\ matemáticas {D}} \ modelos _ {s} \ phi$ ${\ matemáticas {D}} \ modelos _ {s} \ psi$
${\ matemáticas {D}} \ modelos _ {s} \ phi \ lor \ psi$ , si y solo si o es verdadero, ${\ matemáticas {D}} \ modelos _ {s} \ phi$ ${\ matemáticas {D}} \ modelos _ {s} \ psi$
${\mathcal {D}}\models _{s}\phi \to \psi$ , si y solo si , ${\ matemáticas {D}} \ modelos _ {s} \ phi$ ${\ matemáticas {D}} \ modelos _ {s} \ psi$
${\mathcal {D}}\models _{s}\existe x\,\phi$ , si y solo si, para alguna sustitución , que difiere solo del valor de la variable , ${\mathcal {D}}\models_{{s'}}\phi$ $s'$ $s$ $X$
${\mathcal {D}}\models_{s}\forall x\,\phi$ , si y sólo si para todas las sustituciones , que difiere de sólo el valor de la variable . ${\mathcal {D}}\models_{{s'}}\phi$ $s'$ $s$ $X$

La fórmula es verdadera en (que se denota como ) si para todas las permutaciones . Una fórmula se llama válida (lo que se denota como ) si para todos los modelos . Una fórmula se llama satisfacible si para al menos uno . $\fi$ $\mathcal{D}$ ${\mathcal {D}}\modelos \phi$ ${\ matemáticas {D}} \ modelos _ {s} \ phi$ $s$ $\fi$ $\modelos\phi$ ${\mathcal {D}}\modelos \phi$ $\mathcal{D}$ $\fi$ ${\mathcal {D}}\modelos \phi$ $\mathcal{D}$

Propiedades y principales resultados

La lógica de primer orden tiene una serie de propiedades útiles que la hacen muy atractiva como herramienta básica para la formalización de las matemáticas . Los principales son:

completitud (esto significa que para cualquier fórmula cerrada, ya sea ella misma o su negación es derivable);
consistencia (ninguna fórmula puede derivarse simultáneamente con su negación).

Además, si la consistencia es más o menos obvia, entonces la completitud es un resultado no trivial obtenido por Gödel en 1930 ( teorema de completitud de Gödel ). En esencia, el teorema de Gödel establece una equivalencia fundamental entre los conceptos de demostrabilidad y validez .

La lógica de primer orden tiene la propiedad de compacidad , probada por Maltsev : si algún conjunto de fórmulas no es factible, entonces algunos de sus subconjuntos finitos tampoco lo son.

Según el teorema de Löwenheim-Skolem, si un conjunto de fórmulas tiene un modelo, entonces también tiene un modelo de cardinalidad contable como máximo . Relacionado con este teorema está la paradoja de Skolem , que, sin embargo, es solo una paradoja imaginaria .

Lógica de primer orden con igualdad

Muchas teorías de primer orden implican el símbolo de la igualdad. A menudo se lo denomina símbolo de la lógica y se complementa con los axiomas correspondientes que lo definen. Tal lógica se denomina lógica de primer orden con igualdad , y las teorías correspondientes se denominan teorías de primer orden con igualdad . El signo igual se introduce como un símbolo de predicado binario . Los axiomas adicionales introducidos para ello son los siguientes: $=$

${\ estilo de visualización \ para todos x (x = x)}$
$\para todo x\para todo y(x=y)\a (F(x)\a F(y))$

Uso

La lógica de primer orden como modelo de razonamiento formal

Al ser un análogo formalizado de la lógica ordinaria , la lógica de primer orden permite razonar estrictamente sobre la verdad y la falsedad de los enunciados y su relación, en particular, sobre la consecuencia lógica de un enunciado de otro o, por ejemplo, sobre su equivalencia. . Considere un ejemplo clásico de la formalización de declaraciones en lenguaje natural en lógica de primer orden .

Tomemos el razonamiento “Todo hombre es mortal. Sócrates es un hombre. Por lo tanto, Sócrates es mortal .” Denotemos "x es un hombre" a través de MAN (x) y "x es mortal" a través de MERTEN (x). Entonces el enunciado “toda persona es mortal” puede ser representado por la fórmula: x( HOMBRE (x) → MUERTE (x)) el enunciado “Sócrates es un hombre” por la fórmula HOMBRE ( Sócrates ), y “Sócrates es mortal” por la fórmula MUERTE ( Sócrates ). El enunciado como un todo ahora se puede escribir como $\para todos$

( x( HOMBRE (x) → MUERTE (x)) HOMBRE ( Sócrates )) → MUERTE ( Sócrates )

\para todos

{\ estilo de visualización \ tierra}

Véase también

Literatura

Gilbert D., Akkerman V. Fundamentos de lógica teórica. m., 1947
Kleene S.K. Introducción a las metamatemáticas. m., 1957
V. I. Markin. Lógica de predicados // Nueva Enciclopedia Filosófica : en 4 volúmenes / anterior. ed. científica consejo de V. S. Stepin . — 2ª ed., corregida. y adicional - M. : Pensamiento , 2010. - 2816 p.
Mendelson E. Introducción a la lógica matemática. M., 1976
Novikov PS Elementos de lógica matemática. m., 1959
Church A. Introducción a la lógica matemática, volumen I. M. 1960

diccionarios y enciclopedias	gran ruso Britannica (en línea) universalis

Lógicas

Filosofía • Semántica • Sintaxis • Historia

Grupos lógicos

lógica clásica	lógica aristotélica Lógica proposicional Lógica de primer orden Lógica de segundo orden lógica de orden superior
lógica matemática	teoría de conjuntos Teoría del modelo teoría de la computabilidad Teoría de la prueba y matemáticas constructivas lógica lineal sistema formal conclusión natural cálculo de secuencias Álgebra de la lógica Lógica relevante lógica deóntica lógica intuicionista cálculo de Lambek
Lógica no clásica	intuicionismo lógica difusa Lógica subestructural lógica Descripción lógica Lógica multivaluada Síntesis lógica Lógica vinculante Lógica temporal Lógica modal ( Lógica híbrida ) lógica epistémica
lógica filosófica	Pensamiento crítico lógica informal razonamiento deductivo

Componentes

Lista de símbolos booleanos