Mathematical Logic · Discrete Mathematics · GATE CSE

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

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

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. S1 : (¬p ∧ (p ∨ q)) → q S2 : q...

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

The truth table Represents the Boolean function...

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

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

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?

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$$? ...

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)}...

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

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

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

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

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

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

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

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

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

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

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, 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 propositional statement is $$$\left( {P \to \left( {Q \vee R} \right)} \right) \to \left( {\left( {P \wedge Q} \right) \to R} \right)$$$

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

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

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

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