Discussion
Which of the following WFFs is valid (tautology) in predicate logic ?
∀x(P(x) → Q(x)) → (∃xP(x) → ∃xQ(x))
Answer: C
The formula is always valid.
Suppose the antecedent holds, so every object with P also has Q, and suppose there is some object with P. Call it a. Then P(a) is true, so by the first assumption Q(a) is true, and therefore some object has Q.
\[ \begin{aligned} &\forall x(P(x) \to Q(x)),\ P(a) \\ &\Rightarrow Q(a) \Rightarrow \exists x\, Q(x) \end{aligned} \]
The argument uses no property of the domain, so the formula is true in every interpretation, finite or infinite; 'valid only for finite domains' is therefore wrong. Option B confuses the formula with its antecedent: the implication as a whole holds even when P(x) → Q(x) fails for some x, because the implication is then trivially true. ∃x(¬Q(x) ∧ P(x)) is the negation of ∀x(P(x) → Q(x)), not an equivalent of the formula.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development