Lógica de primer orden

Lógica de primer orden: también conocida como lógica de predicados, lógica cuantificacional y cálculo de predicados de primer orden—es una colección de sistemas formales utilizados en matemáticas, filosofía, lingüística e informática. La lógica de primer orden usa variables cuantificadas sobre objetos no lógicos y permite el uso de oraciones que contienen variables, de modo que en lugar de proposiciones como "Sócrates es un hombre", uno puede tener expresiones en la forma & #34;existe x tal que x es Sócrates y x es un hombre", donde "existe" es un cuantificador, mientras que x es una variable. Esto la distingue de la lógica proposicional, que no utiliza cuantificadores ni relaciones; en este sentido, la lógica proposicional es el fundamento de la lógica de primer orden.

Una teoría sobre un tema suele ser una lógica de primer orden junto con un dominio de discurso específico (sobre el cual se extienden las variables cuantificadas), un número finito de funciones de ese dominio a sí mismo, un número finito de predicados definidos en ese dominio y un conjunto de axiomas que se cree valen sobre ellos. A veces, la "teoría" se entiende en un sentido más formal como solo un conjunto de oraciones en lógica de primer orden.

El adjetivo "de primer orden" distingue la lógica de primer orden de la lógica de orden superior, en la que hay predicados que tienen predicados o funciones como argumentos, o en la que se permite la cuantificación sobre predicados o funciones, o ambos. En las teorías de primer orden, los predicados a menudo se asocian con conjuntos. En las teorías interpretadas de orden superior, los predicados pueden interpretarse como conjuntos de conjuntos.

Hay muchos sistemas deductivos para la lógica de primer orden que son sólidos (es decir, todos los enunciados demostrables son verdaderos en todos los modelos) y completos (es decir, todos los enunciados que son verdaderos en todos los modelos son demostrables). Aunque la relación de consecuencia lógica es solo semidecidible, se ha avanzado mucho en la demostración automática de teoremas en lógica de primer orden. La lógica de primer orden también satisface varios teoremas metalógicos que la hacen susceptible de análisis en la teoría de la prueba, como el teorema de Löwenheim-Skolem y el teorema de compacidad.

La lógica de primer orden es el estándar para la formalización de las matemáticas en axiomas y se estudia en los fundamentos de las matemáticas. La aritmética de Peano y la teoría de conjuntos de Zermelo-Fraenkel son axiomatizaciones de la teoría de números y la teoría de conjuntos, respectivamente, en lógica de primer orden. Sin embargo, ninguna teoría de primer orden tiene la fuerza para describir de manera única una estructura con un dominio infinito, como los números naturales o la línea real. Los sistemas de axiomas que describen completamente estas dos estructuras (es decir, los sistemas de axiomas categóricos) se pueden obtener en lógicas más fuertes, como la lógica de segundo orden.

Los fundamentos de la lógica de primer orden fueron desarrollados de forma independiente por Gottlob Frege y Charles Sanders Peirce. Para una historia de la lógica de primer orden y cómo llegó a dominar la lógica formal, ver José Ferreirós (2001).

Introducción

Mientras que la lógica proposicional trata con proposiciones declarativas simples, la lógica de primer orden también cubre predicados y cuantificación.

Un predicado toma una entidad o entidades en el dominio del discurso y se evalúa como verdadero o falso. Considere las dos oraciones "Sócrates es un filósofo" y "Platón es un filósofo". En la lógica proposicional, estas oraciones se consideran no relacionadas y pueden indicarse, por ejemplo, mediante variables como p y q. El predicado "es un filósofo" ocurre en ambas oraciones, que tienen una estructura común de "a es un filósofo". La variable a se instancia como "Sócrates" en la primera oración, y se instancia como "Platón" en la segunda oración. Mientras que la lógica de primer orden permite el uso de predicados, como "es un filósofo" en este ejemplo, la lógica proposicional no lo hace.

Las relaciones entre predicados se pueden establecer mediante conectores lógicos. Considere, por ejemplo, la fórmula de primer orden "si a es un filósofo, entonces a es un erudito". Esta fórmula es una declaración condicional con "a es un filósofo" como su hipótesis, y "a es un erudito" como su conclusión. La verdad de esta fórmula depende del objeto denotado por a, y de las interpretaciones de los predicados "es un filósofo" y "es un erudito".

Los cuantificadores se pueden aplicar a variables en una fórmula. La variable a en la fórmula anterior se puede cuantificar universalmente, por ejemplo, con la oración de primer orden "Para cada a, si a es un filósofo, entonces a es un erudito". El cuantificador universal "para cada" en esta oración expresa la idea de que la afirmación "si a es un filósofo, entonces a es un erudito" se mantiene para todas las opciones de a.

La negación de la oración "Para todo a, si a es un filósofo, entonces a es un erudito" es lógicamente equivalente a la oración "Existe a tal que a es un filósofo y a no es un erudito". El cuantificador existencial "existe" expresa la idea de que el reclamo "a es un filósofo y a no es un erudito" se mantiene para alguna elección de a.

Los predicados "es un filósofo" y "es un erudito" cada uno toma una sola variable. En general, los predicados pueden tomar varias variables. En la oración de primer orden "Sócrates es el maestro de Platón", el predicado "es el maestro de" toma dos variables.

Una interpretación (o modelo) de una fórmula de primer orden especifica lo que significa cada predicado y las entidades que pueden instanciar las variables. Estas entidades forman el dominio del discurso o universo, que generalmente se requiere que sea un conjunto no vacío. Por ejemplo, en una interpretación con el dominio del discurso que consiste en todos los seres humanos y el predicado "es un filósofo" entendido como "fue el autor de la República", la oración "Existe a tal que a es un filosofo" es visto como verdadero, como lo atestigua Platón.

Hay dos partes clave de la lógica de primer orden. La sintaxis determina qué secuencias finitas de símbolos son expresiones bien formadas en lógica de primer orden, mientras que la semántica determina los significados detrás de estas expresiones.

Sintaxis

Alfabeto

A diferencia de los lenguajes naturales, como el inglés, el lenguaje de la lógica de primer orden es completamente formal, por lo que se puede determinar mecánicamente si una expresión determinada está bien formada. Hay dos tipos clave de expresiones bien formadas: términos, que representan objetos de forma intuitiva, y fórmulas, que expresan de forma intuitiva afirmaciones que pueden ser verdaderas o falsas. Los términos y fórmulas de la lógica de primer orden son cadenas de símbolos, donde todos los símbolos juntos forman el alfabeto del lenguaje. Como ocurre con todos los lenguajes formales, la naturaleza de los símbolos en sí está fuera del alcance de la lógica formal; a menudo se los considera simplemente como letras y signos de puntuación.

Es común dividir los símbolos del alfabeto en símbolos lógicos, que siempre tienen el mismo significado, y símbolos no-lógicos, cuyo significado varía por interpretación. Por ejemplo, el símbolo lógico ∧ ∧ {displaystyle land } siempre representa "y"; nunca se interpreta como "o", que es representado por el símbolo lógico Alternativa Alternativa {displaystyle lor }. Sin embargo, un símbolo predicado no-lógico como Phil(x) podría ser interpretado significar "x es un filósofo", "x es un hombre llamado Felipe", o cualquier otro predicado no deseado dependiendo de la interpretación a la mano.

Símbolos lógicos

Los símbolos lógicos son un conjunto de caracteres que varían según el autor, pero generalmente incluyen lo siguiente:

• Símbolos cuantificadores: О para la cuantificación universal, y ∃ para la cuantificación existencial
• Conectores lógicos: ∧ para conjunción, Alternativa por disyunción, → por implicación, Administración para bicondicional, ¬ por negligencia. Algunos autores utilizan Cpq en lugar de → y Epq en lugar de Administración, especialmente en contextos donde → se utiliza para otros fines. Además, la herradura . puede reemplazar →; el triple-bar ↑ puede reemplazar Administración; una inclinación (~), Np, o Fp puede reemplazar ¬; una barra doble .. {displaystylefn}, +{displaystyle +}, o Apq puede reemplazar Alternativa; y un ampersand ", Kpq, o el punto medio ⋅ puede reemplazar ∧, especialmente si estos símbolos no están disponibles por razones técnicas. (Los símbolos antes mencionados Cpq, Epq, Np, Apq, y Kpq son utilizados en la notación polaca.)
• Parentes, corchetes y otros símbolos de puntuación. La elección de tales símbolos varía dependiendo del contexto.
• Un conjunto infinito variables, a menudo denotado por letras minúsculas al final del alfabeto x, Sí., z,... Los subscriptos se utilizan a menudo para distinguir variables: x₀, x₁, x₂,....
• An Signatura de igualdad (a veces, Signatura de identidad) = (ver § Equality and its axioms below).

No todos estos símbolos son necesarios en la lógica de primer orden. Cualquiera de los cuantificadores junto con la negación, la conjunción (o disyunción), las variables, los paréntesis y la igualdad son suficientes.

Otros símbolos lógicos incluyen los siguientes:

• Constantes de la verdad: T, V, o ⊤ para "verdad" y F, O, o ⊥ para "falso" (V y O son de notación polaca). Sin tales operadores lógicos de valence 0, estas dos constantes sólo se pueden expresar usando cuantificadores.
• Conectividades lógicas adicionales como el trazo Sheffer, Dpq (NAND), y exclusiva o, Jpq.

Símbolos no lógicos

Los símbolos no lógicos representan predicados (relaciones), funciones y constantes. Solía ser una práctica estándar usar un conjunto fijo e infinito de símbolos no lógicos para todos los propósitos:

• Por cada entero n≥ 0, hay una colección de n-ary, o n-lugar, símbolos predicados. Porque representan relaciones entre n elementos, también se llaman relación símbolos. Por cada aridad n, hay un suministro infinito de ellos:

  Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃,...

• Por cada entero n≥ 0, hay infinitamente muchos n- símbolos de función:

  f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃,...

