Comparing Boolean Expressions | AP CSA Unit 2 Study Guide

Getting Started

In programming, we often need to make decisions based on multiple conditions. This can lead to complex logical statements that are difficult to read and debug. This topic explores how different boolean expressions can be logically equivalent, allowing us to simplify and rewrite our code to be more efficient and understandable without changing its behavior.

What You Should Be Able to Do

Evaluate compound boolean expressions that use && (AND), || (OR), and ! (NOT).
Determine if two boolean expressions are logically equivalent for all possible inputs.
Apply De Morgan’s Laws to rewrite a negated boolean expression into an equivalent form.
Simplify negated relational expressions (e.g., !(x > 10)).
Use truth tables to verify the equivalence of boolean expressions.

Key Concepts & Java Implementation

The Core Idea

A boolean expression is any statement in Java that evaluates to either true or false. Often, we combine simple expressions using logical operators like && (AND) and || (OR) to form compound conditions.

Logical equivalence is a fundamental concept where two different-looking boolean expressions produce the exact same result for all possible values of their variables. For example, in plain English, the statement "It is not the case that the door is open AND the light is on" is logically the same as saying "The door is closed OR the light is off."

The primary tool for establishing this equivalence is a set of rules called De Morgan's Laws. These laws describe how to correctly distribute a negation operator (!) across a compound boolean expression. Understanding these laws allows you to simplify complex logic, making your if statements and loop conditions easier to reason about.

Syntax & Implementation

De Morgan's Laws provide a template for rewriting negated && and || expressions.

De Morgan's Laws Table

Original Expression	Equivalent Expression	Description
`!(A && B)`	`!A
`!(A		B)`

Here, A and B represent any valid boolean expression, such as x > 5 or isFinished.

Annotated Java Examples

The following two code blocks are functionally identical. The second version uses De Morgan's Laws to simplify the condition, which can be easier to read.


// Example 1: Original complex condition

int score = 75;

boolean isBonusActive = false;


// Check if the game is NOT over (score is positive AND bonus is not active)

if (!(score <= 0 || isBonusActive == true)) {

    System.out.println("Game continues...");

} else {

    System.out.println("Game over.");

}

// Output: Game continues...


// Example 2: Equivalent condition using De Morgan's Laws

int score = 75;

boolean isBonusActive = false;


// The original condition was !(A || B), where A is (score <= 0) and B is (isBonusActive == true).

// The equivalent is !A && !B.

// !A is !(score <= 0), which simplifies to (score > 0).

// !B is !(isBonusActive == true), which simplifies to (isBonusActive == false) or just !isBonusActive.

if (score > 0 && !isBonusActive) {

    System.out.println("Game continues...");

} else {

    System.out.println("Game over.");

}

// Output: Game continues...

Tracing & Analysis

To prove that two expressions are equivalent, we can use a truth table. A truth table systematically lists every possible combination of true/false values for the variables and shows the result of each expression. If the result columns are identical, the expressions are logically equivalent.

Execution Trace: Truth Table for !(A && B) vs. !A || !B

| A | B | A && B | !(A && B) | !A | !B | !A || !B | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | true | true | true | false | false | false | false | | true | false | false | true | false | true | true | | false | true | false | true | true | false | true | | false | false | false | true | true | true | true |

Analysis

As you can see, the result column for !(A && B) is identical to the result column for !A || !B. This provides a formal proof that they are interchangeable in any Java program. Applying De Morgan's Laws is not just a theoretical exercise; it is a practical skill for writing cleaner, more maintainable code by removing complex negations.

Java Syntax Quick-Reference

A compact reference for the logical and relational operators used in this topic.

&&: The logical AND operator. Returns true only if both operands are true.
||: The logical OR operator. Returns true if at least one operand is true.
!: The logical NOT operator. Inverts the boolean value of its operand ( true becomes false, false becomes true).
==: The equality operator. Returns true if two values are equal.
!=: The inequality operator. Returns true if two values are not equal. It is the direct equivalent of !(a == b).

Core Code Examples & Terminology

Boolean Expression: A piece of code that evaluates to a single true or false value. For example, x > 10 or isReady && hasTime.
Logical Equivalence: The property of two boolean expressions that evaluate to the same result (true or false) for all possible input values.
De Morgan's Laws: A pair of rules for transforming logical expressions that show how to distribute a negation over AND and OR operators.
Truth Table: A table that lists all possible combinations of inputs for a boolean expression and shows the computed output for each combination.
Core Snippet 1: Negating an AND
```
!(isLoggedIn && isAdmin)
```
This expression is logically equivalent to !isLoggedIn || !isAdmin.
Core Snippet 2: Negating an OR
```
!(isWeekend || isHoliday)
```
This expression is logically equivalent to !isWeekend && !isHoliday.
Core Snippet 3: Negating a Relational Operator
```
!(temperature > 90.0)
```
This expression is logically equivalent to temperature <= 90.0.

Core Skill Check

Code Tracing: What is the final value of message after this Java code runs: int x = 10; String message = "OK"; if (!(x > 5 && x < 20)) { message = "INVALID"; }?
- Answer: "OK"
Debugging: Identify the logical error in this attempted simplification: !(age < 18 || hasPermission) was rewritten as age > 18 && !hasPermission.
- Answer: The negation of age < 18 is age >= 18, not age > 18.
Application: Write a single line of Java code that declares a boolean variable isValid and initializes it with an expression that is logically equivalent to !(score < 0 || score > 100).
- Answer: boolean isValid = score >= 0 && score <= 100;

Common Misconceptions & Errors

Forgetting to Flip the Operator: A common mistake when applying De Morgan's laws is distributing the ! but forgetting to change && to || (or vice-versa). For example, incorrectly thinking !(A && B) is !A && !B.
Incorrectly Negating Relational Operators: The negation of > is <=, not <. Similarly, the negation of < is >=. Forgetting the "or equal to" part is a frequent source of bugs.
Confusing == and !=: The expression !(a == b) is always equivalent to a != b. Avoid writing the former, as the latter is much clearer.
Partial Distribution of Negation: The ! operator must be applied to every term inside the parentheses. !(A || B) is not !A || B.

Summary

Comparing and simplifying boolean expressions is a key skill for writing clear and correct conditional logic. Two expressions are logically equivalent if they produce the same outcome for all inputs. De Morgan's Laws provide the primary rules for this simplification, stating that !(A && B) is equivalent to !A || !B, and !(A || B) is equivalent to !A && !B. By applying these laws and correctly negating relational operators, you can transform complex, negated conditions into simpler, positive forms that make your code easier to read, debug, and maintain.

Comparing Boolean Expressions - AP Computer Science A Study Guide