La 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 utiliza 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", se pueden tener expresiones en la forma "existe x tal que x es Sócrates y x es un hombre", donde "existe " es un cuantificador, mientras que x es una variable. [1] Esto la distingue de la lógica proposicional , que no utiliza cuantificadores ni relaciones ; [2] en este sentido, la lógica proposicional es la base de la lógica de primer orden.
Una teoría sobre un tema, como la teoría de conjuntos, una teoría de grupos [3] o una teoría formal de la aritmética , suele ser una lógica de primer orden junto con un dominio de discurso específico (sobre el cual varían las variables cuantificadas), finitamente. muchas funciones de ese dominio hacia sí mismo, un número finito de predicados definidos en ese dominio y un conjunto de axiomas que se cree que son válidos sobre ellos. La "teoría" a veces se entiende en un sentido más formal, como simplemente un conjunto de oraciones en lógica de primer orden.
El término "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 de predicados, funciones o ambos. [4] : 56 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 sólo semidecidible , se ha avanzado mucho en la demostración automatizada 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 la 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 recta 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 sólidas, 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 . [5] 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).
Mientras que la lógica proposicional se ocupa de proposiciones declarativas simples, la lógica de primer orden cubre además los predicados y la cuantificación . Un predicado se evalúa como verdadero o falso para una entidad o entidades en el dominio del discurso .
Consideremos las dos frases " Sócrates es un filósofo" y " Platón es un filósofo". En lógica proposicional , estas oraciones en sí mismas se consideran los individuos de estudio y podrían denotarse, por ejemplo, mediante variables como p y q . No se los ve como una aplicación de un predicado, como por ejemplo , a ningún objeto particular en el dominio del discurso, sino que se los considera puramente un enunciado que es verdadero o falso. [6] Sin embargo, en lógica de primer orden, estas dos oraciones pueden expresarse como afirmaciones de que un determinado objeto individual o no lógico tiene una propiedad. En este ejemplo, ambas oraciones tienen la forma común para algún individuo , en la primera oración el valor de la variable x es "Sócrates" y en la segunda oración es "Platón". Debido a la capacidad de hablar de individuos no lógicos junto con los conectivos lógicos originales, la lógica de primer orden incluye la lógica proposicional. [7]
La verdad de una fórmula como " x es un filósofo" depende de qué objeto se denota por x y de la interpretación del predicado "es un filósofo". En consecuencia, " x es un filósofo" por sí solo no tiene un valor de verdad definido de verdadero o falso, y es similar a un fragmento de oración. [8] Las relaciones entre predicados se pueden establecer utilizando conectivos lógicos . Por ejemplo, la fórmula de primer orden "si x es un filósofo, entonces x es un erudito", es un enunciado condicional con " x es un filósofo" como hipótesis y " x es un erudito" como conclusión, lo que nuevamente necesita la especificación de x para tener un valor de verdad definido.
Los cuantificadores se pueden aplicar a variables en una fórmula. La variable x en la fórmula anterior se puede cuantificar universalmente, por ejemplo, con la frase de primer orden "Para cada x , si x es un filósofo, entonces x es un erudito". El cuantificador universal "para cada" en esta oración expresa la idea de que la afirmación "si x es un filósofo, entonces x es un erudito" es válida para todas las elecciones de x .
La negación de la oración "Para cada x , si x es un filósofo, entonces x es un erudito" es lógicamente equivalente a la oración "Existe x tal que x es un filósofo y x no es un erudito". El cuantificador existencial "existe" expresa la idea de que la afirmación " x es un filósofo y x no es un erudito" es válida para alguna elección de x .
Los predicados "es un filósofo" y "es un erudito" toman cada uno 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 qué 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 formado por todos los seres humanos y el predicado "es filósofo" entendido como "fue el autor de la República ", se ve la frase "Existe x tal que x es filósofo" como verdadera, como lo atestiguó Platón. [ se necesita aclaració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.
A diferencia de los lenguajes naturales, como el inglés, el lenguaje de la lógica de primer orden es completamente formal, de modo 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 idioma.
Como ocurre con todos los lenguajes formales , la naturaleza de los símbolos mismos está fuera del alcance de la lógica formal; A menudo se los considera simplemente letras y símbolos 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 según la interpretación. [9] Por ejemplo, el símbolo lógico siempre representa "y"; nunca se interpreta como "o", que se representa mediante el símbolo lógico . Sin embargo, un símbolo de predicado no lógico como Phil ( x ) podría interpretarse en el sentido de " x es un filósofo", " x es un hombre llamado Philip" o cualquier otro predicado unario dependiendo de la interpretación en cuestión.
Los símbolos lógicos son un conjunto de caracteres que varían según el autor, pero normalmente incluyen lo siguiente: [10]
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:
Los símbolos no lógicos representan predicados (relaciones), funciones y constantes. Solía ser una práctica estándar utilizar un conjunto fijo e infinito de símbolos no lógicos para todos los propósitos:
Cuando la aridad de un símbolo de predicado o de función se desprende claramente del contexto, a menudo se omite el superíndice n .
En este enfoque tradicional, sólo existe un lenguaje de lógica de primer orden. [13] 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 utilizados en una aplicación particular. Esta elección se realiza mediante una firma . [14]
Las firmas típicas en matemáticas son {1, ×} o simplemente {×} para grupos , [3] o {0, 1, +, ×, <} para campos ordenados . No hay restricciones en cuanto al número de símbolos no lógicos. La firma puede ser vacía , finita o infinita, incluso incontable . En las demostraciones modernas del teorema de Löwenheim-Skolem, por ejemplo, aparecen firmas incontables .
Aunque en algunos casos las firmas pueden implicar cómo se deben interpretar los símbolos no lógicos, la interpretación de los símbolos no lógicos en la firma es separada (y no necesariamente fija). Las firmas se refieren más a la sintaxis que a la semántica.
En este enfoque, cada símbolo no lógico es de uno de los siguientes tipos:
El enfoque tradicional se puede recuperar en el enfoque moderno, simplemente especificando que la firma "personalizada" consista en secuencias tradicionales de símbolos no lógicos.
Las reglas de formación definen los términos y fórmulas de la lógica de primer orden. [16] Cuando los términos y fórmulas se representan como cadenas de símbolos, estas reglas se pueden utilizar para escribir una gramática formal para términos y fórmulas. Estas reglas generalmente no tienen 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 iniciales, por ejemplo las variables en el caso de los términos.
El conjunto de términos se define inductivamente mediante las siguientes reglas: [17]
Sólo 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 incluya un símbolo de predicado es un término.
El conjunto de fórmulas (también llamadas fórmulas bien formadas [18] o WFF ) se define inductivamente mediante las siguientes reglas:
Sólo las expresiones que pueden obtenerse mediante un número finito de aplicaciones de las reglas 1 a 5 son fórmulas. Se dice que las fórmulas obtenidas de las dos primeras reglas son fórmulas atómicas .
Por ejemplo:
es una fórmula, si f es un símbolo de función unaria, P un símbolo de predicado unario y Q un símbolo de predicado ternario. Sin embargo, no es una fórmula, aunque sí una cadena de símbolos del alfabeto.
La función de los paréntesis en la definición es garantizar que cualquier fórmula sólo pueda obtenerse 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 sobre dónde se utilizan paréntesis en las fórmulas. Por ejemplo, algunos autores utilizan 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 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 falsa. 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, añaden esto. [19]
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:
Además, se pueden insertar puntuaciones adicionales que no sean requeridas por la definición, para que las fórmulas sean más fáciles de leer. Así la fórmula:
podría escribirse como:
En algunos campos, es común utilizar notación infija para relaciones y funciones binarias, en lugar de la notación de prefijo 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 versus representación .
Las definiciones anteriores utilizan notación infija para conectivos binarios como . Una convención menos común es la notación polaca , en la que se escribe , y así sucesivamente 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 rara vez se utiliza en la práctica porque es difícil de leer para los humanos. En notación polaca, la fórmula:
se convierte en "∀x∀y→Pfx¬→ PxQfyxz".
En una fórmula, una variable puede aparecer libre o ligada (o ambas). Una formalización de esta noción se debe a Quine: primero se define el concepto de ocurrencia de variable, luego si una ocurrencia de variable es libre o ligada, luego si un símbolo de variable en general es libre o ligado. Para distinguir diferentes apariciones del símbolo x idéntico, cada aparición de un símbolo x variable en una fórmula φ se identifica con la subcadena inicial de φ hasta el punto en el que aparece dicha instancia del símbolo x . [8] p.297 Entonces, se dice que una ocurrencia de x está ligada si esa ocurrencia de x se encuentra dentro del alcance de al menos uno de o . Finalmente, x está ligado en φ si todas las apariciones de x en φ están ligadas. [8] págs.142--143
Intuitivamente, un símbolo de variable es libre en una fórmula si en ningún momento se cuantifica: [8] pp.142--143 en ∀ y P ( x , y ) , la única aparición de la variable x es libre mientras que la de y es atado. Las apariciones de variables libres y ligadas en una fórmula se definen inductivamente de la siguiente manera.
Por ejemplo, en ∀ x ∀ y ( P ( x ) → Q ( x , f ( x ), z )) , x e y ocurren solo ligados, [20] z ocurre solo libre y w no es ninguno de los dos porque no ocurren en la fórmula.
Las variables libres y ligadas de una fórmula no tienen por qué ser conjuntos disjuntos: en la fórmula P ( x ) → ∀ x Q ( x ) , la primera aparición de x , como argumento de P , es libre mientras que la segunda, como argumento de Q , está obligado.
Una fórmula en lógica de primer orden sin apariciones de variables libres se llama 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 x representa. Pero la oración ∃ x Phil( x ) será verdadera o falsa en una interpretación dada.
En matemáticas, el lenguaje de 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 ≤. Entonces:
Los axiomas de grupos abelianos ordenados se pueden expresar como un conjunto de oraciones en el idioma. Por ejemplo, el axioma que establece que el grupo es conmutativo suele escribirse
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 constante) en ese lenguaje. También determina un dominio del 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 y a 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 detallará aquí).
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 del discurso D y una función de interpretación I que asigna 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 afirmación sobre estos objetos; por ejemplo, establece la existencia de algún objeto en D para el cual el predicado P es verdadero (o, más precisamente, para el cual el predicado asignado al símbolo de predicado P por la interpretación es verdadero). Por ejemplo, se puede tomar D como el conjunto de números enteros .
Los símbolos no lógicos se interpretan de la siguiente manera:
Una fórmula se evalúa como verdadera o falsa dada una interpretación y una asignación de variable μ que asocia un elemento del dominio del discurso con cada variable. La razón por la que se requiere una asignación de variable es para dar significado a fórmulas con variables libres, como . El valor de verdad de esta fórmula cambia según los valores que denotan xey .
En primer lugar, la asignación de variable μ puede extenderse a todos los términos de la lengua, con el resultado de que cada término se asigna a un único elemento del dominio del discurso. Para realizar esta asignación se utilizan las siguientes reglas:
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.
Si una fórmula no contiene variables libres, al igual que una oración, entonces la asignación de variable inicial no afecta su valor de verdad. En otras palabras, una oración es verdadera según M y si y solo si es verdadera según M y cualquier otra asignación de variable .
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 de modo que cada nuevo símbolo constante se asigna a su elemento correspondiente del dominio. Ahora se define sintácticamente la verdad para fórmulas cuantificadas, de la siguiente manera:
Este enfoque alternativo proporciona exactamente los mismos valores de verdad a todas las oraciones que el enfoque mediante asignaciones de variables.
Si una oración φ se evalúa como verdadera bajo una interpretación dada M , se dice que M satisface φ; esto se denota [21] . Una oración es satisfactoria si hay alguna interpretación según la cual es verdadera. Esto es un poco diferente del símbolo de la teoría de modelos, donde denota satisfacibilidad en un modelo, es decir, "hay una asignación adecuada de valores en el dominio de a símbolos variables de ". [22]
La satisfacibilidad de fórmulas con variables libres es más complicada, porque una interpretación por sí sola no determina el valor de verdad de dicha fórmula. La convención más común es que una fórmula φ con variables libres ,..., se dice que se satisface mediante una interpretación si la fórmula φ sigue siendo verdadera independientemente de qué individuos del dominio del discurso están asignados a sus variables libres ,..., . Esto tiene el mismo efecto que decir que una fórmula φ se cumple si y sólo si se cumple su cierre universal .
Una fórmula es lógicamente válida (o simplemente válida ) si es verdadera en todas las interpretaciones. [23] Estas fórmulas desempeñan 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 cada interpretación que hace que ψ sea verdadera también hace que φ sea verdadera. En este caso se dice que φ está lógicamente implicado por ψ.
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 lógica proposicional de Lindenbaum-Tarski . 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 de vinculación de variables:
Todas estas álgebras son redes que extienden adecuadamente 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 en el alcance de más de tres cuantificadores tiene el mismo poder expresivo que el álgebra de relaciones . [24] : 32–33 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 . [25] : 803
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 incluyan también todas las consecuencias lógicas de los axiomas. Se considera que los axiomas son válidos dentro de la teoría y de ellos se pueden derivar otras oraciones que sean válidas dentro de la teoría.
Una estructura de primer orden que satisface todas las oraciones de una teoría dada se dice que es un modelo de 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 teoría de modelos .
Muchas teorías tienen una interpretación prevista , un modelo determinado 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 que la 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.
La definición anterior requiere que el dominio del discurso de cualquier interpretación no esté 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 sólo puede ser una clase elemental en lógica de primer orden si se permiten dominios vacíos o si la estructura vacía se elimina de la clase. .
Sin embargo, existen varias dificultades con los dominios vacíos:
Por 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.
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 del secuente , 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 a menudo se denominan derivaciones en la teoría de la prueba. A menudo también se les llama 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 pueda derivarse del sistema es lógicamente válida. Por el contrario, un sistema deductivo es completo si toda fórmula lógicamente válida es derivable. Todos los sistemas analizados en este artículo son sólidos y completos. También comparten la propiedad de que es posible comprobar efectivamente que una deducción supuestamente válida es en realidad una deducción; Estos sistemas de deducción se denominan efectivos .
Una propiedad clave de los sistemas deductivos es que son puramente sintácticos, de modo que las derivaciones pueden verificarse sin considerar ninguna interpretación. Por tanto, un argumento sólido es correcto en todas las interpretaciones posibles del lenguaje, independientemente de si esa interpretación se refiere a matemáticas, economía o alguna otra área.
En general, la consecuencia lógica en lógica de primer orden es sólo semidecidible : si una oración A implica lógicamente una oración B, entonces esta se puede descubrir (por ejemplo, buscando una prueba hasta encontrarla, usando alguna prueba efectiva, sólida y completa). sistema). Sin embargo, si A no implica lógicamente B, esto no significa que A implique lógicamente la negación de B. No existe un procedimiento eficaz que, dadas las fórmulas A y B, decida siempre correctamente si A implica lógicamente B.
Una regla de inferencia establece que, dada una fórmula particular (o conjunto de fórmulas) con una determinada propiedad como hipótesis, se puede derivar otra fórmula (o conjunto de fórmulas) específica como conclusión. La regla es sólida (o preserva la verdad) si preserva la validez en el sentido de que siempre que cualquier 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 contiene 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 ninguna variable libre de t quede ligada durante el proceso de sustitución. (Si alguna variable libre de t queda ligada, entonces para sustituir x por t primero es necesario cambiar las variables ligadas de φ para que difieran de las variables libres de t ).
Para ver por qué es necesaria la restricción de las variables ligadas, considere la fórmula lógicamente válida φ dada por , en la firma de (0,1,+,×,=) de la aritmética. Si t es el término "x + 1", la fórmula φ[ t / y ] es , lo cual será falso en muchas interpretaciones. El problema es que la variable libre x de t quedó ligada durante la sustitución. El reemplazo deseado se puede obtener cambiando el nombre de la variable ligada x de φ a otra cosa, digamos z , de modo que la fórmula después de la sustitución sea , que nuevamente es lógicamente válida.
La regla de sustitución demuestra varios aspectos comunes de las reglas de inferencia. Es enteramente sintáctico; se puede decir si se aplicó correctamente sin apelar a ninguna interpretación. Tiene limitaciones (sintácticamente definidas) sobre cuándo se puede aplicar, que deben respetarse para preservar la exactitud 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.
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 mediante una regla de inferencia. Los axiomas lógicos constan de 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 del estilo de Hilbert tienen una pequeña cantidad de reglas de inferencia, junto con varios esquemas infinitos de axiomas lógicos. Es común tener sólo modus ponens y generalización universal como reglas de inferencia.
Los sistemas de deducción natural se parecen 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; lo compensan agregando reglas de inferencia adicionales que pueden usarse para manipular los conectivos lógicos en las fórmulas de la prueba.
El cálculo siguiente se desarrolló para estudiar las propiedades de los sistemas de deducción natural. [26] En lugar de trabajar con una fórmula a la vez, utiliza secuencias , que son expresiones de la forma:
donde A 1 , ..., An , B 1 , ..., B k son fórmulas y el símbolo del torniquete se utiliza como puntuación para separar las dos mitades. Intuitivamente, un secuente expresa la idea que implica .
A diferencia de los métodos que acabamos de describir, las derivaciones en el método de cuadros 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 demostrable, el método de cuadros intenta demostrar que la negación de A es insatisfactoria. El árbol de la derivación tiene en su raíz; el árbol se ramifica de una manera que refleja la estructura de la fórmula. Por ejemplo, para demostrar que es insatisfactorio es necesario demostrar que C y D son insatisfactorios; esto corresponde a un punto de ramificación en el árbol con el padre y los hijos C y D.
La regla de resolución es una regla única 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 demuestra demostrando que la negación de la fórmula es insatisfactoria. La resolución se utiliza comúnmente en la demostración automatizada 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 primero deben convertirse a esta forma mediante Skolemización . La regla de resolución establece que a partir de las hipótesis y , se puede obtener la conclusión .
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 conectivos y son útiles para poner fórmulas en forma normal prenex . Algunas identidades demostrables incluyen:
Existen varias convenciones diferentes para utilizar 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, de modo que los "dos" miembros dados son los mismo miembro. Este enfoque también añade ciertos axiomas sobre la igualdad al sistema deductivo empleado. Estos axiomas de igualdad son: [27] : 198–200
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 sustitución". 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:
Muchas otras propiedades de la igualdad son consecuencias de los axiomas anteriores, por ejemplo:
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, estos satisfarán exactamente las mismas fórmulas bajo cualquier interpretación). Es decir, la relación de igualdad ahora puede interpretarse mediante una relación de equivalencia arbitraria en el dominio del discurso que sea 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 utiliza para referirse a una interpretación en la que ningún individuo distinto a y b satisface a = b . En lógica de primer orden con igualdad, sólo se consideran modelos normales, por lo que no existe ningún término para un modelo que no sea modelo normal. Cuando se estudia 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 los 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.
Si una teoría tiene una fórmula binaria A ( x , y ) que satisface la reflexividad y la ley de Leibniz, se dice que la teoría tiene igualdad o que es una teoría con igualdad. Es posible que la teoría no tenga todos los ejemplos de los esquemas anteriores como axiomas, sino más bien 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 como iguales si alguna relación no cambia cambiando s por t en cualquier argumento.
Algunas teorías permiten otras definiciones ad hoc de igualdad:
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 lógica de primer orden en sí, más que a propiedades de teorías individuales. Proporcionan herramientas fundamentales para la construcción de modelos de teorías de primer orden.
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 φ; En general, estos modelos tendrán una cardinalidad arbitrariamente grande, por lo que las consecuencias lógicas no se pueden 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á lógicamente implícito en φ, eventualmente se encontrará tal derivación. Por tanto, la consecuencia lógica de primer orden es semidecidible : es posible hacer una enumeración efectiva de todos los pares de oraciones (φ,ψ) tales 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 (distinto de la igualdad). Esto significa que no existe ningún procedimiento de decisión que determine si fórmulas arbitrarias son lógicamente válidas. Este resultado fue establecido independientemente 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 pruebas demuestran una conexión entre la insolubilidad del problema de decisión por primera vez. 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 consecuencias lógicas es decidible. Estos incluyen la lógica proposicional y la lógica de predicados monádicos , que es 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 Bernays-Schönfinkel de fórmulas de primer orden 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 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 a λ. 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 sólo 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 pueden axiomatizarse 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: cualquier teoría de primer orden con un modelo infinito también tiene un modelo de cardinalidad mayor que el continuo. Dado que la recta real es infinita, cualquier teoría satisfecha por la recta real también lo es por algunos modelos no estándar . Cuando el teorema de Löwenheim-Skolem se aplica a teorías de conjuntos de primer orden, las consecuencias no intuitivas se conocen como paradoja de Skolem .
El teorema de la compacidad establece que un conjunto de oraciones de primer orden tiene un modelo si y sólo si cada subconjunto finito del mismo tiene un modelo. [30] 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, ya que proporciona un método fundamental para construir modelos.
El teorema de la compacidad tiene un efecto limitante sobre qué colecciones de estructuras de primer orden son clases elementales. Por ejemplo, el teorema de la compacidad implica que cualquier teoría que tenga modelos finitos arbitrariamente grandes tiene un modelo infinito. Por tanto, la clase de todos los gráficos finitos no es una clase elemental (lo mismo ocurre con muchas otras estructuras algebraicas).
También hay limitaciones más sutiles de la lógica de primer orden que están implícitas en el teorema de la compacidad. Por ejemplo, en informática, muchas situaciones se pueden modelar como un gráfico dirigido de estados (nodos) y conexiones (bordes dirigidos). Para validar un sistema de este tipo puede ser necesario demostrar que no se puede alcanzar ningún estado "malo" desde ningún estado "bueno". Por lo tanto, se busca determinar si los estados buenos y malos están en diferentes componentes conectados del gráfico. Sin embargo, el teorema de la compacidad se puede utilizar para demostrar que los gráficos conectados no son una clase elemental en la lógica de primer orden, y no existe una fórmula φ( x , y ) de la lógica de primer orden, en la lógica de los gráficos , que exprese la idea de que hay un camino de x a y . Sin embargo , la conectividad se puede expresar en lógica de segundo orden , pero no solo con cuantificadores de conjuntos existenciales, ya que también goza de compacidad.
Per Lindström demostró que las propiedades metalógicas que acabamos de discutir caracterizan en realidad la lógica de primer orden en el sentido de que ninguna lógica más fuerte puede tener también 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:
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 indecidible, lo que significa que es imposible un algoritmo de decisión sólido, completo y definitivo para la demostrabilidad. Esto ha llevado al estudio de interesantes fragmentos decidibles, como C 2 : lógica de primer orden con dos variables y los cuantificadores de conteo y . [31]
El teorema de Löwenheim-Skolem muestra que si una teoría de primer orden tiene un 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 . Por tanto, 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 la lógica infinitaria y la lógica de orden superior, son más expresivas en el sentido de que permiten axiomatizaciones categóricas de los números naturales o reales [ aclaración necesaria ] . Sin embargo, esta expresividad tiene un costo metalógico: según el teorema de Lindström , el teorema de compacidad y el teorema descendente de Löwenheim-Skolem no pueden sostenerse en ninguna lógica más fuerte que la de primer orden.
La lógica de primer orden es capaz de formalizar muchas construcciones de cuantificadores simples 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í, existen características complicadas del lenguaje natural que no pueden expresarse 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". [32]
Existen muchas variaciones de la lógica de primer orden. Algunos de ellos 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, ampliando la semántica mediante cuantificadores adicionales u otros nuevos símbolos lógicos. Por ejemplo, la lógica infinita permite fórmulas de tamaño infinito y la lógica modal añade símbolos de posibilidad y necesidad.
La lógica de primer orden se puede estudiar en lenguajes con menos símbolos lógicos que los descritos anteriormente:
Restricciones como estas son útiles como técnica para reducir el número de reglas de inferencia o esquemas de axiomas en sistemas deductivos, lo que conduce a pruebas más breves de resultados metalógicos. El costo de las restricciones es que se vuelve más difícil expresar enunciados en lenguaje natural en el sistema formal en cuestión, porque los conectivos lógicos utilizados en los enunciados en lenguaje natural deben ser reemplazados por sus definiciones (más largas) en términos de la colección restringida de conectivos 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 tanto, existe un equilibrio entre la facilidad de trabajar dentro del sistema formal y la facilidad de demostrar resultados sobre el sistema formal.
También es posible restringir las aridades de los símbolos de función y de los símbolos de predicados, en teorías suficientemente expresivas. En principio, se puede prescindir por completo de funciones de aridad mayores que 2 y predicados de aridad mayores 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 cumplan los axiomas naturales de una función de emparejamiento y sus proyecciones.
Las interpretaciones ordinarias de primer orden tienen un único dominio de discurso en el que oscilan todos los cuantificadores. La lógica de primer orden con muchos ordenamientos permite que las variables tengan diferentes tipos , que tienen diferentes dominios. Esto también se denomina lógica tipificada de primer orden y las clases se denominan tipos (como en tipo de datos ), pero no es lo mismo que la teoría de tipos de primer orden . La lógica multiordenada de primer orden se utiliza a menudo en el estudio de la aritmética de segundo orden . [34]
Cuando sólo hay un número finito de tipos en una teoría, la lógica de primer orden con muchos tipos puede reducirse a una lógica de primer orden con un solo orden. [35] : 296–299 Se introduce en la teoría de orden único un símbolo de predicado unario para cada tipo en la teoría de orden múltiple y se agrega un axioma que dice que estos predicados unarios dividen el dominio del discurso. Por ejemplo, si hay dos tipos, se agregan los símbolos de predicado y el axioma:
Entonces, los elementos que satisfacen se consideran elementos del primer tipo, y los elementos que satisfacen, como elementos del segundo tipo. Se puede cuantificar cada tipo utilizando el símbolo de predicado correspondiente para limitar el rango de cuantificación. Por ejemplo, para decir que hay un elemento del primer tipo que satisface la fórmula φ( x ), se escribe:
Se pueden agregar cuantificadores adicionales a la lógica de primer orden.
La lógica infinita permite oraciones infinitamente largas. Por ejemplo, se puede permitir una conjunción o disyunción de infinitas fórmulas, o una cuantificación de infinitas variables. Surgen oraciones infinitamente largas 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 infinitas conjunciones y disyunciones. Sin embargo, también es posible admitir firmas generalizadas en las que se permite que los símbolos de función y relación tengan infinitas aridades, o en las que los cuantificadores pueden vincular infinitas variables. Debido a que una fórmula infinita no puede representarse 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 infinitarias más comúnmente estudiadas se denominan 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. De manera más general, 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 sólo un número finito de ellas pueden estar en el alcance de cualquier cuantificador cuando una fórmula aparece como subfórmula de otra. [36] En otras lógicas infinitas, una subfórmula puede estar en el alcance de infinitos cuantificadores. Por ejemplo, en L κ∞ , un único cuantificador universal o existencial puede vincular arbitrariamente muchas variables simultáneamente. De manera similar, la lógica L κλ permite la cuantificación simultánea de menos de λ variables, así como conjunciones y disyunciones de tamaño menor que κ.
La lógica de punto fijo extiende la lógica de primer orden agregando el cierre bajo los puntos menos fijos de los operadores positivos. [37]
El rasgo característico de la lógica de primer orden es que los individuos pueden cuantificarse, pero no los predicados. De este modo
es una fórmula legal de primer orden, pero
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 añadiendo este último tipo de cuantificación. Otras lógicas de orden superior permiten la cuantificación de tipos aún mayores que 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 pueden cuantificarse.
A diferencia de la lógica de primer orden, para la cual sólo 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 eficaz para la lógica de segundo orden que sea sólido y completo bajo una 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 forma única los números naturales y la recta 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.
La demostración automatizada de teoremas se refiere al desarrollo de programas informáticos que buscan y encuentran derivaciones (demostraciones formales) de teoremas matemáticos. [38] 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 complicadas funciones heurísticas para intentar encontrar una derivación en menos tiempo que una búsqueda ciega. [39]
El área relacionada de verificación automatizada de pruebas utiliza programas informáticos para comprobar que las pruebas creadas por humanos sean correctas. A diferencia de los complicados demostradores de teoremas automatizados, los sistemas de verificación pueden ser lo suficientemente pequeños como para que su exactitud pueda comprobarse tanto manualmente como mediante verificación automatizada de software. Esta validación del verificador de pruebas es necesaria para dar confianza de que cualquier derivación etiquetada como "correcta" es realmente correcta.
Algunos verificadores de pruebas, como Metamath , insisten en tener una derivación completa como entrada. Otros, como Mizar e Isabelle , toman un boceto de prueba bien formateado (que aún puede ser muy largo y detallado) y completan las piezas que faltan mediante 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: se les conoce como asistentes de prueba . También pueden utilizar lógicas formales que sean más sólidas 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 para que la escriba un ser humano, [40] los resultados a menudo se formalizan como una serie de lemas, para los cuales las derivaciones se pueden construir por separado.
Los demostradores de teoremas automatizados también se utilizan para implementar la verificación formal en informática. En este entorno, los demostradores de teoremas se utilizan para verificar la exactitud de los programas y del hardware, como los procesadores, con respecto a una especificación formal . Como ese análisis requiere mucho tiempo y, por lo tanto, es costoso, normalmente se reserva para proyectos en los que un mal funcionamiento tendría graves consecuencias humanas o financieras.
Para el problema de 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 : ver Verificación de modelos § Lógica de primer orden .
![{\displaystyle (\lnot [\forall xP(x)])\to \exists x[\lnot P(x)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b34883b819ec8da58478c3cf001a557826a8bb9)
![{\displaystyle (\forall x\forall y\,[\mathop {\leq } (\mathop {+} (x,y),z)\to \forall x\,\forall y\,\mathop {+} (x,y)=0)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/540d5b5e22885c61946b05841d437c576e4c3b8c)
![{\displaystyle (\forall x)(\forall y)[x+y=y+x].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1649ba2cb0d9003b8558c4449aa8c137d6b4c1e6)
![{\displaystyle \forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ead06cc9bbab4a341137f21ec450deea1a63209)
![{\displaystyle \forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44b1e8b20e39514ecabe08db08307aeb674e9878)
