Question: How does negation work with forall and exists?
Answer: $\neg \forall x[ G ] \Longleftrightarrow \exists x[ \neg G ]$, and $\neg \exists x[ G ] \Longleftrightarrow \forall x[ \neg G ]$.

  1. Given: $L$ is a language, $M$ is a FA, $w$ is a string such that $w\in L(M)$ and $w \notin L$.

    1. "all strings accepted by M are not in L" : T / F / Maybe
    2. "not all strings accepted by M are in L" : T / F / Maybe

  2. Consider the following attempted restatements of the definition of grammar $G$ being ambiguous:

    1. there is not a string in L(G) that doesn't have a unique parse tree
    2. every string in L(G) does not have a unique parse tree
    3. there is a string in L(G) that doesn't have a unique parse tree
    4. not every string in L(G) has a unqiue parse tree
    5. there is not a string in L(G) that has a unique parse tree
    6. not every string in L(G) doesn't have a unique parse tree

    Model each of these in first order logic. Simplify using the above rules to push the negations inwards, and then assess: is this equivalent to the grammar being ambiguous?

    Note: Just assume strings in L(G) are our domain of discourse in order to simplify things. So, for example:

    (f) is equivalent to: $\neg \forall s[ \neg \text{uniquePT}(s) ]$, equivalent to $\exists s[ \neg\neg \text{uniquePT}(s) ]$, equivalent to $\exists s[ \text{uniquePT}(s) ]$.

    ... so (f) is not a correct restatement of the grammar being ambiguous.