First-order logic

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable.^[1] This distinguishes it from propositional logic, which does not use quantifiers or relations;^[2] in this sense, propositional logic is the foundation of first-order logic.

A theory about a topic is usually a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set of axioms believed to hold about them. Sometimes, "theory" is understood in a more formal sense, which is just a set of sentences in first-order logic.

The adjective "first-order" distinguishes first-order logic from higher-order logic, in which there are predicates having predicates or functions as arguments, or in which predicate quantifiers or function quantifiers or both are permitted.^[3]:56​ In first-order theories, predicates are often associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets.

There are many deductive systems for first-order logic which are both sound (i.e., all provable statements are true in all models) and complete (i.e. all statements which are true in all models are provable). Although the logical consequence relation is only semidecidable, much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several metalogical theorems that make it amenable to analysis in proof theory, such as the Löwenheim–Skolem theorem and the compactness theorem.

First-order logic is the standard for the formalization of mathematics into axioms, and is studied in the foundations of mathematics.Peano arithmetic and Zermelo–Fraenkel set theory are axiomatizations of number theory and set theory, respectively, into first-order logic. No first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the natural numbers or the real line. Axiom systems that do fully describe these two structures (that is, categorical axiom systems) can be obtained in stronger logics such as second-order logic.

The foundations of first-order logic were developed independently by Gottlob Frege and Charles Sanders Peirce.^[4] For a history of first-order logic and how it came to dominate formal logic, see José Ferreirós (2001).

Вступление

В то время как логика высказываний имеет дело с простыми декларативными предложениями, логика первого порядка дополнительно охватывает предикаты и количественную оценку .

A predicate takes an entity or entities in the domain of discourse as input while outputs are either True or False. Consider the two sentences "Socrates is a philosopher" and "Plato is a philosopher". In propositional logic, these sentences are viewed as being unrelated, and might be denoted, for example, by variables such as p and q. The predicate "is a philosopher" occurs in both sentences, which have a common structure of "a is a philosopher". The variable aпредставлен как «Сократ» в первом предложении и как «Платон» во втором предложении. В то время как логика первого порядка допускает использование предикатов, таких как «является философом» в этом примере, логика высказываний - нет. ^[5]

Relationships between predicates can be stated using logical connectives. Consider, for example, the first-order formula "if a is a philosopher, then a is a scholar". This formula is a conditional statement with "a is a philosopher" as its hypothesis, and "a is a scholar" as its conclusion. The truth of this formula depends on which object is denoted by a, and on the interpretations of the predicates "is a philosopher" and "is a scholar".

Quantifiers can be applied to variables in a formula. The variable a in the previous formula can be universally quantified, for instance, with the first-order sentence "For every a, if a is a philosopher, then a is a scholar". The universal quantifier "for every" in this sentence expresses the idea that the claim "if a is a philosopher, then a is a scholar" holds for all choices of a.

The negation of the sentence "For every a, if a is a philosopher, then a is a scholar" is logically equivalent to the sentence "There exists a such that a is a philosopher and a is not a scholar". The existential quantifier "there exists" expresses the idea that the claim "a is a philosopher and a is not a scholar" holds for some choice of a.

Каждый из предикатов «философ» и «ученый» принимает одну переменную. Как правило, предикаты могут принимать несколько переменных. В предложении первого порядка «Сократ - учитель Платона» сказуемое «является учителем» принимает две переменные.

An interpretation (or model) of a first-order formula specifies what each predicate means, and the entities that can instantiate the variables. These entities form the domain of discourse or universe, which is usually required to be a nonempty set. For example, in an interpretation with the domain of discourse consisting of all human beings and the predicate "is a philosopher" understood as "was the author of the Republic", the sentence "There exists a such that a is a philosopher" is seen as being true, as witnessed by Plato.

Syntax

There are two key parts of first-order logic. The syntax determines which finite sequences of symbols are well-formed expressions in first-order logic, while the semantics determines the meanings behind these expressions.

Alphabet

В отличие от естественных языков, таких как английский, язык логики первого порядка является полностью формальным, так что можно механически определить, правильно ли сформировано данное выражение. Есть два ключевых типа правильно сформированных выражений: термины , которые интуитивно представляют объекты, и формулы , которые интуитивно выражают предикаты, которые могут быть истинными или ложными. Термины и формулы логики первого порядка представляют собой цепочки символов , где все символы вместе образуют алфавит языка. Как и во всех формальных языках , природа самих символов выходит за рамки формальной логики; их часто считают просто буквами и знаками препинания.

It is common to divide the symbols of the alphabet into logical symbols, which always have the same meaning, and non-logical symbols, whose meaning varies by interpretation. For example, the logical symbol ${\displaystyle \land }$ always represents "and"; it is never interpreted as "or", which is represented by the logical symbol ${\displaystyle \lor }$.^[6] On the other hand, a non-logical predicate symbol such as Phil(x) could be interpreted to mean "x is a philosopher", "x is a man named Philip", or any other unary predicate depending on the interpretation at hand.

Logical symbols

There are several logical symbols in the alphabet, which vary by author but usually include:^[6][7]

• The quantifier symbols: ∀ for universal quantification, and ∃ for existential quantification
• The logical connectives: ∧ for conjunction, ∨ for disjunction, → for implication, ↔ for biconditional, ¬ for negation. Occasionally other logical connective symbols are included. Some authors^[8] use Cpq, instead of →, and Epq, instead of ↔, especially in contexts where → is used for other purposes. Moreover, the horseshoe ⊃ may replace →; the triple-bar ≡ may replace ↔; a tilde (~), Np, or Fp, may replace ¬; a double bar ${\displaystyle \|}$, ${\displaystyle +}$ or Apq may replace ∨; and ampersand &, Kpq, or the middle dot, ⋅, may replace ∧, especially if these symbols are not available for technical reasons. (The aforementioned symbols Cpq, Epq, Np, Apq, and Kpq are used in Polish notation.)
• Parentheses, brackets, and other punctuation symbols. The choice of such symbols varies depending on context.
• Бесконечный набор переменных , часто обозначаемых строчными буквами в конце алфавита x , y , z , .... Индексы часто используются для различения переменных: x ₀ , x ₁ , x ₂ , ....
• Символ равенства (иногда, символ идентичности ) = ; см. раздел о равенстве ниже .

Не все эти символы требуются - достаточно только одного из кванторов, отрицания и конъюнкции, переменных, скобок и равенства. Есть множество незначительных вариаций, которые могут определять дополнительные логические символы:

• In some occasions, the truth constants T, Vpq, or ⊤, for "true" and F, Opq, or ⊥, for "false" are included. Without any such logical operators of valence 0, these two constants can only be expressed using quantifiers.
• In other occasions, additional logical connectives are included, such as the Sheffer stroke, Dpq (NAND), and exclusive or, Jpq.

Non-logical symbols

The non-logical symbols represent predicates (relations), functions and constants on the domain of discourse. It used to be standard practice to use a fixed, infinite set of non-logical symbols for all purposes. A more recent practice is to use different non-logical symbols according to the application one has in mind. Therefore, it has become necessary to name the set of all non-logical symbols used in a particular application. This choice is made via a signature.^[9]

The traditional approach is to have only one, infinite, set of non-logical symbols (one signature) for all applications. Consequently, under the traditional approach there is only one language of first-order logic.^[10] This approach is still common, especially in philosophically oriented books.

1. For every integer n ≥ 0, there is a collection of n-ary, or n-place, predicate symbols. Because they represent relations between n elements, they are also called relation symbols. For each arity n, we have an infinite supply of them:

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

2. For every integer n ≥ 0, there are infinitely many n-ary function symbols:

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

In contemporary mathematical logic, the signature varies by application. Typical signatures in mathematics are {1, ×} or just {×} for groups, or {0, 1, +, ×, <} for ordered fields. There are no restrictions on the number of non-logical symbols. The signature can be empty, finite, or infinite, even uncountable. Uncountable signatures occur for example in modern proofs of the Löwenheim–Skolem theorem.

