Boolean Algebra

ACSL Boolean Algebra problems ask you to simplify expressions or find which input combinations make an expression true. This is one of the more rule-heavy topics, but the rules are consistent and learnable. Once you internalize them, simplification becomes almost mechanical.

The operators

Precedence (highest first): NOT, then AND, then XOR/XNOR, then OR

This means $A+B{C}^{\prime }$ is read as $A+(B\cdot (\text{NOT }C))$, not $((A+B)\cdot C{)}^{\prime }$.

The laws you need to memorize

These are your tools for simplification. Every step in an ACSL simplification problem uses one of these.

Identity and annihilator

$A+0=AA\cdot 1=A\text{(identity)}$ $A+1=1A\cdot 0=0\text{(annihilator)}$

Complement

$A+A^{\prime }=1A\cdot A^{\prime }=0$

Idempotent

$A+A=AA\cdot A=A$

Double negation

$(A^{\prime }{)}^{\prime }=A$

Commutative

$A+B=B+AA\cdot B=B\cdot A$

Associative

$A+(B+C)=(A+B)+C$ $A\cdot (B\cdot C)=(A\cdot B)\cdot C$

Distributive

$A\cdot (B+C)=AB+AC\text{(AND distributes over OR)}$ $A+BC=(A+B)(A+C)\text{(OR distributes over AND - less intuitive!)}$

Absorption

$A+AB=AA(A+B)=A$

This is the one students forget most often. It says: if $A$ is true, the whole expression is true regardless of $B$; if $A$ is false, $AB$ is false anyway.

DeMorgan’s Laws

$(A+B{)}^{\prime }=A^{\prime }\cdot B^{\prime }\text{(NOT of OR = AND of NOTs)}$ $(A\cdot B{)}^{\prime }=A^{\prime }+B^{\prime }\text{(NOT of AND = OR of NOTs)}$

These are the most important laws for ACSL problems. They let you push a NOT inside parentheses by flipping the operator and negating each term.

Simplification strategy

Here’s a systematic approach that works for most ACSL problems:

1. Apply DeMorgan’s to eliminate NOTs over groups
2. Expand using the distributive law
3. Look for complements ($A\cdot A^{\prime }=0$) and identities ($A+0=A$)
4. Apply absorption ($A+AB=A$)
5. Simplify remaining terms

Worked example

Simplify: $(A(A+B){)}^{\prime }\cdot (B^{\prime }+A^{\prime })$

Step 1 - Absorption inside the NOT: $A(A+B)=A$

Step 2 - Distribute:

Step 3 - Absorption: $A^{\prime }+A^{\prime }{B}^{\prime }=A^{\prime }$

$=A^{\prime }$

Answer: $A^{\prime }$ (or NOT A)

Worked example 2

Find all ordered pairs $(A,B)$ that make this true: $A^{\prime }(A+B)+A{B}^{\prime }$

Simplify first:

This is $A\oplus B$! It’s true when $A$ and $B$ are different.

True pairs: $(0,1)$ and $(1,0)$

Worked example 3 (3 variables)

Find all ordered triples $(A,B,C)$ that make this true: $AB+B{C}^{\prime }+A^{\prime }C$

This has 3 variables, so simplification is worth trying before resorting to an 8-row truth table. But this expression doesn’t simplify further - no terms share enough to combine. So use a truth table:

True for: (0,0,1), (0,1,0), (0,1,1), (1,1,0), (1,1,1) - 5 out of 8 combinations.

Tip: When you can’t simplify, don’t waste time trying. Go straight to the truth table.

Truth table approach

When simplification feels hard, or to verify your answer, use a truth table.

For 2 variables (A, B), there are 4 rows. For 3 variables, 8 rows.

Example: Verify that $A^{\prime }B+A{B}^{\prime }=A\oplus B$

Columns match. Verified.

When to use truth tables vs algebraic simplification:

• 2 variables (4 rows): truth table is fast, use it to verify
• 3 variables (8 rows): either approach works
• 4+ variables: algebraic is usually faster

Common mistakes

1. Wrong precedence. $A+BC$ is NOT $(A+B)C$. AND binds tighter than OR.
2. DeMorgan’s applied incorrectly. $(AB{)}^{\prime }=A^{\prime }+B^{\prime }$, not $A^{\prime }{B}^{\prime }$. You must flip the operator.
3. Forgetting absorption. If you end up with $X+XY$, simplify to $X$. Don’t stop too early.
4. Distributing NOT incorrectly. $(A+B{)}^{\prime }\ne A^{\prime }+B^{\prime }$. You need DeMorgan’s, not just distributing the NOT.

Contest strategy

• If the problem says “simplify,” use algebraic laws
• If it says “find all values,” simplify first, then evaluate (or use truth table directly)
• With 2 variables, truth tables take ~30 seconds and are foolproof
• Always write which law you’re applying at each step - this prevents errors
• Typical time: 60-90 seconds