Cuando la aridad de un símbolo de predicado o símbolo de función es clara por el contexto, el superíndice n a menudo se omite.

En este enfoque tradicional, solo hay un lenguaje de lógica de primer orden. Este enfoque sigue siendo común, especialmente en libros de orientación filosófica.

Una práctica más reciente es utilizar diferentes símbolos no lógicos según la aplicación que se tenga en mente. Por lo tanto, se ha vuelto necesario nombrar el conjunto de todos los símbolos no lógicos usados en una aplicación particular. Esta elección se realiza a través de una firma.

Las firmas típicas en matemáticas son {1, ×} o simplemente {×} para grupos, o {0, 1, +, ×, <} para campos ordenados. No hay restricciones en el número de símbolos no lógicos. La firma puede ser vacía, finita o infinita, incluso incontable. Las firmas incontables ocurren, por ejemplo, en las demostraciones modernas del teorema de Löwenheim-Skolem.

Aunque las firmas pueden implicar en algunos casos cómo deben interpretarse los símbolos no lógicos, la interpretación de los símbolos no lógicos en la firma es independiente (y no necesariamente fija). Las firmas se refieren a la sintaxis más que a la semántica.

En este enfoque, cada símbolo no lógico es de uno de los siguientes tipos:

• A símbolo predicado (o relación símboloCon algunos Valence (o arity, número de argumentos) mayor o igual a 0. Estas letras suelen ser denotadas por mayúsculas como P, Q y R. Ejemplos:
  • In P()x), P es un símbolo predicado de valence 1. Una posible interpretación es "x es un hombre".
  • In Q()x,Sí.), Q es un símbolo predicado de valence 2. Posibles interpretaciones incluyen "x es mayor que Sí."y"x es el padre de Sí.".
  • Las relaciones de valence 0 se pueden identificar con variables proposiciones, que pueden soportar cualquier declaración. Una posible interpretación de R "Sócrates es un hombre".
• A símbolo de la función, con algún valence mayor o igual a 0. Estos son a menudo denotados por letras romanas minúsculas tales como f, g y h. Ejemplos:
  • f()x) puede ser interpretado como "el padre de x". En aritmética, puede soportar "-x". En la teoría de conjuntos, puede soportar "el conjunto de poder de x".
  • En aritmética, g()x,Sí.) puede soportar "x+Sí.". En la teoría de conjuntos, puede significar "la unión de x y Sí.".
  • Los símbolos de función de valence 0 se llaman símbolos constantes, y a menudo se denotan por letras minúsculas al principio del alfabeto como a, b y c. El símbolo a Puede defender a Sócrates. En aritmética, puede soportar 0. En teoría de conjuntos, puede soportar el conjunto vacío.

El enfoque tradicional se puede recuperar en el enfoque moderno, simplemente especificando el "personalizado" la firma consiste en las secuencias tradicionales de símbolos no lógicos.

Reglas de formación

.índice■ ::= "
Silencio .índice■ "
.variable■ ::= "x" .índice■.constante■ ::= "c" .índice■.función■ ::= "f1" .índice■.función binaria■ ::= "f2" .índice■.Función ternaria■ ::= "f3" .índice■.unry predicate■ ::= "p1" .índice■.binario predicate■ ::= "p2" .índice■.ternary predicate■ ::= "p3" .índice■.mandato■ ::= .variable■ Silencio .constante■ Silencio .función■ "(.mandato■ ")"
Silencio .función binaria■ "(.mandato■ " .mandato■ ")"
Silencio .Función ternaria■ "(.mandato■ " .mandato■ " .mandato■ ")"
.fórmula atómica■ ::= "TRUE"
"FALSE"
Silencio .mandato■ "=" .mandato■Silencio .unry predicate■ "(.mandato■ ")"
Silencio .binario predicate■ "(.mandato■ " .mandato■ ")"
Silencio .ternary predicate■ "(.mandato■ " .mandato■ " .mandato■ ")"
.fórmula■ ::= .fórmula atómica■ Silencio "¬" .fórmula■Silencio .fórmula■ "Dejar" .fórmula■Silencio .fórmula■ "Ley" .fórmula■Silencio .fórmula■ "⇒" .fórmula■Silencio .fórmula■ "Animación" .fórmula■Silencio .fórmula■ ")"
TENIDO "ÉL" .variable■ .fórmula■Silencio .variable■ .fórmula■

Las reglas de formación definen los términos y fórmulas de la lógica de primer orden. Cuando los términos y fórmulas se representan como cadenas de símbolos, estas reglas se pueden usar para escribir una gramática formal para términos y fórmulas. Estas reglas generalmente son independientes del contexto (cada producción tiene un solo símbolo en el lado izquierdo), excepto que se puede permitir que el conjunto de símbolos sea infinito y puede haber muchos símbolos de inicio, por ejemplo, las variables en el caso de los términos.

Términos

El conjunto de términos se define inductivamente por las siguientes reglas:

• Variables. Cualquier símbolo variable es un término.
• Funciones. Si f es un n- Símbolo de función diario, y t₁,... t_n son términos, entonces f()t₁,...t_n) es un término. En particular, los símbolos que denotan las constantes individuales son símbolos de función nula, y por lo tanto son términos.

Solo las expresiones que pueden obtenerse mediante un número finito de aplicaciones de las reglas 1 y 2 son términos. Por ejemplo, ninguna expresión que implique un símbolo de predicado es un término.

Fórmulas

El conjunto de fórmulas (también llamadas fórmulas bien formadas o WFF) se define inductivamente por las siguientes reglas:

• Predicar símbolos. Si P es un n- Símbolo predicado y t₁,... t_n son términos entonces P()t₁,...t_n) es una fórmula.
• Igualdad. Si el símbolo de igualdad es considerado parte de la lógica, y t₁ y t₂ son términos, entonces t₁ = t₂ es una fórmula.
• Negación. Si φ φ {displaystyle varphi } es una fórmula, entonces ¬ ¬ φ φ {displaystyle lnot varphi } es una fórmula.
• Conectores binarios. Si φ φ {displaystyle varphi } y ↑ ↑ {displaystyle psi } son fórmulas, entonces (φ φ → → ↑ ↑ {displaystyle varphi rightarrow psi }) es una fórmula. Reglas similares se aplican a otros conectores lógicos binarios.
• Cuantificadores. Si φ φ {displaystyle varphi } es una fórmula y x es una variable, entonces О О xφ φ {displaystyle forall xvarphi } (para todos x, φ φ {displaystyle varphi } ostentos) y ∃ ∃ xφ φ {displaystyle exists xvarphi } (hay x tal que φ φ {displaystyle varphi }) son fórmulas.

Solo las expresiones que pueden obtenerse mediante un número finito de aplicaciones de las reglas 1 a 5 son fórmulas. Las fórmulas obtenidas a partir de las dos primeras reglas se denominan fórmulas atómicas.

Por ejemplo,

О О xО О Sí.()P()f()x))→ → ¬ ¬ ()P()x)→ → Q()f()Sí.),x,z))){displaystyle forall xforall y(P(f(x))rightarrow neg (P(x)rightarrow Q(f(y),x,z))}

es una fórmula, si f es un símbolo de función no deseado, P un símbolo predicado no deseado, y Q un símbolo predicado ternario. Sin embargo, О О xx→ → {displaystyle forall x,xrightarrow } no es una fórmula, aunque es una cadena de símbolos del alfabeto.

La función de los paréntesis en la definición es garantizar que cualquier fórmula solo se pueda obtener de una manera: siguiendo la definición inductiva (es decir, hay un árbol de análisis único para cada fórmula). Esta propiedad se conoce como legibilidad única de fórmulas. Existen muchas convenciones para el uso de paréntesis en las fórmulas. Por ejemplo, algunos autores usan dos puntos o puntos en lugar de paréntesis, o cambian los lugares en los que se insertan los paréntesis. La definición particular de cada autor debe ir acompañada de una prueba de legibilidad única.

Esta definición de una fórmula no admite la definición de una función if-then-else ite(c, a, b), donde "c" es una condición expresada como una fórmula, que devolvería "a" si c es verdadera y "b" si es falso. Esto se debe a que tanto los predicados como las funciones solo pueden aceptar términos como parámetros, pero el primer parámetro es una fórmula. Algunos lenguajes basados en lógica de primer orden, como SMT-LIB 2.0, agregan esto.

Convenciones de notación

Por conveniencia, se han desarrollado convenciones sobre la precedencia de los operadores lógicos, para evitar la necesidad de escribir paréntesis en algunos casos. Estas reglas son similares al orden de las operaciones en aritmética. Una convención común es:

• ¬ ¬ {displaystyle lnot } se evalúa primero
• ∧ ∧ {displaystyle land } y Alternativa Alternativa {displaystyle lor } se evalúan próximamente
• Los cuantificadores se evalúan próximamente
• → → {displaystyle to } es evaluado último.

Además, se pueden insertar signos de puntuación adicionales no requeridos por la definición para facilitar la lectura de las fórmulas. Así la fórmula

¬ ¬ О О xP()x)→ → ∃ ∃ x¬ ¬ P()x){displaystyle lnot forall xP(x)to exists xlnot P(x)}

podría escribirse como

()¬ ¬ [О О xP()x)])→ → ∃ ∃ x[¬ ¬ P()x)].{displaystyle (lnot [forall xP(x)])to exists x[lnot P(x)].}

En algunos campos, es común usar notación de infijos para funciones y relaciones binarias, en lugar de la notación de prefijos definida anteriormente. Por ejemplo, en aritmética, normalmente se escribe "2 + 2 = 4" en lugar de "=(+(2,2),4)". Es común considerar las fórmulas en notación infija como abreviaturas de las fórmulas correspondientes en notación prefija, cf. también estructura de términos vs. representación.

