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:

“Ram is a student.”
“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:

Constants – Represent specific objects. Example: “Ram”, “Delhi”.
Variables – Represent generic objects. Example: x,y,zx, y, zx,y,z.
Predicates – Represent properties or relationships between objects. Example: S(x)S(x)S(x) means “x is a student”.
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

Translate the following statements into predicate logic:
- a) “All students in this university study mathematics.”
- b) “Some cities in India are polluted.”
Prove that if ∀x (P(x) → Q(x)) and P(a) are true, then Q(a) must be true.
Show that “Every human has a mother” can be written using nested quantifiers.
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.