I am new to discrete mathematics, and while doing the exercises on nested quantifiers I stumbled unto this exercise.
Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate “x has asked y a question,” where the domain consists of all people associated with your school. Use quantifiers to express each of these statements.
g) There's a faculty member who has asked every other faculty member a question.
I answered the following:
$$\exists x\forall y[((x \not = y) \land F(x) \land F(y))\to A(x,y)]$$
If I read my statement in English I get the following:
There's a person x, for every person y, if person x is not the same as person y and both x and y belong to faculty, then x has asked y a question.
However, when I checked the answer the book says the following:
$$\exists x[F(x) \land \forall y((F(y)\land(y\not=x))\to A(x,y))]$$
This answer I read as follows:
There's a person x such that x is a faculty member and for every person y, if y is not x and y is a faculty member, then x has asked y a question.
Which seems the same to me.
All my other answers have the same issue, I use 2 nested quantifiers and then use conditions to express the statement, but in the answers, they are all 1 quantifier outside then another one inside as a condition.
Is there any difference between my answer and the one given in the book?
If there is can someone explain to me what is the difference and what is the best way to think about quantifiers?
Because as I understand them they are just loops.
So my way of expressing the statement was:
for each x{
for each y{
if x and y something then
do something}}
the way the book does it looks to me this way:
for each x{
if x something then{
for each y{
if y something then
do something}}}
The way I see this the loops are the same except for efficiency, the second loop will run inner loop only for certain x. And in the first versions the inner loop runs for every x.
Should i apply the same thinking to nested quantifiers?
Think about efficiency when i translate english statement to logic statement?
These two experssions are not the same ... the book's answer is correct and yours is not.
Notice that we can make your statement trivially true by simply picking any object in the domain that is not a faculty member: for such an object $x$, $F(x)$ will be false, and hence the whole antecedent of the conditional will be false, and hence the whole conditional will be true, and since this will be the case for any $y$, the whole statement is true. In other words, as soon as there is an object in the domain that is not a faculty member, your statement will be true ... and so it ends up not saying anything about any faculty Member asking questions to all other facult members!
But notice that the book's answer first makes sure that $x$ is a faculty member, which is why it works.
Alo notice that the main connective of the body inside the quantifiers for your statement is a $\to$ .... inside an existential statement like yours, that is almost never correct. However, for the book' answer, the main connective inside the existential is a $\land$, while for the universal it is a $\to$ ... both are very good signs: existentials tend to go hand in hand with $\land$, while universals tend to go hand in hand with $\to$
Finally, it is not necessary to have the quantifiers inside the statement like the book has. There are equivalence principles that allow you to pull them out. BUT: 1) you have to be very careful in pulling out quantifiers: sometimes the quantifier changes from a universal to an existential or vice versa. And sometimes, you need to change variables. 2) often the statements that introduce the quantifiers only at the point where they are needed are more readable and understandable... pulling them all out like you tend to do typically makes for less readable statements.
Now, as it so happens, you can pull out the universal as is, and get:
$\exists x \ \forall y (F(x) \land (F(y) \land y \not = x) \rightarrow A(x,y)))$
But notice that the parentheses are at a different spot than you have them, so this is not the same as your statement.