Boolean Algebra

Boolean algebra is the algebraic structure that handles binary variables and logic operations. It is the mathematical foundation of digital circuit design.

Basic Operations

The primary operations are:

• AND ($\cdot$ or $\land$): $1 \cdot 1 = 1$, else $0$.
• OR ($+$ or $\lor$): $0 + 0 = 0$, else $1$.
• NOT ($\bar{x}$ or $\neg x$): $\bar{1} = 0, \bar{0} = 1$.

def boolean_table(func):
  print("A | B | Result")
  print("---------")
  for a in [0, 1]:
      for b in [0, 1]:
          print(f"{a} | {b} | {func(a, b)}")

# XOR Implementation
xor_func = lambda a, b: (a or b) and not (a and b)
boolean_table(xor_func)

Algebraic Laws

1. Idempotence: $x + x = x, x \cdot x = x$.
2. De Morgan’s Laws: $\overline{x + y} = \bar{x} \cdot \bar{y}$ and $\overline{x \cdot y} = \bar{x} + \bar{y}$.
3. Absorption: $x + (x \cdot y) = x$.

def de_morgan_test(x, y):
  lhs = not (x or y)
  rhs = (not x) and (not y)
  return lhs == rhs

print(f"De Morgan (0, 0): {de_morgan_test(0, 0)}")
print(f"De Morgan (1, 0): {de_morgan_test(1, 0)}")
print(f"De Morgan (1, 1): {de_morgan_test(1, 1)}")

Sum of Products (SOP) and Simplification

Every boolean function can be represented as a Sum of Products (canonical form). Simplification is typically done using Karnaugh Maps or the Quine-McCluskey algorithm.