Negation of conjunction (and)
Goal: negate a statement of the form P ∧ Q.
Key identity (De Morgan):
How to form it:
Negate each substatement: ¬P, ¬Q
Replace the connective: replace ∧ with ∨
Result: ¬(P ∧ Q) is equivalent to (¬P) ∨ (¬Q)
Example from lecture:
Original: "We are in class and paying attention." (P ∧ Q where P = We are in class, Q = We are paying attention)
Negation: "We are not in class or we are not paying attention." (¬P ∨ ¬Q)
Truth table intuition (P ∧ Q): true only when both P and Q are true; thus ¬(P ∧ Q) is true in all other cases.
P Q | P ∧ Q | ¬(P ∧ Q)
T T | T | F
T F | F | T
F T | F | T
F F | F | T
Related equivalence: the same can be expressed as ¬(P ∧ Q) ≡ (¬P) ∨ (¬Q).
Negation of disjunction (or)
Goal: negate a statement of the form P ∨ Q.
Key identity (De Morgan):
How to form it:
Negate each substatement: ¬P, ¬Q
Replace the connective: replace ∨ with ∧
Result: ¬(P ∨ Q) is equivalent to (¬P) ∧ (¬Q)
Example from lecture:
Original: "We are in class or paying attention." (P ∨ Q)
Negation: "We are not in class and we are not paying attention." (¬P ∧ ¬Q)
Truth table intuition (P ∨ Q): true if at least one of P, Q is true; thus ¬(P ∨ Q) is true only when both are false.
P Q | P ∨ Q | ¬(P ∨ Q)
T T | T | F
T F | T | F
F T | T | F
F F | F | T
Caution on language:
English uses or in ways that can be inclusive or exclusive; in logic we treat ∨ as inclusive unless stated otherwise. The term "nor" is not the same as ¬(P ∨ Q) in all contexts; it can be used to express a different negation in everyday language.
Negation of a conditional (If P then Q)
Goal: negate a statement of the form P → Q.
Key identity:
How to form it:
You negate the conclusion Q, keep the hypothesis P, and form a conjunction: P ∧ ¬Q.
Truth table intuition (P → Q): false only when P is true and Q is false; otherwise true. Its negation is true exactly when P is true and Q is false.
P Q | P → Q | ¬(P → Q)
T T | T | F
T F | F | T
F T | T | F
F F | T | F
Practical examples:
Example 1: If the lights are on, there is electricity.
Negation: The lights are on and there is no electricity.
Example 2: If the team shows up, the game is played.
Negation: The team shows up and the game is not played.
Important distinction:
Converse: Q → P
Inverse: ¬P → ¬Q
Neither converse nor inverse are generally equivalent to the original P → Q; the contrapositive ¬Q → ¬P is logically equivalent to the original.
Contrapositive (for a conditional)
Given P → Q, its contrapositive is ¬Q → ¬P.
This is logically equivalent to the original statement.
If the original conclusion has a compound form, apply negation to the components and form the contrapositive accordingly:
For P → (Q ∨ R), the contrapositive is ¬(Q ∨ R) → ¬P, which simplifies to (¬Q ∧ ¬R) → ¬P.
Worked example from lecture:
Original: If x^2 = 16, then x = 4 or x = -4 (P → (Q ∨ R))
Contrapositive: ¬(Q ∨ R) → ¬P ⇔ (¬Q ∧ ¬R) → ¬P
In concrete terms: If x ≠ 4 and x ≠ -4, then x^2 ≠ 16.
Practical note:
You can derive the contrapositive by either applying the general rule directly or by reasoned substitution using the specific substatements; both lead to the same result.
Negation of universal and existential statements
Overview:
Universal statement: ∀x ∈ Domain, P(x) (all elements have property P).
Existential statement: ∃x ∈ Domain, P(x) (there exists at least one element with P).
Negation rules:
Negation of a universal statement: ¬(∀x P(x)) ≡ ∃x ¬P(x)
Everyday phrasing: "There exists some x such that P(x) is false." i.e., some element does not have the property.
Negation of an existential statement: ¬(∃x P(x)) ≡ ∀x ¬P(x)
Everyday phrasing: "No x has property P" or "All x do not have P."
Examples from lecture:
Universal examples:
All dogs are good. Negation: Some dogs are not good. (There exists a dog that is not good.)
No cats are good. (Equivalently, All cats are not good.)
All students have a campus-wide ID. Negation: There exists a student without a campus-wide ID.
Existential examples:
Some people like cats. Negation: No people like cats (Nobody likes cats).
There exists at least one CS major. Negation: There are no CS majors.
Mixed quantified example (from lecture):
Original: For all real numbers x, there exists a real number y such that x·y = 1.
Negation: There exists a real number x such that for all real numbers y, x·y ≠ 1.
Alternate form of the same negation: There exists x such that there does not exist y with x·y = 1.
Intuition: The negation looks for a counterexample: an x with no corresponding y that yields 1 when multiplied by x.
Additional note on “some” vs “at least one”:
In mathematics, "some" is read as “at least one.”
Practical use:
To negate a universal statement, switch to an existential one and negate the predicate.
To negate an existential statement, switch to a universal one and negate the predicate.
Quick references and tips
Core De Morgan identities:
Negation of a conditional:
Contrapositive:
If then the contrapositive is (logically equivalent to the original).
Universal vs existential negations:
Language notes:
In logic, ∨ is inclusive OR unless stated otherwise; XOR would be a more specific operator: .
Verbal phrasing may differ, but the formal equivalents above are what count for proofs and problem solving.
Practice prompts (from the lecture context)
Given P: "We are in class" and Q: "We are paying attention": write the negation of P ∧ Q and interpret it in words.
Given P: "We are in class" and Q: "We are paying attention": write the negation of P ∨ Q and interpret it in words.
For P → Q with P: "the lights are on" and Q: "there is electricity": write the negation in words and in symbolic form; explain what scenario would falsify the original conditional.
For the statement: For all real numbers x, there exists a real number y such that x·y = 1, write one form of its negation and explain why that disproof works (including the special case x = 0 as intuitive support).
Compare and contrast the contrapositive with the converse and inverse for a simple conditional, and explain which one is logically equivalent to the original.
Connections to broader topics
These negation rules underpin much of mathematical logic, proofs, and computer science correctness arguments.
They connect to the process of solving equations and inequalities by identifying counterexamples (existence of a counterexample negates a universal claim).
The universal/existential framework helps formalize statements about domains, functions, and properties in mathematics, as illustrated by the f(x) = x example and the domain discussion mentioned in the lecture.