Let fa(x) and pda(y) be two predicates such that fa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equiv(a, b) be another predicate such that equiv(a, b) means a and b are equivalent. Which of the following first order logic statements represents: "Each finite state automaton has an equivalent pushdown automaton"? A. (forall x fa(x)) -> (exists y pda(y) ^ equiv(x, y)) B. forall x (fa(x) -> exists y (pda(y) ^ equiv(x, y))) C. ~exists x (fa(x) ^ ~exists y (pda(y) ^ equiv(x, y))) D. forall x exists y (fa(x) ^ pda(y) ^ equiv(x, y))
GATE 2008 · Discrete Mathematics · First Order Logic · easy
Answer: B. forall x (fa(x) -> exists y (pda(y) ^ equiv(x,y)))
- Apply 'each A has a B' pattern: forall x (fa(x) -> exists y (pda(y) ^ equiv(x,y))). This is option B.
- Check option A for scope error: Option A: (forall x fa(x)) -> (exists y pda(y) ^ equiv(x,y)). The x in equiv(x,y) is now outside the forall x scope — x is a free variable, which is not a valid closed sentence for this statement.
- Verify equivalence of B and C: Option C: ~exists x (fa(x) ^ ~exists y (pda(y) ^ equiv(x,y))) = forall x ~(fa(x) ^ ~exists y...) = forall x (fa(x) -> exists y (pda(y) ^ equiv(x,y))). So C is equivalent to B.