Mathematical Logic · Discrete Mathematics · GATE CSE

Consider the following expressions: $$\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$(i)$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ false $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $$(ii...

Let $$p,q,r,s$$ represent the following propositions. $$p:\,\,\,x \in \left\{ {8,9,10,11,12} \right\}$$ $$q:\,\,\,x$$ is a composite number $$r:\,\,\,...

In a room there are only two types of people, namely Type $$1$$ and Type $$2.$$ Type $$1$$ people always tell the truth and Type $$2$$ people always l...

Consider the following two statements. $$S1:$$ If a candidate is known to be corrupt, then he will not be elected $$S2:$$ If a candidate is kind, he w...

Consider the following statements: P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equiv...

Consider the statement "Not all that glitters is gold" Predicate glitters$$(x)$$ is true if $$x$$ glitters and predicate gold$$(x)$$ is true if $$x...

Consider the following logical inferences. $${{\rm I}_1}:$$ If it rains then the cricket match will not be played. The cricket match was played. Inf...

What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"

The truth table Represents the Boolean function...

A set of Boolean connectives is functionally complete if all Boolean function can be synthesized using those, Which of the following sets of connectiv...

Identify the correct translation into logical notation of the following assertion. $$Some\,boys\,in\,the\,class\,are\,taller\,than\,all\,the\,girls$$...

Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x$$ and $$y$$ chosen from some universe. Consider the following stateme...

"If X then Y unless Z" is represented by which of the following formulas in propositional logic? (" $$\neg $$ " is negation, " $$ \wedge $$ " is conju...

Consider two well-formed formulas in propositional logic $$F1:P \Rightarrow \neg P$$ $$F2:\left( {P \Rightarrow \neg P} \right) \vee \left( {\neg P \...

What is the converse of the following assertion? I stay only if you go

The proposition $$p \wedge \left( { \sim p \vee q} \right)$$ is

Which of the following predicate calculus statements is/are valid?

Let p and q be two propositions. Consider the following two formulae in propositional logic. S1 : (¬p ∧ (p ∨ q)) → q S2 : q...

Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x....

Consider the first-order logic sentence $$\varphi \equiv \,\,\,\,\,\,\,\exists s\exists t\exists u\forall v\forall w$$ $$\forall x\forall y\psi \lef...

Which one of the following well-formed formulae in predicate calculus is NOT valid?

Which one of the following well formed formulae is a tautology?

Which one of the following Boolean expressions is NOT A tautology?

The CORRECT formula for the sentence, "not all rainy days are cold" is

Which one of the following propositional logic formulas is TRUE when exactly two of $$p, q,$$ and $$r$$ are TRUE?

What is the logical translation of the following statement? "None of my friends are perfect."

Which one of the following is NOT logically equivalent to $$\neg \exists x\left( {\forall y\left( \alpha \right) \wedge \left( {\forall z\left( \beta...

Which one of the following options is correct given three positive integers $$x, y$$ and $$z$$, and a predicate $$P\left( x \right) = \neg \left( {x ...

Suppose the predicate $$F(x,y,t)$$ is used to represent the statements that person $$x$$ can fool person $$y$$ at time $$t$$. Which one of the state...

Which one of the following is the most appropriate logical formula to represent the statement: "$$Gold\,and\,silver\,ornaments\,are\,precious$$" The f...

Consider the following well-formed formulae: $${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$ $${\rm I}{\rm I}.\,\,\,\,\,\,\neg...

The binary operation ◻ is defined as follows: Which one of the following is equivalence to $$P \vee Q$$? ...

If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$$ simplifies to

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 aut...

Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formulae with $$x$$ as a free variab...

$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent? $${\rm I}.$$ $${\rm P}\, \vee \sim Q$$ $${\rm I}{\...

Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall u,\exists v,\gamma } \right)}...

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

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lion attack if ...

Consider the following propositional statements: $${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equiv \left( {\left( {A \to C} \r...

A logical binary relation $$ \odot $$, is defined as follows: Let ~ be the unary negation (NOT) operator, with higher precedence then $$ \odot $$. ...

Consider the following first order logic formula in which $$R$$ is a binary relation symbol. $$\forall x\forall y\left( {R\left( {x,\,y} \right) \Righ...

Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta $$ denote the symmetric difference operator defined as $$P\Delta Q = \left( {P \cup Q} \right) - \left( ...

What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student

Let $$P, Q$$ and $$R$$ be three atomic prepositional assertions. Let $$X$$ denotes $$\left( {P \vee Q} \right) \to R$$ and $$Y$$ denote $$\left( {P \t...

Let $$P(x)$$ and $$Q(x)$$ be arbitrary predicates. Which of the following statement is always TRUE?

The following propositional statement is $$$\left( {P \to \left( {Q \vee R} \right)} \right) \to \left( {\left( {P \wedge Q} \right) \to R} \right)$$$

Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments: $$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r ...

The following resolution rule is used in logic programming. Derive clause $$\left( {P \vee Q} \right)$$ from clauses $$\left( {P \vee R} \right)$$, $$...

Let $$a, b, c, d$$ be propositions. Assume that the equivalences $$a \leftrightarrow \left( {b \vee \neg b} \right)$$ and $$b \leftrightarrow c$$ hold...

Which one of the following is false? Read $$ \wedge $$ as AND, $$ \vee $$ as OR, $$ \sim $$ as NOT, $$ \to $$ as one way implication and $$ \leftright...

If the proposition $$\neg p \Rightarrow q$$ is true, then the truth value of the proposition $$\neg p \vee \left( {p \Rightarrow q} \right)$$ where $$...

Let $$p$$ and $$q$$ be propositions. Using only the truth table decide whether $$p \Leftrightarrow q$$ does not imply $$p \to \sim q$$ is true or fa...

Indicate which of the following well-formed formula are valid:

Determine whether each of the following is a tautology, a contradiction, or neither ("$$ \vee $$" is disjunction, "$$ \wedge $$" is conjuction, ...

Let $$\left( {\left\{ {p,\,q} \right\},\, * } \right)$$ be a semi group where $$p * p = q$$. Show that: (a) $$p * q = q * p,$$, and (b) $$q * q =...

(a) Show that the formula $$\left[ {\left( { \sim p \vee Q} \right) \Rightarrow \left( {q \Rightarrow p} \right)} \right]$$ is not a tautology. (b) Le...

Show that proposition $$C$$ is a logical consequence of the formula $$A \wedge \left( {A \to \left( {B \vee C} \right) \wedge \left( {B \to \sim A} ...

Uses Modus ponens $$\left( {A,\,\,A \to B\,|\,\, = B} \right)$$ or resolution to show that the following set is inconsistent: (1) $$Q\left( x \right) ...