First-Order Logic
Introduction
First-order logic—also known as predicate 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 such as "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier and "x" is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations.
Syntax
The syntax of first-order logic is the set of rules that defines which strings of symbols formed from the alphabet of a first-order language are syntactically valid expressions in that language. The alphabet of a first-order language consists of a set of symbols for logical connectives, quantifiers, punctuation, variables, and predicates. The syntax rules for first-order logic are typically given as a set of inductive definitions or a formal grammar.
Logical Connectives
Logical connectives, also known as logical operators, are symbols used to combine smaller statements into larger ones. In first-order logic, the logical connectives are usually taken to be ¬ (not), ∧ (and), ∨ (or), → (implies), and ↔ (if and only if).
Quantifiers
Quantifiers are symbols used to indicate the quantity or scope of the variables in a statement. In first-order logic, there are two quantifiers: ∀ (for all) and ∃ (there exists).
Variables
Variables are symbols that can stand for any object in the domain of discourse. In first-order logic, variables are usually denoted by lowercase letters from the end of the alphabet, such as x, y, and z.
Predicates
Predicates are symbols that stand for properties or relations. In first-order logic, predicates are usually denoted by uppercase letters from the beginning of the alphabet, such as A, B, and C.
Semantics
The semantics of first-order logic concerns the interpretation of first-order languages and the truth or falsity of sentences in these languages. An interpretation of a first-order language assigns a domain of discourse to the language and interprets the quantifiers, variables, and predicates of the language in terms of this domain.
Truth Values
In first-order logic, every well-formed formula (or sentence) is assigned a truth value, either true or false, under an interpretation. The truth value of a sentence depends on the interpretation of its predicates and variables and the truth values of its subformulas.
Models
A model of a set of sentences in a first-order language is an interpretation under which all the sentences in the set are true. The concept of a model is central to the study of model theory, a branch of mathematical logic that deals with the relationship between a formal language and its interpretations.
Inference Rules and Proof Systems
First-order logic has a variety of inference rules and proof systems that can be used to derive conclusions from premises. These include natural deduction, sequent calculus, and the tableau method, among others. Each of these systems provides a formal way to manipulate sentences in first-order logic and to prove theorems.
Limitations and Extensions
While first-order logic is powerful and widely applicable, it has certain limitations. For example, it cannot express certain kinds of statements, such as those involving an infinite number of objects. There are also certain logical truths that cannot be proven in first-order logic. These limitations have led to the development of various extensions and alternatives to first-order logic, including second-order logic, higher-order logic, and modal logic.
Applications
First-order logic has many applications in various fields. In mathematics, it is the standard form of logic used in formal proofs. In computer science, it is used in the design of programming languages and databases. In artificial intelligence, it is used to represent knowledge and to perform reasoning tasks. In philosophy, it is used to formalize arguments and to analyze the structure of language and thought.