GATE CSE 2008 | Mathematical Logic Question 37 | Discrete Mathematics

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ means that $$y$$ is a pushdown automation. 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 automation has an equivalent pushdown automation.

$$\left( {\forall x\,\,fsa\left( x \right)} \right) \Rightarrow \left( {\exists y\,\,pda\left( y \right) \wedge \,equivalent\,\,\left( {x,\,y} \right)} \right)$$

$$ \sim \forall y\left( {\exists x\,\,fsa\left( x \right) \Rightarrow pda\left( y \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$

$$\forall x\,\exists y\left( {fsa\left( x \right) \wedge pda\left( y \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$

$$\forall x\,\exists y\left( {fsa\left( y \right) \wedge pda\left( x \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Which one of these first-order logic formulae is valid?

$$\forall x\left( {P\left( x \right) \Rightarrow Q\left( x \right)} \right) \Rightarrow \left( {\left( {\forall xP\left( x \right)} \right) \Rightarrow \left( {\forall xQ\left( x \right)} \right)} \right)$$

$$\exists x\left( {P\left( x \right) \vee Q\left( x \right)} \right) \Rightarrow \left( {\left( {\exists xP\left( x \right)} \right) \Rightarrow \left( {\exists xQ\left( x \right)} \right)} \right)$$

$$\exists x\left( {P\left( x \right) \wedge Q\left( x \right)} \right) \Leftrightarrow \left( {\left( {\exists xP\left( x \right)} \right) \wedge \left( {\exists xQ\left( x \right)} \right)} \right)$$

$$\forall x\exists yP\left( {x,y} \right) \Rightarrow \exists y\forall xP\left( {x,y} \right)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Which one of the first order predicate calculus statements given below correctly expresses the following English statement?

Tigers and lion attack if they are hungry of threatened.

$$\forall x[(tiger(x) \wedge lion(x)) \to $$$$\{ (hungry(x) \vee threatened(x)) \to attacks(x)\} ]$$

$$\forall x[(tiger(x) \vee lion(x)) \to $$$$\{ (hungry(x) \wedge threatened(x)) \to attacks(x)\} ]$$

$$\forall x[(tiger(x) \vee lion(x)) \to $$$$\{ attacks(x) \to (hungry(x)) \vee threatened(x))\} ]$$

$$\forall x[(tiger(x) \vee lion(x)) \to $$$$\{ (hungry(x) \vee threatened(x)) \to attacks(x)\} ]$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the following propositional statements:

$${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equiv \left( {\left( {A \to C} \right) \wedge \left( {B \to C} \right)} \right)$$
$${\rm P}2:\,\,\left( {\left( {A \vee B} \right) \to C} \right) \equiv \left( {\left( {A \to C} \right) \vee \left( {B \to C} \right)} \right)$$ Which one of the following is true?

$$P1$$ is tautology, but not $$P2$$

$$P2$$ is tautology, but not $$P1$$

$$P1$$ and $$P2$$ are both tautologies

Both $$P1$$ and $$P2$$ are not tautologies

PREVIOUS NEXT