Las definiciones anteriores utilizan notación de infijo para conexiones binarias tales como → → {displaystyle to }. Una convención menos común es la notación polaca, en la que se escribe → → {displaystyle rightarrow }, ∧ ∧ {displaystyle wedge } y así delante de sus argumentos en lugar de entre ellos. Esta convención es ventajosa porque permite descartar todos los símbolos de puntuación. Como tal, la notación polaca es compacta y elegante, pero raramente utilizada en la práctica porque es difícil para los humanos leer. En la notación polaca, la fórmula

О О xО О Sí.()P()f()x))→ → ¬ ¬ ()P()x)→ → Q()f()Sí.),x,z))){displaystyle forall xforall y(P(f(x))rightarrow neg (P(x)rightarrow Q(f(y),x,z))}

se convierte en "∀x∀y→Pfx¬→ PxQfyxz".

Variables libres y enlazadas

En una fórmula, una variable puede aparecer libre o limitada (o ambas). Intuitivamente, una ocurrencia variable está libre en una fórmula si no está cuantificada: en ∀y P(x, y), la única aparición de la variable x está libre mientras que la de y está vinculada. Las ocurrencias de variables libres y ligadas en una fórmula se definen inductivamente de la siguiente manera.

Fórmulas atómicas

Si φ es una fórmula atómica, entonces x ocurre libre en φ si x ocurre en φ. Además, no hay variables ligadas en ninguna fórmula atómica.

Negación

x se produce gratis en ¬φ si x ocurre libre en φ. x ocurre atado en ¬φ si x ocurre obligado en φ

Conectores binarios

x ocurre libre en (φ → ↑Si y sólo si x ocurre libre en cualquiera φ o ↑. x ocurre obligado en (φ → ↑Si y sólo si x ocurre obligado en cualquiera φ o ↑. La misma regla se aplica a cualquier otro conector binario en lugar de →.

Cuantificadores

x ocurre libre en ОSí. φ, si y sólo si x ocurre libre en φ y x es un símbolo diferente de Sí.. También, x ocurre obligado en ОSí. φ, si y sólo si x es Sí. o x ocurre obligado en φ. La misma regla tiene ∃ en lugar de О.

Por ejemplo, en ∀x ∀y (P(x) → Q(x,f(x),z)) , x y y aparecen solo enlazados, z solo aparecen libres y w no es ninguno porque no aparece en la fórmula.

Las variables libres y ligadas de una fórmula no necesitan ser conjuntos disjuntos: en la fórmula P(x) → ∀ x Q(x), la primera ocurrencia de x, como argumento de P, es libre mientras que el segundo, como argumento de Q, está ligado.

Una fórmula en lógica de primer orden sin ocurrencias de variables libres se denomina oración de primer orden. Estas son las fórmulas que tendrán valores de verdad bien definidos bajo una interpretación. Por ejemplo, si una fórmula como Phil(x) es verdadera debe depender de lo que representa x. Pero la oración ∃x Phil(x) será verdadera o falsa en una interpretación dada.

Ejemplo: grupos abelianos ordenados

En matemáticas, el lenguaje de los grupos abelianos ordenados tiene un símbolo constante 0, un símbolo de función unaria −, un símbolo de función binaria + y un símbolo de relación binaria ≤. Después:

• Las expresiones +(x, Sí.) y +(x, +(Sí., −z)) términos. Estos son generalmente escritos como x + Sí. y x + Sí. − z.
• Las expresiones +(x, Sí.) = 0 y ≤(+(x, +(Sí., −z)), +(x, Sí.) fórmulas atómicas. Estos son generalmente escritos como x + Sí. = 0 y x + Sí. − z ≤ x + Sí..
• La expresión ()О О xО О Sí.[≤ ≤ ⁡ ⁡ ()+⁡ ⁡ ()x,Sí.),z)→ → О О xО О Sí.+⁡ ⁡ ()x,Sí.)=0)]{displaystyle (forall xforall y,[Mathop {leq } (mathop {+} (x,y),z)to forall x,forall y,mathop {+} (x,y)=0)}} es un fórmula, que generalmente se escribe como О О xО О Sí.()x+Sí.≤ ≤ z)→ → О О xО О Sí.()x+Sí.=0).{displaystyle forall xforall y(x+yleq z)to forall xforall y(x+y=0). } Esta fórmula tiene una variable libre, z.

Los axiomas para grupos abelianos ordenados pueden expresarse como un conjunto de oraciones en el idioma. Por ejemplo, el axioma que indica que el grupo es conmutativo generalmente se escribe ()О О x)()О О Sí.)[x+Sí.=Sí.+x].{displaystyle (forall x)(forall y)[x+y=y+x].}

Semántica

Una interpretación de un lenguaje de primer orden asigna una denotación a cada símbolo no lógico (símbolo de predicado, símbolo de función o símbolo de constante) en ese lenguaje. También determina un dominio de discurso que especifica el rango de los cuantificadores. El resultado es que a cada término se le asigna un objeto que representa, a cada predicado se le asigna una propiedad de los objetos ya cada oración se le asigna un valor de verdad. De esta manera, una interpretación proporciona significado semántico a los términos, predicados y fórmulas del lenguaje. El estudio de las interpretaciones de los lenguajes formales se denomina semántica formal. Lo que sigue es una descripción de la semántica estándar o tarskiana para la lógica de primer orden. (También es posible definir la semántica del juego para la lógica de primer orden, pero además de requerir el axioma de elección, la semántica del juego concuerda con la semántica tarskiana para la lógica de primer orden, por lo que la semántica del juego no se elaborará aquí).

Estructuras de primer orden

La forma más común de especificar una interpretación (especialmente en matemáticas) es especificar una estructura (también llamada modelo; ver más abajo). La estructura consta de un dominio de discurso D y una función de interpretación I mapeando símbolos no lógicos a predicados, funciones y constantes.

El dominio del discurso D es un conjunto no vacío de "objetos" de algún tipo. Intuitivamente, dada una interpretación, una fórmula de primer orden se convierte en una declaración sobre estos objetos; por ejemplo, ∃ ∃ xP()x){displaystyle exists xP(x)} declara la existencia de algún objeto en D para el cual el predicado P es cierto (o, más precisamente, para el cual el predicado asignado al símbolo predicado P por la interpretación es verdad). Por ejemplo, uno puede tomar D para ser el conjunto de enteros.

Los símbolos no lógicos se interpretan de la siguiente manera:

• La interpretación de una n- Símbolo de función diario es una función Dⁿ a D. Por ejemplo, si el dominio del discurso es el conjunto de enteros, un símbolo de función f de la aridad 2 se puede interpretar como la función que da la suma de sus argumentos. En otras palabras, el símbolo f se asocia con la función I()f){displaystyle I(f)} que, en esta interpretación, es adicional.

• La interpretación de un símbolo constante (un símbolo de función de la aridad 0) es una función de D⁰ (un conjunto cuyo único miembro es el tuple vacío) a D, que se puede identificar simplemente con un objeto en D. Por ejemplo, una interpretación puede asignar el valor I()c)=10{displaystyle I(c)=10} al símbolo constante c{displaystyle c}.

• La interpretación de una n- El símbolo predicado es un conjunto de n-tuples of elements of D, dando los argumentos para los cuales el predicado es verdad. Por ejemplo, una interpretación I()P){displaystyle I(P)} de un símbolo de predicación binaria P puede ser el conjunto de pares de enteros tal que el primero es menos que el segundo. Según esta interpretación, el predicado P sería cierto si su primer argumento es menos que su segundo argumento. Equivalentemente, símbolos predicados pueden ser asignados funciones de valor booleano de Dⁿ a {}true,false}{displaystyle{mathrm {true,false}} {fnMicrosoft Sans Serif}}.

Evaluación de valores de verdad

Una fórmula evalúa a verdadero o falso dada una interpretación y una asignación variable μ que asocia un elemento del dominio del discurso con cada variable. La razón por la que se requiere una asignación variable es dar significados a fórmulas con variables libres, como Sí.=x{displaystyle y=x}. El valor de verdad de esta fórmula cambia dependiendo de si x y Sí. denota al mismo individuo.

Primero, la asignación variable μ se puede extender a todos los términos del idioma, con el resultado de que cada término se asigna a un solo elemento del dominio del discurso. Las siguientes reglas se utilizan para hacer esta asignación:

