🤔Proof Theory Unit 3 – First-Order Logic: Syntax and Semantics

Key Concepts and Definitions

• First-order logic (FOL) is a formal system used to represent and reason about logical statements
• FOL consists of a set of symbols, rules for constructing well-formed formulas (wffs), and a semantics for interpreting the meaning of these formulas
• Syntax refers to the rules governing the structure and composition of formulas in FOL
  • Includes the alphabet of symbols and the grammar for constructing well-formed formulas
• Semantics assigns meaning to the formulas in FOL by defining how they are interpreted in a given model or structure
• Variables in FOL represent arbitrary objects within the domain of discourse
• Quantifiers, such as the universal quantifier $\forall$ and the existential quantifier $\exists$, are used to express properties of variables and their relationships
• Connectives, including conjunction $\land$, disjunction $\lor$, implication $\rightarrow$, and negation $\lnot$, are used to combine and modify formulas

Syntax of First-Order Logic

• The alphabet of FOL consists of variables, constants, function symbols, predicate symbols, connectives, and quantifiers
• Terms are the basic building blocks of FOL and can be variables, constants, or function symbols applied to other terms
• Atomic formulas are formed by applying predicate symbols to terms
• Complex formulas are constructed using connectives and quantifiers to combine atomic formulas or other complex formulas
• The formation rules specify how to construct well-formed formulas using the alphabet and grammar of FOL
  • For example, if $P$ is a predicate symbol and $x$ is a variable, then $P(x)$ is a well-formed atomic formula
• The scope of a quantifier is the formula it directly applies to, and this determines the range of variables bound by the quantifier
• Free variables are those not bound by any quantifier in a formula, while bound variables are those within the scope of a quantifier

Semantics of First-Order Logic

• The semantics of FOL define how formulas are interpreted and evaluated in a given model or structure
• A model consists of a non-empty domain of discourse and an interpretation function that assigns meaning to the symbols in the language
  • The domain of discourse is the set of objects that the variables and constants in FOL can refer to
• The interpretation function maps constants to elements of the domain, function symbols to functions on the domain, and predicate symbols to relations on the domain
• A valuation is a function that assigns values from the domain to the free variables in a formula
• The truth value of a formula is determined by evaluating it in a given model under a specific valuation
  • For example, the formula $\forall x (P(x) \rightarrow Q(x))$ is true in a model if for every element $a$ in the domain, if $P(a)$ is true, then $Q(a)$ is also true
• Logical consequence and satisfiability are important concepts in the semantics of FOL
  • A formula is a logical consequence of a set of formulas if it is true in every model where all the formulas in the set are true
  • A formula is satisfiable if there exists a model and a valuation under which it is true

Formulas and Well-Formed Formulas

• Formulas in FOL are constructed using the alphabet and formation rules of the language
• Atomic formulas are the simplest type of formula and consist of a predicate symbol applied to terms
  • For example, $P(x, f(y))$ is an atomic formula, where $P$ is a predicate symbol, $x$ and $y$ are variables, and $f$ is a function symbol
• Complex formulas are built from atomic formulas and other complex formulas using connectives and quantifiers
• The formation rules ensure that formulas are well-formed and meaningful in FOL
  • These rules specify the allowed combinations of symbols and the order in which they can appear
• Well-formed formulas (wffs) are those that adhere to the formation rules and can be assigned a truth value in a given model
• Formulas that are not well-formed are considered syntactically invalid and cannot be interpreted in FOL
  • For example, $\forall x P(x) \land Q(x)$ is not a well-formed formula because the scope of the quantifier is ambiguous

Quantifiers and Variables

• Quantifiers in FOL are used to express properties of variables and their relationships
• The universal quantifier $\forall$ is used to state that a formula holds for all values of a variable in the domain
  • For example, $\forall x P(x)$ means that the predicate $P$ is true for every element $x$ in the domain
• The existential quantifier $\exists$ is used to state that a formula holds for at least one value of a variable in the domain
  • For example, $\exists x P(x)$ means that there exists an element $x$ in the domain for which the predicate $P$ is true
• Variables can be bound by quantifiers, meaning that their values are determined by the quantifier
  • In the formula $\forall x P(x) \land Q(y)$, $x$ is a bound variable, while $y$ is a free variable
