Official PYQ · 2019Q35Propositional and First Order LogicMCQ2 marks

GATE CS 2019 Q35 — Propositional and First Order Logic

Consider the first order predicate formula $\varphi$ :

$\forall x [ ( \forall z \: z | x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z | w \Rightarrow ((w=z) \vee (z=1)))]$

Here $a \mid b$ denotes that $’a \text{ divides } b’$ , where $a$ and $b$ are integers. Consider the following sets:

$S_1: \{1, 2, 3, \dots , 100\}$
$S_2:$ Set of all positive integers
$S_3:$ Set of all integers

Which of the above sets satisfy $\varphi$ ?

View worked solution

Answer: C

Let the predicate $P(u)$ be defined as:

P(u) \equiv \forall z \ [z \mid u \Rightarrow (z = u \vee z = 1)]

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

GATE CS · 2026Propositional and First Order Logic
For two different persons $x$ and $y$ , the predicate $M(x, y)$ denotes that $x$ knows $y$ . Consider the following statement. There is a person who does not know anyone else, but that person is known by everyone else. Which one of the following expressions represents the above statement?
MCQ · 1 mark
GATE CS · 2025Propositional and First Order Logic
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: mother $(y, x): y$ is the mother of $x$ noteq $(x, y): x$ and $y$ are not equal
MSQ · 2 marks
GATE CS · 2025Propositional and First Order Logic
Let $P(x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
MCQ · 1 mark
GATE CS · 2024Propositional and First Order Logic
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?
MCQ · 1 mark
GATE CS · 2023Propositional and First Order Logic
Geetha has a conjecture about integers, which is of the form $\forall x(P(x) \Longrightarrow \exists y Q(x, y)),$ 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?
MSQ · 1 mark
GATE CS · 2021Propositional and First Order Logic
Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_1: (\neg p\wedge(p\vee q))\rightarrow q$ $S_2: q\rightarrow(\neg p\wedge(p\vee q))$ Which one of the following choices is correct?
MCQ · 1 mark

Browse this topic

More Propositional and First Order Logic questions

GATE CS 2019 Q35 — Propositional and First Order Logic

Related questions