Predicate Logic

1. Introduction to Predicate Logic

Propositional logic is useful for representing simple true/false statements, but it has limitations when dealing with variables and general statements. For example:

  • “All students in this class are hardworking.”
  • “Some Indian cities have metro rail networks.”

These statements cannot be adequately expressed using propositional logic. To handle such cases, Predicate Logic (also called First-Order Logic, FOL) is used.

Why Do We Need Predicate Logic?

Consider these two statements:

  1. “Ram is a student.”
  2. “All students are hardworking.”

Using predicate logic, we can represent these in a structured form:

  • Let S(x) mean “x is a student.”
  • Let H(x) mean “x is hardworking.”
  • The first statement becomes: S(Ram)
  • The second statement becomes: ∀x (S(x) → H(x))

Thus, predicate logic allows us to work with general statements that involve variables.

2. Components of Predicate Logic

Predicate logic consists of the following key components:

  1. Constants – Represent specific objects. Example: “Ram”, “Delhi”.
  2. Variables – Represent generic objects. Example: x,y,zx, y, zx,y,z.
  3. Predicates – Represent properties or relationships between objects. Example: S(x)S(x)S(x) means “x is a student”.
  4. Quantifiers – Used to specify how many objects satisfy a given predicate.

3. Quantifiers in Predicate Logic

Quantifiers allow us to express statements about all or some objects in a given domain.

3.1 Universal Quantifier ( ∀ )

  • Denoted as ∀ (for all)
  • It states that a predicate holds true for all elements in the domain.
  • Example: ∀x (S(x) → H(x))
    • Meaning: “For all x, if x is a student, then x is hardworking.”

Example

  • “All citizens of India have the right to vote.”
  • Let C(x) mean “x is a citizen of India.”
  • Let V(x) mean “x has the right to vote.”
  • This can be written as:
    ∀x(C(x)→V(x))∀x (C(x) → V(x))∀x(C(x)→V(x))

3.2 Existential Quantifier ( ∃ )

  • Denoted as ∃ (there exists)
  • It states that a predicate holds true for at least one element in the domain.
  • Example: ∃x S(x)
    • Meaning: “There exists at least one person who is a student.”

Example from

  • “Some Indian cities have metro rail.”
  • Let M(x) mean “x has a metro rail system.”
  • Let C(x) mean “x is an Indian city.”
  • This can be written as:
    ∃x(C(x)∧M(x))∃x (C(x) ∧ M(x))∃x(C(x)∧M(x))

4. Nested Quantifiers

Sometimes, we need to use multiple quantifiers in a statement.

4.1 Example of Nested Quantifiers

Consider: “Every school has at least one student.”

  • Let S(y) mean “y is a school”.
  • Let P(x, y) mean “x is a student in y”.

This can be written as:
∀y(S(y)→∃xP(x,y))∀y (S(y) → ∃x P(x, y))∀y(S(y)→∃xP(x,y))

This means: “For every school y, there exists at least one student x such that x is in y.”

5. Rules of Inference in Predicate Logic

5.1 Universal Instantiation (UI)

  • If a statement is true for all elements, it must be true for any specific element.
  • Example:
    • Given: ∀x (C(x) → V(x))
    • Conclusion: If C(Ram) is true, then V(Ram) must be true.

5.2 Universal Generalization (UG)

  • If a statement is true for every specific element, it must be true for all elements.
  • Example:
    • If V(Ram), V(Sita), V(Ravi), … are true for all people, we conclude:
    • ∀x V(x) is true.

5.3 Existential Instantiation (EI)

  • If a statement is true for some element, we can introduce a new element.
  • Example:
    • Given ∃x P(x), we introduce a specific ccc such that P(c) is true.

5.4 Existential Generalization (EG)

  • If a predicate holds for at least one element, then an existential statement is valid.
  • Example:
    • If P(Ram) is true, we conclude ∃x P(x).

6. Practice Questions

  1. Translate the following statements into predicate logic:
    • a) “All students in this university study mathematics.”
    • b) “Some cities in India are polluted.”
  2. Prove that if ∀x (P(x) → Q(x)) and P(a) are true, then Q(a) must be true.
  3. Show that “Every human has a mother” can be written using nested quantifiers.
  4. Convert the following logical statements into English:
    • a) ∀x (S(x) → H(x))
    • b) ∃y (F(y) ∧ C(y))

Conclusion

Predicate Logic extends Propositional Logic by allowing us to express statements involving variables and quantifiers. It is widely used in Artificial Intelligence, Database Queries (SQL), and Theoretical Computer Science.