• The scope of a quantifier is the formula it directly applies to, and this determines the range of variables bound by the quantifier
  • In the formula $\forall x (P(x) \rightarrow \exists y Q(x, y))$, the scope of $\forall x$ is $(P(x) \rightarrow \exists y Q(x, y))$, and the scope of $\exists y$ is $Q(x, y)$
• Nested quantifiers can be used to express more complex properties and relationships between variables
  • For example, $\forall x \exists y P(x, y)$ means that for every element $x$ in the domain, there exists an element $y$ such that the predicate $P$ holds for the pair $(x, y)$

Truth Tables and Interpretations

• Truth tables are used to evaluate the truth values of formulas in propositional logic, which is a simpler form of logic than FOL
• In FOL, the truth value of a formula depends on the interpretation of the symbols in the language and the values assigned to the variables
• An interpretation consists of a domain of discourse and a function that assigns meaning to the constants, function symbols, and predicate symbols in the language
  • For example, in an interpretation where the domain is the set of natural numbers, the constant symbol $0$ could be assigned the value 0, the function symbol $+$ could be assigned the addition function, and the predicate symbol $<$ could be assigned the less-than relation
• A valuation is a function that assigns values from the domain to the free variables in a formula
• The truth value of a formula in FOL is determined by evaluating it in a given interpretation under a specific valuation
  • For example, the formula $\forall x (x < x + 1)$ is true in the interpretation of natural numbers described above, regardless of the valuation of $x$
• Logical consequence and satisfiability are important concepts in the semantics of FOL
  • A formula is a logical consequence of a set of formulas if it is true in every interpretation where all the formulas in the set are true
  • A formula is satisfiable if there exists an interpretation and a valuation under which it is true

Applications and Examples

• FOL is used in various fields, including mathematics, computer science, and artificial intelligence, to represent and reason about complex statements and theories
• In mathematics, FOL is used to formalize definitions, axioms, and theorems
  • For example, the Peano axioms for natural numbers can be expressed in FOL using the constant symbol $0$, the function symbol $S$ (for successor), and the axioms such as $\forall x (S(x) \neq 0)$ and $\forall x \forall y (S(x) = S(y) \rightarrow x = y)$
• In computer science, FOL is used in the design and analysis of algorithms, databases, and knowledge representation systems
  • FOL can be used to specify the preconditions and postconditions of an algorithm, express integrity constraints in a database, or represent facts and rules in a knowledge base
• FOL is also used in artificial intelligence for tasks such as automated theorem proving, planning, and natural language understanding
  • For example, a planning problem can be represented in FOL using predicates for the initial state, goal state, and actions, and a plan can be generated by finding a sequence of actions that satisfies the goal formula
• Real-world examples of FOL applications include:
  • Representing and reasoning about family relationships (e.g., $\forall x \forall y (Parent(x, y) \rightarrow Ancestor(x, y))$)
  • Modeling and querying databases (e.g., $\exists x (Employee(x) \land Salary(x) > 50000)$)
  • Formalizing and proving mathematical theorems (e.g., the fundamental theorem of arithmetic)

Common Pitfalls and Tips

• One common pitfall in FOL is confusing the universal and existential quantifiers or misplacing them in a formula
  • Remember that $\forall x P(x)$ means "for all $x$, $P(x)$ holds," while $\exists x P(x)$ means "there exists an $x$ such that $P(x)$ holds"
  • Pay attention to the scope of quantifiers and ensure that they bind the intended variables
• Another pitfall is forgetting to specify the domain of discourse or using an inappropriate domain for the problem at hand
  • Always clearly define the domain of discourse and ensure that it includes all the objects relevant to the problem
• When constructing formulas, be mindful of the precedence and associativity of the connectives and quantifiers
  • Use parentheses to clarify the intended order of operations and avoid ambiguity
• When working with complex formulas, break them down into smaller, more manageable parts and analyze each part separately
  • Use the formation rules and the definitions of connectives and quantifiers to guide your analysis
• Practice translating natural language statements into FOL formulas and vice versa to develop a better understanding of the language and its applications
  • Start with simple statements and gradually work up to more complex ones
• Take advantage of online resources, such as tutorials, examples, and problem sets, to reinforce your understanding of FOL and practice your skills
  • Participate in study groups or discussions with classmates to share insights and clarify difficult concepts