acalculator

How do I simplify Boolean algebra?

Type a Boolean expression such as AB + AB' + A'B, or the minterm numbers of a function. The Boolean algebra calculator finds the simplest sum of products and product of sums, with the minterms and maxterms.

Your numbers

Start from
Simplest sum of products
A + B

The simplest form is A + B.

Simplest product of sums
(A + B)
Minterms
Σm(1, 2, 3)
Maxterms
ΠM(0)
Variables
A, B

Simplest sum of products: A + B. The simplest form is A + B.

How to calculate

Simplifies a Boolean expression, or a list of minterms with don’t-cares, to a minimal sum of products and product of sums (Quine-McCluskey), with its minterms and maxterms.

Example with the default inputs (Start from Expression, Expression AB + AB' + A'B): The simplest form is A + B.

Method: Truth table from the expression; prime implicants by the Quine-McCluskey method; a minimal cover by exact search (fewest terms, then fewest literals, then a fixed order). The product of sums is the complement’s minimal sum, by De Morgan’s laws.

  • Variables are single letters (case does not matter); at most 5 of them.
  • A row number reads the variables as binary digits, the first variable (in alphabetical order) the highest bit.
  • When several forms are equally short, one is chosen by a fixed order, so another correct answer may exist.

Machine-readable copies: Markdown, JSON.

Worked examples

Each example is checked against the calculator on every build.

  1. Start from Minterms, Number of variables 4, Minterms 4, 8, 10, 11, 12, 15, Don’t cares (optional) 9, 14 gives Simplest sum of products AB' + AC + BC'D', Minterms Σm(4, 8, 10, 11, 12, 15), Maxterms ΠM(0, 1, 2, 3, 5, 6, 7, 13).Source: Wikipedia, Quine–McCluskey algorithm: f(A,B,C,D) = Σm(4,8,10,11,12,15) + d(9,14) has the minimal forms BC′D′ + AB′ + AC and BC′D′ + AD′ + AC, https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
  2. Start from Expression, Expression A + A'B gives Simplest sum of products A + B, Simplest product of sums (A + B), Minterms Σm(1, 2, 3), Variables A, B.Source: Kuphaldt, Lessons in Electric Circuits Vol. IV, §7.5 Boolean Rules for Simplification (A + AB = A, A + A′B = A + B), LibreTexts, https://workforce.libretexts.org/Bookshelves/Electronics_Technology/Electric_Circuits_IV_-_Digital_Circuitry_(Kuphaldt)/07:_Boolean_Algebra/7.05:_Boolean_Rules_for_Simplification
  3. Start from Expression, Expression A + AB gives Simplest sum of products A, Simplest product of sums A, Minterms Σm(2, 3).Source: Kuphaldt, Lessons in Electric Circuits Vol. IV, §7.5 Boolean Rules for Simplification (A + AB = A, A + A′B = A + B), LibreTexts, https://workforce.libretexts.org/Bookshelves/Electronics_Technology/Electric_Circuits_IV_-_Digital_Circuitry_(Kuphaldt)/07:_Boolean_Algebra/7.05:_Boolean_Rules_for_Simplification
  4. Start from Expression, Expression AB + BC(B + C) gives Simplest sum of products AB + BC, Simplest product of sums (A + C)B, Minterms Σm(3, 6, 7).Source: Kuphaldt, Lessons in Electric Circuits Vol. IV, §7.6 Circuit Simplification Examples (AB + BC(B + C) = B(A + C)), LibreTexts, https://workforce.libretexts.org/Bookshelves/Electronics_Technology/Electric_Circuits_IV_-_Digital_Circuitry_(Kuphaldt)/07:_Boolean_Algebra/7.06:_Circuit_Simplification_Examples
  5. Start from Expression, Expression AB + AB' + A'B gives Simplest sum of products A + B, Maxterms ΠM(0).Source: Kuphaldt, Lessons in Electric Circuits Vol. IV, §7.5 Boolean Rules for Simplification (A + AB = A, A + A′B = A + B), LibreTexts, https://workforce.libretexts.org/Bookshelves/Electronics_Technology/Electric_Circuits_IV_-_Digital_Circuitry_(Kuphaldt)/07:_Boolean_Algebra/7.05:_Boolean_Rules_for_Simplification (AB + AB′ = A, then A + A′B = A + B)
  6. Start from Expression, Expression A XOR B gives Simplest sum of products AB' + A'B, Simplest product of sums (A' + B')(A + B).Source: Kuphaldt, Lessons in Electric Circuits Vol. IV, §7.5 Boolean Rules for Simplification (A + AB = A, A + A′B = A + B), LibreTexts, https://workforce.libretexts.org/Bookshelves/Electronics_Technology/Electric_Circuits_IV_-_Digital_Circuitry_(Kuphaldt)/07:_Boolean_Algebra/7.05:_Boolean_Rules_for_Simplification

How it works

From an expression. Letters are variables (upper and lower case are the same letter), 0 is false and 1 is true. Operators, from the one that binds most to the one that binds least:

  1. NOT: ' (or ’, ′) after a letter, a constant or a bracket, as often as you like; or !, ~, ¬ or the word NOT before it.
  2. AND: letters or brackets side by side (AB, A(B + C)), or ·, *, ., &, ∧ or the word AND.
  3. XOR: ^, ⊕ or the word XOR.
  4. OR: +, |, ∨ or the word OR.

