GATE CS 2018 (Forenoon) — Question 38

Discrete MathematicsPropositional and First-Order Quantifier LogicMCQ2 marks · −2/3 if wrongHard

Consider the first-order logic sentence \(\varphi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y \psi(s, t, u, v, w, x, y)\) where \(\psi(s, t, u, v, w, x, y)\) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose \(\varphi\) has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
  1. A
    There exists at least one model of \(\varphi\) with universe of size less than or equal to 3.
  2. B
    There exists no model of \(\varphi\) with universe of size less than or equal to 3.
  3. C
    There exists no model of \(\varphi\) with universe of size greater than 7.
  4. D
    Every model of \(\varphi\) has a universe of size equal to 7.
Practise the full 2018-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Propositional and First-Order Quantifier LogicTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group