How to use the boolean expression simplifier
- Choose expression or list of minterms. For an expression, use AND, OR, NOT, XOR, IMPLIES and IFF, or the symbols & | ! ^ -> <->, with up to six variables.
- For minterms, give the variable names (most significant first), the rows that give 1 counting from 0, and optionally the don't care rows.
- Read the simplest sum of products and product of sums, each in algebra notation and with symbols.
- Check the table of prime implicants to see which groups of rows each term covers and which are in the answer.
Formula
minterm numbers come from the truth table rows, with the first variable as the top bit
merge two terms that differ in exactly one variable and repeat until nothing merges; what is left are the prime implicants
choose the fewest prime implicants that cover every 1 row; among those, the fewest literals
product of sums: minimize the rows that give 0 the same way, then negate each term
This is the Quine-McCluskey method with an exact search for the cover. Don't care rows may be used to make terms bigger but never need to be covered.
A three input majority function
The expression (A & B) | (A & !B & C) | (!A & B & C) is 1 on rows 3, 5, 6 and 7 of the truth table. Merging gives three prime implicants, BC (rows 3 and 7), AC (rows 5 and 7) and AB (rows 6 and 7), and all three are needed. The simplest sum of products is BC + AC + AB, with 3 terms and 6 literals.
The product of sums is (A + B)(A + C)(B + C), which is also three terms of two variables. For a function of four variables with rows 4, 8, 10, 11, 12 and 15 giving 1 and rows 9 and 14 as don't cares, the smallest sum of products has 3 terms and 7 literals and the smallest product of sums has 3 clauses and 6 literals. A tautology simplifies to 1 and a contradiction to 0.
Reading the notation
In algebra notation, a prime mark after a variable means NOT, writing variables side by side means AND, and a plus sign means OR. So A'B + C means (NOT A AND B) OR C. In the symbol form the same function is (¬A ∧ B) ∨ C. A product of sums is a list of OR clauses joined by AND.
To see the full table behind an expression, use the Truth Table Generator. To work in binary, see the Number Base Converter.
More than one answer
Several equally small expressions can exist for the same function, and the tool shows one of them. Every answer is correct if it gives 1 on all the rows that must be 1 and 0 on all the rows that must be 0. Don't care rows are free, so the answer may give either value on them.
More logic and number tools
For related logic, chemistry and number problems, try the Chemical Equation Balancer, Chinese Remainder Theorem Solver and Continued Fraction Calculator.
Assumptions and limits
- The function has between 0 and 6 variables, so at most 64 rows.
- Variable names start with a letter and use letters, digits and underscores.
- Rows are numbered from 0 with the first variable as the most significant bit.
- Don't care rows are rows whose value does not matter.
Frequently asked questions
What is the Quine-McCluskey method?
It is a way to simplify a boolean function by merging terms that differ in one variable until none can merge, then choosing the fewest of the resulting prime implicants that cover all the 1 rows.
What is a sum of products?
It is an OR of AND terms, such as BC + AC + AB. Each term is a product of variables or their negations, and the function is 1 when any term is 1.
What is a don't care in logic?
It is an input row whose output you do not care about, perhaps because that input never happens. The simplifier may treat it as 0 or 1, whichever gives a smaller expression.
Is the simplest form unique?
No. Some functions have several forms with the same number of terms and literals, and the tool shows one. All of them are equivalent on the rows that matter.