GATE Overflow Test Series | Discrete Mathematics | Test 1 | Question: 1

Question

Which of the following is the correct formalization for the sentence
"No student loves Bill"? 

(Mark all the appropriate choices)

• A. $\neg \exists x(\text{Student}(x) \wedge \text{Loves}(x,Bill))$
• B. $\forall x(\neg \text{Student}(x) \vee \neg \text{Loves}(x,Bill))$
• C. $\forall x(\neg \text{Student}(x) \vee \text{Loves}(x,Bill))$
• D. $\forall x(\neg \text{Student}(x) \wedge \neg \text{Loves}(x,Bill))$

Answer 1

Let

• Student$(x): x$ is a student
• Loves$(x,\text{Bill}):x\; \text{loves Bill}$

"No student loves Bill"

Domain of discourse: All the people

We can interpret like this way.

• If Raju is a student, then he does not love Bill.
• If Rani is a student, then she does not love Bill.
• If Rakesh is a student, then he does not love Bill.
• If Vani is a student, then she does not love Bill.
• and, so on..

Now, we try to convert same statements, in terms of variables.

• If $x_{1}$ is a student, then $x_{1}$ does not love Bill.
• If $x_{2}$ is a student, then $x_{2}$ does not love Bill.
• If $x_{3}$ is a student, then $x_{3}$ does not love Bill.
• ---------------------------------------------------------------
• If $x_{n}$ is a student, then $x_{n}$ does not love Bill.

Now, try to conclude, the above statements.

• $\text{Student}(x_{1}) \rightarrow \neg \text{Loves}(x_{1},\text{Bill})$
• $\text{Student}(x_{2}) \rightarrow \neg \text{Loves}(x_{2},\text{Bill})$
• $\text{Student}(x_{3}) \rightarrow \neg \text{Loves}(x_{3},\text{Bill})$
• ------------------------------------------------------------
• $\text{Student}(x_{n}) \rightarrow \neg \text{Loves}(x_{n},\text{Bill})$

We , can write above statements using universal quantifier $(\forall)$.

• $\forall x(\text{Student}(x) \rightarrow \neg \text{Loves}(x,\text{Bill}))$
• $\forall x(\neg \text{Student}(x) \vee \neg \text{Loves}(x,\text{Bill}))\quad [\because P \rightarrow Q \equiv \neg P \vee Q]$

Demorgan's laws:

• $\neg \forall x (P(x) \vee Q(x)) \equiv \exists x (\neg P(x) \wedge \neg Q(x))$
• $\neg \exists x (P(x) \wedge Q(x)) \equiv \forall x (\neg P(x) \vee \neg Q(x))$

Now, $\forall x(\neg \text{Student}(x) \vee \neg \text{Loves}(x,\text{Bill})) \equiv \forall x[\neg (\text{Student}(x) \wedge \text{Loves}(x,\text{Bill}))]\equiv \neg \exists x[\text{Student}(x) \wedge \text{Loves}(x,\text{Bill})]$

So, the correct answer is $A;B$

Answer 2

Both options A and B are equivalent as we can push $\neg$ into a first order logic formula by interchanging $\vee$ and $\wedge$,  interchanging $\exists$ and $\forall$ and negating every term.