Skip to content
GATETECH

GATE CS Propositional and First Order Logic questions

Practise Propositional and First Order Logic questions for GATE CS. Explore official PYQs and original topic-wise quizzes, check answers and view available solutions. Free, no sign-in.

Subject, topic, year and type filter the full library. Match any choice within a filter, and all selected filter categories. Search, source and sort apply to this page.

20 on this page
Official PYQ2005Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Let P,Q,P, Q, and RR be three atomic propositional assertions. Let XX denote (P∨Q)→R( P ∨ Q ) → R and YY denote (P→R)∨(Q→R).(P → R) ∨ (Q → R). Which one of the following is a tautology?
Official PYQ2005Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
What is the first order predicate calculus statement equivalent to the following? "Every teacher is liked by some student"
Official PYQ2004Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
The following propositional statement is (P  ⟹  (Q∨R))  ⟹  ((P∧Q)  ⟹  R)\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right)
Official PYQ2004Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: taller(x,y)\text{taller} (x, y) is true if xx is taller than yy.
Official PYQ2003Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
The following resolution rule is used in logic programming. Derive clause (P∨Q)(P \vee Q) from clauses (P∨R),(Q∨¬R)(P\vee R),(Q \vee ¬R) Which of the following statements related to this rule is FALSE?
Official PYQ2003Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Consider the following formula and its two interpretations I1I_1 and I2I_2. α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right] I1I_1 : Domain: the set of natural numbers PxP_x = 'xx is a prime number' QxyQ_{xy} = 'yy divides xx' …
Official PYQ2003Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Which of the following is a valid first order formula? (Here α\alpha and β\beta are first order formulae with xx as their only free variable)
Official PYQ2002Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
"If XX then YY unless ZZ" is represented by which of the following formulas in propositional logic? ("¬\neg" is negation, "∧\land" is conjunction, and "→\rightarrow" is implication)
Official PYQ2001Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Consider two well-formed formulas in propositional logic F1:P⇒¬PF_1: P \Rightarrow \neg P F2:(P⇒¬P)∨(¬P⇒P)F_2: (P \Rightarrow \neg P) \lor ( \neg P \Rightarrow P) Which one of the following statements is correct?
Official PYQ2000Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Let a,b,c,da, b, c, d be propositions. Assume that the equivalence a⇔(b∨¬b)a ⇔ ( b \vee \neg b) and b⇔cb ⇔c hold. Then the truth-value of the formula (a∧b)→(a∧c)∨d(a ∧ b) → (a ∧ c) ∨ d is always
Official PYQ1998Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
What is the converse of the following assertion? I stay only if you go
Official PYQ1997Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Which of the following propositions is a tautology?
Official PYQ1996Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Which of the following is NOT True? (Read ∧\wedge as AND, ∨\vee as OR, ¬\neg as NOT, →\rightarrow as one way implication and ↔\leftrightarrow as two way implication)
Official PYQ1995Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
If the proposition ¬p→q\lnot p \to q is true, then the truth value of the proposition ¬p∨(p→q)\lnot p \lor \left ( p \to q \right ), where ¬\lnot is negation, ∨\lor is inclusive OR and →\to is implication, is
Official PYQ1994Engineering MathematicsPropositional and First Order LogicNAT · 1 mark
Let pp and qq be propositions. Using only the Truth Table, decide whether p⟺qp \Longleftrightarrow q does not imply p→¬qp \to \lnot q is True or False.
Official PYQ1993Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Let A be a finite set of size n. The number of elements in the power set of A×AA\times A is:
Official PYQ1993Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
The proposition p∧(∼p∨q)p \wedge (\sim p \vee q) is:
Official PYQ1992Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Which of the following is/are a tautology?
Official PYQ1992Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
Which of the following predicate calculus statements is/are valid?
Official PYQ1991Engineering MathematicsPropositional and First Order LogicMCQ · 1 mark
If F1F_1, F2F_2 and F3F_3 are propositional formulae such that F1∧F2→F3F_1 \land F_2 \rightarrow F_3 and F1∧F2→∼F3F_1 \land F_2 \rightarrow \sim F_3 are both tautologies, then which of the following is true: