Boolean Expression Solver

truth table with step-by-step sub-expression columns

Starting values — Boolean Expression Solver

Boolean expression	A & B

Change any control above and the results recompute from these.

Loading interactive simulation...

Pick the variable that explains the most 🖖

A useful hardware trick: pick the input variable that best separates TRUE/FALSE behavior, implement each branch separately, then multiplex through that input. That's exactly what the information-gain split below computes: it finds the variable whose value reduces uncertainty about the output the most - the same idea decision trees use to choose their first split.

one row for every possibility 🖖

A truth table is simply an exhaustive list: it writes out every possible combination of TRUE/FALSE inputs and shows what the expression does for each. With n variables there are 2ⁿ rows, so each new input doubles the table — 3 variables give 8 rows, 5 give 32. The intermediate columns matter too: they build up each sub-expression in turn, so you can follow the logic one operator at a time instead of trusting the final answer.

32 rows, four billion functions 🖖

The table for 5 variables has just 32 rows, yet the number of different expressions you can define over them is 2³² = 4,294,967,296. Every distinct way of filling the output column with 0s and 1s is its own Boolean function, and there are 2^(2ⁿ) of them in total. So this modest tool quietly explores a space of more than four billion possible logic circuits — one for each pattern the final column can take.

BOOLEAN EXPRESSIONS — WHICH LAW SIMPLIFIES THIS ONE?

Which Simplification Case Are You In?

Two expressions are the same expression exactly when their truth tables match, and that is the only test that settles it. The laws of Boolean algebra are the matches worth knowing by sight: pushing a NOT inwards, multiplying out a bracket, dropping a term that changes nothing, and spotting the term the others already covered. Build the table and the answer is never in doubt.

A NOT sitting on a bracket — De Morgan swaps the connective ¬(A ∧ B) = ¬A ∨ ¬B

A bracket to multiply out — distribution A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)

A term that adds nothing — absorption A ∨ (A ∧ B) = A

A term the others already cover — the consensus theorem (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)

The expression stops depending on its inputs at all A ∨ ¬A = 1

A NOT sitting on a bracket — De Morgan swaps the connective

What you know: A negation applied to a whole expression. Pushing it inside turns AND into OR, or OR into AND, and negates each part on the way.

Law: ¬(A ∧ B) = ¬A ∨ ¬B

Worked example: !(A & B) is the same expression as !A | !B — the two output columns agree on all four rows

Open this case: De Morgan !(A & B)

A NOT sitting on a bracket — De Morgan swaps the connective. Push the NOT inside and the AND becomes an OR; the two output columns are identical. A negation applied to a whole expression. Pushing it inside turns AND into OR, or OR into AND, and negates each part on the way. — Push the NOT inside and the AND becomes an OR; the two output columns are identical.

A bracket to multiply out — distribution

What you know: AND distributes over OR exactly as multiplication distributes over addition. Expanding gives a sum of products, the standard form for turning an expression into a circuit.

Law: A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)

Worked example: A & (B | C) is the same as (A & B) | (A & C), across all eight rows of three variables

Open this case: A & (B | C)

A bracket to multiply out — distribution. Expanding the bracket gives two product terms whose OR matches the original. AND distributes over OR exactly as multiplication distributes over addition. Expanding gives a sum of products, the standard form for turning an expression into a circuit. — Expanding the bracket gives two product terms whose OR matches the original.

A term that adds nothing — absorption

What you know: When one term already implies another, the weaker one can be dropped. A | (A & B) is simply A, whatever B happens to be.

Law: A ∨ (A ∧ B) = A

Worked example: A | (A & B) = A: where A is 1 the output is 1 regardless, and where A is 0 the second term is 0 as well

Open this case: absorption law

A term that adds nothing — absorption. The second term only fires where the first already did, so it never affects the output. When one term already implies another, the weaker one can be dropped. A | (A & B) is simply A, whatever B happens to be. — The second term only fires where the first already did, so it never affects the output.

A term the others already cover — the consensus theorem

What you know: Three terms where the third is the consensus of the first two: it only covers cases they cover between them. Removing it changes no row of the table.

Law: (A∧B) ∨ (¬A∧C) ∨ (B∧C) = (A∧B) ∨ (¬A∧C)

Worked example: (A & B) | (!A & C) | (B & C) equals (A & B) | (!A & C) — the third term is redundant on all eight rows

Open this case: consensus theorem

A term the others already cover — the consensus theorem. Dropping the third term leaves the output column untouched on every row. Three terms where the third is the consensus of the first two: it only covers cases they cover between them. Removing it changes no row of the table. — Dropping the third term leaves the output column untouched on every row.

The expression stops depending on its inputs at all

What you know: A column of all ones is a tautology; a column of all zeros is a contradiction. Either way the variables have stopped mattering.

Law: A ∨ ¬A = 1

Worked example: A | !A is 1 on both rows, and its mirror image A & !A is 0 on both

Open this case: tautology A | !A

The expression stops depending on its inputs at all. Both rows give the same output, so the input has no influence whatsoever. A column of all ones is a tautology; a column of all zeros is a contradiction. Either way the variables have stopped mattering. — Both rows give the same output, so the input has no influence whatsoever.

References (2)

Problems solved in full

Sum of minterms for the expression !(A & B) 5 steps
The expression is !(A & B), on the two variables A and B. Count the rows where it comes out 1, write the function as a sum of minterms, then work out what you can build from this one gate and nothing else.
1. Two variables, each free to be 0 or 1, so the table gets one row per pair. The parser reports that count before it evaluates anything, because the size of the question is fixed by the variables and not by the expression written over them.
  
  $2^{2} = 4$
2. Fill the inner column first. A & B is 1 only when both inputs are 1, so three rows carry 0 and the last carries 1. The table prints this sub-expression as its own column beside the result, which lets you check the parse rather than only the answer.
  
  $A \land B : 0, 0, 0, 1$
3. NOT flips every entry and does nothing else. The three zeros become ones and the single one becomes zero, so the result column is the exact negative of the column above it.
  
  $\neg (A \land B) : 1, 1, 1, 0$
4. That leaves 3 of the 4 rows at 1. As a fraction it is 0.75, which the panel states as a percentage of the input combinations.
  
  $\frac{3}{4} = 0.75 = 75.0%$
5. Name each true row by the conjunction that is 1 on that row and on no other — its minterm — and OR the three of them together. This is the canonical disjunctive normal form, and it is the list the tool prints under the table.
  
  $(\neg A \land \neg B) \lor (\neg A \land B) \lor (A \land \neg B)$
Answer

NAND is 1 on 3 of the 4 rows, 75.0%, and its normal form is those 3 minterms. Now the payoff. Feed A into both inputs and A NAND A is !(A & A), which is !A — you have NOT. Feed the output of a NAND back into both inputs of another and the two negations cancel, so (A NAND B) NAND (A NAND B) is AND. For OR, negate both inputs first: (A NAND A) NAND (B NAND B) is !(!A & !B), and !A & !B is 1 on the single row 0,0, so its negation is 1 on the other 3 — which is A OR B. NOT, AND and OR are exactly what step 5 used to write a function as a normal form, so this one 4-row column can express every Boolean function of any number of variables.

$A ↑ A = \neg A, (A ↑ A) ↑ (B ↑ B) = A \lor B$
Building the column from scratch for !A | !B 6 steps
Now take !A | !B, which shares no operator with !(A & B) — no negated bracket, no AND anywhere. Build its column from scratch and see where it lands.
1. Two NOT columns, both printed beside the result. !A is 1 on the 2 rows where A is 0; !B is 1 on the 2 rows where B is 0. They agree on one row and both fail on one row.
  
  $\neg A : 1, 1, 0, 0 \neg B : 1, 0, 1, 0$
2. OR is 0 only where both of its inputs are 0, and that happens on exactly one row: A=1, B=1, the row where neither negation survives. Every other row has at least one 1 to contribute.
  
  $\neg A \lor \neg B : 1, 1, 1, 0$