• Variables. Cada variable x evaluar a μ()x)
• Funciones. Condiciones t1,...... ,tn{displaystyle t_{1},ldotst_{n} que se han evaluado a los elementos d1,...... ,dn{displaystyle ################################################################################################################################################################################################################################################################ del dominio del discurso, y n- Símbolo de función f, el término f()t1,...... ,tn){displaystyle f(t_{1},ldotst_{n}} evaluar a ()I()f))()d1,...... ,dn){displaystyle (I(f))(d_{1},ldotsd_{n}}.

A continuación, a cada fórmula se le asigna un valor de verdad. La definición inductiva utilizada para realizar esta asignación se denomina esquema T.

• Fórmulas atómicas (1). Una fórmula P()t1,...... ,tn){displaystyle P(t_{1},ldotst_{n}} se asocia el valor verdadero o falso dependiendo de si .. v1,...... ,vn.. ▪ ▪ I()P){displaystyle langle v_{1},ldotsv_{n}rangle in I(P)}, donde v1,...... ,vn{displaystyle v_{1},ldotsv_{n} son la evaluación de los términos t1,...... ,tn{displaystyle t_{1},ldotst_{n} y I()P){displaystyle I(P)} es la interpretación de P{displaystyle P}, que por suposición es un subconjunto Dn{displaystyle D^{n}.
• Fórmulas atómicas (2). Una fórmula t1=t2{displaystyle T_{1}=t_{2} se asigna verdadero si t1{displaystyle T_{1} y t2{displaystyle T_{2} evaluar al mismo objeto del dominio del discurso (ver la sección sobre igualdad abajo).
• Conectores lógicos. Una fórmula en la forma ¬ ¬ φ φ {displaystyle neg varphi }, φ φ → → ↑ ↑ {displaystyle varphi rightarrow psi }, etc. se evalúa según la tabla de la verdad para el conjuntivo en cuestión, como en la lógica proposicional.
• Cuantificadores existenciales. Una fórmula ∃ ∃ xφ φ ()x){displaystyle exists xvarphi (x)} es verdad M y μ μ {displaystyle mu } si existe una evaluación μ μ .{displaystyle mu} de las variables que sólo difieren de μ μ {displaystyle mu } relativa a la evaluación x y tal que φ es verdad según la interpretación M y la asignación variable μ μ .{displaystyle mu}. Esta definición formal captura la idea de que ∃ ∃ xφ φ ()x){displaystyle exists xvarphi (x)} es cierto si y sólo si hay una manera de elegir un valor para x tal que φ(x) está satisfecho.
• Cuantificadores universales. Una fórmula О О xφ φ ()x){displaystyle forall xvarphi (x)} es verdad M y μ μ {displaystyle mu } si φ(x) es verdad para cada par compuesto por la interpretación M y una asignación variable μ μ .{displaystyle mu} que difiere de μ μ {displaystyle mu } sólo en el valor de x. Esto captura la idea de que О О xφ φ ()x){displaystyle forall xvarphi (x)} es verdad si cada posible elección de un valor para x causas φ(xPara ser verdad.

Si una fórmula no contiene variables libres, y así es una frase, entonces la asignación variable inicial no afecta su valor de verdad. En otras palabras, una frase es verdadera según M y μ μ {displaystyle mu } si y sólo si es verdad M y cada otra asignación variable μ μ .{displaystyle mu}.

Existe un segundo enfoque común para definir valores de verdad que no se basa en funciones de asignación de variables. En cambio, dada una interpretación M, primero se agrega a la firma una colección de símbolos constantes, uno para cada elemento del dominio del discurso en M; digamos que para cada d en el dominio el símbolo constante c_d es fijo. La interpretación se amplía para que cada nuevo símbolo constante se asigne a su correspondiente elemento del dominio. Uno ahora define la verdad para fórmulas cuantificadas sintácticamente, como sigue:

• Cuantificadores existenciales (alternados). Una fórmula ∃ ∃ xφ φ ()x){displaystyle exists xvarphi (x)} es verdad M si hay algo d en el dominio del discurso tal que φ φ ()cd){displaystyle varphi (c_{d})} sostiene. Aquí. φ φ ()cd){displaystyle varphi (c_{d})} es el resultado de la sustitución c_d para cada ocurrencia libre de x en φ.
• cuantificadores universales (alternate). Una fórmula О О xφ φ ()x){displaystyle forall xvarphi (x)} es verdad M si, por cada d en el dominio del discurso, φ φ ()cd){displaystyle varphi (c_{d})} es verdad M.

Este enfoque alternativo otorga exactamente los mismos valores de verdad a todas las oraciones que el enfoque a través de asignaciones de variables.

Validez, satisfacibilidad y consecuencia lógica

Si una frase φ evalúa a verdadero en virtud de una interpretación dada M, uno dice que M satisfizo φ; esto es denotado M⊨ ⊨ φ φ {displaystyle MvDash varphi }. Una oración satisfizo si hay alguna interpretación bajo la cual es verdad. Esto es un poco diferente del símbolo ⊨ ⊨ {displaystyle vDash } de la teoría modelo, donde M⊨ ⊨ φ φ {displaystyle MvDash phi } denota la satisfiabilidad en un modelo, es decir, "hay una asignación adecuada de valores en M{displaystyle M}'s dominio a símbolos variables φ φ {displaystyle phi }".

La satisfacción de las fórmulas con variables libres es más complicada, porque una interpretación por sí sola no determina el valor verdadero de tal fórmula. La convención más común es que una fórmula φ con variables libres x1{displaystyle x_{1}},... xn{displaystyle x_{n} se dice que está satisfecho por una interpretación si la fórmula φ sigue siendo verdadera independientemente de qué individuos del dominio del discurso son asignados a sus variables libres x1{displaystyle x_{1}},... xn{displaystyle x_{n}. Esto tiene el mismo efecto que decir que una fórmula φ está satisfecha si y sólo si su cierre universal О О x1...... О О xnφ φ ()x1,...... ,xn){displaystyle forall x_{1}dots forall x_{n}phi (x_{1},dotsx_{n}) } está satisfecho.

Una fórmula es lógicamente válida (o simplemente válida) si es verdadera en todas las interpretaciones. Estas fórmulas juegan un papel similar a las tautologías en la lógica proposicional.

Una fórmula φ es una consecuencia lógica de una fórmula ψ si toda interpretación que hace verdadera a ψ también hace verdadera a φ. En este caso se dice que φ está implícita lógicamente en ψ.

Algebraizaciones

Un enfoque alternativo a la semántica de la lógica de primer orden procede a través del álgebra abstracta. Este enfoque generaliza las álgebras de Lindenbaum-Tarski de la lógica proposicional. Hay tres formas de eliminar variables cuantificadas de la lógica de primer orden que no implican reemplazar los cuantificadores con otros operadores de términos vinculantes de variables:

• Álgebra cínica, por Alfred Tarski y colegas;
• Álgebra poliádica, de Paul Halmos;
• Predicar la lógica del funerario, principalmente debido a Willard Quine.

Estas álgebras son retículas que extienden correctamente el álgebra booleana de dos elementos.

Tarski y Givant (1987) demostraron que el fragmento de lógica de primer orden que no tiene una oración atómica que se encuentra en el ámbito de más de tres cuantificadores tiene el mismo poder expresivo que el álgebra de relaciones. Este fragmento es de gran interés porque es suficiente para la aritmética de Peano y la teoría de conjuntos más axiomática, incluida la ZFC canónica. También prueban que la lógica de primer orden con un par ordenado primitivo es equivalente a un álgebra de relaciones con dos funciones de proyección de pares ordenados.

Teorías de primer orden, modelos y clases elementales

Una teoría de primer orden de una firma particular es un conjunto de axiomas, que son oraciones que consisten en símbolos de esa firma. El conjunto de axiomas suele ser finito o recursivamente enumerable, en cuyo caso la teoría se llama efectiva. Algunos autores exigen que las teorías también incluyan todas las consecuencias lógicas de los axiomas. Se considera que los axiomas se mantienen dentro de la teoría y de ellos se pueden derivar otras oraciones que se mantienen dentro de la teoría.

Se dice que una estructura de primer orden que satisface todas las oraciones en una teoría dada es un modelo de la teoría. Una clase elemental es el conjunto de todas las estructuras que satisfacen una teoría particular. Estas clases son un tema principal de estudio en la teoría de modelos.

Muchas teorías tienen una interpretación prevista, un determinado modelo que se tiene en cuenta al estudiar la teoría. Por ejemplo, la interpretación prevista de la aritmética de Peano consiste en los números naturales habituales con sus operaciones habituales. Sin embargo, el teorema de Löwenheim-Skolem muestra que la mayoría de las teorías de primer orden también tendrán otros modelos no estándar.

Una teoría es consistente si no es posible demostrar una contradicción a partir de los axiomas de la teoría. Una teoría es completa si, para cada fórmula en su firma, esa fórmula o su negación es una consecuencia lógica de los axiomas de la teoría. El teorema de incompletitud de Gödel muestra que las teorías efectivas de primer orden que incluyen una porción suficiente de la teoría de los números naturales nunca pueden ser consistentes y completas.

Dominios vacíos

La definición anterior requiere que el dominio del discurso de cualquier interpretación no debe estar vacío. Hay configuraciones, como la lógica inclusiva, donde se permiten dominios vacíos. Además, si una clase de estructuras algebraicas incluye una estructura vacía (por ejemplo, hay un poset vacío), esa clase solo puede ser una clase elemental en lógica de primer orden si se permiten dominios vacíos o si se elimina la estructura vacía de la clase..

Sin embargo, existen varias dificultades con los dominios vacíos:

• Muchas reglas comunes de la inferencia sólo son válidas cuando el dominio del discurso es requerido para ser no vacío. Un ejemplo es la regla que dice que φ φ Alternativa Alternativa ∃ ∃ x↑ ↑ {displaystyle varphi lor exists xpsi } implicación ∃ ∃ x()φ φ Alternativa Alternativa ↑ ↑ ){displaystyle exists x(varphi lor psi)} cuando x no es una variable libre en φ φ {displaystyle varphi }. Esta regla, que se utiliza para poner fórmulas en forma normal prenexo, es el sonido en dominios no vacíos, pero no sonoro si se permite el dominio vacío.
• La definición de verdad en una interpretación que utiliza una función de asignación variable no puede funcionar con dominios vacíos, porque no hay funciones de asignación variable cuyo rango está vacío. (Similarly, uno no puede asignar interpretaciones a símbolos constantes.) Esta definición de la verdad requiere que uno debe seleccionar una función de asignación variable (μ arriba) antes de que los valores de la verdad para incluso fórmulas atómicas puedan definirse. Entonces el valor de verdad de una frase se define como su valor de verdad bajo cualquier asignación variable, y se demuestra que este valor de la verdad no depende de qué asignación es elegida. Esta técnica no funciona si no hay funciones de asignación en absoluto; debe cambiarse para acomodar dominios vacíos.

Por lo tanto, cuando se permite el dominio vacío, a menudo debe tratarse como un caso especial. La mayoría de los autores, sin embargo, simplemente excluyen el dominio vacío por definición.

Sistemas deductivos

Se utiliza un sistema deductivo para demostrar, sobre una base puramente sintáctica, que una fórmula es una consecuencia lógica de otra fórmula. Existen muchos sistemas de este tipo para la lógica de primer orden, incluidos los sistemas deductivos de estilo Hilbert, la deducción natural, el cálculo secuencial, el método de cuadros y la resolución. Estos comparten la propiedad común de que una deducción es un objeto sintáctico finito; el formato de este objeto y la forma en que está construido varían ampliamente. Estas deducciones finitas en sí mismas a menudo se denominan derivaciones en la teoría de la demostración. También suelen llamarse pruebas, pero están completamente formalizadas a diferencia de las pruebas matemáticas en lenguaje natural.

