Mathematical Logic · Discrete Mathematics · GATE CSE

Let $P(x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

Let p and q be the following propositions:

p: Fail grade can be given.

q: Student scores more than 50% marks.

Consider the statement: “Fail grade cannot be given when student scores more than 50% marks.”

Which one of the following is the CORRECT representation of the above statement in propositional logic?

Geetha has a conjecture about integers, which is of the form

$$\forall x\left( {P(x) \Rightarrow \exists yQ(x,y)} \right)$$,

where P is a statement about integers, and Q is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

Choose the correct choice(s) regarding the following propositional logic assertion S:

S : ((P ∧ Q)→ R)→ ((P ∧ Q)→ (Q → R))

Let p and q be two propositions. Consider the following two formulae in propositional logic.

S₁ : (¬p ∧ (p ∨ q)) → q

S₂ : q → (¬p ∧ (p ∨ q))

Which one of the following choices is correct?

The number of expressions given above that are logically implied by $$P \wedge \left( {P \Rightarrow Q} \right)$$) is _____________.

$$p:\,\,\,x \in \left\{ {8,9,10,11,12} \right\}$$
$$q:\,\,\,x$$ is a composite number
$$r:\,\,\,x$$ is a perfect square
$$s:\,\,\,x$$ is a prime number

The integer $$x \ge 2$$ which satisfies $$\neg \left( {\left( {p \Rightarrow q} \right) \wedge \left( {\neg r \vee \neg s} \right)} \right)$$ is ______________.

Which of the following options is correct?

$$S1:$$ If a candidate is known to be corrupt, then he will not be elected
$$S2:$$ If a candidate is kind, he will be elected

Which one of the following statements follows from $$S1$$ and $$S2$$ as per sound inference rules of logic?

Which of the following about L, M, and N is Correct?

Which one of the following logical formulae represents the above statement?

$${{\rm I}_2}:$$ If it rains then the cricket match will not be played. It did not rain
Inference:the cricket match was played. which of the following is TRUE?

Represents the Boolean function

Which one of the following is its equivalent?

$$Some\,boys\,in\,the\,class\,are\,taller\,than\,all\,the\,girls$$
Note: taller$$\left( {x,\,y} \right)$$ is true if $$x$$ is taller than $$y$$.

Which of the following statements is correct?

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"?

The meanings of the predicates used are:

$\bullet$ mother $(y, x): y$ is the mother of $x$

$\bullet$ noteq $(x, y): x$ and $y$ are not equal

Which one of the following statements is necessarily true?

"$$Gold\,and\,silver\,ornaments\,are\,precious$$"

The following notations are used:
$$G\left( x \right):\,\,x$$ is a gold ornament.
$$S\left( x \right):\,\,x$$ is a silver ornament.
$$P\left( x \right):\,\,x$$ is precious.

Which one of the following is equivalence to $$P \vee Q$$?

$${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {\neg P\left( x \right)} \right)$$
$${\rm I}V.\,\,\,\,\,\,\exists x\left( {\neg P\left( x \right)} \right)$$

Which of the above are equivalent?

$${\rm I}.$$ $${\rm P}\, \vee \sim Q$$
$${\rm I}{\rm I}.$$ $$ \sim \left( { \sim {\rm P} \wedge Q} \right)$$
$${\rm I}{\rm I}{\rm I}.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge \sim Q} \right)$$
$${\rm I}V.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge Q} \right)$$

Each finite state automation has an equivalent pushdown automation.

Tigers and lion attack if they are hungry of threatened.

$${\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?

Let ~ be the unary negation (NOT) operator, with higher precedence then $$ \odot $$. Which one of the following is equivalent to $$A \wedge B?$$

The formula is

($${\rm I}$$) $$P\Delta \left( {Q \cap R} \right) = \left( {P\Delta Q} \right) \cap \left( {P\Delta R} \right)$$
($${\rm I}{\rm I}$$) $$P \cap \left( {Q\Delta R} \right) = \left( {P \cap Q} \right)\Delta \left( {P \cap R} \right)$$

Which one of the following is a tautology?

$$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r \to s} \right) \wedge \left( {p \vee r} \right)} \right] \to \left( {\neg s \to q} \right)$$
$$Q:\left[ {\left( {\neg p \wedge q} \right) \wedge \left[ {q \to \left( {p \to r} \right)} \right]} \right] \to \neg r$$
$$R:\left[ {\left[ {\left( {q \wedge r} \right) \to p} \right] \wedge \left( {\neg q \vee p} \right)} \right] \to r$$
$$S:\left[ {p \wedge \left( {p \to r} \right) \wedge \left( {q \vee \neg r} \right)} \right] \to q$$

Which of the above arguments are valid?

Which of the following statements related to this rule is FALSE?

(i)$$\,\,\,\,\,\,A \leftrightarrow \left( {A \vee A} \right)$$
(ii)$$\,\,\,\,\,\,\left( {A \vee B} \right) \to B$$
(iii)$$\,\,\,\,\,\,A \vee \left( {\neg \left( {A \vee B} \right)} \right)$$

(b) Let $$A$$ be a tautology and $$B$$ be any other formula. Prove that $$\left( {A \vee B} \right)$$ is a tautology.

(1) $$Q\left( x \right) \to P\left( x \right)V \sim R\left( a \right)$$
(2) $$R\left( a \right) \vee \sim Q\left( a \right)$$
(3) $$Q\left( a \right)$$
(4) $$ \sim P\left( y \right)$$
where $$x$$ and $$y$$ are universally quantifies variables, $$a$$ is a constant and $$P, Q, R$$ are monadic predicates.