Discrete Mathematics – 2-Mark Questions (Predicate Logic & Quantifiers)
1. 1. Define simple statement function.
A simple statement function is a propositional function or predicate that contains variables
and becomes a statement when specific values are substituted for those variables.
2. 2. What are the two types of quantifier?
The two types of quantifiers are:
1. Universal Quantifier (∀)
2. Existential Quantifier (∃)
3. 3. Define Universal Quantifiers.
A universal quantifier (∀) states that a predicate is true for all elements in the domain.
Example: (∀x)P(x) means P(x) is true for every x.
4. 4. Define Existential Quantifiers.
An existential quantifier (∃) states that there exists at least one element in the domain for
which the predicate is true. Example: (∃x)P(x) means P(x) is true for some x.
5. 5. What are free and bound variables in predicate logic?
A free variable is not quantified and can take any value from the domain. A bound variable
is within the scope of a quantifier.
6. 6. Define the rules of specification and generalization in predicate logic.
Specification: From (∀x)P(x), we infer P(a) for any a.
Generalization: From P(a), we infer (∀x)P(x), if a is arbitrary.
7. 7. Translate into verbal statement: (∀x)(C(x) → A(x))
Every cat is an animal.
8. 8. Show that (∀x)(P(x) ∧ Q(x)) ⇒ (∃x)P(x) is logically valid.
If P(x) and Q(x) are true for all x, then P(x) must be true for at least one x, hence (∃x)P(x) is
true. So, the implication is valid.
9. 9. Rewrite using quantifiers: “All students are intelligent”.
(∀x)(S(x) → I(x)), where S(x): x is a student, I(x): x is intelligent.
10. 10. Write in symbolic form: “All mangoes are sweet”.
(∀x)(M(x) → S(x)), where M(x): x is a mango, S(x): x is sweet.
11. 11. Write the negation of: “Every student in this class is intelligent”.
¬(∀x)(S(x) → I(x)) ≡ (∃x)(S(x) ∧ ¬I(x))
12. 12. Express using quantifiers: For every x, there exists a y such that x² + y² ≥ 10
(∀x)(∃y)(x² + y² ≥ 10)
13. 13. If P(x): x² < 10, universe: {1,2,3,4}, find truth value of (∀x)P(x).
Check:
1²=1<10 ✓
2²=4<10 ✓
3²=9<10 ✓
4²=16>10 ✗
So, (∀x)P(x) is FALSE.
14. 14. Negation using quantifiers: “Any integer is either positive or negative”.
¬(∀x ∈ Z)((x > 0) ∨ (x < 0)) ≡ (∃x ∈ Z)(x ≤ 0 ∧ x ≥ 0) ⇒ (∃x)(x = 0)
15. 15. Let Z be integers. Find truth value:
a) (∀x ∈ Z), |x| = x
b) (∃x ∈ Z), |x| = x
a) FALSE, because |−1| = 1 ≠ −1
b) TRUE, since |1| = 1
16. 16. Rewrite predicates as statements:
a)(∃x)O(x)
b)(∀x)(L(x) ∨ G(x))
a) There exists an odd integer.
b) Every integer is either less than 10 or greater than 9.
17. 17. Rewrite using quantifiers: “Some men are genius”.
(∃x)(M(x) ∧ G(x)), where M(x): x is a man, G(x): x is genius.
18. 18. Show (∃y)(∀x)P(x, y) ⇔ (∀y)(∃x)P(x, y) is not equivalent.
They are not logically equivalent. Example: Let P(x,y): x<y. Then (∃y)(∀x)(x<y) is false, but
(∀y)(∃x)(x<y) is true.
19. 19. Show (∀x)(H(x) → M(x)) ∧ H(s) ⇒ M(s).
From (∀x)(H(x) → M(x)), apply specification: H(s) → M(s). Given H(s), so M(s) is true by
modus ponens.
20. 20. Find truth value of (∀x ∈ S), |x|² ≤ 3|x| - 2, where S={-2,-1,0,1,2}.
Check each:
|-2|²=4, 3×2−2=4 → ✓
|-1|²=1, 1→✓
|0|²=0 ≤ −2 ✗
So, FALSE.
21. 21. Translate: H(j) ∧ L(k, j), L(x,y): x loves y, H(x): x is handsome
John is handsome and Ketty loves John.
22. 22. Negation of: “Everybody loves somebody sometime”
¬(∀x)(∃y)(∃t)L(x,y,t) ≡ (∃x)(∀y)(∀t)¬L(x,y,t)
23. 23. Define Universal generalization and specification rule
Specification: From (∀x)P(x), deduce P(a).
Generalization: From P(a), deduce (∀x)P(x), if a is arbitrary.
24. 24. Define Existential generalization and specification rule.
Specification: From (∃x)P(x), deduce P(a), for some a.
Generalization: From P(a), deduce (∃x)P(x).
25. 25. Let P(x, y): x+y=10. Find truth value:
(i) P(2,3)
(ii) P(6,8)
P(2,3): 2+3=5 ≠10 ⇒ FALSE
P(6,8): 6+8=14 ≠10 ⇒ FALSE