Usbrth

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:
$$ negexists x forall y S(x) implies (L(y) land B(x,y)) $$

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

Correct solution:
$$negexists xforall y S(x) land (L(y) implies B(x, y))$$

Are they equivalent?

My solution 1:
$$ negexists 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:

$$ negexists 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:
$$ negexists x forall y (S(x) land L(y)) implies B(x,y) $$

Again, I'll rewrite this as:

$$ negexists 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:
$$negexists xforall 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 xexists y neg (S(x) land (L(y) to B(x, y))$$

which is equivalent to:

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

thus to:

$$forall xexists 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!)