Boolean Algebra Toolkit

• Truth Table to Boolean Expression and Logic Diagram Generator
• Boolean Expression Evaluator and Truth Table Generator

Installation

pip install balg

Usage

from balg.boolean import Boolean
booleanObject = Boolean()

1. To generate an expression's truth table:

input_expression: str = "~(A & B & C)+(A & B)+(B & C)"
tt: str = booleanObject.expr_to_tt(input_expression)

2. To generate an expression given the minterms and variables:

variables: List[str] = ['A', 'B', 'C']
minterms: List[int]  = [0, 1, 3, 7]
expression: str   = booleanObject.tt_to_expr(variables, minterms)

3. To generate a logic diagram given an expression:

input_expression: str = "~(A & B & C)+(A & B)+(B & C)"
file_name: str = "logic_diagram12"
format: str = "png"
directory: str = "examples" # stores in the current directory by default
booleanObject.expr_to_dg(input_expression, file_name, directory, format)

4. To generate a logic diagram given variables and minterms

variables: List[str] = ['A', 'B', 'C']
minterms: List[int]  = [0, 1, 3, 7]
file_name: str = "logic_diagram12"
directory: str = "examples"
format: str = "png"
booleanObject.tt_to_dg(variables, minterms, file_name, directory, format)

5. To assert equality for expressions

expressions_list = ["(A & ~B) + (~A & B)", "(A ^ B)", "(A + B) & ~(A & B)"]
ret = booleanObject.expr_cmp(expression_list) # returns True

6. To simplify expressions (ambiguous):

simplified_expr: str = booleanObject.expr_simplify("~(A) + ~(B)")

7. To generate random expressions:

#generating a single expression
expression: str = boolean.generate_expression(max_depth=4, max_identifiers=5)

#generating multiple expressions
expression: List[str] = boolean.generate_expressions(max_depth=4, max_identifiers=5, count=100)

#max_depth refers to nesting depth:
expression = "A" #nesting_depth = 0
expression = "(((4)))"  #nesting_depth = 3

#max_identifiers refers to the number of identifiers allowed in an expression
expression = "A + B + C" # has 3 identifiers

Example Diagrams

((A & B) & C) + (~C)

(A & B) + (~(A & B) & ~C) + (C & B)

Other diagrams can be found in the diagrams/ directory

Explanation of the Quine-McCluskey Algorithm

This section deals with converting a given truth table to a minimized boolean expression using the Quine-McCluskey algorithm and producing a logic diagram.

Overview

1. Initialize variables & Minterms
2. Identify essential Prime implicants
3. Minimize & Synthesize the boolean function

Initialization

• The synthesizer is initialized with a list of character variables and minterms:
• Minterms refer to values for which the output is 1.
• Prime implicants are found by repeatedly combining minterms that differ by only one variable:

The Quine-McCluskey Algorithm

               The Quine-McCluskey Algorithm

+-----------------------------------+
| initialize variables and minterms |
| variables := [A, B, C]            |
| minterms  := [0, 3, 6, 7]         |
| minters   := [000, 011, 110, 111] |
+-----------------------------------+
                |
                /
               /
               |
               V
        +-----------------------+
        | find prime_implicants |
        | | A | B | C |  out |  |
        | |---|---|---|------|  |
        | | 0 | 0 | 0 |  1   |  |
        | | 0 | 0 | 1 |  0   |  |
        | | 0 | 1 | 0 |  0   |  |
        | | 0 | 1 | 1 |  1   |  |
        | | 1 | 0 | 0 |  0   |  |
        | | 1 | 0 | 1 |  0   |  |
        | | 1 | 1 | 0 |  1   |  |
        | | 1 | 1 | 1 |  1   |  |
        +-----------------------+
                 |
                 |
                  \
                   |
                   V
