Predicate Logic and Quantifiers Questions and Answers

Q: Which one of the following well-formed formulae in predicate calculus is NOT valid?

The formula that is NOT valid is ∀x (p(x) &or; q(x)) ⇒ (∀x p(x) &or; ∀x q(x)).Counterexample: let the domain be the integers, \(p(x)\) = “x is even” and \(q(x)\) = “x is odd”. Every integer is even or odd, so the left side is true, but neither “all integers are even” nor “all are odd” is true.The others are valid. (A): if \(\forall x\,p(x)\) fails then \(\exists x\neg p(x)\) holds, and if it holds then the premise gives \(\forall x\,q(x)\). (B): an existential distributes over disjunction, so the two sides are equivalent. (C): a witness of \(p \land q\) is a witness for each separately.

Q: Let P(x, y) be a propositional function, then .................. is a tautology.

The tautology is ∃x∀y P(x, y) → ∀y∃x P(x, y).If some single x0 makes P(x0, y) true for every y, then for each y there is certainly an x making P(x, y) true, namely that same x0. So the implication holds for every predicate P and every domain: it is valid.The others can fail. In (A) and (B), knowing that P holds for some x at one fixed y0 says nothing about P at other values of y. In (D), ∃x∀y P(x, y) guarantees some x that works for all y, but not that the particular fixed value x0 is that x. The converse of the correct option, ∀y∃x → ∃x∀y, is also not valid, which is the usual trap.

Which one of the following well-formed formulae in predicate calculus is NOT valid?

A.(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬p(x) ∨ ∀x q(x))
B.(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))
C.∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))
D.∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))

Exam Year(s)

GATE CS - 2016,

Answer: D

The formula that is NOT valid is ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)).

Counterexample: let the domain be the integers, \(p(x)\) = “x is even” and \(q(x)\) = “x is odd”. Every integer is even or odd, so the left side is true, but neither “all integers are even” nor “all are odd” is true.

The others are valid. (A): if \(\forall x\,p(x)\) fails then \(\exists x\neg p(x)\) holds, and if it holds then the premise gives \(\forall x\,q(x)\). (B): an existential distributes over disjunction, so the two sides are equivalent. (C): a witness of \(p \land q\) is a witness for each separately.

Discuss in Forum

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?

A.\((\exists y)(\forall x)((x\neq y)\rightarrow(M(x,y)\wedge\neg M(y,x)))\)
B.\((\forall y)(\exists x)((x\neq y)\rightarrow(M(x,y)\wedge\neg M(y,x)))\)
C.\((\exists y)(\exists x)((x\neq y)\rightarrow(M(x,y)\wedge\neg M(y,x)))\)
D.\((\forall y)(\forall x)((x\neq y)\rightarrow(M(x,y)\wedge\neg M(y,x)))\)

Exam Year(s)

GATE CS - 2026,

Answer: A

The expression is \((\exists y)(\forall x)((x\neq y)\rightarrow(M(x,y)\wedge\neg M(y,x)))\).

Read the statement as: there is a person y such that, for every other person x, x knows y and y does not know x. 'There is a person' is an existential quantifier on y, placed outside; 'everyone else' is a universal quantifier on x inside it; and 'else' becomes the condition x ≠ y. M(x, y) says x knows y, and ¬M(y, x) says y does not know x.

Swapping to ∀y ∃x says every person has someone who knows them and whom they do not know, a much weaker claim about everybody. ∃y ∃x only needs one such pair. ∀y ∀x would require every person to be known by, and not know, every other person, which is impossible for two people.

Discuss in Forum

Consider the first-order logic sentence

\[ \begin{aligned} \varphi \equiv\ & \exists s \exists t \exists u \forall v \forall w \forall x \forall y \\ & \psi(s,t,u,v,w,x,y) \end{aligned} \]

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?

A.There exists at least one model of \(\varphi\) with universe of size less than or equal to 3.
B.There exists no model of \(\varphi\) with universe of size less than or equal to 3.
C.There exists no model of \(\varphi\) with universe of size greater than 7.
D.Every model of \(\varphi\) has a universe of size equal to 7.

Exam Year(s)

GATE CS - 2018,

Answer: A

The statement that is necessarily true is that there exists at least one model of \(\varphi\) with universe of size at most 3.

Take the model with 7 elements and choose witnesses \(s, t, u\) for the three existential quantifiers. Restrict the model to the set {s, t, u}, which has at most 3 elements. Because there are no function symbols, this set is closed and gives a substructure, and the quantifier-free formula \(\psi\) has the same truth value on its elements as in the big model.

The universal part says \(\psi(s,t,u,v,w,x,y)\) holds for every choice of \(v, w, x, y\) in the big model, so in particular for every choice from {s, t, u}. Hence the small structure is also a model of \(\varphi\).

That makes 'no model of size at most 3' false. The other two fail too: if \(\psi\) is always true, \(\varphi\) has models of every size, including sizes above 7, so the universe need not be exactly 7.

Discuss in Forum

Let P(x, y) be a propositional function, then .................. is a tautology.

A.∃xP (x, y0) → ∀yP (x0, y), x0 is a fixed value from domain of x and y0 is a fixed value from domain of y
B.∃xP (x, y0) → ∃x ∀yP (x, y), y0 is a fixed value from domain of y
C.∃x∀y P(x, y) → ∀y∃x P(x, y)
D.∃x∀y P(x, y) → ∀yP (x0, y), x0 is a fixed value from domain of x

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The tautology is ∃x∀y P(x, y) → ∀y∃x P(x, y).

If some single x0 makes P(x0, y) true for every y, then for each y there is certainly an x making P(x, y) true, namely that same x0. So the implication holds for every predicate P and every domain: it is valid.

The others can fail. In (A) and (B), knowing that P holds for some x at one fixed y0 says nothing about P at other values of y. In (D), ∃x∀y P(x, y) guarantees some x that works for all y, but not that the particular fixed value x0 is that x. The converse of the correct option, ∀y∃x → ∃x∀y, is also not valid, which is the usual trap.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Predicate Logic and Quantifiers Questions and Answers || Predicate Logic and Quantifiers MCQ Questions and Answers || Predicate Logic and Quantifiers GK Questions and Answers || Predicate Logic and Quantifiers GK MCQ Questions || Predicate Logic and Quantifiers Multiple Choice Questions and Answers || Predicate Logic and Quantifiers GK || GK on Predicate Logic and Quantifiers || Discrete Mathematics Questions and Answers || Discrete Mathematics MCQ Questions and Answers || Discrete Mathematics GK Questions and Answers || GK on Discrete Mathematics

Predicate Logic and Quantifiers Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications