Boolean Algebra

Boolean Algebra

---

Definitions

---

Laws of Boolean Algebra

---

Python Implementations

Truth Table Generator

from itertools import product

def truth_table(expression_func, variables):
    n = len(variables)
    header = variables + ["Result"]
    print(" | ".join(f"{v:>6}" for v in header))
    print("-" * (8 * len(header)))
    for values in product([0, 1], repeat=n):
        env = dict(zip(variables, values))
        result = expression_func(**env)
        row = [str(v) for v in values] + [str(int(result))]
        print(" | ".join(f"{v:>6}" for v in row))

# Example: F = A AND (B OR NOT C)
truth_table(
    lambda A, B, C: A & (B | (not C)),
    ['A', 'B', 'C']
)

Boolean Simplification

def boolean_simplify_sop(minterms, variables):
    """Convert minterms to SOP expression."""
    terms = []
    for m in minterms:
        term = []
        for i, v in enumerate(variables):
            if m & (1 << (len(variables) - 1 - i)):
                term.append(v)
            else:
                term.append(f"{v}'")
        terms.append("".join(term))
    return " + ".join(terms)

def boolean_simplify_pos(maxterms, variables):
    """Convert maxterms to POS expression."""
    terms = []
    for m in maxterms:
        term = []
        for i, v in enumerate(variables):
            if m & (1 << (len(variables) - 1 - i)):
                term.append(f"{v}'")
            else:
                term.append(v)
        terms.append("(" + " + ".join(term) + ")")
    return " * ".join(terms)

# SOP for F(A,B,C) = sum of minterms 1, 3, 5, 7
print(boolean_simplify_sop([1, 3, 5, 7], ['A', 'B', 'C']))
# Output: A'B'C + A'BC + AB'C + ABC

Karnaugh Map

def karnaugh_map_4var(minterms):
    """Print K-map for 4-variable function."""
    # K-map ordering: 00, 01, 11, 10
    order = [0, 1, 3, 2]
    map = [[0] * 4 for _ in range(4)]

    for m in minterms:
        row = (m >> 2) & 3
        col = m & 3
        ri = order.index(row)
        ci = order.index(col)
        map[ri][ci] = 1

    print("    AB\\CD  00   01   11   10")
    labels = ['00', '01', '11', '10']
    for i, label in enumerate(labels):
        row_str = " ".join(f"  {map[i][j]} " for j in range(4))
        print(f"     {label}  {row_str}")

    return map

# Example: F(A,B,C,D) = sum of minterms 0,1,2,5,6,7,8,9,10,14
karnaugh_map_4var([0, 1, 2, 5, 6, 7, 8, 9, 10, 14])

Logic Gate Simulation

def AND(a, b):
    return a & b

def OR(a, b):
    return a | b

def NOT(a):
    return 1 - a

def NAND(a, b):
    return NOT(AND(a, b))

def NOR(a, b):
    return NOT(OR(a, b))

def XOR(a, b):
    return AND(OR(a, b), NAND(a, b))

def XNOR(a, b):
    return NOT(XOR(a, b))

# Half adder
def half_adder(a, b):
    s = XOR(a, b)
    c = AND(a, b)
    return s, c

# Full adder
def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(s1, cin)
    cout = OR(c1, c2)
    return s, cout

# Test
for a in range(2):
    for b in range(2):
        s, c = half_adder(a, b)
        print(f"{a} + {b} = {c}{s}")

---

Karnaugh Maps

---

Applications in AI/ML

---

Common Mistakes

---

Interview Questions

1. What are the three basic Boolean operations? AND ($\cdot$), OR ($+$), and NOT ($\bar{\cdot}$). All Boolean functions can be expressed using these three.

2. State De Morgan's laws. $\overline{ab} = \bar{a} + \bar{b}$ and $\overline{a+b} = \bar{a}\bar{b}$. These convert between AND/OR through complementation.

3. What is the dual of a Boolean expression? Swap AND with OR and 0 with 1. The dual of a true identity is also true (Principle of Duality).

4. How do you simplify a Boolean expression? Use algebraic laws (absorption, distribution, De Morgan's) or Karnaugh maps for visual minimization.

5. What is a minterm and maxterm? A minterm is a product of all variables (each true or complemented); a maxterm is a sum. There are $2^n$ of each for $n$ variables.

6. What is the consensus theorem? $ab + \bar{a}c + bc = ab + \bar{a}c$. The term $bc$ is redundant (consensus of $ab$ and $\bar{a}c$).

7. How do Karnaugh maps work? Group adjacent 1s in powers of 2 on a Gray-coded grid. Each group becomes one product term. Larger groups = simpler expression.

8. What is functional completeness? A set of operations is functionally complete if any Boolean function can be expressed using only those operations. {AND, OR, NOT} and {NAND} and {NOR} are each functionally complete.

---

Practice Problems

---

Quick Reference

---

Quine-McCluskey Method

def quine_mccluskey(minterms, num_vars):
    def count_ones(n):
        return bin(n).count('1')

    def combine_terms(t1, t2):
        diff = 0
        pos = -1
        for i in range(num_vars):
            b1 = (t1 >> i) & 1
            b2 = (t2 >> i) & 1
            if b1 != b2:
                diff += 1
                pos = i
        if diff == 1:
            return t1 & ~(1 << pos)
        return None

    groups = {}
    for m in minterms:
        ones = count_ones(m)
        groups.setdefault(ones, []).append([m])

    prime_implicants = []
    while groups:
        new_groups = {}
        used = set()
        for g1 in sorted(groups.keys()):
            for g2 in sorted(groups.keys()):
                if g2 <= g1:
                    continue
                for t1 in groups[g1]:
                    for t2 in groups[g2]:
                        combined = combine_terms(t1[0], t2[0])
                        if combined is not None:
                            new_terms = sorted(set(t1 + t2))
                            key = tuple(new_terms)
                            if key not in new_groups:
                                new_groups[key] = [new_terms]
                            else:
                                new_groups[key].append(new_terms)
                            used.add(t1[0])
                            used.add(t2[0])

        for g in groups.values():
            for t in g:
                if t[0] not in used:
                    prime_implicants.append(t)

        if not new_groups:
            break
        groups = {}
        for key, terms in new_groups.items():
            ones = count_ones(key[0])
            groups.setdefault(ones, []).extend(terms)

    return prime_implicants

# Example: minimize F(A,B,C) = sum(1, 2, 3, 5, 7)
pis = quine_mccluskey([1, 2, 3, 5, 7], 3)
print(f"Prime implicants: {[bin(p[0]) for p in pis]}")

---

Boolean Function Properties

---

Cross-References

• Graph Theory — Discrete Graphs: Graph coloring uses Boolean logic
• Trees — Discrete Trees: Tree traversals use Boolean conditions
• Number Theory — Discrete Number Theory: Finite field arithmetic
• Recurrence Relations — Discrete Recurrence: Boolean function complexity
• Automata Theory — Discrete Automata: State transitions use Boolean logic
• Applications — Discrete Applications: Digital circuits and logic design