De Morgan's Laws
Visualizing De Morgan's Laws
!(a && b) → !a || !b
↑ ↑ ↑
NOT negate flip
distributes each AND
part to OR
!(a || b) → !a && !b
↑ ↑ ↑
NOT negate flip
distributes each OR
part to AND
Proof with truth tables
Applying De Morgan's Laws to code
Example 1: Negate a range check
java
// Original: NOT in range [1, 100]
!(x >= 1 && x <= 100)
// Apply De Morgan's: flip && to ||, negate each part
!(x >= 1) || !(x <= 100)
// Simplify the negations
x < 1 || x > 100
Example 2: Negate an OR condition
java
// Original: NOT (weekend)
!(day == 6 || day == 7)
// Apply De Morgan's: flip || to &&, negate each part
day != 6 && day != 7
Example 3: Negate a compound condition
java
// "NOT (old enough AND has permission)"
!(age >= 18 && hasPermission)
// De Morgan's:
age < 18 || !hasPermission
Negating comparison operators
java
!(x > 5) → x <= 5
!(x == 10) → x != 10
!(x <= 0) → x > 0
Step-by-step simplification
Step 1: Apply De Morgan's on the outer !
!(!(x > 0)) && !(y == 5)
Step 2: Double negation: !(!(x > 0)) → x > 0
x > 0 && !(y == 5)
Step 3: Negate the comparison
x > 0 && y != 5
Equivalent if-else structures
Pair 1: Negating the condition, swapping branches
java
// Version A
if (x > 0) {
System.out.println("positive");
} else {
System.out.println("non-positive");
}
// Version B (equivalent)
if (x <= 0) {
System.out.println("non-positive");
} else {
System.out.println("positive");
}
Pair 2: Combining conditions
java
// Version A
if (x > 0) {
if (y > 0) {
System.out.println("both positive");
}
}
// Version B (equivalent)
if (x > 0 && y > 0) {
System.out.println("both positive");
}
AP exam practice problems
Problem 1 Which is equivalent to `!(a > b && c != d)`?
- •
- •
- •
- •
Problem 2 Which is equivalent to `!(x == 5 || x == 10)`?
- •
- •
- •
- •
Problem 3 Simplify: `!(!(done) && count < 10)`
De Morgan's: !(!(done)) || !(count < 10)
Simplify: done || count >= 10
Complete example: Equivalent conditions
java
public class EquivalentDemo {
public static void main(String[] args) {
int temp = 72;
boolean raining = false;
// These two conditions are equivalent:
// Version 1: Direct
if (temp >= 60 && temp <= 85 && !raining) {
System.out.println("Nice weather!");
}
// Version 2: Negate and flip using De Morgan's
// !(nice weather) = too cold OR too hot OR raining
if (!(temp < 60 || temp > 85 || raining)) {
System.out.println("Nice weather!");
}
// Both print for temp=72, raining=false
}
}
AP Exam Tips
- •
- •
- •
- •
- •
- •