Boolean arithmetic

Boolean

Named after George Boole.

Boolean algebra properties

Associativity

a + (b+c) = (a+b) + c
a(bc) = (ab)c

Absorption

a + ab = a
a(a + b) = a

de Morgan's laws

(ab)' = a' + b'
(a+b)' = a'b'

Identity

a + 0 = a
a.1 = a

Commutativity

a.b = b.a
a + b = b + a

Distributivity

a(b + c) = ab + ac
a + bc = (a + b).(a + c)

Idempotency

a.a = a
a + a = a

Involution

aka 'double negation'.

(a')' = a

Operations

NOT: aka inverter

AND

a	b	y
0	0	0
0	1	0
1	0	0
1	1	1

OR

a	b	y
0	0	0
0	1	1
1	0	1
1	1	1

XOR

Exclusive OR.

True only when inputs doesn't have the same value.

a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

NAND

Inverted AND

a	b	y
0	0	1
0	1	1
1	0	1
1	1	0

NOR

Inverted OR

a	b	y
0	0	1
0	1	0
1	0	0
1	1	0

XNOR

Inverted XOR.

ie, True when both inputs are the same.

a	b	y
0	0	1
0	1	0
1	0	0
1	1	1

Universal gates

Can be used to realize any other gate.
NAND, NOR

NAND

NOT: (A.A)' → 1 NAND gate
AND: (AB)'' → 2 NAND gates
OR: (A+B)'' = (A'B')' → 3 NAND gates

NOR

NOT: (A+A)' → 1 NOR gate
AND: (AB)'' = (A'+B')' → 3 NOR gates
OR: (A+B)'' → 2 NOR gates

References

Switching Theory and Finite Automata (Third edition) by Zvi Kohavi, Niraj K. Jha
[https://www.mi.mun.ca/users/cchaulk/misc/boolean.html](https://www.mi.mun.ca/users/cchaulk/misc/boolean.htm)