First-order logic digs deeper into the meaning behind symbols and statements. It introduces interpretations, which give real-world significance to abstract symbols, and models, which are interpretations that make formulas true.

Truth assignments in first-order logic are more complex than in propositional logic. They involve mapping symbols to elements, functions, and relations in a specific domain, allowing for more nuanced and powerful logical reasoning.

Interpretations, Models, and Truth Assignments

Defining Interpretations, Models, and Truth Assignments

• An interpretation in first-order logic assigns meanings to the non-logical symbols in a formula, including constants, function symbols, and predicate symbols
• A model in first-order logic is an interpretation that makes a formula true
  • A formula is satisfiable if it has at least one model
• A truth assignment in first-order logic assigns truth values (true or false) to the atomic formulas in a formula based on an interpretation
• The domain of discourse is the set of objects over which the quantifiers in a first-order logic formula range
  • The domain is non-empty and specified by the interpretation

Mapping Symbols to Elements, Functions, and Relations

• An interpretation maps each constant symbol to an element in the domain
  • For example, the constant symbol a might be mapped to the number 3 in the domain of natural numbers
• An interpretation maps each n-ary function symbol to an n-ary function on the domain
  • For example, the binary function symbol f might be mapped to the addition function on the domain of natural numbers
• An interpretation maps each n-ary predicate symbol to an n-ary relation on the domain
  • For example, the unary predicate symbol P might be mapped to the set of even numbers in the domain of natural numbers

Truth Values in First-Order Logic

Assigning Truth Values to Atomic Formulas

• To determine the truth value of a first-order logic formula under a given interpretation, first assign truth values to the atomic formulas based on the interpretation
  • For example, if the interpretation maps the constant symbol a to the number 3 and the unary predicate symbol P to the set of even numbers, then the atomic formula P(a) would be assigned the truth value false
• The truth values of compound formulas are then determined by the truth-functional connectives and quantifiers, following the same rules as in propositional logic

Evaluating Quantified Formulas

• For universally quantified formulas (∀x P(x)), the formula is true if P(x) is true for all elements in the domain; otherwise, it is false
  • For example, if the domain is the set of natural numbers and P(x) represents the property "x is even," then the formula ∀x P(x) would be false
• For existentially quantified formulas (∃x P(x)), the formula is true if P(x) is true for at least one element in the domain; otherwise, it is false
  • For example, if the domain is the set of natural numbers and P(x) represents the property "x is even," then the formula ∃x P(x) would be true
• The truth value of a formula with nested quantifiers depends on the order of the quantifiers and the interpretation of the variables and predicates
  • For example, the formula ∀x ∃y (x < y) is true in the domain of natural numbers, but the formula ∃y ∀x (x < y) is false

Satisfiability and Validity of Formulas

Satisfiability and Models

• A formula is satisfiable if there exists at least one model (interpretation) that makes the formula true
  • For example, the formula ∃x P(x) is satisfiable in the domain of natural numbers if P is interpreted as the set of even numbers
• A formula is unsatisfiable if no such model exists
  • For example, the formula ∀x P(x) ∧ ∀x ¬P(x) is unsatisfiable in any domain because it asserts a contradiction
• To prove that a formula is satisfiable, it is sufficient to find one model that makes the formula true

Validity and Interpretations

• A formula is valid if it is true under all possible interpretations
  • In other words, every interpretation is a model for the formula
  • For example, the formula ∀x P(x) ∨ ¬∀x P(x) is valid because it is a tautology (true under all interpretations)
• To prove that a formula is valid, it is necessary to show that the formula is true under all possible interpretations
  • This can be done by using proof methods such as natural deduction or semantic tableaux
• To prove that a formula is unsatisfiable, it is necessary to show that no model exists that makes the formula true

Syntax vs Semantics in First-Order Logic

Syntax: Structure and Rules

• Syntax in first-order logic refers to the formal structure and rules for constructing well-formed formulas, without considering their meaning
  • For example, the formula ∀x (P(x) ∧ Q(x)) is syntactically correct because it follows the rules for constructing formulas using quantifiers and connectives
• The syntax of first-order logic provides the framework for expressing statements

Semantics: Meaning and Truth

• Semantics in first-order logic deals with the meaning and truth values of formulas under given interpretations
  • For example, the formula ∀x (P(x) ∧ Q(x)) is true under an interpretation if, for every element x in the domain, both P(x) and Q(x) are true
• Interpretations bridge the gap between syntax and semantics by assigning meanings to the non-logical symbols in a formula
• The truth value of a syntactically correct formula depends on the interpretation of its non-logical symbols and the structure of the formula itself

Relationship between Syntax and Semantics

• Satisfiability and validity are semantic properties of formulas that depend on the existence of models, which are determined by interpretations
  • For example, the syntactically correct formula ∀x P(x) is satisfiable if there exists an interpretation (model) where P(x) is true for all elements in the domain, and it is valid if P(x) is true for all elements in the domain under every possible interpretation
• The syntax of a formula determines its structure, while the semantics determines its meaning and truth value under different interpretations