Official PYQ · 2003Q33Propositional and First Order LogicMCQ1 mark

GATE CS 2003 Q33 — Propositional and First Order Logic

Consider the following formula and its two interpretations $I_1$ and $I_2$ .

$\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]$

$I_1$ : Domain: the set of natural numbers

$P_x$ = ' $x$ is a prime number'

$Q_{xy}$ = ' $y$ divides $x$ '

$I_2$ : same as $I_1$ except that $P_x$ = ' $x$ is a composite number'.

Which of the following statements is true?

View answer

Answer: D

Worked explanation not available yet.

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 2003 Q33 — Propositional and First Order Logic

Related questions