1.2 Basic concepts and terminology of first-order logic

First-order logic is the foundation of model theory, providing a formal language to express mathematical statements. It uses variables, constants, functions, and predicates to build complex formulas that capture relationships and properties within a specific domain.

Understanding the components of first-order logic is crucial for grasping more advanced concepts in model theory. By mastering the syntax and semantics of well-formed formulas, you'll be equipped to analyze and construct logical arguments in various mathematical contexts.

Components of First-Order Logic

Variables, Constants, and Functions

Top images from around the web for Variables, Constants, and Functions

• 

  Monforte | Syntactic analyses of discourse particles through the microvariation of Basque ote ... View original

  Is this image relevant?

• 

  pikes - Representation model View original

  Is this image relevant?

• 

  Monforte | Syntactic analyses of discourse particles through the microvariation of Basque ote ... View original

  Is this image relevant?

• 

  pikes - Representation model View original

  Is this image relevant?

1 of 2

Top images from around the web for Variables, Constants, and Functions

• 

  Monforte | Syntactic analyses of discourse particles through the microvariation of Basque ote ... View original

  Is this image relevant?

• 

  pikes - Representation model View original

  Is this image relevant?

• 

  Monforte | Syntactic analyses of discourse particles through the microvariation of Basque ote ... View original

  Is this image relevant?

• 

  pikes - Representation model View original

  Is this image relevant?

1 of 2

• Variables represent unspecified objects within a domain of discourse denoted by lowercase letters (x, y, z)
• Constants represent specific, named objects within the domain denoted by lowercase letters or descriptive names (a, b, c)
• Functions map one or more arguments to a single value represented by lowercase letters with parentheses containing arguments (f(x), g(x,y))
  • Example: father(x) represents a function that returns the father of x
  • Example: add(x,y) represents a function that adds two numbers x and y

Predicates and Quantifiers

• Predicates express relations or properties that can be true or false for objects denoted by uppercase letters (P(x), Q(x,y))
  • Example: Tall(x) represents the property of x being tall
  • Example: GreaterThan(x,y) represents the relation of x being greater than y
• Universal quantifier (∀) expresses statements about all objects in the domain
  • Example: $\forall x P(x)$ means "for all x, P(x) is true"
• Existential quantifier (∃) expresses statements about some objects in the domain
  • Example: $\exists x Q(x)$ means "there exists an x such that Q(x) is true"

Logical Connectives

• Conjunction (∧) represents "and" in logical expressions
• Disjunction (∨) represents "or" in logical expressions
• Negation (¬) represents "not" in logical expressions
• Implication (→) represents "if...then" in logical expressions
• Biconditional (↔) represents "if and only if" in logical expressions
  • Example: $(P \wedge Q) \rightarrow R$ means "if P and Q are true, then R is true"
  • Example: $\neg P \vee Q$ means "either P is false or Q is true"

Terms, Formulas, and Sentences

Terms and Atomic Formulas

• Terms represent objects in the domain including variables, constants, and functions applied to other terms
  • Example: x (variable), c (constant), f(g(x)) (function applied to another function)
• Atomic formulas consist of a predicate symbol followed by a list of terms in parentheses
  • Example: P(x) represents a unary predicate applied to variable x
  • Example: Q(f(x),y) represents a binary predicate applied to function f(x) and variable y

Complex Formulas and Sentences

• Formulas build recursively from atomic formulas using logical connectives and quantifiers
  • Example: $\forall x (P(x) \rightarrow Q(x))$ represents "for all x, if P(x) is true, then Q(x) is true"
• Sentences (closed formulas) contain no free variables with all variables bound by quantifiers
  • Example: $\forall x \exists y R(x,y)$ represents "for every x, there exists a y such that R(x,y) is true"
• Free variables occur in formulas without being bound by quantifiers
• Bound variables are within the scope of a quantifier in a formula

Well-Formed Formulas (WFFs)

• WFFs adhere to syntactic rules of first-order logic ensuring grammatical correctness and meaning
• WFFs constructed recursively starting with atomic formulas and building complex formulas
• Balanced parentheses in WFFs properly enclose subformulas and argument lists
• Quantifiers in WFFs followed by a variable and a formula binding the specified variable
  • Example: $\forall x (P(x) \vee Q(x))$ is a WFF, but $\forall (P(x) \vee Q(x))$ is not

Syntax vs Semantics in First-Order Logic

Syntactic Rules and Structure

• Syntax specifies rules for constructing well-formed formulas
• Syntactic rules govern formation of terms, atomic formulas, and complex formulas
  • Example: The formula $P(x) \wedge Q(y)$ is syntactically correct, while $P(x \wedge Q(y)$ is not
• Formal languages require clear syntax to avoid ambiguity and ensure precise reasoning
  • Example: Parentheses in $(P \wedge Q) \vee R$ and $P \wedge (Q \vee R)$ change the syntactic structure and meaning

Semantic Interpretation and Meaning

• Semantics deals with interpretation and meaning of formulas
• Semantic rules determine how constructs are interpreted in models
  • Example: The sentence $\forall x (Human(x) \rightarrow Mortal(x))$ is interpreted as "all humans are mortal"
• Truth values assigned to sentences based on given structure or model
  • Example: The formula $P(a) \wedge Q(b)$ is true in a model if both P(a) and Q(b) are true in that model

Relationship Between Syntax and Semantics

• Syntax focuses on form and structure while semantics focuses on content and truth conditions
• Interplay between syntax and semantics crucial for understanding logical concepts
  • Logical consequence determines if a conclusion follows from given premises
  • Validity assesses if a formula is true in all possible interpretations
  • Satisfiability determines if a formula is true in at least one interpretation
• Syntactically correct formulas may have different semantic interpretations in different models
  • Example: $\forall x P(x)$ is syntactically correct but its truth value depends on the interpretation of P and the domain of x

Properties of Well-Formed Formulas

Recursive Construction and Parentheses

• WFFs defined recursively starting with atomic formulas and building complex formulas
  • Example: If P(x) is a WFF, then $\neg P(x)$ and $\forall x P(x)$ are also WFFs
• Balanced parentheses in WFFs properly enclose subformulas and argument lists
  • Example: $(P(x) \wedge Q(y))$ is well-formed, while $(P(x) \wedge Q(y)$ is not due to unbalanced parentheses

Quantifiers and Variable Binding

• Quantifiers in WFFs followed by a variable and a formula binding the specified variable
  • Example: $\forall x (P(x) \rightarrow Q(x))$ is a WFF, but $\forall (P(x) \rightarrow Q(x))$ is not
• Scope of quantifiers determines the part of the formula where the variable is bound
  • Example: In $\forall x (P(x) \wedge \exists y Q(x,y))$, x is bound throughout the formula, while y is bound only within Q(x,y)

Logical Connectives and Precedence

• Precedence of logical connectives follows specific order unless modified by parentheses
  • Order: negation, conjunction, disjunction, implication, biconditional
  • Example: $P \vee Q \wedge R$ is interpreted as $P \vee (Q \wedge R)$ due to precedence
• Substitutability allows replacement of free variables by terms without altering well-formedness
  • Example: In P(x), x can be substituted by a constant a or a function f(y) to form P(a) or P(f(y))
• Restrictions on substitution prevent variable capture in quantified formulas
  • Example: In $\forall x P(x)$, substituting x with a term containing a free variable y is not allowed if y would become bound