edited by
13,844 views
70 votes
70 votes

Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{equivalent} (a,b)$ means $a$ and $b$ are equivalent. Which of the following first order logic statements represent the following?

Each finite state automaton has an equivalent pushdown automaton

  1. $\left(\forall x \text{ fsa}\left(x\right) \right) \implies \left( \exists y \text{ pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  2. $\neg \forall y \left(\exists x \text{ fsa}\left(x\right)  \implies \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  3. $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  4. $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$
edited by

5 Answers

–3 votes
–3 votes
Let a and b be two proposition
a: Good Mobile phones.
b: Cheap Mobile Phones.

P and Q can be written in logic as
P: a-->~b
Q: b-->~a.

Truth Table
a   b   ~a  ~b   P   Q
T   T   F    F   F   F
T   F   F    T   T   T
F   T   T    F   T   T
F   F   T    T   T   T

it clearly shows P and Q are equivalent.
so option D is Correct
Answer:

Related questions

3 votes
3 votes
3 answers
1
ParthPratim asked Nov 3, 2022
969 views
I have been trying to solve the question GATE CSE 2008 Question.Are the following two representations logically equivalent ?$\beta \rightarrow (\exists x, \alpha (x))$$\e...
37 votes
37 votes
11 answers
4