Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following:
Each finite state automaton has an equivalent pushdown automaton.

•  (A) $\left(\forall x fsa\left(x\right)\right)\Rightarrow \left(\exists y pda\left(y\right) \Lambda \mathrm{equivalent} \left(x,y\right)\right)$
•  (B) $~\forall y\left(\exists x fsa\left(x\right)\Rightarrow pda\left(y\right) \Lambda \mathrm{equivalent} \left(x,y\right)\right)$
•  (C) $\forall x\exists y\left(fsa\left(x\right) \Lambda pda\left(y\right) \Lambda equivalent \left(x,y\right)\right)$
•  (D) $\forall x\exists y\left(fsa\left(y\right) \Lambda pda\left(x\right) \Lambda equivalent \left(x,y\right)\right)$

Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?

•  (A) $\neg \forall x\left(Graph\left(x\right)\Rightarrow Connected\left(x\right)\right)$
•  (B) $\exists x\left(Graph\left(x\right)\wedge \neg Connected\left(x\right)\right)$
•  (C) $\neg \forall x\left(\neg Graph\left(x\right)\vee Connected\left(x\right)\right)$
•  (D) $\forall x\left(Graph\left(x\right)\Rightarrow \neg Connected\left(x\right)\right)$