Un sistema deductivo es sólido si cualquier fórmula que se pueda derivar en el sistema es lógicamente válida. Por el contrario, un sistema deductivo es completo si todas las fórmulas lógicamente válidas son derivables. Todos los sistemas discutidos en este artículo son sólidos y completos. También comparten la propiedad de que es posible verificar efectivamente que una deducción supuestamente válida es en realidad una deducción; tales sistemas de deducción se denominan efectivos.

Una propiedad clave de los sistemas deductivos es que son puramente sintácticos, por lo que las derivaciones se pueden verificar sin tener en cuenta ninguna interpretación. Por lo tanto, un argumento sólido es correcto en todas las interpretaciones posibles del lenguaje, independientemente de si esa interpretación se trata de matemáticas, economía o alguna otra área.

En general, la consecuencia lógica en la lógica de primer orden solo es semidecidible: si una oración A implica lógicamente una oración B, entonces esta puede descubrirse (por ejemplo, buscando una prueba hasta encontrarla, usando algún sonido efectivo)., sistema de prueba completo). Sin embargo, si A no implica lógicamente B, esto no significa que A implica lógicamente la negación de B. No existe un procedimiento eficaz que, dadas las fórmulas A y B, siempre decida correctamente si A implica lógicamente B.

Reglas de inferencia

Una regla de inferencia establece que, dada una fórmula particular (o conjunto de fórmulas) con una determinada propiedad como hipótesis, otra fórmula específica (o conjunto de fórmulas) puede derivarse como conclusión. La regla es sólida (o conservadora de la verdad) si conserva la validez en el sentido de que cada vez que una interpretación satisface la hipótesis, esa interpretación también satisface la conclusión.

Por ejemplo, una regla común de inferencia es la regla de sustitución. Si t es un término y φ es una fórmula que posiblemente contenga la variable x, entonces φ[t/x ] es el resultado de reemplazar todas las instancias libres de x por t en φ. La regla de sustitución establece que para cualquier φ y cualquier término t, se puede concluir φ[t/x] a partir de φ siempre que no exista una variable libre de t se vincula durante el proceso de sustitución. (Si alguna variable libre de t se vincula, entonces para sustituir t por x primero es necesario cambiar las variables vinculadas de φ para diferir de las variables libres de t.)

Para ver por qué es necesaria la restricción de las variables atadas, considere la fórmula lógicamente válida φ dada por ∃ ∃ x()x=Sí.){displaystyle exists x(x=y)}, en la firma de (0,1,+,×,=) de aritmética. Si t es el término "x + 1", la fórmula φ[t/Sí.] es ∃ ∃ x()x=x+1){displaystyle exists x(x=x+1)}, que será falso en muchas interpretaciones. El problema es que la variable libre x de t fue obligado durante la sustitución. El reemplazo previsto se puede obtener renombrando la variable atada x de φ a otra cosa, decir z, por lo que la fórmula después de la sustitución es ∃ ∃ z()z=x+1){displaystyle exists z(z=x+1)}, que es de nuevo lógicamente válido.

La regla de sustitución demuestra varios aspectos comunes de las reglas de inferencia. Es completamente sintáctico; se puede decir si se aplicó correctamente sin apelar a ninguna interpretación. Tiene limitaciones (definidas sintácticamente) sobre cuándo se puede aplicar, que deben respetarse para preservar la corrección de las derivaciones. Además, como suele ser el caso, estas limitaciones son necesarias debido a las interacciones entre variables libres y ligadas que ocurren durante las manipulaciones sintácticas de las fórmulas involucradas en la regla de inferencia.

Sistemas estilo Hilbert y deducción natural

Una deducción en un sistema deductivo al estilo de Hilbert es una lista de fórmulas, cada una de las cuales es un axioma lógico, una hipótesis que se ha asumido para la derivación en cuestión, o que se deriva de fórmulas anteriores a través de una regla de inferencia. Los axiomas lógicos consisten en varios esquemas de axiomas de fórmulas lógicamente válidas; estos abarcan una cantidad significativa de lógica proposicional. Las reglas de inferencia permiten la manipulación de cuantificadores. Los sistemas típicos de estilo Hilbert tienen un pequeño número de reglas de inferencia, junto con varios esquemas infinitos de axiomas lógicos. Es común tener solo modus ponens y generalización universal como reglas de inferencia.

Los sistemas de deducción natural se asemejan a los sistemas de estilo Hilbert en que una deducción es una lista finita de fórmulas. Sin embargo, los sistemas de deducción natural no tienen axiomas lógicos; compensan agregando reglas adicionales de inferencia que se pueden usar para manipular los conectores lógicos en fórmulas en la prueba.

Cálculo secuencial

El cálculo secuente fue desarrollado para estudiar las propiedades de los sistemas de deducción natural. En lugar de trabajar con una fórmula a la vez, utiliza secuencias, que son expresiones de la forma

A1,...... ,An⊢ ⊢ B1,...... ,Bk,{displaystyle A_{1},ldotsA_{n}vdash B_{1},ldots B_{k},}

Donde A₁A_n, B₁,..._k son las fórmulas y el símbolo del torntil ⊢ ⊢ {displaystyle vdash } se utiliza como puntuación para separar las dos mitades. Intuitivamente, un secuenciador expresa la idea de que ()A1∧ ∧ ⋯ ⋯ ∧ ∧ An){displaystyle (A_{1}land cdots land A_{n}} implicación ()B1Alternativa Alternativa ⋯ ⋯ Alternativa Alternativa Bk){displaystyle (B_{1}lor cdots lor B_{k}}.

Método de cuadros

Una prueba de tablas para la fórmula proposición (a ∨ ¬b) ∧ b) → a.

A diferencia de los métodos descritos, los derivados en el método tableaux no son listas de fórmulas. En cambio, una derivación es un árbol de fórmulas. Para demostrar que una fórmula A es provable, el método tableaux intenta demostrar que la negación de A es insaciable. El árbol de la derivación tiene ¬ ¬ A{displaystyle lnot A} en su raíz; las ramas del árbol de una manera que refleja la estructura de la fórmula. Por ejemplo, para mostrar que CAlternativa Alternativa D{displaystyle Clor D} es insaciable requiere demostrar que C y D son cada uno insaciables; esto corresponde a un punto de ramificación en el árbol con el padre CAlternativa Alternativa D{displaystyle Clor D} y niños C y D.

Resolución

La regla de resolución es una sola regla de inferencia que, junto con la unificación, es sólida y completa para la lógica de primer orden. Al igual que con el método de cuadros, una fórmula se prueba mostrando que la negación de la fórmula es insatisfactoria. La resolución se usa comúnmente en la demostración automática de teoremas.

El método de resolución funciona sólo con fórmulas que son disyunciones de fórmulas atómicas; las fórmulas arbitrarias deben ser convertidas primero a esta forma a través de Skolemization. La regla de la resolución dice que de las hipótesis A1Alternativa Alternativa ⋯ ⋯ Alternativa Alternativa AkAlternativa Alternativa C{displaystyle A_{1}lor cdots lor A_{k}lor C} y B1Alternativa Alternativa ⋯ ⋯ Alternativa Alternativa BlAlternativa Alternativa ¬ ¬ C{displaystyle B_{1}lor cdots lor B_{l}lor lnot C}, la conclusión A1Alternativa Alternativa ⋯ ⋯ Alternativa Alternativa AkAlternativa Alternativa B1Alternativa Alternativa ⋯ ⋯ Alternativa Alternativa Bl{displaystyle A_{1}lor cdots lor A_{k}lor B_{1}lor cdots lor B_{l} se puede obtener.

Identidades demostrables

Se pueden probar muchas identidades, que establecen equivalencias entre fórmulas particulares. Estas identidades permiten reorganizar fórmulas moviendo cuantificadores a través de otros conectores, y son útiles para poner fórmulas en forma normal prenex. Algunas identidades comprobables incluyen:

¬ ¬ О О xP()x).. ∃ ∃ x¬ ¬ P()x){displaystyle lnot forall x,P(x)Leftrightarrow exists x,lnot P(x)}

¬ ¬ ∃ ∃ xP()x).. О О x¬ ¬ P()x){displaystyle lnot exists x,P(x)Leftrightarrow forall x,lnot P(x)}

О О xО О Sí.P()x,Sí.).. О О Sí.О О xP()x,Sí.){displaystyle forall x,forall y,P(x,y)Leftrightarrow forall y,forall x,P(x,y)}

∃ ∃ x∃ ∃ Sí.P()x,Sí.).. ∃ ∃ Sí.∃ ∃ xP()x,Sí.){displaystyle exists x,exists y,P(x,y)Leftrightarrow exists y,exists x,P(x,y)}

О О xP()x)∧ ∧ О О xQ()x).. О О x()P()x)∧ ∧ Q()x)){displaystyle forall x,P(x)land forall x,Q(x)Leftrightarrow forall x,(P(x)land Q(x)}

∃ ∃ xP()x)Alternativa Alternativa ∃ ∃ xQ()x).. ∃ ∃ x()P()x)Alternativa Alternativa Q()x)){displaystyle exists x,P(x)lor exists x,Q(x)Leftrightarrow exists x,(P(x)lor Q(x)}

P∧ ∧ ∃ ∃ xQ()x).. ∃ ∃ x()P∧ ∧ Q()x)){displaystyle Pland exists x,Q(x)Leftrightarrow exists x,(Pland Q(x)} (donde) x{displaystyle x} no debe ocurrir libre en P{displaystyle P})

PAlternativa Alternativa О О xQ()x).. О О x()PAlternativa Alternativa Q()x)){displaystyle Plor forall x,Q(x)Leftrightarrow forall x,(Plor Q(x)} (donde) x{displaystyle x} no debe ocurrir libre en P{displaystyle P})

