Boolean Algebra

**Boolean algebra** is a set of **laws** for rewriting Boolean expressions. Each law says that two expressions are **equivalent**: they have the same truth value for every input, so you may always replace one with the other. With the laws you can **simplify** an expression without building a new truth table every time. We write 1 for true and 0 for false (the interactive truth tables use 1 and 0 too). Engineers often write $A \cdot B$ for $A \land B$, $A + B$ for $A \lor B$ and $\overline{A}$ for $\neg A$: these mean exactly the same. In this lesson we use $\land$, $\lor$ and $\neg$. **The laws** ($A$, $B$ and $C$ are Boolean variables): | Law | AND form | OR form | |:---|:---:|:---:| | Identity | $A \land 1 = A$ | $A \lor 0 = A$ | | Null (domination) | $A \land 0 = 0$ | $A \lor 1 = 1$ | | Idempotent | $A \land A = A$ | $A \lor A = A$ | | Complement | $A \land \neg A = 0$ | $A \lor \neg A = 1$ | | Double negation | $\neg\neg A = A$ | (only one form) | | Commutative | $A \land B = B \land A$ | $A \lor B = B \lor A$ | | Associative | $(A \land B) \land C = A \land (B \land C)$ | $(A \lor B) \lor C = A \lor (B \lor C)$ | | Distributive | $A \land (B \lor C) = (A \land B) \lor (A \land C)$ | $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ | | Absorption | $A \land (A \lor B) = A$ | $A \lor (A \land B) = A$ | | De Morgan | $\neg(A \land B) = \neg A \lor \neg B$ | $\neg(A \lor B) = \neg A \land \neg B$ | Notice the pattern: swap $\land$ with $\lor$ and 0 with 1 in one column and you get the other column. This is called **duality**. **Simplifying step by step:** use one law per step and name it. Then check the result with a truth table: if the final columns match in every row, the simplification is correct.

Identity and Null Laws

Simplify $(A \land 1) \lor (B \land 0)$.

Use the identity law on the first bracket: $A \land 1 = A$, because AND with true changes nothing = $A \lor (B \land 0)$

Use the null law on the second bracket: $B \land 0 = 0$, because AND with false is always false = $A \lor 0$

Use the identity law again: $A \lor 0 = A$, because OR with false changes nothing = $A$

Answer: $(A \land 1) \lor (B \land 0) = A$. The value of $B$ does not matter at all.

Proving the Absorption Law

Show with other laws that $A \lor (A \land B) = A$.

Write $A$ as $A \land 1$ (identity law): $A \lor (A \land B) = (A \land 1) \lor (A \land B)$ = Both brackets start with $A$

Factor out $A$ (distributive law, read from right to left): $(A \land 1) \lor (A \land B) = A \land (1 \lor B)$ = $A \land (1 \lor B)$

Use the commutative and null laws: $1 \lor B = B \lor 1 = 1$ = $A \land 1$

Use the identity law: $A \land 1 = A$ = $A$

Answer: $A \lor (A \land B) = A$. In words: if $A$ is true the whole OR is true, and if $A$ is false then $A \land B$ is false too. Either way the result equals $A$.

De Morgan and Double Negation

Simplify $\neg(\neg A \land B)$ and check the result with a truth table.

Apply De Morgan's law: The NOT of an AND becomes an OR of the NOTs: $\neg(\neg A \land B) = \neg\neg A \lor \neg B$ = $\neg\neg A \lor \neg B$

Use double negation: $\neg\neg A = A$ = $A \lor \neg B$

Build the column of the original: Rows $(A, B)$ = 00, 01, 10, 11: $\neg A \land B$ is 0, 1, 0, 0, so $\neg(\neg A \land B)$ is 1, 0, 1, 1 = 1, 0, 1, 1

Build the column of the result: $\neg B$ is 1, 0, 1, 0, so $A \lor \neg B$ is 1, 0, 1, 1 = Same column in every row

Answer: $\neg(\neg A \land B) = A \lor \neg B$. The two columns match in all 4 rows, so the simplification is correct.

Factoring and the Complement Law

Simplify $(A \land B) \lor (A \land \neg B)$ and check it with a truth table.

Factor out $A$ (distributive law): $(A \land B) \lor (A \land \neg B) = A \land (B \lor \neg B)$ = $A \land (B \lor \neg B)$

Use the complement law: $B \lor \neg B = 1$, because $B$ is either true or false = $A \land 1$

Use the identity law: $A \land 1 = A$ = $A$

Check with a truth table: Rows $(A, B)$ = 00, 01, 10, 11: $A \land B$ is 0, 0, 0, 1 and $A \land \neg B$ is 0, 0, 1, 0, so the OR is 0, 0, 1, 1 = Same as column $A$: 0, 0, 1, 1

Answer: $(A \land B) \lor (A \land \neg B) = A$. A circuit with 4 gates (two AND, one NOT, one OR) becomes a single wire.

Fewer Gates in a Circuit

A circuit computes $\neg(A \lor B) \lor (\neg A \land B)$. Simplify it and count the gates saved (one gate for each $\land$, $\lor$ and $\neg$).

Count the gates of the original: Operators: $\neg$ and $\lor$ in the first part, $\neg$ and $\land$ in the second part, and the $\lor$ in the middle = 5 gates

Apply De Morgan's law to the first part: $\neg(A \lor B) = \neg A \land \neg B$ = $(\neg A \land \neg B) \lor (\neg A \land B)$

Factor out $\neg A$ (distributive law): $(\neg A \land \neg B) \lor (\neg A \land B) = \neg A \land (\neg B \lor B)$ = $\neg A \land (\neg B \lor B)$