In this approach, every non-logical symbol is of one of the following types.

1. A predicate symbol (or relation symbol) with some valence (or arity, number of arguments) greater than or equal to 0. These are often denoted by uppercase letters such as P, Q and R.^[6]
   • Relations of valence 0 can be identified with propositional variables. For example, P, which can stand for any statement.
   • For example, P(x) is a predicate variable of valence 1. One possible interpretation is "x is a man".
   • Q(x,y) is a predicate variable of valence 2. Possible interpretations include "x is greater than y" and "x is the father of y".
2. A function symbol, with some valence greater than or equal to 0. These are often denoted by lowercase roman letters such as f, g and h.^[6]
   • Examples: f(x) may be interpreted as for "the father of x". In arithmetic, it may stand for "-x". In set theory, it may stand for "the power set of x". In arithmetic, g(x,y) may stand for "x+y". In set theory, it may stand for "the union of x and y".
   • Function symbols of valence 0 are called constant symbols, and are often denoted by lowercase letters at the beginning of the alphabet such as a, b and c.^[6] The symbol a may stand for Socrates. In arithmetic, it may stand for 0. In set theory, such a constant may stand for the empty set.

The traditional approach can be recovered in the modern approach, by simply specifying the "custom" signature to consist of the traditional sequences of non-logical symbols.

Formation rules

<index> ::= "" | <index> "'"<variable> ::= "x" <index><constant> ::= "c" <index><unary function> ::= "f1" <index><binary function> ::= "f2" <index><ternary function> ::= "f3" <index><unary predicate> ::= "p1" <index><binary predicate> ::= "p2" <index><ternary predicate> ::= "p3" <index><term> ::= <variable> | <constant> | <unary function> "(" <term> ")" | <binary function> "(" <term> "," <term> ")" | <ternary function> "(" <term> "," <term> "," <term> ")"<atomic formula> ::= "TRUE" | "FALSE" | < термин > "=" < термин > | < унарный предикат > "(" < термин > ")" | < бинарный предикат > "(" < термин > "," < термин > ")" | <ternary predicate> "(" <term> "," <term> "," <term> ")"<formula> ::= <atomic formula> | "¬" <formula> | <formula> "∧" <formula> | <formula> "∨" <formula> | < формула > "⇒" < формула > | < формула > «⇔» < формула > | "(" < формула > ")" | «∀» < переменная >  < формула > | «∃» < переменная >  < формула >

The formation rules define the terms and formulas of first-order logic.^[13] When terms and formulas are represented as strings of symbols, these rules can be used to write a formal grammar for terms and formulas. These rules are generally context-free (each production has a single symbol on the left side), except that the set of symbols may be allowed to be infinite and there may be many start symbols, for example the variables in the case of terms.

Terms

The set of terms is inductively defined by the following rules:

1. Variables. Any variable is a term.
2. Functions. Any expression f(t₁,...,t_n) of n arguments (where each argument t_i is a term and f is a function symbol of valence n) is a term. In particular, symbols denoting individual constants are nullary function symbols, and thus are terms.

Only expressions which can be obtained by finitely many applications of rules 1 and 2 are terms. For example, no expression involving a predicate symbol is a term.

Formulas

The set of formulas (also called well-formed formulas^[14] or WFFs) is inductively defined by the following rules:

1. Predicate symbols. If P is an n-ary predicate symbol and t₁, ..., t_n are terms then P(t₁,...,t_n) is a formula.
2. Equality. If the equality symbol is considered part of logic, and t₁ and t₂ are terms, then t₁ = t₂ is a formula.
3. Negation. If ${\displaystyle \varphi }$ is a formula, then ${\displaystyle \lnot \varphi }$ is a formula.
4. Бинарные связки. Если и являются формулами, то ( ) является формулой. Подобные правила применяются к другим двоичным логическим связкам.${\displaystyle \varphi }$${\displaystyle \psi }$${\displaystyle \varphi \rightarrow \psi }$
5. Квантификаторы. Если - формула, а x - переменная, то (для всех x выполняется) и (существует x такой, что ) являются формулами.${\displaystyle \varphi }$${\displaystyle \forall x\varphi }$${\displaystyle \varphi }$${\displaystyle \exists x\varphi }$${\displaystyle \varphi }$

Формулами являются только выражения, которые можно получить конечным числом применений правил 1–5. Формулы, полученные из первых двух правил, называются атомарными формулами .

Например,

${\displaystyle \forall x\forall y(P(f(x))\rightarrow \neg (P(x)\rightarrow Q(f(y),x,z)))}$

is a formula, if f is a unary function symbol, P a unary predicate symbol, and Q a ternary predicate symbol. On the other hand, ${\displaystyle \forall x\,x\rightarrow }$ is not a formula, although it is a string of symbols from the alphabet.

Роль круглых скобок в определении состоит в том, чтобы гарантировать, что любую формулу можно получить только одним способом - следуя индуктивному определению (т. Е. Существует уникальное дерево синтаксического анализа для каждой формулы). Это свойство известно как уникальная читаемость формул. Существует много соглашений о том, где скобки используются в формулах. Например, некоторые авторы используют двоеточия или точки вместо круглых скобок или меняют места, в которых они вставляются. Конкретное определение каждого автора должно сопровождаться доказательством уникальной читаемости.

Это определение формулы не поддерживает определение функции if-then-else ite(c, a, b), где «c» - это условие, выраженное в виде формулы, которая вернет «a», если c истинно, и «b», если оно ложно. Это связано с тем, что и предикаты, и функции могут принимать только термины в качестве параметров, но первый параметр - это формула. Некоторые языки, построенные на логике первого порядка, такие как SMT-LIB 2.0, добавляют это. ^[15]

Условные обозначения

Для удобства были разработаны соглашения о приоритете логических операторов, чтобы избежать необходимости писать круглые скобки в некоторых случаях. Эти правила аналогичны порядку операций в арифметике. Обычное соглашение:

• ${\displaystyle \lnot }$ оценивается в первую очередь
• ${\displaystyle \land }$и оцениваются далее${\displaystyle \lor }$
• Далее оцениваются кванторы.
• ${\displaystyle \to }$ оценивается последней.

Более того, могут быть вставлены лишние знаки препинания, не требуемые определением, для облегчения чтения формул. Таким образом, формула

${\displaystyle \lnot \forall xP(x)\to \exists x\lnot P(x)}$

можно было бы записать как

${\displaystyle (\lnot [\forall xP(x)])\to \exists x[\lnot P(x)].}$

В некоторых полях обычно используется инфиксная нотация для двоичных отношений и функций вместо префиксной нотации, определенной выше. Например, в арифметике обычно пишут «2 + 2 = 4» вместо «= (+ (2,2), 4)». Принято рассматривать формулы в инфиксной записи как аббревиатуры для соответствующих формул в префиксной записи, ср. также временная структура против представления .

The definitions above use infix notation for binary connectives such as ${\displaystyle \to }$. A less common convention is Polish notation, in which one writes ${\displaystyle \rightarrow }$, ${\displaystyle \wedge }$ and so on in front of their arguments rather than between them. This convention is advantageous in that it allows all punctuation symbols to be discarded. As such, Polish notation is compact and elegant, but rarely used in practice because it is hard for humans to read. In Polish notation, the formula

${\displaystyle \forall x\forall y(P(f(x))\rightarrow \neg (P(x)\rightarrow Q(f(y),x,z)))}$

becomes "∀x∀y→Pfx¬→ PxQfyxz".

Free and bound variables

In a formula, a variable may occur free or bound (or both). Intuitively, a variable occurrence is free in a formula if it is not quantified:^[16] in ∀y P(x, y), the sole occurrence of variable x is free while that of y is bound. The free and bound variable occurrences in a formula are defined inductively as follows.

Atomic formulas

If φ is an atomic formula, then x occurs free in φ if and only if x occurs in φ. Moreover, there are no bound variables in any atomic formula.

Negation

