An archived instance of a Discrete forum

Negation

mark

Consider the statement

Every natural number greater than 1 is either prime or composite.

Write down a symbolic version of the statement in the form

(\forall x) (P(x) \text{ or } Q(x))

Write down the negation of the statement; be sure to apply De Morgan’s laws.

asmith42

(\exists x)(\lnot P(x) \land \lnot Q(x))

chooke

(\exists x) (\neg(P(x)) \wedge \neg(Q(x)))

I am unclear on the negation of a function. Would we simply negate the whole function, or do we have to distribute the negation out somehow to the independent variable?

mark

Remember that P(x) is a proposition involving the variable x. So maybe

P(x) \text{ represents } ``{x} \text{ is even''}.

Then

\lnot P(x) \text{ represents } ``\text{it's not the case that } {x} \text{ is even''}.

Of course, you might more naturally write ``{x} \text{ is not even''} but, from the symbolic perspective,
\lnot P(x) just not P(x); there’s no negation beyond that.

ssatterw

\forall \mathbb{N}x (P(x)\lor C(x))
\lnot (\forall \mathbb{N}x (P(x)\lor C(x)))