+----------------------------------+
|  | group | minterm | A | B | C | |
|  |-------|---------|---|---|---| |
|  |   0   | m[0]    | 0 | 0 | 0 | |
|  |   2   | m[1]    | 0 | 1 | 1 | |
|  |       | m[2]    | 1 | 1 | 0 | |
|  |   3   | m[3]    | 1 | 1 | 1 | |
|  |-------|---------|---|---|---| |
+----------------------------------+
                    \
                     \
                      |
                      V
        +-------------------------------------------+
        | find pair where only one variable differs |
        | | group | minterm    | A | B | C |  expr  |
        | |-------|------------|---|---|---|--------|
        | |   0   | m[0]       | 0 | 0 | 0 | ~(ABC) |
        | |   2   | m[1]-m[3]  | _ | 1 | 1 |  BC    |
        | |       | m[2]-m[3]  | 1 | 1 | _ |  AB    |
        +-------------------------------------------+
                        |
                       /
                      |
                      V
    +-------------------------------------------+
    |  since the bit-diff between pairs in each |
    |  class is > 1, we move onto the next step |
    |                                           |
    |   |  expr  | m0  | m1  | m2  | m3   |     |
    |   |--------|-----|-----|-----|------|     |
    |   | ~(ABC) | X   |     |     |      |     |
    |   |   BC   |     |  X  |     |      |     |
    |   |   AB   |     |     |  X  |      |     |
    |   |--------|-----|-----|-----|------|     |
    +-------------------------------------------+
                            |
                            |
                           /
                          |
                          V
              +-----------------------------------------+
              | If each column contains one element     |
              | the expression can't be eliminated.     |
              | Therefore, the resulting expression is: |
              |         ~(ABC) + BC + AB                |
              +-----------------------------------------+

Tips

1. Use parentheses when the order of operations is ambiguous.
2. The precedence is as follows, starting from the highest: NOT -> OR -> (AND, XOR)

Documentation (for developers)

class TruthTableSynthesizer(variables: List[str], minterms: List[int])
class BooleanExpression(expression: str)
class Boolean()
class BooleanExpressionGenerator(max_identifiers: int = 5, max_depth: int = 5)

TruthTableSynthesizer.decimal_to_binary(num: int) -> str
TruthTableSynthesizer.combine_implicants(implicants: List[Set[str]]) -> Set[str]
TruthTableSynthesizer.get_prime_implicants() -> Set[str]
TruthTableSynthesizer.covers_minterm(implicant: str, minterm: str) -> bool
TruthTableSynthesizer.get_essential_prime_implicants(prime_implicants: Set[str]) -> Set[str]
TruthTableSynthesizer.minimize_function(prime_implicants: Set[str], essential_implicants: Set[str]) -> List[str]
TruthTableSynthesizer.implicant_to_expression(implicant: str) -> str
TruthTableSynthesizer.synthesize() -> str

BooleanExpression.to_postfix(inifx: str) -> List[str]
BooleanExpression.evaluate(values: Dict[str, bool]) -> bool
BooleanExpression.tt() -> List[Tuple[Dict[str, bool], bool]]
BooleanExpression.fmt_tt() -> str
BooleanExpression.generate_logic_diagram() -> graphviz.Digraph

BooleanExpressionGenerator.generate_expression() -> str
BooleanExpressionGenerator.generate_expressions(number: int = 1) -> List[str]

Boolean.expr_to_tt(input_expression: str) -> str
Boolean.tt_to_expr(variables: List[str], minterms: List[int]) -> str
Boolean.tt_to_dg(variables: List[str], minterms: List[int], file: str | None = None, directory: str | None = None, format: str = "png") -> str
Boolean.expr_to_dg(input_expression: str, file: str | None = None, directory: str | None = None, format: str = "png") -> str
Boolean.expr_simplify(input_expression: str) -> str
Boolean.expr_cmp(expressions: List[str]) -> bool
Boolean.generate_expression(max_identifiers: int=5, max_depth: int=4) -> str
Boolean.generate_expressions(max_identifiers: int=5, max_depth: int=4, number: int) -> List[str]

TODO

0. Optimize functions 0.5. LaTeX interface
1. NAND, NOR, XNOR
2. Implication (X -> Y) and bi-implication (X <-> Y)
3. Add support for constants (1, 0)
4. Implement functional completeness testing
5. Expression comparison by comparing minterms (grammar agnostic)
6. (improbable) implement Quantum Gates
7. (improbable) potential integration with Verilog systems