Predicate Logic
Introduction
Predicate logic, also known as first-order logic or quantificational logic, is a formal logical system that is widely used in mathematics, philosophy, linguistics, and computer science. It is a non-trivial extension of propositional logic, which only considers propositions as a whole, to the analysis of the internal structure of propositions.
Formal Structure
The formal structure of predicate logic is based on the concepts of predicates, variables, and quantifiers.
Predicates
A predicate is a symbol or string of symbols that can be true or false depending on the values of its variables. For example, the predicate P(x) could represent the statement "x is a prime number". The variable x can be replaced by any object, and the truth value of P(x) depends on whether that object is a prime number.
Variables
Variables in predicate logic are placeholders that can represent any object in the domain of discourse. The domain of discourse, also known as the universe of discourse, is the set of all things that are under discussion in a particular context.
Quantifiers
Quantifiers are symbols that specify how many objects in the domain of discourse satisfy a certain predicate. The two most common quantifiers are the universal quantifier (∀), which means "for all", and the existential quantifier (∃), which means "there exists".
Syntax and Semantics
The syntax of predicate logic specifies the rules for forming well-formed formulas, while the semantics provides the rules for interpreting these formulas.
Syntax
The syntax of predicate logic is based on the use of symbols for predicates, variables, quantifiers, and logical connectives. A well-formed formula in predicate logic is built up from atomic formulas by the application of logical connectives and quantifiers.
An atomic formula is a formula that contains no smaller parts that are themselves formulas. It consists of a predicate symbol followed by a certain number of terms, which can be variables or constants.
Semantics
The semantics of predicate logic provides a way to determine the truth value of a formula for a given interpretation. An interpretation specifies a domain of discourse and an assignment of values to the variables and predicates in the formula.
Inference Rules and Proof Theory
Predicate logic has a set of inference rules that allow one to derive new formulas from existing ones. These rules, together with the axioms of predicate logic, form the basis of its proof theory.
The proof theory of predicate logic is concerned with the formal manipulation of formulas and the derivation of theorems. A theorem in predicate logic is a formula that can be derived from the axioms using the inference rules.
Model Theory
Model theory is a branch of mathematical logic that deals with the relationship between a formal language (such as predicate logic) and its interpretations, or models. A model of a set of formulas in predicate logic is an interpretation in which all the formulas are true.
Limitations and Extensions
While predicate logic is a powerful tool, it has certain limitations. For example, it cannot express statements about "all properties" or "all sets", because these would require a higher level of quantification.
There are several extensions of predicate logic that aim to overcome these limitations, such as second-order logic, which allows quantification over sets of objects, and modal logic, which introduces the concepts of necessity and possibility.