Formal Logic II Unit 2 ReviewFirst–Order Logic – Syntax and Semantics

Key Concepts and Definitions

• First-order logic (FOL) extends propositional logic by introducing quantifiers, variables, and predicates to represent and reason about complex statements and relationships
• Predicates are symbols that represent properties or relations between objects (e.g., $P(x)$ could represent "x is a prime number")
• Variables are symbols that stand for arbitrary objects within a domain (e.g., $x$, $y$, $z$)
• Quantifiers express the extent to which a predicate holds for the objects in a domain
  • Universal quantifier ($\forall$) asserts that a predicate holds for all objects in the domain
  • Existential quantifier ($\exists$) asserts that a predicate holds for at least one object in the domain
• Constants are symbols that represent specific objects in the domain (e.g., $a$, $b$, $c$)
• Functions are symbols that represent mappings from objects in the domain to other objects (e.g., $f(x)$ could represent "the father of x")
• Terms are expressions that refer to objects in the domain and can be variables, constants, or functions applied to terms

Syntax of First-Order Logic

• The syntax of FOL defines the rules for constructing well-formed formulas (WFFs) using the language's symbols and connectives
• The alphabet of FOL consists of variables, constants, predicates, functions, quantifiers, logical connectives, and punctuation symbols (e.g., parentheses, commas)
• Terms are recursively defined as variables, constants, or functions applied to terms
• Atomic formulas are predicates applied to terms (e.g., $P(x)$, $Q(a, f(x))$)
• Complex formulas are built from atomic formulas using logical connectives and quantifiers
  • Negation ($\neg$), conjunction ($\land$), disjunction ($\lor$), implication ($\to$), and equivalence ($\leftrightarrow$) are used to combine formulas
  • Quantifiers ($\forall$ and $\exists$) are used to bind variables and specify the scope of predicates
• The scope of a quantifier is the formula immediately following it, and the variable bound by the quantifier is called the quantified variable
• Free variables are variables not bound by any quantifier in a formula, while bound variables are variables within the scope of a quantifier

Semantics of First-Order Logic

• The semantics of FOL define the meaning and truth conditions of formulas in the language
• An interpretation (or model) for a FOL language consists of a non-empty domain of objects and assignments of meanings to the language's symbols
  • Constants are assigned specific objects in the domain
  • Predicates are assigned relations on the domain (i.e., subsets of the Cartesian product of the domain with itself)
  • Functions are assigned mappings from tuples of objects in the domain to objects in the domain
• A variable assignment is a function that maps each variable to an object in the domain
• The truth value of a formula is determined by the interpretation and the variable assignment
  • Atomic formulas are true if the objects assigned to the terms are in the relation assigned to the predicate
  • Complex formulas' truth values are determined by the truth values of their constituent formulas and the logical connectives used
• Quantified formulas are evaluated by considering the truth values of the formula under different variable assignments
  • $\forall x \, \phi(x)$ is true if $\phi(x)$ is true for every object in the domain
  • $\exists x \, \phi(x)$ is true if $\phi(x)$ is true for at least one object in the domain

Quantifiers and Variables

• Quantifiers are logical symbols that express the quantity of objects for which a predicate holds in a domain
• The universal quantifier ($\forall$) asserts that a predicate holds for all objects in the domain
  • Example: $\forall x \, (P(x) \to Q(x))$ means "for all x, if P(x) is true, then Q(x) is true"
• The existential quantifier ($\exists$) asserts that a predicate holds for at least one object in the domain
  • Example: $\exists x \, (P(x) \land Q(x))$ means "there exists an x such that both P(x) and Q(x) are true"
• Variables are symbols that stand for arbitrary objects within a domain and can be bound by quantifiers
  • Bound variables are variables within the scope of a quantifier
  • Free variables are variables not bound by any quantifier in a formula
• The scope of a quantifier is the formula immediately following it, and the variable bound by the quantifier is called the quantified variable
• Nested quantifiers can be used to express more complex statements
  • Example: $\forall x \, \exists y \, (P(x) \to Q(y))$ means "for all x, there exists a y such that if P(x) is true, then Q(y) is true"
