Boolean Algebra and De Morgan’s Theorem

Boolean algebra is the math of 0s and 1s. It lets you simplify a tangle of gates into the smallest equivalent circuit — fewer gates means less area, less power and less delay. These identities are the rules you apply, by hand or with a tool, to minimise logic.

Core identities

• Identity: A·1 = A, A+0 = A
• Null: A·0 = 0, A+1 = 1
• Idempotent: A·A = A, A+A = A
• Complement: A·A' = 0, A+A' = 1
• Distributive: A·(B+C) = A·B + A·C
• De Morgan: (A·B)' = A'+B',   (A+B)' = A'·B'

De Morgan’s theorem is the one you will use most: it converts an AND of inverts into a NAND, and is how synthesis tools push inversions around to match the gates a library actually has.

Algebra is only trustworthy if the simplified expression is truly equivalent. The simulator checks it exhaustively — it sweeps all 8 input combinations and confirms the raw expression A·B + A·B' equals the simplified A, and that both De Morgan forms hold:

module tb;
  reg a, b, c; integer i; reg bad;
  initial begin
    bad = 0;
    for (i = 0; i < 8; i = i + 1) begin
      {a,b,c} = i[2:0];
      // A*B + A*B' simplifies to A
      if ( (a&b)|(a&~b)  !== a )            bad = 1;
      // De Morgan: (A*B)' == A' + B'
      if ( ~(a&b) !== (~a|~b) )             bad = 1;
      // De Morgan: (A+B)' == A' * B'
      if ( ~(a|b) !== (~a&~b) )             bad = 1;
    end
    $display(bad ? "MISMATCH - identity does not hold" :
                   "all 8 combinations: simplification and both De Morgan forms hold");
    $finish;
  end
endmodule

8949156890722041246706784019460874855907104555879304182892854005746153351507044