Key Boolean Logic Operations

Why This Matters

Boolean logic is the foundation of every decision your program makes. When you write an IF statement, combine conditions with AND or OR, or check whether a user meets multiple criteria, you're using Boolean operations. The AP exam tests whether you can trace through conditional logic, predict program output when multiple conditions combine, and recognize equivalent expressions in both multiple-choice questions and the Create Performance Task.

You're being tested on more than just knowing that AND requires both inputs to be true. The exam expects you to understand how to negate compound conditions and when two different-looking expressions actually do the same thing. Don't just memorize truth tables. Know how each operation behaves in real code and when to use one over another.

---

The Core Three: AND, OR, and NOT

These three operations form the backbone of all conditional logic in programming. Every complex Boolean expression on the AP exam can be broken down into combinations of these.

AND Operation

• Returns true only when ALL conditions are true. If any input is false, the entire expression evaluates to false.
• In AP pseudocode, this is written as AND. Use it whenever multiple criteria must all be satisfied. For example, checking if a test score is in a range: score >= 0 AND score <= 100.
• Short-circuit evaluation means the computer won't check the second condition if the first is already false. This matters when the second condition could cause an error, like dividing by zero: x ≠ 0 AND (10/x > 2) is safe because if x is 0, the division never runs.

OR Operation

• Returns true when AT LEAST ONE condition is true. It only evaluates to false when every input is false.
• Use OR when meeting any single criterion is enough. For example, checking if a user qualifies for a discount: isStudent OR isSenior.
• Short-circuit evaluation skips the second condition if the first is already true, since the result is guaranteed to be true regardless.

NOT Operation

• Inverts a single Boolean value. True becomes false, false becomes true.
• When placed before parentheses, it applies to the entire expression inside: NOT(A AND B) negates the whole compound condition, not just A.
• NOT is essential for De Morgan's Laws, which you'll need when simplifying or rewriting negated expressions (covered below).

---

Compound Logic: XOR and Negated Gates

These operations build on the core three to handle special cases. XOR appears occasionally on the exam, and understanding how negation combines with AND/OR is critical for expression simplification.

XOR (Exclusive OR) Operation

• Returns true when the inputs are DIFFERENT. Exactly one input must be true, not both and not neither.
• The key difference from regular OR: when both inputs are true, OR returns true but XOR returns false. Think of it as "one or the other, but not both."
• XOR is useful for toggle scenarios. For example, a light switch system where flipping either switch changes the light's state, but flipping both puts it back where it started.

NAND (NOT AND) Operation

• Returns false ONLY when both inputs are true. It's the exact opposite of AND.
• Equivalent to writing NOT(A AND B). It outputs true for every input combination except $(1, 1)$.
• NAND is called a universal gate because any Boolean function can be built using only NAND operations. This matters more in circuit design than on the AP CSP exam, but it's good to know the concept.

NOR (NOT OR) Operation

• Returns true ONLY when both inputs are false. It's the exact opposite of OR.
• Equivalent to writing NOT(A OR B). It outputs true only for the $(0, 0)$ input combination.
• NOR is also a universal gate, just like NAND.

---

Tools for Analysis and Simplification

These techniques help you verify Boolean expressions, prove equivalence, and simplify complex conditions. The AP exam tests these skills when you need to trace code or identify equivalent program segments.

Truth Tables

A truth table lists every possible input combination alongside the output for a given expression. For an expression with $n$ variables, you'll have $2^n$ rows.

Building a truth table (step by step):

1. List all variables as column headers, then add a column for the full expression.
2. Fill in every possible combination of true/false for the variables. With 2 variables, that's 4 rows; with 3, it's 8.
3. Evaluate the expression for each row, working from the innermost operations outward.
4. To prove two expressions are equivalent, build tables for both and confirm every row matches.

For example, here's the truth table for A AND B:

Boolean Expressions and Simplification

Boolean expressions combine variables using AND, OR, and NOT to represent complex conditions in a single statement. Simplification reduces complexity while preserving the same behavior, which leads to more readable code.

A few useful identities to know:

• $A \text{ AND true} = A$ (AND with true changes nothing)
• $A \text{ OR false} = A$ (OR with false changes nothing)
• $A \text{ AND false} = \text{false}$ (AND with false is always false)
• $A \text{ OR true} = \text{true}$ (OR with true is always true)
• $\text{NOT}(\text{NOT } A) = A$ (double negation cancels out)

De Morgan's Laws

These two laws tell you how to distribute a NOT across a compound condition. They come up constantly on the exam.

• First law: NOT(A AND B) equals (NOT A) OR (NOT B). Negating an AND flips it to OR and negates each part.
• Second law: NOT(A OR B) equals (NOT A) AND (NOT B). Negating an OR flips it to AND and negates each part.

The pattern: when you push a NOT inward, the operator flips (AND becomes OR, OR becomes AND) and each individual condition gets negated.

Example: NOT(score >= 70 AND attendance >= 80) becomes score < 70 OR attendance < 80. Notice how AND flipped to OR, and each comparison flipped to its opposite.

Logical Equivalence

Two expressions are logically equivalent when they produce identical truth values for every possible input combination. The exam tests this by showing code segments and asking which produces the same output, requiring you to recognize transformed expressions.

You can prove equivalence using truth tables, algebraic manipulation, or known identities like De Morgan's Laws and double negation. When in doubt on the exam, pick a few test values and plug them into both expressions. If any value produces different results, they're not equivalent.

---

Quick Reference Table

---

Self-Check Questions

1. If x = 5 and y = 10, what does (x > 3) AND (y < 8) evaluate to, and why does short-circuit evaluation NOT skip the second condition here?

2. Which two operations are universal gates, and what property makes them "universal"?

3. Using De Morgan's Laws, rewrite NOT(score >= 70 AND attendance >= 80) as an equivalent expression without the outer NOT.

4. Compare AND and XOR: for which input combination do they produce different outputs, and why does this matter when checking conditions?

5. An FRQ shows two code segments: one uses NOT(A OR B) and the other uses (NOT A) AND (NOT B). How would you demonstrate these are logically equivalent using a truth table?