La igualdad y sus axiomas

Existen varias convenciones diferentes para usar la igualdad (o identidad) en la lógica de primer orden. La convención más común, conocida como lógica de primer orden con igualdad, incluye el símbolo de igualdad como un símbolo lógico primitivo que siempre se interpreta como la relación de igualdad real entre miembros del dominio del discurso, tal que el "dos" los miembros dados son el mismo miembro. Este enfoque también agrega ciertos axiomas sobre la igualdad al sistema deductivo empleado. Estos axiomas de igualdad son:

• Reflexividad. Para cada variable x, x = x.
• Sustitución de funciones. Para todas las variables x y Sí., y cualquier símbolo de función f,

  x = Sí. → f(... x,...) = f(... Sí.,...).

• Sustitución de fórmulas. Para cualquier variable x y Sí. y cualquier fórmula φ(x), si φ' se obtiene reemplazando cualquier número de ocurrencias libres de x en φ con Sí., tal que estos siguen siendo casos libres de Sí., entonces

  x = Sí. → (φ → φ').

Estos son esquemas de axiomas, cada uno de los cuales especifica un conjunto infinito de axiomas. El tercer esquema se conoce como ley de Leibniz, "el principio de sustitutividad", "la indiscernibilidad de los idénticos", o "la propiedad de reemplazo". El segundo esquema, que involucra el símbolo de función f, es (equivalente a) un caso especial del tercer esquema, usando la fórmula

x = Sí. →f(... x,...) = z → f(... Sí.,...) = z).

Muchas otras propiedades de la igualdad son consecuencia de los axiomas anteriores, por ejemplo:

• Simmetría. Si x = Sí. entonces Sí. = x.
• Transitividad. Si x = Sí. y Sí. = z entonces x = z.

Lógica de primer orden sin igualdad

Un enfoque alternativo considera que la relación de igualdad es un símbolo no lógico. Esta convención se conoce como lógica de primer orden sin igualdad. Si se incluye una relación de igualdad en la firma, los axiomas de igualdad ahora deben agregarse a las teorías bajo consideración, si se desea, en lugar de considerarse reglas de lógica. La principal diferencia entre este método y la lógica de primer orden con igualdad es que una interpretación ahora puede interpretar a dos individuos distintos como "iguales" (aunque, según la ley de Leibniz, estas satisfarán exactamente las mismas fórmulas bajo cualquier interpretación). Es decir, la relación de igualdad ahora puede ser interpretada por una relación de equivalencia arbitraria en el dominio del discurso que es congruente con respecto a las funciones y relaciones de la interpretación.

Cuando se sigue esta segunda convención, el término modelo normal se usa para referirse a una interpretación donde ningún individuo distinto a y b satisfacen a = b. En la lógica de primer orden con igualdad, solo se consideran modelos normales, por lo que no existe un término para un modelo que no sea un modelo normal. Cuando se estudia la lógica de primer orden sin igualdad, es necesario modificar los enunciados de resultados como el teorema de Löwenheim-Skolem para que solo se consideren modelos normales.

La lógica de primer orden sin igualdad se emplea a menudo en el contexto de la aritmética de segundo orden y otras teorías aritméticas de orden superior, donde la relación de igualdad entre conjuntos de números naturales suele omitirse.

Definiendo la igualdad dentro de una teoría

Si una teoría tiene una fórmula binaria A(x,y) que satisface la reflexividad y la ley de Leibniz, la teoría se dice que tiene igualdad, o que es una teoría con igualdad. Es posible que la teoría no tenga todas las instancias de los esquemas anteriores como axiomas, sino como teoremas derivables. Por ejemplo, en teorías sin símbolos de función y con un número finito de relaciones, es posible definir la igualdad en términos de las relaciones, definiendo los dos términos s y t ser igual si alguna relación no cambia al cambiar s a t en cualquier argumento.

Algunas teorías permiten otras definiciones ad hoc de igualdad:

• En la teoría de órdenes parciales con un símbolo de relación ≤, uno podría definir s = t ser una abreviatura para s ≤ t ∧ t ≤ s.
• En la teoría de conjuntos con una relación ANTE, uno puede definir s = t ser una abreviatura para Оx ()s ▪ x Administración t ▪ x∧x ()x ▪ s Administración x ▪ t). Esta definición de igualdad satisface automáticamente los axiomas para la igualdad. En este caso, se debe sustituir el axioma habitual de la extensión, que se puede decir como О О xО О Sí.[О О z()z▪ ▪ x.. z▪ ▪ Sí.)⇒ ⇒ x=Sí.]{displaystyle forall xforall y[forall z(zin xLeftrightarrow zin y)Rightarrow x=y]}, con una formulación alternativa О О xО О Sí.[О О z()z▪ ▪ x.. z▪ ▪ Sí.)⇒ ⇒ О О z()x▪ ▪ z.. Sí.▪ ▪ z)]{displaystyle forall xforall y[forall z(zin xLeftrightarrow zin y)Rightarrow forall z(xin zLeftrightarrow yin z)}, que dice que si se pone x y Sí. tienen los mismos elementos, entonces también pertenecen a los mismos conjuntos.

Propiedades metalógicas

Una motivación para el uso de la lógica de primer orden, en lugar de la lógica de orden superior, es que la lógica de primer orden tiene muchas propiedades metalógicas que las lógicas más fuertes no tienen. Estos resultados se refieren a propiedades generales de la propia lógica de primer orden, más que a propiedades de teorías individuales. Proporcionan herramientas fundamentales para la construcción de modelos de teorías de primer orden.

Integridad e indecidibilidad

El teorema de completitud de Gödel, demostrado por Kurt Gödel en 1929, establece que existen sistemas deductivos sólidos, completos y efectivos para la lógica de primer orden y, por lo tanto, la relación de consecuencia lógica de primer orden es capturada por la demostrabilidad finita. Ingenuamente, la afirmación de que una fórmula φ implica lógicamente una fórmula ψ depende de cada modelo de φ; estos modelos en general tendrán una cardinalidad arbitrariamente grande, por lo que la consecuencia lógica no se puede verificar de manera efectiva verificando cada modelo. Sin embargo, es posible enumerar todas las derivaciones finitas y buscar una derivación de ψ a partir de φ. Si ψ está implicado lógicamente por φ, eventualmente se encontrará tal derivación. Por lo tanto, la consecuencia lógica de primer orden es semidecidible: es posible hacer una enumeración efectiva de todos los pares de oraciones (φ, ψ) tal que ψ sea una consecuencia lógica de φ.

A diferencia de la lógica proposicional, la lógica de primer orden es indecidible (aunque semidecidible), siempre que el lenguaje tenga al menos un predicado de aridad al menos 2 (aparte de la igualdad). Esto significa que no existe un procedimiento de decisión que determine si las fórmulas arbitrarias son lógicamente válidas. Este resultado fue establecido de forma independiente por Alonzo Church y Alan Turing en 1936 y 1937, respectivamente, dando una respuesta negativa al Entscheidungsproblem planteado por David Hilbert y Wilhelm Ackermann en 1928. Sus demostraciones demuestran una conexión entre la imposibilidad de resolver el problema de decisión para los primeros la lógica del orden y la insolubilidad del problema de la detención.

Hay sistemas más débiles que la lógica completa de primer orden para los cuales la relación de consecuencia lógica es decidible. Estos incluyen la lógica proposicional y la lógica de predicados monádicos, que es una lógica de primer orden restringida a símbolos de predicados unarios y sin símbolos de función. Otras lógicas sin símbolos de función que son decidibles son el fragmento protegido de la lógica de primer orden, así como la lógica de dos variables. La clase de fórmulas de primer orden de Bernays-Schönfinkel también es decidible. Los subconjuntos decidibles de la lógica de primer orden también se estudian en el marco de la lógica de descripción.

El teorema de Löwenheim-Skolem

El teorema de Löwenheim-Skolem muestra que si una teoría de cardinalidad de primer orden λ tiene un modelo infinito, entonces tiene modelos de cada cardinalidad infinita mayor o igual que λ. Uno de los primeros resultados en la teoría de modelos implica que no es posible caracterizar la contabilidad o la incontabilidad en un lenguaje de primer orden con una firma contable. Es decir, no existe una fórmula de primer orden φ(x) tal que una estructura arbitraria M satisfaga φ si y solo si el dominio del discurso de M es contable (o, en el segundo caso, incontable).).

El teorema de Löwenheim-Skolem implica que las estructuras infinitas no se pueden axiomatizar categóricamente en la lógica de primer orden. Por ejemplo, no existe una teoría de primer orden cuyo único modelo sea la recta real: toda teoría de primer orden con un modelo infinito también tiene un modelo de cardinalidad mayor que el continuo. Dado que la línea real es infinita, cualquier teoría satisfecha por la línea real también es satisfecha por algunos modelos no estándar. Cuando el teorema de Löwenheim-Skolem se aplica a las teorías de conjuntos de primer orden, las consecuencias no intuitivas se conocen como la paradoja de Skolem.

El teorema de la compacidad

El teorema de compacidad establece que un conjunto de oraciones de primer orden tiene un modelo si y solo si cada subconjunto finito tiene un modelo. Esto implica que si una fórmula es una consecuencia lógica de un conjunto infinito de axiomas de primer orden, entonces es una consecuencia lógica de un número finito de esos axiomas. Este teorema fue demostrado por primera vez por Kurt Gödel como consecuencia del teorema de completitud, pero con el tiempo se han obtenido muchas demostraciones adicionales. Es una herramienta central en la teoría de modelos, proporcionando un método fundamental para construir modelos.

El teorema de compacidad tiene un efecto limitante sobre qué colecciones de estructuras de primer orden son clases elementales. Por ejemplo, el teorema de compacidad implica que cualquier teoría que tenga modelos finitos arbitrariamente grandes tiene un modelo infinito. Por lo tanto, la clase de todos los gráficos finitos no es una clase elemental (lo mismo vale para muchas otras estructuras algebraicas).

