01 / 21
T F F T

Comparing
Boolean Expressions

Learn how to determine when two Boolean expressions are logically equivalent, use truth tables to prove it, and apply De Morgan's Laws to simplify complex conditions.

AP Computer Science A

What Is a Boolean Expression?

A Boolean expression is any expression in Java that evaluates to exactly one of two values: true or false. They are the building blocks of every decision your program makes.

Relational
Comparisons like \(<), \(>), \(==), \(\ne), \(\le), \(\ge)
Logical
Compound operators: \(&&\) (AND), \(||\) (OR), \(!\) (NOT)
Combined
Nesting relational inside logical: \((x > 5) \&\& (y < 10)\)

What Does Equivalent Mean?

Two Boolean expressions are logically equivalent if they produce the same result for every possible combination of input values. They may look different in code, but they behave identically.

// These two expressions are equivalent: boolean a = !(x > 5); // \(!(x > 5)\) boolean b = (x <= 5); // \((x \le 5)\) // a == b for ALL values of x

Why Compare Them?

1
Simplify code: Replace a complex condition with a shorter, clearer equivalent.
2
Debug logic errors: Verify that your refactored condition still does the same thing.
3
Ace the AP exam: The College Board frequently asks you to identify equivalent expressions.
4
Write negations: Correctly negate a condition (e.g., flipping an if to an else).

Truth Tables: The Core Tool

A truth table lists every possible combination of inputs and the resulting output. If two expressions have identical output columns, they are equivalent.

\(p\) \(q\) \(p \&\& q\) \(!(!p \|\| !q)\)
truetruetruetrue
truefalsefalsefalse
falsetruefalsefalse
falsefalsefalsefalse

De Morgan's Laws

De Morgan's Laws are the most important equivalences on the AP exam. They tell you how NOT distributes over AND and OR:

Law 1
\(!(p \&\& q)\) is equivalent to \(!p \|\| !q\)
Law 2
\(!(p \|\| q)\) is equivalent to \(!p \&\& !q\)

De Morgan's Visualized

Law 1
\(!(p \&\& q)\)
\(=\)
\(!p \|\| !q\)
\(&&\) becomes \(||\)
Law 2
\(!(p \|\| q)\)
\(=\)
\(!p \&\& !q\)
\(||\) becomes \(&&\)
 Pattern: Push NOT in Negate each operand + flip the operator

Negating Relational Operators

When NOT is applied to a simple comparison, you can replace it with the opposite operator. No need for De Morgan's here:

Original Negation
\(!(a == b)\)\(a \ne b\)
\(!(a \ne b)\)\(a == b\)
\(!(a < b)\)\(a \ge b\)
\(!(a > b)\)\(a \le b\)
\(!(a \le b)\)\(a > b\)
\(!(a \ge b)\)\(a < b\)

== vs .equals()

When comparing objects (especially Strings), == and .equals() are not equivalent. This is the most common source of Boolean bugs in Java.

== (Reference)
Checks if two variables point to the same object in memory. For primitives, compares values directly.
.equals() (Value)
Checks if two objects have the same content. The correct way to compare Strings and other objects.
String s1 = new String("hello"); String s2 = new String("hello"); s1 == s2 // false (different objects) s1.equals(s2) // true (same content)

How to Compare Step by Step

1
Identify variables: List all Boolean variables or sub-expressions (p, q, etc.).
2
Build a truth table: Create rows for every combination (\(2^n\) rows for \(n\) variables).
3
Evaluate both expressions: Fill in the output column for each expression on every row.
4
Compare columns: If every row matches, the expressions are equivalent. If any row differs, they are not.

Example 1: Applying De Morgan's

Simplify: \(!(x > 3 \&\& y < 10)\)

1
Apply De Morgan's Law 1: NOT over AND becomes OR. Negate each operand.
2
Negate \(!(x > 3)\): becomes \(x \le 3\)
3
Negate \(!(y < 10)\): becomes \(y \ge 10\)
4
Combine: \(x \le 3 \|\| y \ge 10\)
// Original !(x > 3 && y < 10) // Simplified (equivalent) x <= 3 || y >= 10

Example 2: Truth Table Proof

Are these equivalent? \(!(a \|\| b)\) and \(!a \&\& !b\)

\(a\) \(b\) \(!(a \|\| b)\) \(!a \&\& !b\)
TTFF
TFFF
FTFF
FFTT

Example 3: Non-Equivalent Trap

Are these equivalent? \(!(a \&\& b)\) and \(!a \&\& !b\)

\(a\) \(b\) \(!(a \&\& b)\) \(!a \&\& !b\)
TTFF
TFTF
FTTF
FFTT

Short-Circuit Evaluation

Java uses short-circuit evaluation for \(&&\) and \(||\). This affects behavior but not logical equivalence (when expressions have no side effects).

\(&&\) (AND)
If the left side is false, the right side is never evaluated. Result is already false.
\(||\) (OR)
If the left side is true, the right side is never evaluated. Result is already true.
// Safe: short-circuit prevents NullPointerException if (str != null && str.length() > 0) { // str.length() only runs if str != null }

Common Mistakes

✕ Distributing NOT incorrectly
Writing \(!(a \&\& b)\) as \(!a \&\& !b\) instead of \(!a \|\| !b\). You must also flip the operator.
✕ Forgetting boundary values
Writing \(!(x < 5)\) as \(x > 5\) instead of \(x \ge 5\). The negation of strict is non-strict.
✕ Using == for Strings
Comparing String objects with == checks reference, not content. Use .equals() for value comparison.

Equivalence Summary

Expression Equivalent Form Rule
\(!(p \&\& q)\)\(!p \|\| !q\)De Morgan's 1
\(!(p \|\| q)\)\(!p \&\& !q\)De Morgan's 2
\(!(a < b)\)\(a \ge b\)Negate relational
\(!(a == b)\)\(a \ne b\)Negate equality
\(!!p\)\(p\)Double negation
\(p \&\& \text{true}\)\(p\)Identity
\(p \|\| \text{false}\)\(p\)Identity

Question 1 of 5

Which expression is equivalent to \(!(x > 10 \&\& y < 5)\)?

Question 2 of 5

What is the result of \(!(\text{false} \|\| \text{true})\)?

Question 3 of 5

Which pair of expressions is NOT equivalent?

Question 4 of 5

Given int x = 7, what does \(!(x \ge 7 \|\| x < 3)\) evaluate to?

Question 5 of 5

Which expression is equivalent to \(!(a \ne b)\)?