Rules of Quantification in Logic
Quantification is a fundamental concept in symbolic logic used to express propositions involving variables.
Get IGNOU MPYE-001 Solved Assignment Pdf of all answers for 2024-25 session by clicking on above button.
The rules of quantification govern the use and manipulation of quantifiers in logical statements. Quantifiers allow us to generalize or specify propositions over a domain of discourse. The two primary quantifiers are:
- Universal Quantifier (∀\forall):
- Denotes “for all” or “for every.”
- Example: ∀x(P(x))\forall x (P(x)) means “P(x) is true for all x in the domain.”
- Existential Quantifier (∃\exists):
- Denotes “there exists” or “for at least one.”
- Example: ∃x(P(x))\exists x (P(x)) means “There exists at least one x in the domain for which P(x) is true.”
Rules of Quantification
1. Universal Instantiation (UI):
- If a property holds for all elements in a domain, it holds for any specific element in the domain.
- Rule: From ∀x(P(x))\forall x (P(x)), we can infer P(a)P(a) for any specific aa in the domain.
- Example:
- Premise: ∀x(x>0→x2>0)\forall x (x > 0 \rightarrow x^2 > 0).
- Inference: a>0→a2>0a > 0 \rightarrow a^2 > 0.
2. Universal Generalization (UG):
- If a property P(a)P(a) holds for an arbitrary element aa in the domain, we can conclude ∀x(P(x))\forall x (P(x)).
- Rule: From P(a)P(a) (arbitrary aa), infer ∀x(P(x))\forall x (P(x)).
- Example:
- a+0=aa + 0 = a (true for arbitrary aa).
- Conclusion: ∀x(x+0=x)\forall x (x + 0 = x).
3. Existential Instantiation (EI):
- If there exists an element for which a property holds, we can introduce a specific element (symbolically) for that property.
- Rule: From ∃x(P(x))\exists x (P(x)), we infer P(c)P(c), where cc is a particular but arbitrary instance.
- Example:
- Premise: ∃x(x2=4)\exists x (x^2 = 4).
- Inference: c2=4c^2 = 4 (where cc could be 22 or −2-2).
4. Existential Generalization (EG):
- If a property holds for a specific element, we can conclude that there exists an element in the domain for which the property is true.
- Rule: From P(a)P(a), infer ∃x(P(x))\exists x (P(x)).
- Example:
- 22=42^2 = 4.
- Conclusion: ∃x(x2=4)\exists x (x^2 = 4).
Application of Quantification Rules
Example 1: Universal Instantiation and Modus Ponens
Premises:
- ∀x(P(x)→Q(x))\forall x (P(x) \rightarrow Q(x)).
- P(a)P(a).
Application:
- By Universal Instantiation, from ∀x(P(x)→Q(x))\forall x (P(x) \rightarrow Q(x)), infer P(a)→Q(a)P(a) \rightarrow Q(a).
- Using Modus Ponens with P(a)P(a), conclude Q(a)Q(a).
Example 2: Universal Generalization
Given: a+0=aa + 0 = a (true for any arbitrary aa).
Application: By Universal Generalization, conclude ∀x(x+0=x)\forall x (x + 0 = x).
Example 3: Existential Instantiation and Proof
Premises:
- ∃x(P(x))\exists x (P(x)).
- ∀x(P(x)→Q(x))\forall x (P(x) \rightarrow Q(x)).
Application:
- By Existential Instantiation, assume P(c)P(c) holds for some cc.
- From ∀x(P(x)→Q(x))\forall x (P(x) \rightarrow Q(x)), infer P(c)→Q(c)P(c) \rightarrow Q(c).
- Since P(c)P(c) holds, conclude Q(c)Q(c).
- By Existential Generalization, infer ∃x(Q(x))\exists x (Q(x)).
Example 4: Combining Quantifiers
Problem: Show that ∀x(∃y(x<y))\forall x (\exists y (x < y)) implies ∃y(∀x(x<y))\exists y (\forall x (x < y)) is false.
- Assume ∀x(∃y(x<y))\forall x (\exists y (x < y)): For every xx, there exists a yy such that x<yx < y.
- This does not mean a single yy exists for all xx, contradicting ∃y(∀x(x<y))\exists y (\forall x (x < y)).
Conclusion
Quantification rules are essential for formal reasoning in predicate logic. They allow us to infer new truths from general or specific statements and are widely applied in mathematics, computer science, and artificial intelligence. Through proper use of these rules, complex logical relationships can be analyzed and validated effectively.