Syntax of First-Order Logic

Syntax of First-Order Logic

First-order logic (FOL) extends propositional logic by introducing quantifiers and predicates. It allows for more expressive statements about objects and their relationships. Understanding the syntax of first-order logic is essential for constructing valid arguments and proofs.

Basic Components of First-Order Logic

The syntax of first-order logic consists of several key components:

• Constants: These represent specific objects in the domain of discourse. For example, 'a' could represent a specific person, like 'Alice'.
• Variables: These are symbols that can represent any object in the domain. Common variables include 'x', 'y', and 'z'.
• Predicates: Predicates are functions that return true or false. They express properties of objects or relationships between them. For example, 'Loves(a, b)' could represent 'Alice loves Bob'.
• Functions: Functions map objects to other objects. An example is 'FatherOf(x)', which gives the father of the object represented by 'x'.
• Logical Connectives: These include 'and' (∧), 'or' (∨), 'not' (¬), 'implies' (→), and 'if and only if' (↔). They are used to form complex statements from simpler ones.

Forming Atomic Sentences

An atomic sentence is the simplest type of statement in first-order logic. It consists of a predicate followed by its arguments. For example, the atomic sentence:

Loves(a, b)

states that 'Alice loves Bob'. Here, 'Loves' is the predicate, and 'a' and 'b' are the constants representing Alice and Bob, respectively.

Complex Sentences

Complex sentences can be formed using logical connectives. For example, you can combine atomic sentences:

Likes(a, b) ∧ Likes(b, c)

This sentence means 'Alice likes Bob and Bob likes Charlie'. The 'and' connective (∧) combines two atomic sentences.

Quantifiers in First-Order Logic

First-order logic introduces two main quantifiers: the universal quantifier (∀) and the existential quantifier (∃).

Universal Quantifier (∀)

The universal quantifier states that a property holds for all objects in the domain. For example:

∀x Loves(x, b)

This sentence means 'For all x, x loves Bob'. It asserts that everyone loves Bob.

Existential Quantifier (∃)

The existential quantifier states that there exists at least one object in the domain for which a property holds. For example:

∃x Loves(x, b)

This sentence means 'There exists an x such that x loves Bob'. It indicates that at least one person loves Bob.

Well-Formed Formulas

A well-formed formula (WFF) is a syntactically correct expression in first-order logic. It must follow specific rules for combining constants, variables, predicates, and quantifiers. Here are some examples of well-formed formulas:

• ∀x (Loves(x, b) → Likes(x, b))

  means 'For all x, if x loves Bob, then x likes Bob.'

• ∃y (Loves(a, y) ∧ Likes(y, c))

  means 'There exists a y such that Alice loves y and y likes Charlie.'

Free and Bound Variables

In first-order logic, variables can be free or bound. A free variable is not quantified and can take any value. A bound variable is quantified by a quantifier (∀ or ∃) and is restricted to a specific scope.

For example, in the formula:

∀x (Loves(x, b) ∧ Likes(x, c))

The variable 'x' is bound by the universal quantifier. In contrast, in the formula:

Loves(a, b) ∧ Likes(x, c)

The variable 'x' is free because it is not quantified.

Examples of Syntax in First-Order Logic

Let us consider a few examples to illustrate the syntax of first-order logic:

Example 1

Consider the statement: 'Every student in the class is studying'. In first-order logic, we can express this as:

∀x (Student(x) → Studying(x))

Here, 'Student(x)' is a predicate that checks if 'x' is a student, and 'Studying(x)' checks if 'x' is studying.

Example 2

Consider the statement: 'There is a student who is studying'. This can be expressed as:

∃x (Student(x) ∧ Studying(x))

In this case, we are asserting that there exists at least one student who is studying.

Example 3

For the statement: 'If any student studies, then they pass', we can write:

∀x (Student(x) ∧ Studying(x) → Pass(x))

This means that for every 'x', if 'x' is a student and 'x' is studying, then 'x' passes.

Common Mistakes in Syntax

Summary

• First-order logic extends propositional logic by including quantifiers and predicates.
• Atomic sentences consist of predicates and their arguments.
• Complex sentences can be formed using logical connectives.
• Quantifiers include the universal quantifier (∀) and the existential quantifier (∃).
• Well-formed formulas must follow specific syntax rules.
• Variables can be free or bound depending on their quantification.

Check your understanding

1. What is the difference between a free variable and a bound variable in first-order logic?
2. How would you express the statement 'Every person loves someone' in first-order logic?
3. Provide an example of a well-formed formula that uses both quantifiers.
4. What is the importance of parentheses in first-order logic syntax?