What would be the translation of the following sentence in logic?

1.4k Views Asked by At

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.

Some student has asked every faculty member a question.

My Answer: ∃x∀y((S(x)∧F(y))→A(x, y))

Book Answer: ∀y(F(y) →∃x(S(x) ∨ A(x, y)))

3

There are 3 best solutions below

0
On BEST ANSWER

The book's answer is a possible, though I would say quite awkward interpretation of the English sentence, where it could be a different student for the different faculty members asking questions. But as pointed out in the comments, it should have a conjunction in place of the disjunction if you follow its interpretation.

Your interpretation (that it is the same student for every faculty member) is much more natural. But, you did not do this quite correctly either. Your sentence would be true as soon as there is something $x$ in the domain for which $S(x)$ is false, so that's not what you want. Instead do: $\exists x (S(x) \land \forall y (F(y) \to A(x,y)))$. And if you really feel the need to pull all quantifiers to the front, that would be equivalent to $\exists x \forall y (S(x) \land (F(y) \to A(x,y))$

0
On

The sentence is ambiguous, it has two possible meanings.

∃x∀y(S(x)∧(F(y)→A(x, y)) (but with the bracketing around the implication, not the conjunction) says "There is some student who asked every faculty member a question (the same student for every faculty member)".

∀y(F(y) →∃x(S(x) ∧ A(x, y))) (but with conjunction, not disjunction, I assume you made a typo there) says "For every some faculty member there is some student who asked them a question (though different faculty members may have been asked by different students)".

These statements are not equivalent (the first implies the second but not vice versa), but both are possible readings of the sentence.

So both your and your book's answer are correct, though yours is the more straightforward interpretation.

0
On

Other answers have covered what the correct answer is, I'd like to cover why your answer is wrong.

With existential quantification, we're making a claim of existence. We're saying that there is a member of the domain that satisfies the predicate - there is some x that is S. In predicate logic, this is us saying that that piece of the formula is true. It's like assigning T to an atomic proposition in propositional logic.

Let's look at the formula you've written - ∃x∀y((S(x)∧F(y))→A(x, y)). From propositional logic, we know that a conditional is only false when the antecedent is true and the consequent is false. This means that $S(x) \land F(y)$ can be false without causing us any issues. A conjunction is false when either conjunct is false. If $F(y)$ is false, that isn't an issue as universal quantification isn't claiming that a y that is F exists. If $S(x)$ is false, that is an issue as we've guaranteed that it's true. It doesn't make sense to say "This thing I guarantee 100% to be true could be false and it doesn't affect the truth of the formula".

What we want instead is a formula where $S(x)$ being true, which we've claimed, matters. If we look @Bram28's answer - ∃x(S(x)∧∀y(F(y)→A(x,y))) - what happens if $S(x)$ is false, that there is no x that is S? The whole formula becomes false - it matters and it makes intuitive sense.

As I said earlier, universal quantification doesn't imply existence. So, if instead of "some student..." it was "all students..." then ∀x∀y((S(x)∧F(y))→A(x, y)) or ∀x(S(x)→∀y(F(y)→A(x,y))) would be correct, because it's not a problem if there are no students or faculty.

This is a really awkward part of predicate logic, so if something's not clear, please ask.