x occurs free in ¬φ if and only if x occurs free in φ. x occurs bound in ¬φ if and only if x occurs bound in φ

Binary connectives

x occurs free in (φ → ψ) if and only if x occurs free in either φ or ψ. x occurs bound in (φ → ψ) if and only if x occurs bound in either φ or ψ. The same rule applies to any other binary connective in place of →.

Quantifiers

x occurs free in ∀y φ, if and only if x occurs free in φ and x is a different symbol from y. Also, x occurs bound in ∀y φ, if and only if x is y or x occurs bound in φ. The same rule holds with ∃ in place of ∀.

For example, in ∀x ∀y (P(x) → Q(x,f(x),z)), x and y occur only bound,^[17] z occurs only free, and w is neither because it does not occur in the formula.

Free and bound variables of a formula need not be disjoint sets: in the formula P(x) → ∀x Q(x), the first occurrence of x, as argument of P, is free while the second one, as argument of Q, is bound.

A formula in first-order logic with no free variable occurrences is called a first-order sentence. These are the formulas that will have well-defined truth values under an interpretation. For example, whether a formula such as Phil(x) is true must depend on what x represents. But the sentence ∃x Phil(x) will be either true or false in a given interpretation.

Example: ordered abelian groups

In mathematics, the language of ordered abelian groups has one constant symbol 0, one unary function symbol −, one binary function symbol +, and one binary relation symbol ≤. Then:

• Выражения + ( x , y ) и + ( x , + ( y , - ( z ))) являются терминами . Обычно они записываются как x + y и x + y - z .
• Выражения + ( x , y ) = 0 и ≤ (+ ( x , + ( y , - ( z ))), + ( x , y )) являются атомарными формулами . Обычно они записываются как x + y = 0 и x + y - z  ≤  x + y .
• Выражение представляет собой формулу , которая обычно записывается как Эта формула имеет одну свободную переменную z .${\displaystyle (\forall x\forall y\,[\mathop {\leq } (\mathop {+} (x,y),z)\to \forall x\,\forall y\,\mathop {+} (x,y)=0)]}$${\displaystyle \forall x\forall y(x+y\leq z)\to \forall x\forall y(x+y=0).}$

Аксиомы для упорядоченных абелевых групп могут быть выражены в виде набора предложений на языке. Например, аксиома о коммутативности группы обычно записывается${\displaystyle (\forall x)(\forall y)[x+y=y+x].}$

Семантика

Интерпретация языка первого порядка присваивает каждому денотат не-логического символа в этом языке. Он также определяет область дискурса, которая определяет диапазон кванторов. В результате каждому термину назначается объект, который он представляет, каждому предикату присваивается свойство объектов и каждому предложению присваивается значение истинности. Таким образом, интерпретация придает семантическое значение терминам, предикатам и формулам языка. Изучение интерпретаций формальных языков называется формальной семантикой . Далее следует описание стандартной или тарской семантики для логики первого порядка. (Также можно определить семантику игры для логики первого порядка, but aside from requiring the axiom of choice, game semantics agree with Tarskian semantics for first-order logic, so game semantics will not be elaborated herein.)

The domain of discourse D is a nonempty set of "objects" of some kind. Intuitively, a first-order formula is a statement about these objects; for example, ${\displaystyle \exists xP(x)}$ states the existence of an object x such that the predicate P is true where referred to it. The domain of discourse is the set of considered objects. For example, one can take ${\displaystyle D}$ to be the set of integer numbers.

The interpretation of a function symbol is a function. For example, if the domain of discourse consists of integers, a function symbol f of arity 2 can be interpreted as the function that gives the sum of its arguments. In other words, the symbol f is associated with the function ${\displaystyle I(f)}$ which, in this interpretation, is addition.

The interpretation of a constant symbol is a function from the one-element set D⁰ to D, which can be simply identified with an object in D. For example, an interpretation may assign the value ${\displaystyle I(c)=10}$ to the constant symbol ${\displaystyle c}$.

Интерпретация n -арного предикатного символа - это набор n - кортежей элементов предметной области дискурса. Это означает, что, учитывая интерпретацию, предикатный символ и n элементов предметной области, можно сказать, является ли предикат истинным для этих элементов в соответствии с данной интерпретацией. Например, интерпретация I (P) двоичного символа предиката P может быть набором пар целых чисел, так что первое меньше второго. Согласно этой интерпретации, предикат P будет истинным, если его первый аргумент меньше второго.

Структуры первого порядка

Наиболее распространенный способ определения интерпретации (особенно в математике) - это указать структуру (также называемую моделью ; см. Ниже). Структура состоит из непустого множества D , образующего область дискурса, и интерпретации I нелогических терминов подписи. Эта интерпретация сама по себе является функцией:

• Каждый символ функции F арности п присваивается функция от до D . В частности, каждому постоянному символу подписи присваивается индивидуум в предметной области.${\displaystyle I(f)}$${\displaystyle D^{n}}$
• Each predicate symbol P of arity n is assigned a relation ${\displaystyle I(P)}$ over ${\displaystyle D^{n}}$ or, equivalently, a function from ${\displaystyle D^{n}}$ to ${\displaystyle \{\mathrm {true,false} \}}$. Thus each predicate symbol is interpreted by a Boolean-valued function on D.

Evaluation of truth values

A formula evaluates to true or false given an interpretation, and a variable assignment μ that associates an element of the domain of discourse with each variable. The reason that a variable assignment is required is to give meanings to formulas with free variables, such as ${\displaystyle y=x}$. The truth value of this formula changes depending on whether x and y denote the same individual.

First, the variable assignment μ can be extended to all terms of the language, with the result that each term maps to a single element of the domain of discourse. The following rules are used to make this assignment:

1. Variables. Each variable x evaluates to μ(x)
2. Functions. Given terms ${\displaystyle t_{1},\ldots ,t_{n}}$ that have been evaluated to elements ${\displaystyle d_{1},\ldots ,d_{n}}$ of the domain of discourse, and a n-ary function symbol f, the term ${\displaystyle f(t_{1},\ldots ,t_{n})}$ evaluates to ${\displaystyle (I(f))(d_{1},\ldots ,d_{n})}$.

Next, each formula is assigned a truth value. The inductive definition used to make this assignment is called the T-schema.