También hay limitaciones más sutiles de la lógica de primer orden que están implícitas por el teorema de compactidad. Por ejemplo, en la ciencia informática, muchas situaciones pueden ser modeladas como un gráfico dirigido de estados (nodos) y conexiones (ristas dirigidos). Validar tal sistema puede requerir demostrar que ningún estado "malo" puede ser alcanzado desde cualquier estado "bueno". Así se busca determinar si los estados buenos y malos están en diferentes componentes conectados del gráfico. Sin embargo, el teorema de compactidad se puede utilizar para demostrar que los gráficos conectados no son una clase elemental en la lógica de primer orden, y no hay fórmula φ(x,Sí.) de la lógica de primer orden, en la lógica de los gráficos, que expresa la idea de que hay un camino de x a Sí.. Sin embargo, la conexión se puede expresar en la lógica de segundo orden, pero no con sólo cuantificadores de conjunto existencial, como .. 11{displaystyle Sigma ¿Qué? también goza de compactidad.

Teorema de Lindström

Per Lindström mostró que las propiedades metalógicas que acabamos de discutir en realidad caracterizan la lógica de primer orden en el sentido de que ninguna lógica más fuerte también puede tener esas propiedades (Ebbinghaus y Flum 1994, Capítulo XIII). Lindström definió una clase de sistemas lógicos abstractos y una definición rigurosa de la fuerza relativa de un miembro de esta clase. Estableció dos teoremas para sistemas de este tipo:

• Un sistema lógico que satisface la definición de Lindström que contiene la lógica de primer orden y satisface tanto el teorema de Löwenheim–Skolem como el teorema de compactidad deben ser equivalentes a la lógica de primer orden.
• Un sistema lógico que satisface la definición de Lindström que tiene una relación de consecuencia lógica semidecida y satisface el teorema de Löwenheim–Skolem debe ser equivalente a la lógica de primera orden.

Limitaciones

Aunque la lógica de primer orden es suficiente para formalizar gran parte de las matemáticas y se usa comúnmente en informática y otros campos, tiene ciertas limitaciones. Estos incluyen limitaciones en su expresividad y limitaciones de los fragmentos de lenguajes naturales que puede describir.

Por ejemplo, la lógica de primer orden es indecible, lo que significa que es imposible un algoritmo de decisión sólido, completo y terminador para la probabilidad. Esto ha llevado al estudio de fragmentos interesantes y decidables, como C₂: lógica de primer orden con dos variables y los cuantificadores de conteo ∃ ∃ ≥ ≥ n{displaystyle exists ^{geq No. y ∃ ∃ ≤ ≤ n{displaystyle exists ^{leq No..

Expresividad

El teorema de Löwenheim-Skolem muestra que si una teoría de primer orden tiene algún modelo infinito, entonces tiene infinitos modelos de cada cardinalidad. En particular, ninguna teoría de primer orden con un modelo infinito puede ser categórica. Así, no existe una teoría de primer orden cuyo único modelo tenga como dominio el conjunto de los números naturales, o cuyo único modelo tenga como dominio el conjunto de los números reales. Muchas extensiones de la lógica de primer orden, incluidas las lógicas infinitarias y las lógicas de orden superior, son más expresivas en el sentido de que permiten axiomatizaciones categóricas de los números naturales o números reales. Sin embargo, esta expresividad tiene un costo metalógico: según el teorema de Lindström, el teorema de compacidad y el teorema de Löwenheim-Skolem hacia abajo no pueden sostenerse en ninguna lógica más fuerte que la de primer orden.

Formalización de lenguajes naturales

La lógica de primer orden puede formalizar muchas construcciones simples de cuantificadores en lenguaje natural, como "todas las personas que viven en Perth viven en Australia". Por lo tanto, la lógica de primer orden se utiliza como base para los lenguajes de representación del conocimiento, como FO(.).

Aún así, hay características complicadas del lenguaje natural que no se pueden expresar en lógica de primer orden. "Cualquier sistema lógico que sea apropiado como instrumento para el análisis del lenguaje natural necesita una estructura mucho más rica que la lógica de predicados de primer orden".

Restricciones, extensiones y variaciones

Existen muchas variaciones de la lógica de primer orden. Algunos de estos no son esenciales en el sentido de que simplemente cambian la notación sin afectar la semántica. Otros cambian el poder expresivo de manera más significativa al extender la semántica a través de cuantificadores adicionales u otros nuevos símbolos lógicos. Por ejemplo, las lógicas infinitarias permiten fórmulas de tamaño infinito y las lógicas modales agregan símbolos de posibilidad y necesidad.

Idiomas restringidos

La lógica de primer orden se puede estudiar en lenguajes con menos símbolos lógicos que los descritos anteriormente.

• Porque... ∃ ∃ xφ φ ()x){displaystyle exists xvarphi (x)} se puede expresar como ¬ ¬ О О x¬ ¬ φ φ ()x){displaystyle neg forall xneg varphi (x)}, y О О xφ φ ()x){displaystyle forall xvarphi (x)} se puede expresar como ¬ ¬ ∃ ∃ x¬ ¬ φ φ ()x){displaystyle neg exists xneg varphi (x)}, cualquiera de los dos cuantificadores ∃ ∃ {displaystyle exists } y О О {displaystyle forall } se puede caer.
• Desde φ φ Alternativa Alternativa ↑ ↑ {displaystyle varphi lor psi } se puede expresar como ¬ ¬ ()¬ ¬ φ φ ∧ ∧ ¬ ¬ ↑ ↑ ){displaystyle lnot (lnot varphi land lnot psi)} y φ φ ∧ ∧ ↑ ↑ {displaystyle varphi land psi } se puede expresar como ¬ ¬ ()¬ ¬ φ φ Alternativa Alternativa ¬ ¬ ↑ ↑ ){displaystyle lnot (lnot varphi lor lnot psi)}, o Alternativa Alternativa {displaystyle vee } o ∧ ∧ {displaystyle wedge } se puede caer. En otras palabras, es suficiente tener ¬ ¬ {displaystyle neg } y Alternativa Alternativa {displaystyle vee }, o ¬ ¬ {displaystyle neg } y ∧ ∧ {displaystyle wedge }, como los únicos conectores lógicos.
• Del mismo modo, es suficiente tener sólo ¬ ¬ {displaystyle neg } y → → {displaystyle rightarrow } como conexiones lógicas, o tener sólo el trazo Sheffer (NAND) o el operador de flecha Peirce (NOR).
• Es posible evitar completamente símbolos de función y símbolos constantes, reescribirlos a través de símbolos predicados de una manera apropiada. Por ejemplo, en lugar de usar un símbolo constante 0{displaystyle ;0} uno puede usar un predicado 0()x){displaystyle ;0(x)} (interpretado como x=0{displaystyle ;x=0}), y reemplazar cada predicado como P()0,Sí.){displaystyle ;P(0,y)} con О О x()0()x)→ → P()x,Sí.)){displaystyle forall x;(0(x)rightarrow P(x,y)}. Una función como f()x1,x2,...,xn){displaystyle f(x_{1},x_{2},x_{n}} será reemplazado por un predicado F()x1,x2,...,xn,Sí.){displaystyle F(x_{1},x_{2},...,x_{n},y) } interpretada Sí.=f()x1,x2,...,xn){displaystyle y=f(x_{1},x_{2},x_{n}. Este cambio requiere añadir axiomas adicionales a la teoría a la mano, para que las interpretaciones de los símbolos predicados utilizados tengan la semántica correcta.

Restricciones como estas son útiles como técnica para reducir el número de reglas de inferencia o esquemas de axiomas en los sistemas deductivos, lo que lleva a pruebas más cortas de resultados metalógicos. El costo de las restricciones es que se vuelve más difícil expresar declaraciones en lenguaje natural en el sistema formal en cuestión, porque los conectores lógicos usados en las declaraciones en lenguaje natural deben ser reemplazados por sus definiciones (más largas) en términos de la colección restringida de conectores lógicos. De manera similar, las derivaciones en los sistemas limitados pueden ser más largas que las derivaciones en sistemas que incluyen conectivos adicionales. Por lo tanto, existe una compensación entre la facilidad de trabajar dentro del sistema formal y la facilidad de probar resultados sobre el sistema formal.

También es posible restringir las aridades de símbolos de función y símbolos de predicado, en teorías suficientemente expresivas. En principio, se puede prescindir por completo de funciones de aridad mayor que 2 y predicados de aridad mayor que 1 en teorías que incluyen una función de emparejamiento. Esta es una función de aridad 2 que toma pares de elementos del dominio y devuelve un par ordenado que los contiene. También es suficiente tener dos símbolos de predicado de aridad 2 que definan funciones de proyección de un par ordenado a sus componentes. En cualquier caso, es necesario que se satisfagan los axiomas naturales para una función de emparejamiento y sus proyecciones.

Lógica de clasificación múltiple

Las interpretaciones ordinarias de primer orden tienen un solo dominio de discurso sobre el cual se extienden todos los cuantificadores. La lógica de primer orden de ordenación múltiple permite que las variables tengan diferentes clases, que tienen diferentes dominios. Esto también se llama lógica de primer orden con tipo, y los géneros se llaman tipos (como en el tipo de datos), pero no es lo mismo que la teoría de tipos de primer orden. La lógica de primer orden ordenada por muchos se usa a menudo en el estudio de la aritmética de segundo orden.

Cuando sólo hay muchas clases finitamente en una teoría, la lógica de primer orden de muchos surtidos puede reducirse a la lógica de primer orden. Uno introduce en la teoría de un solo surtido un símbolo predicado siniestro para cada tipo en la teoría de muchos surtidos, y añade un axioma diciendo que estos predicados no deseados particionan el dominio del discurso. Por ejemplo, si hay dos tipos, uno añade símbolos predicados P1()x){displaystyle P_{1}(x)} y P2()x){displaystyle P_{2}(x)} y el axioma

