Negation of a statement?

188 Views Asked by At

L = {M, w| M is a TM, w is a string, and for some nonempty strings x, y, w = xy, M accepts xyx and M rejects yxy}..

Im having issues representing this in mathematical form.

For example what would the negation of "M accepts xyx" be? or "for some nonempty strings x, y, w = xy,"

How would I negate this?

1

There are 1 best solutions below

9
On BEST ANSWER

I'm not sure what you mean by "representing this in mathematical form," but I'll try to help with quantifiers.

To answer your two questions:

Negating "$M$ accepts $xyx$"

There are three possibilities for a Turing Machine on any input: accept, reject, or "run forever" (not halt). So, the negation of "$M \text{ accepts } xyx$" corresponds to "$M$ rejects $xyx$ or $M$ does not halt on $xyx$."

Negating "for some non-empty strings $x$, $y$, $w = xy$"

By "for some," are you saying "for all" or "there exist"?

It sounds like "for some non-empty strings $x$, $y$, $w = xy$" is actually "for $\textit{all}$ non-empty strings $x$, $y$, where $w = xy$". In general, the negation of a statement of the form

$$\text{for all } x_1, x_2, ... , x_n, S$$

(where $S$ is some statement) is the statement

$$\text{there exist } x_1, x_2, ... , x_n | \neg S$$

Where "|" indicates "such that." The reasoning behind this is that the opposite of "this rule always applies" is "there exists a counterexample to this rule."

So in your case, you would be negating "for all non-empty strings $x$, $y$, where $w = xy$, $M$ accepts $xyx$ and $M$ rejects $yxy$." By the rule above, our negation is "there exist non-empty strings $x$, $y$, where $w = xy$, such that $M$ does not accept $xyx$ or $M$ does not reject $yxy$."

Note that the meanings of "$M$ does not accept $xyx$" and "$M$ does not reject $yxy$" have been explained above, and that "$M$ does not accept $xyx$ or $M$ does not reject $yxy$" is the result of De Morgan's law.