3. So 3 of the 4 rows are 1 — the same 0.75, stated as the same percentage.
  
  $\frac{3}{4} = 75.0%$
4. The minterms match too, term for term and in the same order as the first problem.
  
  $(\neg A \land \neg B) \lor (\neg A \land B) \lor (A \land \neg B)$
5. Now compare the two expressions without a table at all. A & B is 1 on exactly one row, so !(A & B) is 0 on exactly that row, and it is the same row that just defeated !A | !B. Two columns that are 0 in the same place and 1 everywhere else are one column.
  
  $\neg (A \land B) \equiv \neg A \lor \neg B$
6. How impressed should you be? A 4-row table has 4 result cells, each 0 or 1, so two variables admit only 16 distinct functions in total. Agreement is cheap in a set that small — which is why step 5 is the part that matters: it fixed one row and never counted the rest.
  
  $2^{2^{2}} = 2^{4} = 16$
Answer

Both expressions come out at 75.0% with the same 3 minterms, because they are one function wearing two names. The canonical form is a fingerprint: two expressions are equivalent exactly when their minterm sets match, so the question of whether two circuits behave the same collapses into whether two lists agree. What does not collapse is the cost of building the lists. 2 variables need 4 rows and you did those in your head; 20 variables need 1,048,576; 100 variables need roughly 1.27×10³⁰ rows, and the fingerprint is still the right idea while the table has stopped being a method. The row-by-row argument in step 5 is the one that survives the jump, because it never mentioned how many rows there were.

$2^{20} = 1048576, 2^{100} \approx 1.27 \times 1 0^{30}$

By the 42Math team · Updated 2026-07-27

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

simple AND - AND: output is 1 only when both A and B are 1
(A OR B) AND NOT C - 3 variables, 8 rows - shows how NOT inverts a whole branch
3-input majority - Majority vote: 1 when at least 2 of A, B, C are 1
2:1 multiplexer - Multiplexer: S=0 outputs A, S=1 outputs B
tautology A | !A - A | !A is true in every row, so the output column is all ones and the input never matters. Combined with its opposite A & !A, these are the two functions the truth table can express without reading the variable at all.
contradiction A & !A - A & !A is false in every row. Every other expression on this page falls between this and its opposite, which is why these two mark the ends of the scale rather than being curiosities.
De Morgan !(A & B) - Load this, then load its partner !A | !B. The two output columns are identical, which is what De Morgan’s law asserts: negating an AND turns it into an OR of the negations. Two expressions, one function.
De Morgan !A | !B - The other half of the De Morgan pair. Set it beside !(A & B) and the output columns match row for row, so the two expressions are not merely equivalent in some cases but the same function written twice.
A & (B | C) - A & (B | C), the left side of the distributive law. Its partner expands it to (A & B) | (A & C); the tables agree everywhere, which is what makes the expansion legal rather than merely plausible.
(A & B) | (A & C) - The expanded form. It costs two ANDs and an OR where the compact version costs one of each, so a law that leaves the truth table alone is not free in hardware — the same reason algebra is worth doing before building.
XOR expanded form - XOR written out of the two cases where the inputs differ. There is no XOR operator here on purpose: seeing it as a sum of minterms is how every function gets built from the three you already have.
A AND A AND A AND A - ANDing a variable with itself four times returns the variable. Notice what this costs: three gates that change nothing, which is exactly what an optimiser exists to remove.
absorption law - A | (A & B) collapses to A, and the B column earns its place by being visibly ignored: wherever A is true the whole thing is true regardless, and wherever A is false the second term is false too.
consensus theorem - The middle term is redundant and the table proves it — delete B & C and the output column is unchanged. Spotting that by inspection is hard, which is why the theorem has a name.
implication A -> B - A implies B is not a primitive — it is !A | B, and the table is the proof. The row that surprises people is A false, B true, where the implication holds.
3-input parity - True when an odd number of inputs are 1, which is XOR chained across three variables. This is the check bit on a memory word, and it catches any single-bit error precisely because flipping one input flips the output.