Home | Blog | Wiki | About

#+LINK w1 https://en.wikipedia.org/wiki/Logic_gate

#+LINK w1 https://en.wikipedia.org/wiki/Boolean_algebra

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)