О О x()P1()x)Alternativa Alternativa P2()x))∧ ∧ ¬ ¬ ∃ ∃ x()P1()x)∧ ∧ P2()x)){displaystyle forall x(P_{1}(x)lor P_{2}(x)land lnot exists x(P_{1}(x)land P_{2}(x)}.

Luego los elementos que satisfacen P1{displaystyle P_{1} son considerados como elementos del primer tipo, y elementos satisfactorios P2{displaystyle P_{2} como elementos del segundo tipo. Uno puede cuantificar sobre cada tipo utilizando el símbolo predicado correspondiente para limitar el rango de cuantificación. Por ejemplo, decir que hay un elemento del primer tipo de fórmula satisfactoria φ(x), uno escribe

∃ ∃ x()P1()x)∧ ∧ φ φ ()x)){displaystyle exists x(P_{1}(x)land varphi (x)}.

Cuantificadores adicionales

Se pueden agregar cuantificadores adicionales a la lógica de primer orden.

• A veces es útil decir que "P()x) para una exactamente x", que se puede expresar como ∃!x P()x). Esta notación, llamada cuantificación de singularidad, puede ser tomada para abreviar una fórmula como ∃x ()P()x∧Sí. ()P()Sí.) →x = Sí.)).
• Lógica de primer orden con cuantificadores extra tiene nuevos cuantificadores QxCon significados como "hay muchos x así... Vea también los cuantificadores de ramificación y los cuantificadores plurales de George Boolos y otros.
• Cuantificadores heridos se utilizan a menudo en el estudio de la teoría de conjuntos o aritmética.

Lógica infinita

La lógica infinita permite oraciones infinitamente largas. Por ejemplo, se puede permitir una conjunción o disyunción de un número infinito de fórmulas, o una cuantificación sobre un número infinito de variables. Las oraciones infinitamente largas surgen en áreas de las matemáticas, incluida la topología y la teoría de modelos.

La lógica infinita generaliza la lógica de primer orden para permitir fórmulas de longitud infinita. La forma más común en que las fórmulas pueden volverse infinitas es a través de conjunciones y disyunciones infinitas. Sin embargo, también es posible admitir firmas generalizadas en las que se permite que los símbolos de funciones y relaciones tengan aridades infinitas, o en las que los cuantificadores pueden vincular infinitas variables. Debido a que una fórmula infinita no se puede representar mediante una cadena finita, es necesario elegir alguna otra representación de fórmulas; la representación habitual en este contexto es un árbol. Por lo tanto, las fórmulas se identifican, esencialmente, con sus árboles de análisis, en lugar de con las cadenas que se analizan.

Las lógicas infinitas más comúnmente estudiadas se denotan L_αβ, donde α y β son números cardinales o el símbolo ∞. En esta notación, la lógica ordinaria de primer orden es L_ωω. En la lógica L_∞ω, se permiten conjunciones o disyunciones arbitrarias al construir fórmulas, y hay un suministro ilimitado de variables. Más generalmente, la lógica que permite conjunciones o disyunciones con menos de κ constituyentes se conoce como L_κω. Por ejemplo, L_ω1ω permite conjunciones y disyunciones contables.

El conjunto de variables libres en una fórmula de L_κω puede tener cualquier cardinalidad estrictamente menor que κ, pero solo un número finito de ellas puede estar en el alcance de cualquier cuantificador cuando una fórmula aparece como subfórmula de otra. En otras lógicas infinitarias, una subfórmula puede estar en el alcance de infinitos cuantificadores. Por ejemplo, en L_κ∞, un solo cuantificador universal o existencial puede vincular arbitrariamente muchas variables simultáneamente. De manera similar, la lógica L_κλ permite la cuantificación simultánea sobre menos de λ variables, así como conjunciones y disyunciones de tamaño menor que κ.

Lógicas no clásicas y modales

• Intuitionistic first-order logic utiliza el cálculo proposiciónl intuitionista más que el clásico; por ejemplo, ¬¬¬φ no necesita ser equivalente a φ.
• Primera orden lógica modal permite describir otros mundos posibles así como este mundo contingentemente verdadero que habitamos. En algunas versiones, el conjunto de mundos posibles varía dependiendo de qué mundo posible habita. Lógica Modal tiene extra modal operators con significados que pueden caracterizarse informalmente como, por ejemplo "es necesario que φ" (verdad en todos los mundos posibles) y "es posible que φ" (verdad en algún mundo posible). Con la lógica estándar de primer orden tenemos un solo dominio y cada predicado se asigna una extensión. Con la lógica modal de primer orden tenemos un función de dominio que asigna a cada mundo posible su propio dominio, para que cada predicado obtenga una extensión sólo relativa a estos mundos posibles. Esto nos permite modelar casos donde, por ejemplo, Alex es un filósofo, pero podría haber sido un matemático, y podría no haber existido en absoluto. En el primer mundo posible P()a) es verdad, en el segundo P()a) es falso, y en el tercer mundo posible no hay a en el dominio en absoluto.
• Lógicas fuzzy de primer orden son las extensiones de primer orden de las lógicas fuzzy proposicionales en lugar de cálculo proposicional clásico.

Lógica de puntos fijos

La lógica de puntos fijos amplía la lógica de primer orden al agregar el cierre debajo de los puntos menos fijos de los operadores positivos.

Lógicas de orden superior

El rasgo característico de la lógica de primer orden es que los individuos pueden ser cuantificados, pero no los predicados. Por lo tanto

∃ ∃ a()Phil()a)){displaystyle exists a({text{Phil}(a)}

es una fórmula legal de primer orden, pero

∃ ∃ Phil()Phil()a)){displaystyle exists {text{Phil}}({text{Phil}(a)} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}

no lo es, en la mayoría de las formalizaciones de la lógica de primer orden. La lógica de segundo orden amplía la lógica de primer orden al agregar el último tipo de cuantificación. Otras lógicas de orden superior permiten la cuantificación sobre tipos incluso superiores a los que permite la lógica de segundo orden. Estos tipos superiores incluyen relaciones entre relaciones, funciones de relaciones a relaciones entre relaciones y otros objetos de tipo superior. Así, el "primero" en la lógica de primer orden describe el tipo de objetos que se pueden cuantificar.

A diferencia de la lógica de primer orden, para la cual solo se estudia una semántica, existen varias semánticas posibles para la lógica de segundo orden. La semántica más comúnmente empleada para la lógica de segundo orden y de orden superior se conoce como semántica completa. La combinación de cuantificadores adicionales y la semántica completa de estos cuantificadores hace que la lógica de orden superior sea más fuerte que la lógica de primer orden. En particular, la relación de consecuencia lógica (semántica) para la lógica de segundo orden y de orden superior no es semidecidible; no existe un sistema de deducción efectivo para la lógica de segundo orden que sea sólido y completo bajo la semántica completa.

La lógica de segundo orden con semántica completa es más expresiva que la lógica de primer orden. Por ejemplo, es posible crear sistemas de axiomas en lógica de segundo orden que caractericen de manera única los números naturales y la línea real. El costo de esta expresividad es que las lógicas de segundo orden y de orden superior tienen menos propiedades metalógicas atractivas que la lógica de primer orden. Por ejemplo, el teorema de Löwenheim-Skolem y el teorema de compacidad de la lógica de primer orden se vuelven falsos cuando se generalizan a lógicas de orden superior con semántica completa.

Demostración automatizada de teoremas y métodos formales

La demostración automatizada de teoremas se refiere al desarrollo de programas informáticos que buscan y encuentran derivaciones (pruebas formales) de teoremas matemáticos. Encontrar derivaciones es una tarea difícil porque el espacio de búsqueda puede ser muy grande; una búsqueda exhaustiva de todas las derivaciones posibles es teóricamente posible pero computacionalmente inviable para muchos sistemas de interés en matemáticas. Así, se desarrollan funciones heurísticas complicadas para intentar encontrar una derivación en menos tiempo que una búsqueda ciega.

El área relacionada de verificación de pruebas automatizada utiliza programas informáticos para comprobar que las pruebas creadas por humanos son correctas. A diferencia de los probadores de teoremas automatizados complicados, los sistemas de verificación pueden ser lo suficientemente pequeños como para que su corrección se pueda verificar tanto a mano como mediante la verificación de software automatizado. Esta validación del verificador de prueba es necesaria para dar confianza de que cualquier derivación etiquetada como "correcta" es realmente correcto.

Algunos verificadores de pruebas, como Metamath, insisten en tener una derivación completa como entrada. Otros, como Mizar e Isabelle, toman un bosquejo de prueba bien formateado (que aún puede ser muy largo y detallado) y completan las partes que faltan haciendo búsquedas de prueba simples o aplicando procedimientos de decisión conocidos: la derivación resultante se verifica luego mediante un "núcleo" de núcleo pequeño. Muchos de estos sistemas están destinados principalmente al uso interactivo por parte de matemáticos humanos: estos se conocen como asistentes de prueba. También pueden usar lógicas formales que son más fuertes que la lógica de primer orden, como la teoría de tipos. Debido a que una derivación completa de cualquier resultado no trivial en un sistema deductivo de primer orden será extremadamente larga de escribir para un ser humano, los resultados a menudo se formalizan como una serie de lemas, para los cuales las derivaciones se pueden construir por separado.

Los probadores de teoremas automatizados también se utilizan para implementar la verificación formal en informática. En este entorno, los probadores de teoremas se utilizan para verificar la exactitud de los programas y del hardware, como los procesadores, con respecto a una especificación formal. Debido a que dicho análisis requiere mucho tiempo y, por lo tanto, es costoso, generalmente se reserva para proyectos en los que un mal funcionamiento tendría graves consecuencias humanas o financieras.

Para el problema de la verificación de modelos, se sabe que los algoritmos eficientes deciden si una estructura finita de entrada satisface una fórmula de primer orden, además de los límites de complejidad computacional: consulte Verificación de modelos § Lógica de primer orden.