Use the complement and identity laws: $\neg B \lor B = 1$ and $\neg A \land 1 = \neg A$ = $\neg A$

Count the gates again: $\neg A$ needs a single NOT gate: $5 - 1 = 4$ = 4 gates saved

Answer: The circuit is equivalent to $\neg A$: one NOT gate instead of 5 gates. Check: the original is true exactly in rows 00 and 01, which are the rows where $A = 0$.

Every $\land$, $\lor$ and $\neg$ in an expression becomes a **logic gate** in a circuit. A shorter expression means fewer gates, and fewer gates mean a chip that is cheaper, smaller, faster and uses less power. - **Electronics**: a processor contains billions of gates, so saving one gate in a circuit that is copied a million times saves a million gates - **Programming**: a condition like NOT (weekend OR holiday) can be rewritten as (NOT weekend) AND (NOT holiday), which is often easier to read and test - **Search and databases**: a filter such as math OR (math AND logic) gives exactly the same results as just math - **Proofs**: the laws let you prove that two circuits or two conditions do the same job without trying every input In the lesson Truth Tables you checked equivalences row by row, and in the lesson Logic Gates you built circuits. Boolean algebra connects the two: it turns a big circuit into a small one, and a truth table confirms that nothing changed.

Mistake: Writing $\neg(A \land B) = \neg A \land \neg B$

Why: De Morgan's law flips the operator as well as the variables. Test $A = 1$, $B = 0$: the left side is $\neg 0 = 1$, the right side is $0 \land 1 = 0$.

Correct: Break the bar and change the sign: $\neg(A \land B) = \neg A \lor \neg B$ and $\neg(A \lor B) = \neg A \land \neg B$.

Mistake: Using rules of ordinary algebra, such as $A \lor A = 2A$ or $A \land A = A^2$

Why: Boolean variables are only 0 or 1, and $1 \lor 1$ is 1, not 2. Repeating a variable adds nothing new.

Correct: Use the idempotent law: $A \lor A = A$ and $A \land A = A$.

Mistake: Reading $A \lor B \land C$ as $(A \lor B) \land C$

Why: AND is evaluated before OR, just like multiplication before addition. With $A = 1$, $B = 0$, $C = 0$ the correct value is $1 \lor 0 = 1$, but the wrong reading gives $1 \land 0 = 0$.

Correct: Add the brackets before you apply a law: $A \lor B \land C = A \lor (B \land C)$.

Mistake: Using the complement law on two different variables, as in $A \land \neg B = 0$

Why: The complement law only works for a variable and its own negation. With $A = 1$, $B = 0$: $A \land \neg B = 1 \land 1 = 1$, not 0.

Correct: Look for the same letter: $A \land \neg A = 0$ and $B \lor \neg B = 1$, but $A \land \neg B$ cannot be simplified.

Designing Cheaper Chips

Chip designers simplify every circuit with Boolean algebra before it is built, because each gate costs space, power and money.

A circuit for $(A \land B) \lor (A \land C)$ uses 3 gates. Factored as $A \land (B \lor C)$, it needs only 2.

Readable Program Conditions

Programmers use De Morgan's laws to remove confusing double negations from conditions in their code.

NOT (weekend OR holiday) is the same as (NOT weekend) AND (NOT holiday): the shop is open on days that are neither.

Search Filters

Search engines and databases simplify filters with the absorption law before they run them.

The filter math OR (math AND logic) returns exactly the same books as the filter math.

Boolean algebra uses laws to rewrite an expression into an equivalent one, without a new truth table each time

Identity, null, idempotent and complement laws remove constants and repeated variables: $A \land 1 = A$, $A \lor 1 = 1$, $A \lor A = A$, $A \land \neg A = 0$

Commutative, associative and distributive laws reorder, regroup and factor; in Boolean algebra OR also distributes over AND

Absorption laws: $A \lor (A \land B) = A$ and $A \land (A \lor B) = A$

De Morgan's laws: break the bar and change the sign, $\neg(A \land B) = \neg A \lor \neg B$ and $\neg(A \lor B) = \neg A \land \neg B$

Simplify one law at a time, name each law and check the result with a truth table; a simpler expression means fewer gates

Q: Why can OR distribute over AND, when $a + b \times c$ is not $(a + b) \times (a + c)$ for numbers?

A: Because Boolean variables are only 0 or 1. Check both cases: if $A = 1$, both sides of $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ are 1; if $A = 0$, both sides become $B \land C$. With ordinary numbers $1 + 2 \times 3 = 7$ but $(1 + 2) \times (1 + 3) = 12$, so this law only holds in Boolean algebra.

Q: How do I know which law to use next?

A: Look for patterns: a NOT in front of brackets calls for De Morgan, a variable repeated in two brackets calls for factoring (distributive law), and a variable next to its own negation calls for the complement law. The constants 0 and 1 disappear with the identity and null laws.

Q: Do I still need truth tables if I know the laws?

A: The laws find the simplification, the truth table confirms it. A table with 2 variables has only 4 rows, so it is a quick and reliable check, especially when you are not sure about a step.

Q: Can I check a law with ordinary arithmetic?

A: Yes, with 0 and 1: $A \land B = A \times B$, $\neg A = 1 - A$ and $A \lor B = A + B - A \times B$. For example, with $A = 1$ and $B = 1$: $1 + 1 - 1 \times 1 = 1$, so $1 \lor 1 = 1$. The calculator in this lesson works with these numbers.

Exit Presentation

Boolean Algebra

1 / 14

Logic & Sets / Boolean Logic

Boolean Algebra

Learn the laws of Boolean algebra, including De Morgan's laws, and use them to simplify expressions step by step and check the result with a truth table.

Advanced30 min

Use arrow keys or spacebar to navigate