First Order Logic

Definition

First Order Logic (FOL) is a formal logical system in which statements are built using:

Constants

• to represent specific objects

Variables

• to represent arbitrary objects

Predicates

• to express properties or relations

Functions

• to map objects to objects

Quantifiers

• to state generality or existence

It allows us to talk about what objects exist in a domain and how they are related, using expressions such as:

• “All students passed the exam”
• “There exists a person who is a doctor”
• “Every city has a road connected to another city”

Unlike propositional logic, first order logic can break a statement into smaller meaningful parts and describe structure more accurately.

Main Content

1. Syntax and Building Blocks of First Order Logic

Constants, variables, predicates, and functions

• are the basic symbols used to construct formulas in first order logic.
• A constant names a specific object, such as a, John, or 5.
• A variable stands for any object in the domain, such as x, y, or z.
• A predicate expresses a property or relation. For example:
  • Student(x) means “x is a student”
  • Loves(x, y) means “x loves y”
• A function maps objects to objects. For example:
  • FatherOf(x) returns the father of x
  • NextState(s) returns the next state of s

Well-formed formulas (WFFs)

• are expressions that follow the rules of first order logic. Examples:

• Student(John)

• Loves(John, Mary)
• ∀x(Student(x) → Intelligent(x))
• ∃x(Teacher(x) ∧ Kind(x))

These formulas are meaningful only when the symbols are combined in the correct way.

2. Quantifiers and Meaning in a Domain

Quantifiers

• specify how many objects in the domain satisfy a statement. The two main quantifiers are:
• Universal quantifier ∀ meaning “for all”
• Existential quantifier ∃ meaning “there exists”

Examples:

• ∀x Human(x) → Mortal(x)
  Means: “All humans are mortal.”

• ∃x Prime(x) ∧ Even(x)
  Means: “There exists an even prime number.”

The domain of discourse

• is the set of objects over which variables range. For example:

• In a classroom domain, variables may represent students.

• In a number theory domain, variables may represent integers.
• In a traffic system, variables may represent intersections or states.

The same formula can have different meanings depending on the domain. For example, ∀x P(x) is only interpretable when we know what objects x refers to.

3. Interpretation, Semantics, and Logical Reasoning

Interpretation

• gives meaning to the symbols of first order logic. It tells us:
• What objects constants refer to
• What predicates mean in the given domain
• What functions do
• Which statements are true or false in that domain

Example interpretation:

• Domain = {Alice, Bob, Carol}
• Student(x) is true for Alice and Bob
• Loves(Alice, Bob) is true
• John refers to Bob

Logical reasoning

• in first order logic is used to derive conclusions from premises. Example:

• Premise 1: ∀x(Student(x) → Studies(x))

• Premise 2: Student(Ravi)
• Conclusion: Studies(Ravi)

This shows how general rules and specific facts together lead to valid inference.

First order logic is widely used in:

• theorem proving
• artificial intelligence
• database query languages
• knowledge representation

Working / Process

1. Identify the domain and the objects

• Decide what the variables will represent.
• Example: students, machines, states, numbers, cities, etc.

2. Convert statements into logical symbols

• Replace natural language with predicates, variables, quantifiers, and connectives.
• Example:
  • “Every student is hardworking” → ∀x(Student(x) → Hardworking(x))
  • “Some student is absent” → ∃x(Student(x) ∧ Absent(x))

3. Apply interpretation and inference rules

• Check whether the formula is true in a given model.
• Use rules such as universal instantiation, existential instantiation, and modus ponens to derive conclusions.
• Example:
  • From ∀x(P(x) → Q(x)) and P(a), infer Q(a).

Advantages / Applications

More expressive than propositional logic

It can represent objects, properties, and relationships, making it suitable for complex real-world knowledge.

Useful in reasoning and automation

It forms the basis of logical inference systems, expert systems, formal verification, and AI reasoning engines.

Strong applications in computer science and mathematics

It is used in:

• database query formulation
• program specification
• automated theorem proving
• knowledge-based systems
• formal modeling of systems and states

Summary

First order logic is a powerful logical framework used to describe objects, properties, and relations with the help of predicates and quantifiers. It extends propositional logic and enables precise mathematical and computational reasoning.