Free preview

83 lessons

Mathematical Foundations for ML

Free preview

Mathematical Foundations for ML · 83 lessons

Build the maths foundations that make ML click

No surprise gaps

Actually remember it

Skip what you know

One subscription. All learning paths included.

Our content is best on a larger screen

Negation and De Morgan's laws

Negating simple statements

Explanation

Every statement has a negation - a new statement with the opposite truth value. If $P$ is true, its negation is false, and vice versa.

Negation

Definition

The negation of a statement $P$ , written $\neg P$ (read "not $P$ "), is true when $P$ is false and false when $P$ is true.

We often label a statement with a letter, for example $P$ : " $x > 3$ ", and write its negation as $\neg P$ : " $x \leq 3$ ".

This mirrors complements from sets: just as $A^c$ contains everything not in $A$ , the negation $\neg P$ captures the opposite of $P$ .

Negating mathematical statements takes a little care. The negation must capture every value the original misses, with no overlap and no gaps. Here are some common patterns:

Statement	Negation	Why
$x > 3$	$x \leq 3$	Flips direction and swaps strict for non-strict. Using $x < 3$ would lose $x = 3$ .
$x \leq 10$	$x > 10$	Same rule: flip direction, swap non-strict for strict.
$x \in A$	$x \notin A$	Swap $\in$ and $\notin$ .
$A \subseteq B$	$A \not\subseteq B$	At least one element of $A$ is not in $B$ .
$n$ is even	$n$ is odd	Add or remove "not" (equivalently, " $n$ is not even").

Key Point

The original statement and its negation form a partition: exactly one of $P$ and $\neg P$ is true for any given value. There is no middle ground.

Example

Negate each of the following statements and determine the truth value of both the original and its negation.

$P$ : $x > 5$ where $x = 3$
$Q$ : $n \in \mathbb{Z}$ where $n = 4.7$
$R$ : $n$ is a perfect square where $n = 9$

Solution

Statement $P$ : $x > 5$

The negation flips the inequality and swaps strict for non-strict:

\neg P\text{: } x \leq 5

With $x = 3$ : the original $P$ is false ( $3$ is not greater than $5$ ), and the negation $\neg P$ is true ( $3 \leq 5$ ). The truth values are opposite, as expected.

Statement $Q$ : $n \in \mathbb{Z}$

The negation swaps membership:

\neg Q\text{: } n \notin \mathbb{Z}

With $n = 4.7$ : the original $Q$ is false ( $4.7$ is not an integer), and the negation $\neg Q$ is true ( $4.7 \notin \mathbb{Z}$ ).

Statement $R$ : $n$ is a perfect square

The negation adds "not":

\neg R\text{: } n \text{ is not a perfect square}

With $n = 9$ : the original $R$ is true ( $9 = 3^2$ ), so the negation $\neg R$ is false.

In every case, the original and its negation have opposite truth values - exactly one is true.

Practice questions

4 questions

Let $P$ : $x < 7$ . What is $\neg P$ ?

Select the correct answer:

$\neg P$ : $x > 7$

$\neg P$ : $x \geq 7$

$\neg P$ : $x \leq 7$

$\neg P$ : $x = 7$

+ 3 more questions

Negating "and" statements

Explanation

We can negate individual statements. What about compound ones? Let's start with conjunctions - statements joined by "and."

Consider $P \wedge Q$ . What does it mean for this to be false?

Recall that $P \wedge Q$ requires both parts to hold. So it fails whenever at least one part fails - that is, when $P$ is false or $Q$ is false. The negation of $P \wedge Q$ is therefore $\neg P$ or $\neg Q$ .

