2
$\begingroup$

My task is to translate the following 2 sentences to first-order logic. I can't figure if my proposed solution is also correct even though it doesn't match the professor's solution.

$1$. No student attended every lecture.

  • S(x): isStudent(x),
  • L(y): isLecture(y),
  • B(x,y): x attended y?

My solution 1:
$$ \neg\exists x \forall y S(x) \implies (L(y) \land B(x,y)) $$

My solution 2:
$$ \neg\exists x \forall y (S(x) \land L(y)) \implies B(x,y) $$

Correct solution:
$$\neg\exists x\forall y S(x) \land (L(y) \implies B(x, y))$$

Are they equivalent?

$\endgroup$
  • $\begingroup$ Solution 1 is not correct: it would only be true if everything were a lecture. Solution 2 is correct and equivalent to the given solution. $\endgroup$ – Berci Apr 6 at 9:21
  • 1
    $\begingroup$ @Berci - Are you sure they're equivalent? It does seem that 2 implies 3, but if we have a universe with no students, it looks like 3 can be true and 2 false by having a non-student attend a lecture. $\endgroup$ – Malice Vidrine Apr 6 at 15:11
  • $\begingroup$ I am not sure either. $\endgroup$ – siva Apr 6 at 15:58
1
$\begingroup$

My solution 1:
$$ \neg\exists x \forall y S(x) \implies (L(y) \land B(x,y)) $$

First, please allow me to add some parentheses to properly indicate the scope of the quantifiers. Also, I cannot stand to see the symbol $\Rightarrow$ being used for the material conditional, since that is more often used for logical implication ... for material implication please use the $\to$. OK, so we have:

$$ \neg\exists x \forall y (S(x) \to (L(y) \land B(x,y))) $$

Well, this is not correct. If you bring the negation inside, you see that this is equivalent to:

$$ \forall x \exists y\ \neg (S(x) \to (L(y) \land B(x,y))) $$

and thus to:

$$ \forall x \exists y\ (S(x) \land \neg (L(y) \land B(x,y))) $$

and, bringing in the $\exists y$:

$$ \forall x \ (S(x) \land \exists y \neg (L(y) \land B(x,y))) $$

... meaning (among other things) that everything in the universe is a student!

OK, so how about your:

My solution 2:
$$ \neg\exists x \forall y (S(x) \land L(y)) \implies B(x,y) $$

Again, I'll rewrite this as:

$$ \neg\exists x \forall y ((S(x) \land L(y)) \to B(x,y)) $$

Now, once again, let's bring in the negation:

$$ \forall x \exists y \ \neg ((S(x) \land L(y)) \to B(x,y)) $$

and thus:

$$ \forall x \exists y \ ((S(x) \land L(y)) \land \neg B(x,y)) $$

or simply:

$$ \forall x \exists y \ (S(x) \land L(y) \land \neg B(x,y)) $$

and thus:

$$ \forall x \ (S(x) \land \exists y (L(y) \land \neg B(x,y))) $$

So, once again this can only be true if (among other things) everything in the universe is a student! OK, so that's not right either.

However, the given answer:

Correct solution:
$$\neg\exists x\forall y S(x) \land (L(y) \implies B(x, y))$$

is indeed correct. If we bring in the $\forall y$, we get:

$$\neg \exists x (S(x) \land \forall y(L(y) \to B(x,y))$$

which is now a bit more easily seen as saying that there is no student such that for every lecture, the student attended that lecture.

In fact, if we start with the original and bring in the negation, we get:

$$\forall x\exists y \neg (S(x) \land (L(y) \to B(x, y))$$

which is equivalent to:

$$\forall x\exists y (S(x) \to \neg (L(y) \to B(x, y))$$

thus to:

$$\forall x\exists y (S(x) \to (L(y) \land \neg B(x, y))$$

and thus to:

$$\forall x (S(x) \to \exists y (L(y) \land \neg B(x, y))$$

which translates back as: 'for every student there is a lecture that they did not attend' ... which is exactly what we want!

(By the way: do you see the advantage of not always having all quantifiers on the outside when doing translation? You often get a much more natural reading of the sentence. Thus, while having all quantifiers on the outside has some practical and theoretical importance for formal logic, when it comes to symbolization, I much prefer to place the quantifiers in the 'proper' place)

Notice how you can clearly see the difference between your Solution 2 and the Given solution at the very end of their transformation. Again, your Solution 2 is equivalent to:

$$ \forall x \ (S(x) \land \exists y (L(y) \land \neg B(x,y))) $$

which says: 'Everything is a student and ...'

while the correct solution is equivalent to:

$$\forall x (S(x) \to \exists y (L(y) \land \neg B(x, y))$$

which says: 'if something is a student, then ...'

This is how the Correct solution is a claim about all students, while your solution 2 (and 1) is a claim about everything (and forces everything to be a student!)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.