GATE 2007-IT
April 5, 2025GATE 2007-IT
April 5, 2025GATE 2007-IT
| Question 21 |
Which one of these first-order logic formula is valid?
| ∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x)) | |
| ∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x)) | |
| ∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x)) | |
| ∀x∃y P(x, y) ⇒ ∃y∀x P(x, y) |
Question 21 Explanation:
LHS = for every x, if P holds then Q holds
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)
Correct Answer: A
Question 21 Explanation:
LHS = for every x, if P holds then Q holds
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)