• The order of quantifiers is important, as it affects the meaning of the formula

Formulas and Well-Formed Formulas

• Formulas in FOL are sequences of symbols that express statements or propositions
• Well-formed formulas (WFFs) are formulas that adhere to the syntax rules of FOL
  • Atomic formulas are the simplest WFFs and consist of predicates applied to terms
  • Complex formulas are built from atomic formulas using logical connectives and quantifiers
• The formation rules for WFFs ensure that formulas are meaningful and can be evaluated for truth or falsity
  • Terms must be properly constructed using variables, constants, and functions
  • Predicates must be applied to the correct number of terms
  • Logical connectives and quantifiers must be used according to their specified syntax
• Examples of WFFs:
  • $P(a)$
  • $\forall x \, (Q(x) \to R(x, b))$
  • $\exists y \, (S(y) \land \neg T(f(y)))$
• Examples of non-WFFs:
  • $P(x)(y)$ (mismatched parentheses)
  • $\forall x \, Q$ (missing formula after quantifier)
  • $R(a, b) \land$ (missing formula after connective)

Truth Tables and Interpretations

• Truth tables are a method for determining the truth values of formulas in FOL under different interpretations
• An interpretation (or model) for a FOL language consists of a non-empty domain of objects and assignments of meanings to the language's symbols
• To construct a truth table, list all possible combinations of truth values for the atomic formulas in the formula
  • For each combination, evaluate the truth value of the overall formula using the semantics of the logical connectives and quantifiers
• The number of rows in a truth table grows exponentially with the number of atomic formulas in the formula
• Interpretations provide meaning to the symbols in a FOL language
  • Constants are assigned specific objects in the domain
  • Predicates are assigned relations on the domain (i.e., subsets of the Cartesian product of the domain with itself)
  • Functions are assigned mappings from tuples of objects in the domain to objects in the domain
• A formula is true under an interpretation if it evaluates to true for all variable assignments in that interpretation
• A formula is false under an interpretation if it evaluates to false for at least one variable assignment in that interpretation

Logical Equivalence and Validity

• Two formulas are logically equivalent if they have the same truth value under every interpretation
  • Logically equivalent formulas can be substituted for each other in any context without changing the meaning
• Examples of logically equivalent formulas:
  • $\phi \to \psi$ and $\neg \phi \lor \psi$
  • $\forall x \, (P(x) \land Q(x))$ and $(\forall x \, P(x)) \land (\forall x \, Q(x))$
• A formula is valid (or logically valid) if it is true under every interpretation
  • Valid formulas are tautologies and represent logical truths
  • Example: $\forall x \, (P(x) \to P(x))$ (a formula is always implied by itself)
• A formula is satisfiable if there exists at least one interpretation under which it is true
  • Satisfiable formulas are consistent and can be made true by some assignment of meanings to the symbols
• A formula is unsatisfiable if it is false under every interpretation
  • Unsatisfiable formulas are contradictions and cannot be made true by any assignment of meanings to the symbols
  • Example: $\exists x \, (P(x) \land \neg P(x))$ (a formula cannot be both true and false for the same object)

Applications and Examples

• FOL is used in various fields, including mathematics, computer science, and philosophy, to represent and reason about complex statements and arguments
• In mathematics, FOL is used to formalize theories and prove theorems
  • Example: the Peano axioms for natural numbers can be expressed in FOL, and properties of natural numbers can be derived from these axioms
• In computer science, FOL is used in artificial intelligence, database theory, and software verification
  • Example: FOL can be used to represent knowledge in a knowledge base and to perform automated reasoning tasks, such as question answering and theorem proving
• In philosophy, FOL is used to analyze and evaluate arguments in areas such as metaphysics, epistemology, and ethics
  • Example: the ontological argument for the existence of God can be formalized in FOL, and its validity can be assessed using logical tools
• Other examples of FOL formulas and their interpretations:
  • $\forall x \, (Human(x) \to Mortal(x))$ (all humans are mortal)
  • $\exists x \, (Prime(x) \land Even(x))$ (there exists an even prime number)
  • $\forall x \, \forall y \, (Parent(x, y) \to Loves(x, y))$ (all parents love their children)