Boolean Algebra & De Morgan's Laws

Boolean algebra lets you describe a logic circuit as an equation, then simplify it before you build anything. A simpler equation means fewer gates, fewer wires, and fewer places for mistakes.

Operation   Notation      Arduino
AND         A·B  or  AB   A && B
OR          A + B         A || B
NOT         A'  or  Ā     !A
XOR         A ⊕ B         A ^ B

Identity:        A + 0 = A          A · 1 = A
Null:            A + 1 = 1          A · 0 = 0
Idempotent:      A + A = A          A · A = A
Complement:      A + A' = 1         A · A' = 0
Double negation: (A')' = A
Commutative:     A + B = B + A      AB = BA
Associative:     (A + B) + C = A + (B + C)
Distributive:    A(B + C) = AB + AC
Absorption:      A + AB = A         A(A + B) = A
Redundancy:      A + A'B = A + B

You don't need to memorize these all at once. Each one can be checked with a small truth table, and after a few problems the common ones become second nature.

De Morgan's laws tell you how to push a NOT through an AND or an OR: invert each input and swap the operation.

(A · B)' = A' + B'     "NOT (A AND B)" = "(NOT A) OR (NOT B)"
(A + B)' = A' · B'     "NOT (A OR B)"  = "(NOT A) AND (NOT B)"

In everyday terms: 'it's not both sunny and warm' means 'it's either not sunny or not warm'. These laws are how you convert between AND/OR designs and NAND/NOR designs.

Here is a 3-input function written directly from a truth table. It needs three 3-input AND gates and a 3-input OR gate. Let's simplify it step by step.

Y = A'BC + ABC + AB'C

  = BC(A' + A) + AB'C        distributive (factor out BC)
  = BC(1) + AB'C             complement: A' + A = 1
  = BC + AB'C                identity
  = C(B + AB')               factor out C
  = C(B + A)                 redundancy: B + B'A = B + A
  = AC + BC

The result needs just two 2-input AND gates and one OR gate. The circuit does exactly the same job with far less hardware.

Any logic function at all can be built using only NAND gates. That's why NAND is called a universal gate, and it's one reason chip designers love it. NOR is universal too.

NOT A   = (A · A)'                  1 NAND gate, inputs tied together
A AND B = ((A · B)')'               NAND followed by a NAND-inverter
A OR B  = (A' · B')'                De Morgan: invert both inputs, then NAND
        = NAND(NAND(A,A), NAND(B,B))   3 NAND gates

You can prove a simplification is correct by checking every input combination. With 3 inputs there are only 8 cases, which is easy work for an Arduino.

bool original(bool A, bool B, bool C) {
  return (!A && B && C) || (A && B && C) || (A && !B && C);
}

bool simplified(bool A, bool B, bool C) {
  return (A && C) || (B && C);
}

void setup() {
  Serial.begin(9600);
  bool allMatch = true;

  for (int i = 0; i < 8; i++) {
    bool A = bitRead(i, 2), B = bitRead(i, 1), C = bitRead(i, 0);
    bool y1 = original(A, B, C);
    bool y2 = simplified(A, B, C);
    Serial.print(A); Serial.print(B); Serial.print(C);
    Serial.print(" -> "); Serial.print(y1);
    Serial.print(" "); Serial.println(y2);
    if (y1 != y2) allMatch = false;
  }

  Serial.println(allMatch ? "Equivalent!" : "NOT equivalent");
}

void loop() {}

• Use De Morgan's laws to rewrite (A + B)' · C using only NAND operations, then verify it with the sketch.
• Build an OR gate from three NAND gates on a 74HC00 and test it with the truth-table tester from the Logic Gates course.
• Simplify Y = AB + A'C + BC and check your answer on the Arduino. (Hint: the BC term is redundant.)