Is my answer logically equivalent to the other?

66 Views Asked by At

$S(x) = x$ is a student

$F(x) = x$ is faculty

$A(x,y) = x$ asked $y$ a question

Some student has not asked any faculty member a question.

Book solution: $\exists x(S(x) \ \land \ \forall y (F(y) \rightarrow \ \neg A(x,y)))$

My solution: $\exists x \forall y((S(x) \ \land \ F(y)) \rightarrow \ \neg A(x,y)))$

I'm not sure if my answer is the same logically.

2

There are 2 best solutions below

0
On BEST ANSWER

They're not the same. In your solution, for example, $x$ could be a teacher; in that case, for all $y$, $S(x) \wedge F(y)$ is false, so the implication $(S(x) \wedge F(y)) \Rightarrow \neg A(x, y)$ is always true.

0
On

Using the Prenex Laws, you can pull the quantifier out, so:

$$\exists x(S(x) \ \land \ \forall y (F(y) \rightarrow \ \neg A(x,y)))$$

is equivalent to:

$$\exists x \forall y (S(x) \ \land (F(y) \rightarrow \ \neg A(x,y)))$$

But since $A \land (B \rightarrow C) \not \Leftrightarrow (A \land B) \rightarrow C$, the latter is not equivalent to your:

$$\exists x \forall y((S(x) \ \land \ F(y)) \rightarrow \ \neg A(x,y)))$$