x
+ 1 = 1 x * 0 = 0 x + 0 = x x * 1 = x x + x = x x * x = x 
x
+ x' = 1 x * x' = 0 0' = 1 1' = 0 x'' = x 
(x
+ y) + z = x + (y + z) (x * y) * z = x * (y * z) x + y = y + x x * y = y * x 
x
+ (y * z) = (x + y) * (x + z) x * (y + z) = (x * y) + (x * z) (x + y)' = x' * y' (x * y)' = x' + y' 

XOR notation: ⊕, ⊻ x ⊕ 1 = x' x ⊕ 0 = x x ⊕ x = 0 
x ⊕ y ⊕ y = x  (x
⊕ y) ⊕ z = x ⊕ (y ⊕ z) x ⊕ y = y ⊕ x 
x
* (y ⊕
z) = (x * y) ⊕
(x * z) x ⊕ y = (x+y)*(x*y)' = x*y' + x'*y 


OR = A or B or both XOR = A or B but not both 000 = 0 001 = 1 010 = 2 011 = 3 100 = 4 101 = 5 110 = 6 111 = 7 
Description 
Formula 
Characteristics 
An example 
Permutation of n things taken k at a time 
k items from n where order matters without repetition 


Combination of n things taken k at a time 
k items from a set of n where order does not matter without repetition 


k ordered things from a set of n elements
with repetition 
n^{k} 
k items from a set of n where order matters repetition allowed 

k unordered sets from a set of n categories with repetition  k sets from a set of n where order does not matter repetition allowed 

Notion 
Logic 
Sets 
Boolean Algebra 
Venn Diagrams  Circuits 
Binary 
Domination OR true 
P ∨ T ⇔ T 
A ∪ U = U 
x + 1 = 1 
∪ =  {1357} + U = U U = {01234567} 

Domination AND false 
P ∧ F ⇔ F 
A ∩ ∅ = ∅  x * 0 = 0 
∩ =  {1357} * {} = {} 

Identity 
P ∨ F ⇔ P 
A ∪ ∅= A 
x + 0 = x 
∪ =  {1357} + {} = {1357} 

Identity 
P ∧ T ⇔ P 
A ∩ U = A 
x * 1 = x 
∩ =  {1357} * U = {1357} 

Idempotence 
P ∨ P ⇔ P 
A ∪ A = A 
x + x = x 
∪ =  {1357} * {1357} = {1357} 

Idempotence  P ∧ P ⇔ P 
A ∩ A = A 
x * x = x 
∩ =  {1357} + {1357} = {1357} 

Associativity 
(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) 
(A ∪ B) ∪ C = A ∪ (B ∪ C) 
(x + y) + z = x + (y + z) 
∪
= = ∪ 
= 
{123567}+{4567} = {1234567} = {1357}+{234567} 
Associativity AND 
(P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) 
(A ∩ B) ∩ C = A ∩ (B ∩ C) 
(x * y) * z = x * (y * z) 
∩
= = ∩ 
= 
{37}*{4567} = {7} = {1357}*{67} 
Commutativity OR 
P ∨ Q ⇔ Q ∨ P 
A ∪ B = B ∪ A 
x + y = y + x 
∪
= = ∪ 
= 
{1357}+{2367} = {123567} = {2367}+{1357} 
Commutativity AND 
P ∧ Q ⇔ Q ∧ P 
A ∩ B = B ∩ A 
x * y = y * x 
∩
= = ∩ 
= 
{1357}*{2367} = {7} = {2367}*{1357} 
Distributivity OR over AND 
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) 
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 
x + (y * z) = (x + y) * (x + z) 
∪
= = ∩ 
=

{1357}+{67} = {13567} = {123567}*{134567} 
Distributivity AND over OR 
P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) 
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 
x * (y + z) = (x * y) + (x * z) 
∩
= = ∪ 
=

{1357}*{234567} = {357} = {37}+{57} 
Complement OR 
P ∨ ¬P ⇔ T 
A ∪ A^{c} = U 
x + x' = 1 
∪ =  {1357}+{0246} = {01234567} = U 

Complement AND 
P ∧ ¬P ⇔ F 
A ∩ A^{c} = ∅  x * x' = 0 
∩ =  {1357}*{0246} = {} 

Complement 
¬F ⇔ T 
∅^{c} = U 
0' = 1 
C =  {}' = U 

Complement 
¬T ⇔ F 
U^{c} = ∅  1' = 0 
C=  U' = {} 

Involution 
¬¬P ⇔ P 
A^{cc} = A 
x'' = x 
CC = C = 
{1357}'' = {0246}' = {1357} 

DeMorgan's Law NOT OR 
¬(P ∨ Q) ⇔ ¬P ∧ ¬Q 
(A ∪ B)^{c} = A^{c} ∩ B^{c} 
(x + y)' = x' * y' 
C = = ∩ 
=

{123567}' = {04} ={0234}*{0145} 
DeMorgan's Law NOT AND 
¬(P ∧ Q) ⇔ ¬P ∨ ¬Q 
(A ∩ B)^{c} = A^{c} ∪ B^{c} 
(x * y)' = x' + y' 
C = = ∪ 
=

{37}' = {012456} = {0234}+{0145} 
Implication 
P → Q ⇔ ¬(P ∧ ¬Q) ⇔ ¬P ∨ Q ⇔ ¬Q → ¬P 
A ⊆ B = (A ∩ B^{c})^{c} = A^{c} ∪ B = B' ⊆ A' 
(x * y')' = x' + y 
⊆ = ⊆ OR: 
{023} 

Associativity XOR 
P⊕(Q⊕R) = (P⊕)Q⊕R 
A ⊻ (B ⊻ C) = (A ⊻ B) ⊻ C 
X⊕(Y⊕Z) = (X⊕)Y⊕Z 
⊕
= 
{1256}⊕{4567} = {1247} 