predicatelogic

Predicate logic, also called first-order logic, is a formal system that extends propositional logic by allowing variables to range over objects and by using predicates to express properties and relations. In predicate logic, formulas are built from variables, constants, function symbols, and predicate symbols of various arities, together with logical connectives and two quantifiers: universal and existential. For example, ∀x (Human(x) → Mortal(x)) states that all humans are mortal, and ∃x (Student(x) ∧ Enrolled(x, CS101)) asserts there is a student enrolled in CS101.

Semantics attach meaning to the formulas via structures: a nonempty domain of discourse, interpretations of the symbols, and truth-conditions rules for the quantifiers. A formula is true in a structure under an assignment of values to free variables. First-order logic is more expressive than propositional logic and can formalize mathematics, computer science concepts, and many areas of philosophy. But its validity is not decidable in general.

Key results include Gödel's completeness theorem, which links semantic truth to syntactic provability, and model-theoretic properties such as Löwenheim–Skolem and Compactness theorems. Some restricted fragments, such as monadic predicate logic (unary predicates only), are decidable, while full first-order logic is not.

Historically, predicate logic developed through the work of Frege, Peano, and the contributions of Russell and Whitehead, with later formalization by Hilbert and Ackermann. It remains the standard framework in mathematics, logic programming, automated reasoning, and theoretical computer science.