1. Atomic formulas (1). A formula ${\displaystyle P(t_{1},\ldots ,t_{n})}$ is associated the value true or false depending on whether ${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle \in I(P)}$, where ${\displaystyle v_{1},\ldots ,v_{n}}$ are the evaluation of the terms ${\displaystyle t_{1},\ldots ,t_{n}}$ and ${\displaystyle I(P)}$ is the interpretation of ${\displaystyle P}$, which by assumption is a subset of ${\displaystyle D^{n}}$.
2. Atomic formulas (2). A formula ${\displaystyle t_{1}=t_{2}}$ is assigned true if ${\displaystyle t_{1}}$ and ${\displaystyle t_{2}}$ evaluate to the same object of the domain of discourse (see the section on equality below).
3. Logical connectives. A formula in the form ${\displaystyle \neg \phi }$, ${\displaystyle \phi \rightarrow \psi }$, etc. is evaluated according to the truth table for the connective in question, as in propositional logic.
4. Экзистенциальные кванторы. Формула истинна согласно M и если существует оценка переменных, которая отличается только от оценки x и такая, что φ истинно согласно интерпретации M и присвоению переменной . Это формальное определение отражает идею, которая истинна тогда и только тогда, когда есть способ выбрать значение для x, такое, что φ ( x ) удовлетворяется.${\displaystyle \exists x\phi (x)}$${\displaystyle \mu }$${\displaystyle \mu '}$${\displaystyle \mu }$${\displaystyle \mu '}$${\displaystyle \exists x\phi (x)}$
5. Universal quantifiers. A formula ${\displaystyle \forall x\phi (x)}$ is true according to M and ${\displaystyle \mu }$ if φ(x) is true for every pair composed by the interpretation M and some variable assignment ${\displaystyle \mu '}$ that differs from ${\displaystyle \mu }$ only on the value of x. This captures the idea that ${\displaystyle \forall x\phi (x)}$ is true if every possible choice of a value for x causes φ(x) to be true.

Если формула и предложение не содержат свободных переменных, то первоначальное присвоение переменной не влияет на ее истинностное значение. Другими словами, предложение истинно согласно M и тогда и только тогда, когда оно истинно согласно M и любому другому присваиванию переменной .${\displaystyle \mu }$${\displaystyle \mu '}$

Существует второй распространенный подход к определению значений истинности, который не полагается на функции присваивания переменных. Вместо этого, учитывая интерпретацию M , сначала к подписи добавляют набор постоянных символов, по одному для каждого элемента области дискурса в M ; говорят, что для каждого d в области постоянный символ c _d фиксирован. Интерпретация расширяется так, что каждый новый постоянный символ присваивается соответствующему элементу домена. Теперь истина для количественных формул определяется синтаксически следующим образом:

1. Existential quantifiers (alternate). A formula ${\displaystyle \exists x\phi (x)}$ is true according to M if there is some d in the domain of discourse such that ${\displaystyle \phi (c_{d})}$ holds. Here ${\displaystyle \phi (c_{d})}$ is the result of substituting c_d for every free occurrence of x in φ.
2. Universal quantifiers (alternate). A formula ${\displaystyle \forall x\phi (x)}$ is true according to M if, for every d in the domain of discourse, ${\displaystyle \phi (c_{d})}$ is true according to M.

This alternate approach gives exactly the same truth values to all sentences as the approach via variable assignments.

Validity, satisfiability, and logical consequence

If a sentence φ evaluates to True under a given interpretation M, one says that M satisfies φ; this is denoted^[18] ${\displaystyle M\vDash \varphi }$. A sentence is satisfiable if there is some interpretation under which it is true.

Satisfiability of formulas with free variables is more complicated, because an interpretation on its own does not determine the truth value of such a formula. The most common convention is that a formula with free variables is said to be satisfied by an interpretation if the formula remains true regardless which individuals from the domain of discourse are assigned to its free variables. This has the same effect as saying that a formula is satisfied if and only if its universal closure is satisfied.

A formula is logically valid (or simply valid) if it is true in every interpretation.^[19] These formulas play a role similar to tautologies in propositional logic.

A formula φ is a logical consequence of a formula ψ if every interpretation that makes ψ true also makes φ true. In this case one says that φ is logically implied by ψ.

Algebraizations

An alternate approach to the semantics of first-order logic proceeds via abstract algebra. This approach generalizes the Lindenbaum–Tarski algebras of propositional logic. There are three ways of eliminating quantified variables from first-order logic that do not involve replacing quantifiers with other variable binding term operators:

• Cylindric algebra, by Alfred Tarski and colleagues;
• Polyadic algebra, by Paul Halmos;
• Predicate functor logic, mainly due to Willard Quine.

These algebras are all lattices that properly extend the two-element Boolean algebra.

Tarski and Givant (1987) showed that the fragment of first-order logic that has no atomic sentence lying in the scope of more than three quantifiers has the same expressive power as relation algebra.^[20]:32–33​ This fragment is of great interest because it suffices for Peano arithmetic and most axiomatic set theory, including the canonical ZFC. They also prove that first-order logic with a primitive ordered pair is equivalent to a relation algebra with two ordered pair projection functions.^[21]:803​

First-order theories, models, and elementary classes

A first-order theory of a particular signature is a set of axioms, which are sentences consisting of symbols from that signature. The set of axioms is often finite or recursively enumerable, in which case the theory is called effective. Some authors require theories to also include all logical consequences of the axioms. The axioms are considered to hold within the theory and from them other sentences that hold within the theory can be derived.

A first-order structure that satisfies all sentences in a given theory is said to be a model of the theory. An elementary class is the set of all structures satisfying a particular theory. These classes are a main subject of study in model theory.

Many theories have an intended interpretation, a certain model that is kept in mind when studying the theory. For example, the intended interpretation of Peano arithmetic consists of the usual natural numbers with their usual operations. However, the Löwenheim–Skolem theorem shows that most first-order theories will also have other, nonstandard models.

A theory is consistent if it is not possible to prove a contradiction from the axioms of the theory. A theory is complete if, for every formula in its signature, either that formula or its negation is a logical consequence of the axioms of the theory. Gödel's incompleteness theorem shows that effective first-order theories that include a sufficient portion of the theory of the natural numbers can never be both consistent and complete.

For more information on this subject see List of first-order theories and Theory (mathematical logic)

Empty domains

Приведенное выше определение требует, чтобы область дискурса любой интерпретации была непустой. Есть настройки, такие как инклюзивная логика , где разрешены пустые домены. Более того, если класс алгебраических структур включает в себя пустую структуру (например, есть пустой объектный набор ), этот класс может быть только элементарным классом в логике первого порядка, если разрешены пустые домены или пустая структура удалена из класса. .

Однако есть несколько трудностей с пустыми доменами:

• Many common rules of inference are only valid when the domain of discourse is required to be nonempty. One example is the rule stating that ${\displaystyle \phi \lor \exists x\psi }$ implies ${\displaystyle \exists x(\phi \lor \psi )}$ when x is not a free variable in ${\displaystyle \phi }$. This rule, which is used to put formulas into prenex normal form, is sound in nonempty domains, but unsound if the empty domain is permitted.
• The definition of truth in an interpretation that uses a variable assignment function cannot work with empty domains, because there are no variable assignment functions whose range is empty. (Similarly, one cannot assign interpretations to constant symbols.) This truth definition requires that one must select a variable assignment function (μ above) before truth values for even atomic formulas can be defined. Then the truth value of a sentence is defined to be its truth value under any variable assignment, and it is proved that this truth value does not depend on which assignment is chosen. This technique does not work if there are no assignment functions at all; it must be changed to accommodate empty domains.

Thus, when the empty domain is permitted, it must often be treated as a special case. Most authors, however, simply exclude the empty domain by definition.

Deductive systems

A deductive system is used to demonstrate, on a purely syntactic basis, that one formula is a logical consequence of another formula. There are many such systems for first-order logic, including Hilbert-style deductive systems, natural deduction, the sequent calculus, the tableaux method, and resolution. These share the common property that a deduction is a finite syntactic object; the format of this object, and the way it is constructed, vary widely. These finite deductions themselves are often called derivations in proof theory. They are also often called proofs, but are completely formalized unlike natural-language mathematical proofs.

A deductive system is sound if any formula that can be derived in the system is logically valid. Conversely, a deductive system is complete if every logically valid formula is derivable. All of the systems discussed in this article are both sound and complete. They also share the property that it is possible to effectively verify that a purportedly valid deduction is actually a deduction; such deduction systems are called effective.

A key property of deductive systems is that they are purely syntactic, so that derivations can be verified without considering any interpretation. Thus a sound argument is correct in every possible interpretation of the language, regardless whether that interpretation is about mathematics, economics, or some other area.

In general, logical consequence in first-order logic is only semidecidable: if a sentence A logically implies a sentence B then this can be discovered (for example, by searching for a proof until one is found, using some effective, sound, complete proof system). However, if A does not logically imply B, this does not mean that A logically implies the negation of B. There is no effective procedure that, given formulas A and B, always correctly decides whether A logically implies B.

Rules of inference

A rule of inference states that, given a particular formula (or set of formulas) with a certain property as a hypothesis, another specific formula (or set of formulas) can be derived as a conclusion. The rule is sound (or truth-preserving) if it preserves validity in the sense that whenever any interpretation satisfies the hypothesis, that interpretation also satisfies the conclusion.

Например, одним из общих правил вывода является правило подстановки . Если t - терм, а φ - формула, возможно, содержащая переменную x , то φ [ t / x ] - результат замены всех свободных экземпляров x на t в φ. Правило подстановки гласит, что для любого φ и любого члена t можно вывести φ [ t / x ] из φ при условии, что никакая свободная переменная t не становится связанной во время процесса замены. (Если некоторая свободная переменная t становится связанной, то заменить t на x it is first necessary to change the bound variables of φ to differ from the free variables of t.)

Чтобы понять, почему необходимо ограничение на связанные переменные, рассмотрим логически действительную формулу φ, заданную как , в сигнатуре (0,1, +, ×, =) арифметики. Если t - это термин «x + 1», формула φ [ t / y ] будет , что будет неверно во многих интерпретациях. Проблема в том, что свободная переменная x из t стала связанной во время подстановки. Намеченная замена может быть получена путем переименования связанной переменной x функции φ в другое имя, например z , так что формула после подстановки будет иметь вид , что снова является логически верным.${\displaystyle \exists x(x=y)}$${\displaystyle \exists x(x=x+1)}$${\displaystyle \exists z(z=x+1)}$

The substitution rule demonstrates several common aspects of rules of inference. It is entirely syntactical; one can tell whether it was correctly applied without appeal to any interpretation. It has (syntactically defined) limitations on when it can be applied, which must be respected to preserve the correctness of derivations. Moreover, as is often the case, these limitations are necessary because of interactions between free and bound variables that occur during syntactic manipulations of the formulas involved in the inference rule.

Hilbert-style systems and natural deduction

Вывод в дедуктивной системе гильбертовского стиля - это список формул, каждая из которых является логической аксиомой , гипотезой, которая была принята для вывода под рукой, или вытекает из предыдущих формул через правило вывода. Логические аксиомы состоят из нескольких схем аксиом логически обоснованных формул; они включают в себя значительную часть логики высказываний. Правила вывода позволяют манипулировать кванторами. Типичные системы гильбертовского стиля имеют небольшое количество правил вывода, а также несколько бесконечных схем логических аксиом. Обычно в качестве правил вывода используются только modus ponens и универсальное обобщение .

Natural deduction systems resemble Hilbert-style systems in that a deduction is a finite list of formulas. However, natural deduction systems have no logical axioms; they compensate by adding additional rules of inference that can be used to manipulate the logical connectives in formulas in the proof.

Sequent calculus

The sequent calculus was developed to study the properties of natural deduction systems.^[22] Instead of working with one formula at a time, it uses sequents, which are expressions of the form

${\displaystyle A_{1},\ldots ,A_{n}\vdash B_{1},\ldots ,B_{k},}$

where A₁, ..., A_n, B₁, ..., B_k are formulas and the turnstile symbol ${\displaystyle \vdash }$ is used as punctuation to separate the two halves. Intuitively, a sequent expresses the idea that ${\displaystyle (A_{1}\land \cdots \land A_{n})}$ implies ${\displaystyle (B_{1}\lor \cdots \lor B_{k})}$.

Tableaux method

В отличие от только что описанных методов, производные в методе таблиц не являются списками формул. Вместо этого вывод - это дерево формул. Чтобы показать, что формула A доказуема, метод таблиц пытается продемонстрировать, что отрицание A неудовлетворительно. Дерево происхождения имеет в своем корне; дерево разветвляется таким образом, чтобы отражать структуру формулы. Например, чтобы показать, что это неудовлетворительно, необходимо показать, что и C, и D неудовлетворительны; это соответствует точке ветвления в дереве с родителем и потомками C и D.${\displaystyle \lnot A}$${\displaystyle C\lor D}$${\displaystyle C\lor D}$

разрешение

The resolution rule is a single rule of inference that, together with unification, is sound and complete for first-order logic. As with the tableaux method, a formula is proved by showing that the negation of the formula is unsatisfiable. Resolution is commonly used in automated theorem proving.

The resolution method works only with formulas that are disjunctions of atomic formulas; arbitrary formulas must first be converted to this form through Skolemization. The resolution rule states that from the hypotheses ${\displaystyle A_{1}\lor \cdots \lor A_{k}\lor C}$ and ${\displaystyle B_{1}\lor \cdots \lor B_{l}\lor \lnot C}$, the conclusion ${\displaystyle A_{1}\lor \cdots \lor A_{k}\lor B_{1}\lor \cdots \lor B_{l}}$ can be obtained.

Provable identities

Many identities can be proved, which establish equivalences between particular formulas. These identities allow for rearranging formulas by moving quantifiers across other connectives, and are useful for putting formulas in prenex normal form. Some provable identities include:

${\displaystyle \lnot \forall x\,P(x)\Leftrightarrow \exists x\,\lnot P(x)}$

${\displaystyle \lnot \exists x\,P(x)\Leftrightarrow \forall x\,\lnot P(x)}$

${\displaystyle \forall x\,\forall y\,P(x,y)\Leftrightarrow \forall y\,\forall x\,P(x,y)}$

${\displaystyle \exists x\,\exists y\,P(x,y)\Leftrightarrow \exists y\,\exists x\,P(x,y)}$

${\displaystyle \forall x\,P(x)\land \forall x\,Q(x)\Leftrightarrow \forall x\,(P(x)\land Q(x))}$

${\displaystyle \exists x\,P(x)\lor \exists x\,Q(x)\Leftrightarrow \exists x\,(P(x)\lor Q(x))}$

${\displaystyle P\land \exists x\,Q(x)\Leftrightarrow \exists x\,(P\land Q(x))}$ (where ${\displaystyle x}$ must not occur free in ${\displaystyle P}$)

${\displaystyle P\lor \forall x\,Q(x)\Leftrightarrow \forall x\,(P\lor Q(x))}$ (where ${\displaystyle x}$ must not occur free in ${\displaystyle P}$)

Equality and its axioms

There are several different conventions for using equality (or identity) in first-order logic. The most common convention, known as first-order logic with equality, includes the equality symbol as a primitive logical symbol which is always interpreted as the real equality relation between members of the domain of discourse, such that the "two" given members are the same member. This approach also adds certain axioms about equality to the deductive system employed. These equality axioms are:^{[23]:198–200}​

1. Reflexivity. For each variable x, x = x.
2. Substitution for functions. For all variables x and y, and any function symbol f,

   x = y → f(...,x,...) = f(...,y,...).

3. Substitution for formulas. For any variables x and y and any formula φ(x), if φ' is obtained by replacing any number of free occurrences of x in φ with y, such that these remain free occurrences of y, then

   x = y → (φ → φ').

These are axiom schemas, each of which specifies an infinite set of axioms. The third schema is known as Leibniz's law, "the principle of substitutivity", "the indiscernibility of identicals", or "the replacement property". The second schema, involving the function symbol f, is (equivalent to) a special case of the third schema, using the formula

x = y → (f(...,x,...) = z → f(...,y,...) = z).

Many other properties of equality are consequences of the axioms above, for example:

1. Симметрия. Если x = y, то y = x . ^[24]
2. Транзитивность. Если x = y и y = z, то x = z . ^[25]

Логика первого порядка без равенства

An alternate approach considers the equality relation to be a non-logical symbol. This convention is known as first-order logic without equality. If an equality relation is included in the signature, the axioms of equality must now be added to the theories under consideration, if desired, instead of being considered rules of logic. The main difference between this method and first-order logic with equality is that an interpretation may now interpret two distinct individuals as "equal" (although, by Leibniz's law, these will satisfy exactly the same formulas under any interpretation). That is, the equality relation may now be interpreted by an arbitrary equivalence relation on the domain of discourse that is congruent в отношении функций и отношений интерпретации.

Когда соблюдается это второе соглашение, термин " нормальная модель" используется для обозначения интерпретации, в которой никакие отдельные индивиды a и b не удовлетворяют a = b . В логике первого порядка с равенством рассматриваются только нормальные модели, поэтому для модели нет другого термина, кроме нормальной модели. Когда изучается логика первого порядка без равенства, необходимо изменить формулировки результатов, такие как теорема Левенгейма – Сколема, так, чтобы рассматривались только нормальные модели.

First-order logic without equality is often employed in the context of second-order arithmetic and other higher-order theories of arithmetic, where the equality relation between sets of natural numbers is usually omitted.

Defining equality within a theory

Если в теории есть бинарная формула A ( x , y ), удовлетворяющая рефлексивности и закону Лейбница, то говорят, что теория имеет равенство или является теорией с равенством. Теория может иметь не все примеры вышеупомянутых схем как аксиомы, а скорее как выводимые теоремы. Например, в теориях без функциональных символов и с конечным числом отношений можно определить равенство в терминах отношений, определяя два члена s и t равными, если какое-либо отношение не изменяется, заменяя s на t в любой аргумент.

Некоторые теории допускают другие специальные определения равенства:

• В теории частичных порядков с одним символом отношения ≤ можно определить s = t как сокращение для s ≤ t ∧ t ≤ s .
• In set theory with one relation ∈, one may define s = t to be an abbreviation for ∀x (s ∈ x ↔ t ∈ x) ∧ ∀x (x ∈ s ↔ x ∈ t). This definition of equality then automatically satisfies the axioms for equality. In this case, one should replace the usual axiom of extensionality, which can be stated as ${\displaystyle \forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]}$, with an alternative formulation ${\displaystyle \forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)]}$, which says that if sets x and y have the same elements, then they also belong to the same sets.

Metalogical properties

Одна из причин использования логики первого порядка, а не логики более высокого порядка , заключается в том, что логика первого порядка обладает множеством металогических свойств, которых нет у более сильных логик. Эти результаты касаются общих свойств самой логики первого порядка, а не свойств отдельных теорий. Они предоставляют фундаментальные инструменты для построения моделей теорий первого порядка.

Полнота и неразрешимость

Gödel's completeness theorem, proved by Kurt Gödel in 1929, establishes that there are sound, complete, effective deductive systems for first-order logic, and thus the first-order logical consequence relation is captured by finite provability. Naively, the statement that a formula φ logically implies a formula ψ depends on every model of φ; these models will in general be of arbitrarily large cardinality, and so logical consequence cannot be effectively verified by checking every model. However, it is possible to enumerate all finite derivations and search for a derivation of ψ from φ. If ψ is logically implied by φ, such a derivation will eventually be found. Thus first-order logical consequence is semidecidable: можно произвести эффективное перечисление всех пар предложений (φ, ψ), таких, что ψ является логическим следствием φ.

В отличие от логики высказываний, логика первого порядка неразрешима (хотя и полуразрешима) при условии, что в языке есть хотя бы один предикат арности не менее 2 (кроме равенства). Это означает, что не существует процедуры принятия решения, которая определяет, являются ли произвольные формулы логически действительными. Этот результат был независимо установлен Алонзо Черчем и Аланом Тьюрингом в 1936 и 1937 годах соответственно, дав отрицательный ответ на проблему Entscheidungs, поставленную Дэвидом Гильбертом и Вильгельмом Аккерманом. in 1928. Their proofs demonstrate a connection between the unsolvability of the decision problem for first-order logic and the unsolvability of the halting problem.

Существуют системы более слабые, чем полная логика первого порядка, для которых разрешимо отношение логических следствий. К ним относятся логика высказываний и монадическая логика предикатов , которая является логикой первого порядка, ограниченной унарными предикатными символами и без функциональных символов. Другие логики без функциональных символов, которые могут быть разрешены, - это охраняемый фрагмент логики первого порядка, а также логика с двумя переменными . Класс Бернейса – Шенфинкеля формул первого порядка также разрешим. Разрешаемые подмножества логики первого порядка также изучаются в рамках логики описания .

Теорема Левенгейма – Сколема.

The Löwenheim–Skolem theorem shows that if a first-order theory of cardinality λ has an infinite model, then it has models of every infinite cardinality greater than or equal to λ. One of the earliest results in model theory, it implies that it is not possible to characterize countability or uncountability in a first-order language with a countable signature. That is, there is no first-order formula φ(x) such that an arbitrary structure M satisfies φ if and only if the domain of discourse of M is countable (or, in the second case, uncountable).

Теорема Левенгейма – Сколема означает, что бесконечные структуры нельзя категорично аксиоматизировать в логике первого порядка. Например, не существует теории первого порядка, единственной моделью которой является действительная линия: любая теория первого порядка с бесконечной моделью также имеет модель мощности, превышающей континуум. Поскольку действительная прямая бесконечна, любая теория, которой удовлетворяет действительная прямая, также удовлетворяется некоторыми нестандартными моделями . Когда теорема Левенхайма – Сколема применяется к теориям множеств первого порядка, неинтуитивные следствия известны как парадокс Сколема .

Теорема компактности

Теорема компактности утверждает, что набор предложений первого порядка имеет модель тогда и только тогда, когда каждое его конечное подмножество имеет модель. ^[26] Это означает, что если формула является логическим следствием бесконечного набора аксиом первого порядка, то она является логическим следствием некоторого конечного числа этих аксиом. Эта теорема была впервые доказана Куртом Гёделем как следствие теоремы о полноте, но со временем было получено множество дополнительных доказательств. Это центральный инструмент в теории моделей, обеспечивающий фундаментальный метод построения моделей.

The compactness theorem has a limiting effect on which collections of first-order structures are elementary classes. For example, the compactness theorem implies that any theory that has arbitrarily large finite models has an infinite model. Thus the class of all finite graphs is not an elementary class (the same holds for many other algebraic structures).

There are also more subtle limitations of first-order logic that are implied by the compactness theorem. For example, in computer science, many situations can be modeled as a directed graph of states (nodes) and connections (directed edges). Validating such a system may require showing that no "bad" state can be reached from any "good" state. Thus one seeks to determine if the good and bad states are in different connected components of the graph. However, the compactness theorem can be used to show that connected graphs are not an elementary class in first-order logic, and there is no formula φ(x,y) of first-order logic, in the logic of graphs, that expresses the idea that there is a path from x to y. Connectedness can be expressed in second-order logic, however, but not with only existential set quantifiers, as ${\displaystyle \Sigma _{1}^{1}}$ also enjoys compactness.

Lindström's theorem

Per Lindström showed that the metalogical properties just discussed actually characterize first-order logic in the sense that no stronger logic can also have those properties (Ebbinghaus and Flum 1994, Chapter XIII). Lindström defined a class of abstract logical systems, and a rigorous definition of the relative strength of a member of this class. He established two theorems for systems of this type:

• Логическая система, удовлетворяющая определению Линдстрема, которая содержит логику первого порядка и удовлетворяет как теореме Левенгейма – Сколема, так и теореме компактности, должна быть эквивалентна логике первого порядка.
• Логическая система, удовлетворяющая определению Линдстрема, которая имеет полуразрешимое отношение логического следствия и удовлетворяет теореме Лёвенгейма – Сколема, должна быть эквивалентна логике первого порядка.

Ограничения

Хотя логика первого порядка достаточна для формализации большей части математики и обычно используется в информатике и других областях, она имеет определенные ограничения. К ним относятся ограничения его выразительности и ограничения фрагментов естественных языков, которые он может описывать.

For instance, first-order logic is undecidable, meaning a sound, complete and terminating decision algorithm for provability is impossible. This has led to the study of interesting decidable fragments, such as C₂: first-order logic with two variables and the counting quantifiers ${\displaystyle \exists ^{\geq n}}$ and ${\displaystyle \exists ^{\leq n}}$.^[27]

Expressiveness

The Löwenheim–Skolem theorem shows that if a first-order theory has any infinite model, then it has infinite models of every cardinality. In particular, no first-order theory with an infinite model can be categorical. Thus there is no first-order theory whose only model has the set of natural numbers as its domain, or whose only model has the set of real numbers as its domain. Many extensions of first-order logic, including infinitary logics and higher-order logics, are more expressive in the sense that they do permit categorical axiomatizations of the natural numbers or real numbers. This expressiveness comes at a metalogical cost, however: by Lindström's theorem, the compactness theorem and the downward Löwenheim–Skolem theorem cannot hold in any logic stronger than first-order.

Formalizing natural languages

First-order logic is able to formalize many simple quantifier constructions in natural language, such as "every person who lives in Perth lives in Australia". But there are many more complicated features of natural language that cannot be expressed in (single-sorted) first-order logic. "Any logical system which is appropriate as an instrument for the analysis of natural language needs a much richer structure than first-order predicate logic".^[28]

Restrictions, extensions, and variations

Есть много вариантов логики первого порядка. Некоторые из них несущественны в том смысле, что они просто изменяют нотацию, не затрагивая семантику. Другие изменяют выразительную силу более значительно, расширяя семантику за счет дополнительных квантификаторов или других новых логических символов. Например, бесконечная логика допускает формулы бесконечного размера, а модальная логика добавляет символы возможности и необходимости.

Запрещенные языки

Логику первого порядка можно изучать на языках с меньшим количеством логических символов, чем описано выше.

• Потому что может быть выражено как , а может быть выражено как любой из двух квантификаторов и может быть опущено.${\displaystyle \exists x\phi (x)}$${\displaystyle \neg \forall x\neg \phi (x)}$${\displaystyle \forall x\phi (x)}$${\displaystyle \neg \exists x\neg \phi (x)}$${\displaystyle \exists }$${\displaystyle \forall }$
• Since ${\displaystyle \phi \lor \psi }$ can be expressed as ${\displaystyle \lnot (\lnot \phi \land \lnot \psi )}$ and ${\displaystyle \phi \land \psi }$ can be expressed as ${\displaystyle \lnot (\lnot \phi \lor \lnot \psi )}$, either ${\displaystyle \vee }$ or ${\displaystyle \wedge }$ can be dropped. In other words, it is sufficient to have ${\displaystyle \neg }$ and ${\displaystyle \vee }$, or ${\displaystyle \neg }$ and ${\displaystyle \wedge }$, as the only logical connectives.
• Similarly, it is sufficient to have only ${\displaystyle \neg }$ and ${\displaystyle \rightarrow }$ as logical connectives, or to have only the Sheffer stroke (NAND) or the Peirce arrow (NOR) operator.
• It is possible to entirely avoid function symbols and constant symbols, rewriting them via predicate symbols in an appropriate way. For example, instead of using a constant symbol ${\displaystyle \;0}$ one may use a predicate ${\displaystyle \;0(x)}$ (interpreted as ${\displaystyle \;x=0}$ ), and replace every predicate such as ${\displaystyle \;P(0,y)}$ with ${\displaystyle \forall x\;(0(x)\rightarrow P(x,y))}$. A function such as ${\displaystyle f(x_{1},x_{2},...,x_{n})}$ will similarly be replaced by a predicate ${\displaystyle F(x_{1},x_{2},...,x_{n},y)}$ interpreted as ${\displaystyle y=f(x_{1},x_{2},...,x_{n})}$. This change requires adding additional axioms to the theory at hand, so that interpretations of the predicate symbols used have the correct semantics.^[29]

Подобные ограничения полезны как метод уменьшения количества правил вывода или схем аксиом в дедуктивных системах, что приводит к более коротким доказательствам металогических результатов. Цена ограничений состоит в том, что становится труднее выражать утверждения на естественном языке в имеющейся формальной системе, потому что логические связки, используемые в операторах естественного языка, должны быть заменены их (более длинными) определениями в терминах ограниченного набора терминов. логические связки. Точно так же производные в ограниченных системах могут быть длиннее, чем производные в системах, которые включают дополнительные связки. Таким образом, существует компромисс между простотой работы в формальной системе и легкостью доказательства результатов, касающихся формальной системы.

It is also possible to restrict the arities of function symbols and predicate symbols, in sufficiently expressive theories. One can in principle dispense entirely with functions of arity greater than 2 and predicates of arity greater than 1 in theories that include a pairing function. This is a function of arity 2 that takes pairs of elements of the domain and returns an ordered pair containing them. It is also sufficient to have two predicate symbols of arity 2 that define projection functions from an ordered pair to its components. In either case it is necessary that the natural axioms for a pairing function and its projections are satisfied.

Many-sorted logic

Обычные интерпретации первого порядка имеют единую область дискурса, охватывающую все кванторы. Многосортированная логика первого порядка позволяет переменным иметь разные виды , которые имеют разные домены. Это также называется типизированной логикой первого порядка , а сортировки - типами (как в типе данных ), но это не то же самое, что теория типов первого порядка . Многосортированная логика первого порядка часто используется при изучении арифметики второго порядка . ^[30]

When there are only finitely many sorts in a theory, many-sorted first-order logic can be reduced to single-sorted first-order logic.^{[31]:296–299}​ One introduces into the single-sorted theory a unary predicate symbol for each sort in the many-sorted theory, and adds an axiom saying that these unary predicates partition the domain of discourse. For example, if there are two sorts, one adds predicate symbols ${\displaystyle P_{1}(x)}$ and ${\displaystyle P_{2}(x)}$ and the axiom

${\displaystyle \forall x(P_{1}(x)\lor P_{2}(x))\land \lnot \exists x(P_{1}(x)\land P_{2}(x))}$.

Then the elements satisfying ${\displaystyle P_{1}}$ are thought of as elements of the first sort, and elements satisfying ${\displaystyle P_{2}}$ as elements of the second sort. One can quantify over each sort by using the corresponding predicate symbol to limit the range of quantification. For example, to say there is an element of the first sort satisfying formula φ(x), one writes

${\displaystyle \exists x(P_{1}(x)\land \phi (x))}$.

Additional quantifiers

Additional quantifiers can be added to first-order logic.

• Иногда полезно сказать, что « P ( x ) выполняется ровно для одного x », что может быть выражено как ∃! х Р ( х ) . Это обозначение, называемое количественной оценкой уникальности , может использоваться для сокращения формулы, например ∃ x ( P ( x ) ∧∀ y ( P ( y ) → ( x = y ))) .
• First-order logic with extra quantifiers has new quantifiers Qx,..., with meanings such as "there are many x such that ...". Also see branching quantifiers and the plural quantifiers of George Boolos and others.
• Bounded quantifiers are often used in the study of set theory or arithmetic.

Infinitary logics

Infinitary logic allows infinitely long sentences. For example, one may allow a conjunction or disjunction of infinitely many formulas, or quantification over infinitely many variables. Infinitely long sentences arise in areas of mathematics including topology and model theory.

Infinitary logic generalizes first-order logic to allow formulas of infinite length. The most common way in which formulas can become infinite is through infinite conjunctions and disjunctions. However, it is also possible to admit generalized signatures in which function and relation symbols are allowed to have infinite arities, or in which quantifiers can bind infinitely many variables. Because an infinite formula cannot be represented by a finite string, it is necessary to choose some other representation of formulas; the usual representation in this context is a tree. Thus formulas are, essentially, identified with their parse trees, rather than with the strings being parsed.

Наиболее часто изучаемые инфинитарные логики обозначаются L _αβ , где α и β - либо кардинальные числа, либо символ ∞. В этих обозначениях обычная логика первого порядка - это L _ωω . В логике L _∞ω при построении формул разрешены произвольные конъюнкции или дизъюнкции, и существует неограниченный запас переменных. В более общем смысле, логика, которая допускает конъюнкции или дизъюнкции с менее чем κ составляющими, известна как L _κω . Например, L _{ω 1 ω} допускает счетные конъюнкции и дизъюнкции.

The set of free variables in a formula of L_κω can have any cardinality strictly less than κ, yet only finitely many of them can be in the scope of any quantifier when a formula appears as a subformula of another.^[32] In other infinitary logics, a subformula may be in the scope of infinitely many quantifiers. For example, in L_κ∞, a single universal or existential quantifier may bind arbitrarily many variables simultaneously. Similarly, the logic L_κλ permits simultaneous quantification over fewer than λ variables, as well as conjunctions and disjunctions of size less than κ.

Non-classical and modal logics

• Интуиционистская логика первого порядка использует интуиционистское, а не классическое исчисление высказываний; например, ¬¬φ не обязательно эквивалентно φ.
• Модальная логика первого порядка позволяет описывать другие возможные миры, а также этот условно истинный мир, в котором мы живем. В некоторых версиях набор возможных миров варьируется в зависимости от того, в каком из возможных миров обитает человек. В модальной логике есть дополнительные модальные операторы со значениями, которые можно неформально охарактеризовать как, например, «необходимо, чтобы φ» (верно во всех возможных мирах) и «возможно, что φ» (верно в некотором возможном мире). При стандартной логике первого порядка у нас есть один домен, и каждому предикату присваивается одно расширение. С модальной логикой первого порядка у нас есть функция предметной областикоторый присваивает каждому возможному миру его собственный домен, так что каждый предикат получает расширение только относительно этих возможных миров. Это позволяет нам моделировать случаи, когда, например, Алекс - философ, но мог бы быть математиком, а мог бы не существовать вовсе. В первом возможном мире P ( a ) истинно, во втором P ( a ) ложно, а в третьем возможном мире вообще нет a в области.
• Нечеткие логики первого порядка - это расширения первого порядка нечетких логик высказываний, а не классическое исчисление высказываний .

Логика фиксированной точки

Fixpoint logic extends first-order logic by adding the closure under the least fixed points of positive operators.^[33]

Higher-order logics

The characteristic feature of first-order logic is that individuals can be quantified, but not predicates. Thus

${\displaystyle \exists a({\text{Phil}}(a))}$

is a legal first-order formula, but

${\displaystyle \exists {\text{Phil}}({\text{Phil}}(a))}$

is not, in most formalizations of first-order logic. Second-order logic extends first-order logic by adding the latter type of quantification. Other higher-order logics allow quantification over even higher types than second-order logic permits. These higher types include relations between relations, functions from relations to relations between relations, and other higher-type objects. Thus the "first" in first-order logic describes the type of objects that can be quantified.

Unlike first-order logic, for which only one semantics is studied, there are several possible semantics for second-order logic. The most commonly employed semantics for second-order and higher-order logic is known as full semantics. The combination of additional quantifiers and the full semantics for these quantifiers makes higher-order logic stronger than first-order logic. In particular, the (semantic) logical consequence relation for second-order and higher-order logic is not semidecidable; there is no effective deduction system for second-order logic that is sound and complete under full semantics.

Second-order logic with full semantics is more expressive than first-order logic. For example, it is possible to create axiom systems in second-order logic that uniquely characterize the natural numbers and the real line. The cost of this expressiveness is that second-order and higher-order logics have fewer attractive metalogical properties than first-order logic. For example, the Löwenheim–Skolem theorem and compactness theorem of first-order logic become false when generalized to higher-order logics with full semantics.

Automated theorem proving and formal methods

Автоматическое доказательство теорем относится к разработке компьютерных программ, которые ищут и находят выводы (формальные доказательства) математических теорем. ^[34] Поиск производных - сложная задача, потому что пространство поиска может быть очень большим; исчерпывающий поиск всех возможных выводов теоретически возможен, но вычислительно невозможен для многих систем, представляющих интерес в математике. Таким образом, сложные эвристические функции разрабатываются, чтобы попытаться найти вывод за меньшее время, чем слепой поиск. ^{[ необходима цитата ]}

The related area of automated proof verification uses computer programs to check that human-created proofs are correct. Unlike complicated automated theorem provers, verification systems may be small enough that their correctness can be checked both by hand and through automated software verification. This validation of the proof verifier is needed to give confidence that any derivation labeled as "correct" is actually correct.

Some proof verifiers, such as Metamath, insist on having a complete derivation as input. Others, such as Mizar and Isabelle, take a well-formatted proof sketch (which may still be very long and detailed) and fill in the missing pieces by doing simple proof searches or applying known decision procedures: the resulting derivation is then verified by a small, core "kernel". Many such systems are primarily intended for interactive use by human mathematicians: these are known as proof assistants. They may also use formal logics that are stronger than first-order logic, such as type theory. Because a full derivation of any nontrivial result in a first-order deductive system will be extremely long for a human to write,^[35] results are often formalized as a series of lemmas, for which derivations can be constructed separately.

Automated theorem provers are also used to implement formal verification in computer science. In this setting, theorem provers are used to verify the correctness of programs and of hardware such as processors with respect to a formal specification. Because such analysis is time-consuming and thus expensive, it is usually reserved for projects in which a malfunction would have grave human or financial consequences.

Известно, что для задачи проверки модели эффективные алгоритмы определяют , удовлетворяет ли входная конечная структура формуле первого порядка в дополнение к ограничениям вычислительной сложности : см. Проверка модели # Логика первого порядка .

Смотрите также

Примечания

References

• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York, NY: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Andrews, Peter B. (2002); An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed., Berlin: Kluwer Academic Publishers. Available from Springer.
• Avigad, Jeremy; Donnelly, Kevin; Gray, David; and Raff, Paul (2007); "A formally verified proof of the prime number theorem", ACM Transactions on Computational Logic, vol. 9 no. 1 doi:10.1145/1297658.1297660
• Barwise, Jon (1977). "An Introduction to First-Order Logic". In Barwise, Jon (ed.). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Amsterdam, NL: North-Holland (published 1982). ISBN 978-0-444-86388-1.
• Monk, J. Donald (1976). Mathematical Logic. New York, NY: Springer New York. ISBN 978-1-4684-9454-9.
• Barwise, Jon; and Etchemendy, John (2000); Language Proof and Logic, Stanford, CA: CSLI Publications (Distributed by the University of Chicago Press)
• Bocheński, Józef Maria (2007); A Précis of Mathematical Logic, Dordrecht, NL: D. Reidel, translated from the French and German editions by Otto Bird
• Ferreirós, José (2001); The Road to Modern Logic — An Interpretation, Bulletin of Symbolic Logic, Volume 7, Issue 4, 2001, pp. 441–484, doi:10.2307/2687794, JSTOR 2687794
• Gamut, LTF (1991), Logic, Language, and Meaning, Volume 2: Intensional Logic and Logical Grammar , Чикаго, Иллинойс: University of Chicago Press, ISBN 0-226-28088-8
• Гильберт, Дэвид ; и Аккерман, Вильгельм (1950); Принципы математической логики , Chelsea (английский перевод Grundzüge der Theoretischen Logik , 1928, первое издание на немецком языке)
• Ходжес, Уилфрид (2001); «Классическая логика I: логика первого порядка», в Гобле, Лу (ред.); Руководство Блэквелла по философской логике , Блэквелл
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; and Thomas, Wolfgang (1994); Mathematical Logic, Undergraduate Texts in Mathematics, Berlin, DE/New York, NY: Springer-Verlag, Second Edition, ISBN 978-0-387-94258-2
• Tarski, Alfred and Givant, Steven (1987); A Formalization of Set Theory without Variables. Vol.41 of American Mathematical Society colloquium publications, Providence RI: American Mathematical Society, ISBN 978-0821810415

External links

• "Predicate calculus", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Стэнфордская энциклопедия философии : Шапиро, Стюарт; « Классическая логика ». Охватывает синтаксис, теорию моделей и метатеорию для логики первого порядка в стиле естественной дедукции.
• Магнус, Полицейский; forall x: введение в формальную логику . Охватывает формальную семантику и теорию доказательств для логики первого порядка.
• Metamath : текущий онлайн-проект по реконструкции математики как огромной теории первого порядка с использованием логики первого порядка и аксиоматической теории множеств ZFC . Principia Mathematica модернизирована.
• Подниекс, Карл; Введение в математическую логику
• Cambridge Mathematical Tripos notes (typeset by John Fremlin). These notes cover part of a past Cambridge Mathematical Tripos course taught to undergraduate students (usually) within their third year. The course is entitled "Logic, Computation and Set Theory" and covers Ordinals and cardinals, Posets and Zorn's Lemma, Propositional logic, Predicate logic, Set theory and Consistency issues related to ZFC and other set theories.
• Tree Proof Generator can validate or invalidate formulas of first-order logic through the semantic tableaux method.