9.4 Negation and Quantifiers

Quantifiers and negation are key to understanding logical statements. We'll look at how to negate universal and existential statements, flipping quantifiers and negating predicates.

These rules are crucial for working with complex logical expressions. We'll also explore De Morgan's laws for quantifiers and learn about contradictory and equivalent forms of quantified statements.

Negating Quantified Statements

Negating Universal Statements

• Universal statements use the universal quantifier $\forall$ (for all) to make assertions about all elements in a domain
• To negate a universal statement, change the universal quantifier $\forall$ to the existential quantifier $\exists$ (there exists) and negate the predicate
• For example, the negation of $\forall x P(x)$ is $\exists x \neg P(x)$, meaning there exists at least one element in the domain for which the predicate is false
• Negating a universal statement is equivalent to asserting that there is a counterexample to the original statement

Negating Existential Statements

• Existential statements use the existential quantifier $\exists$ (there exists) to assert the existence of at least one element in the domain that satisfies the predicate
• To negate an existential statement, change the existential quantifier $\exists$ to the universal quantifier $\forall$ (for all) and negate the predicate
• For instance, the negation of $\exists x P(x)$ is $\forall x \neg P(x)$, meaning the predicate is false for all elements in the domain
• Negating an existential statement is equivalent to asserting that no element in the domain satisfies the original predicate

Quantifier Negation Rules

• The negation of a universally quantified statement $\forall x P(x)$ is an existentially quantified statement with a negated predicate $\exists x \neg P(x)$
• Conversely, the negation of an existentially quantified statement $\exists x P(x)$ is a universally quantified statement with a negated predicate $\forall x \neg P(x)$
• These rules can be summarized as:
  • $\neg(\forall x P(x)) \equiv \exists x \neg P(x)$
  • $\neg(\exists x P(x)) \equiv \forall x \neg P(x)$
• Applying these rules allows for the correct negation of quantified statements while maintaining logical equivalence

Logical Equivalences with Quantifiers

De Morgan's Laws for Quantifiers

• De Morgan's laws for quantifiers are analogous to De Morgan's laws for propositional logic
• The first law states that the negation of a conjunction of two quantified statements is equivalent to the disjunction of their negations:
  • $\neg(\forall x P(x) \wedge \forall x Q(x)) \equiv \exists x \neg P(x) \vee \exists x \neg Q(x)$
• The second law states that the negation of a disjunction of two quantified statements is equivalent to the conjunction of their negations:
  • $\neg(\exists x P(x) \vee \exists x Q(x)) \equiv \forall x \neg P(x) \wedge \forall x \neg Q(x)$
• These laws allow for the simplification and manipulation of complex quantified statements

Contradictory and Equivalent Forms

• Contradictory forms are pairs of quantified statements that cannot both be true simultaneously
• For example, $\forall x P(x)$ and $\exists x \neg P(x)$ are contradictory because they assert opposite claims about the elements in the domain
• Equivalent forms are pairs of quantified statements that have the same truth value for all possible interpretations
• For instance, $\forall x (P(x) \rightarrow Q(x))$ is equivalent to $\exists x P(x) \rightarrow \exists x Q(x)$, as they both express the idea that if there exists an element satisfying $P$, then there must also exist an element satisfying $Q$
• Recognizing contradictory and equivalent forms helps in understanding the relationships between quantified statements and their logical implications