Negation of $\forall x T(x) \implies \exists y L(y)$

logic

I am trying to figure out the negation of $\forall xT(x) \implies \exists y L(y)$

I have two choices in mind

  1. $\exists x T(x) \land \forall y \neg L(y)$

  2. $\forall x T(x) \land \forall y \neg L(y)$

Not sure which is correct. I know in general the negation of $p \implies q$ is $p \land \neg q$ but here how to handle the quantifiers is confusing me.

For instance if the bracketing was $\forall x(T(x) \implies \exists y L(y))$, then I believe the negation would be $\exists x T(x) \land \forall y \neg L(y)$, but in this case since $\forall x T(x)$ is a premise, I think that $2$ is correct.

Best Answer

The traditional convention is that quantifiers bind tighter than the binary connectives: so you should read your formula as $(\forall x T(x)) \implies (\exists y(L(y))$, which makes your proposed answer 2 the correct one. (Your idea about $\forall x(T(x) \implies \exists y(L(y))$ isn't right: $\implies$ should still turn into $\land$ when you negate it. This would lead to answer 1.)

Related Question