GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 45 of 65

Marks: +1, -0

Consider the first-order logic sentence
ϕ=∃ s ∃ t ∃ u ∀ v ∀ w ∀ x ∀ y ψ(s, t, u, v, w, x, y)
where ψ (s t u v w x y , , , , , , ) is a quantifier-free-order logic formula using only predicate symbols and possibly equality, but no function symbols. Suppose φ has a model with a universe containing 7 elements.
Which one of the following statements is necessarily true?

There exists at least one model of φ with universe of size less than or equal to 3.
There exists no model of φ with universe of size less than or equal to 3.
There exists no model of φ with universe of size greater than 7.
. Every model of φ has a universe of size equal to 7.

Validate

Solution:

∀

are always True and

∃

are always False for empty sets.
So there exists at least one model with universe of size 3 (or less than).
Therefore, option (A) is necessarily TRUE.

Go to Question:

Prev Question

Next Question