Negating a conjunction (De Morgan's first law)

Definition

The negation of $P \wedge Q$ is:

\neg(P \wedge Q) = \neg P \vee \neg Q

Negate each part and change "and" to "or."

A common mistake

Gotcha

A tempting but wrong negation of $P \wedge Q$ is $\neg P$ and $\neg Q$ . This says both parts fail, but the original is false as soon as one part fails. Forgetting to swap the connective is the most common error.

This is one half of what are called De Morgan's laws - we will meet the other half next.

Example

Negate the statement: $x$ is positive and $x$ is an integer. Then verify your negation for $x = -3$ , $x = 4$ , and $x = 0.5$ .

Solution

Step 1: Identify $P$ and $Q$ .

$P$ : $x$ is positive
$Q$ : $x$ is an integer

The original statement is $P \wedge Q$ .

Step 2: Negate each part.

$\neg P$ : $x$ is not positive, i.e. $x \leq 0$
$\neg Q$ : $x$ is not an integer, i.e. $x \notin \mathbb{Z}$

Step 3: Apply De Morgan's first law - swap "and" for "or":

\neg(P \wedge Q) = \neg P \vee \neg Q

So the negation is: $x \leq 0$ or $x \notin \mathbb{Z}$ .

Verification:

$x = -3$ : original is false, negation is true. Opposite, as expected.
$x = 4$ : original is true, negation is false. Opposite.
$x = 0.5$ : original is false, negation is true. Opposite.

Full working for each value

Details

$x = -3$ :

Original: $P \wedge Q$ = $-3$ is positive and $-3$ is an integer. The first part is false ( $-3$ is not positive), so the conjunction is false.
Negation: $\neg P \vee \neg Q$ = $-3 \leq 0$ or $-3 \notin \mathbb{Z}$ . The first part is true ( $-3 \leq 0$ ), so the disjunction is true.

$x = 4$ :

Original: $P \wedge Q$ = $4$ is positive and $4$ is an integer. Both parts are true, so the conjunction is true.
Negation: $\neg P \vee \neg Q$ = $4 \leq 0$ or $4 \notin \mathbb{Z}$ . Neither part is true, so the disjunction is false.

$x = 0.5$ :

Original: $P \wedge Q$ = $0.5$ is positive and $0.5$ is an integer. The second part is false ( $0.5 \notin \mathbb{Z}$ ), so the conjunction is false.
Negation: $\neg P \vee \neg Q$ = $0.5 \leq 0$ or $0.5 \notin \mathbb{Z}$ . The second part is true ( $0.5 \notin \mathbb{Z}$ ), so the disjunction is true.

Practice questions

4 questions

What is the negation of $x > 0$ and $x < 10$ ?

Select the correct answer:

$x \leq 0$ and $x \geq 10$

$x \leq 0$ or $x \geq 10$

$x > 0$ or $x < 10$

$x < 0$ or $x > 10$

+ 3 more questions

Negating "or" statements

Explanation

We have seen that negating $P \wedge Q$ swaps the connective to "or." Now consider the other direction: what does it mean for $P \vee Q$ to be false?

Recall that $P \vee Q$ requires at least one part to hold. So it fails only when neither holds - when $P$ is false and $Q$ is false. The negation of $P \vee Q$ is therefore $\neg P$ and $\neg Q$ .

Negating a disjunction (De Morgan's second law)

Definition

The negation of $P \vee Q$ is:

\neg(P \vee Q) = \neg P \wedge \neg Q

Negate each part and change "or" to "and."

Together with the rule for negating "and" statements, we have a pair known as De Morgan's laws: negation always swaps the connective. "And" becomes "or", and "or" becomes "and."

Connection to set complements

Details

De Morgan's laws appear in both sets and logic. The pattern is the same: the "opposite" operation always swaps the connective.

Sets	Statements
$(A \cap B)^c = A^c \cup B^c$	$\neg(P \wedge Q) = \neg P \vee \neg Q$
$(A \cup B)^c = A^c \cap B^c$	$\neg(P \vee Q) = \neg P \wedge \neg Q$
Complement swaps $\cap$ and $\cup$	Negation swaps $\wedge$ and $\vee$

Example

Negate the statement: $n$ is even or $n > 20$ . Then verify your negation for $n = 15$ , $n = 22$ , and $n = 3$ .

Solution

Step 1: Identify $P$ and $Q$ .

$P$ : $n$ is even
$Q$ : $n > 20$

The original statement is $P \vee Q$ .

Step 2: Negate each part.

$\neg P$ : $n$ is odd
$\neg Q$ : $n \leq 20$

Step 3: Apply De Morgan's second law - swap "or" for "and":

\neg(P \vee Q) = \neg P \wedge \neg Q

So the negation is: $n$ is odd and $n \leq 20$ .

Verification:

$n = 15$ : original is false, negation is true. Opposite.
$n = 22$ : original is true, negation is false. Opposite.
$n = 3$ : original is false, negation is true. Opposite.

Full working for each value

Details

$n = 15$ :

Original: $P \vee Q$ = $15$ is even or $15 > 20$ . Neither part is true, so the disjunction is false.
Negation: $\neg P \wedge \neg Q$ = $15$ is odd and $15 \leq 20$ . Both parts are true, so the conjunction is true.

$n = 22$ :

Original: $P \vee Q$ = $22$ is even or $22 > 20$ . Both parts are true, so the disjunction is true.
Negation: $\neg P \wedge \neg Q$ = $22$ is odd and $22 \leq 20$ . The first part is false ( $22$ is even), so the conjunction is false.

$n = 3$ :

Original: $P \vee Q$ = $3$ is even or $3 > 20$ . Neither part is true, so the disjunction is false.
Negation: $\neg P \wedge \neg Q$ = $3$ is odd and $3 \leq 20$ . Both parts are true, so the conjunction is true.

Practice questions

4 questions

What is the negation of $n$ is prime or $n$ is odd?

Select the correct answer:

$n$ is not prime and $n$ is not odd.

$n$ is not prime or $n$ is not odd.

$n$ is prime and $n$ is even.

$n$ is not prime and $n$ is odd.

+ 3 more questions

Part of

Logic

See all 12 lessons, what comes first, and what this unlocks.