Words are read as operators only when the whole run of letters is AND, OR, XOR or NOT; any other run of letters is single-letter variables side by side (ABC is A AND B AND C). At most 5 different letters.

The variables are sorted alphabetically. Row r of the truth table (r = 0 to 2ⁿ − 1) gives the first variable the highest bit of r and the last the lowest bit; the minterms are the rows where the expression is 1.

From minterms. Type the number of variables n (1 to 5, named A, B, C, D, E in order), the minterms and, optionally, the don't cares, as whole numbers from 0 to 2ⁿ − 1 separated by commas or spaces. Repeats count once. A row may not be both.

Simplest sum of products. The Quine-McCluskey method:

  1. Prime implicants: start with every minterm and don't care. Merge any two terms with the same dashes that differ in exactly one bit into one term with a dash there; repeat on the merged terms until none merge. Terms that never merged are the prime implicants. Keep those that cover at least one minterm.
  2. Cover: choose a set of prime implicants that covers every minterm (don't cares need no cover) with, in this order, the fewest terms, then the fewest literals in all, then the first list in this order: write each term as a pattern of 1, 0 and - per variable (first variable first), sort the patterns with 1 before 0 before -, and compare the sorted lists pattern by pattern.
  3. Write each term as its letters in variable order, with ' after a letter whose bit is 0 (pattern 10-1 is AB'D), and join the terms with + in that sorted order. No minterms gives 0; a term with no letters is 1.

Simplest product of sums. The same method on the rows where the function is 0 (the maxterms), with the same don't cares, gives the complement's terms in the same order. By De Morgan's laws each term becomes a sum: a bit 1 gives the letter with ', a bit 0 the letter alone, joined with + (pattern 10-1 is A' + B + D'). Sums of two or more letters are in brackets; the sums are written side by side. A single one-letter sum is written alone. No minterms gives 0 (also when every row is a don't care); otherwise no maxterms gives 1.

Minterms are written Σm(…) and maxterms ΠM(…), the row numbers in increasing order separated by , , or none. Maxterms leave out the don't cares. Variables lists the letters, separated by , , or none for an expression with no letters.

Rules

  • A character that is not a letter, a digit 0 or 1, an operator or a bracket, an unclosed bracket, or a missing operand gives no answer and says why. So do more than 5 letters, a minterm number outside 0 to 2ⁿ − 1, and a row typed as both a minterm and a don't care. As a safeguard, a cover search longer than 2,000,000 steps stops with "This function is too complex to minimise here."

Worked examples by hand

Σm(4, 8, 10, 11, 12, 15) + d(9, 14) (Wikipedia). Prime implicants: -100 (BC'D'), 10-- (AB'), 1--0 (AD'), 1-1- (AC). BC'D' is the only cover of 4 and AC the only cover of 15; 8 needs AB' or AD'. Both covers have 3 terms and 7 literals. Sorted keys: -100 against -100; the first pattern 10-- comes before 1-1- (0 before -), so the answer is AB' + AC + BC'D'.

A + A'B (Kuphaldt 7.5). Rows: 00 → 0, 01 → 1, 10 → 1, 11 → 1, so Σm(1, 2, 3). Prime implicants 1- (A) and -1 (B): A + B. The only 0 row is 00, so the product of sums is (A + B).

A + AB (Kuphaldt 7.5). Σm(2, 3) is the one term 1-: A, and the product of sums is A.

AB + BC(B + C) (Kuphaldt 7.6). Σm(3, 6, 7) gives AB + BC. The 0 rows 0, 1, 2, 4, 5 give the complement's terms 0-0 and -0-, so the product of sums is (A + C)B, the book's B(A + C).

AB + AB' + A'B. Σm(1, 2, 3) again: A + B; maxterms ΠM(0).

A XOR B. Σm(1, 2): no two rows merge, so AB' + A'B. The 0 rows 0 and 3 give (A' + B')(A + B).

Other questions people ask

How do I simplify a Boolean expression?

Apply the rules of Boolean algebra (A + AB = A, A + A′B = A + B, AB + AB′ = A) until no rule shortens it, or use a method that always finds the shortest form, such as a Karnaugh map or the Quine-McCluskey method. This calculator uses Quine-McCluskey, so AB + AB′ + A′B becomes A + B.

How do I type NOT, AND and OR?

NOT is a ’ after a letter or bracket (A′, (A + B)′), or !, ~ or NOT before it. AND is letters side by side (AB), or ·, *, & or AND. OR is +, | or OR. XOR is ^, ⊕ or XOR. Use 0 and 1 for false and true.

What is the Quine-McCluskey method?

It lists the minterms, merges pairs that differ in one variable again and again until nothing merges (the prime implicants), then picks the fewest prime implicants that cover every minterm. It gives the same kind of answer as a Karnaugh map. This calculator takes up to 5 variables.

What are minterms and don’t cares?

A minterm is a row of the truth table where the function is 1, numbered by reading the variables as a binary number (A is the highest bit). A don’t care is a row whose output does not matter, so the method may treat it as 1 or 0, whichever gives a shorter answer.

Why can there be more than one simplest answer?

Two different sets of terms can be equally short. Σm(4, 8, 10, 11, 12, 15) + d(9, 14) is BC′D′ + AB′ + AC or BC′D′ + AD′ + AC. The calculator shows one of them, picked by a fixed order.

What is the product of sums?

The same function written as an AND of ORs, such as (A + C)B for AB + BC. It is found by simplifying the rows where the function is 0 and applying De Morgan’s laws.