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 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 |
nk |
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 ∪ Ac = U |
x + x' = 1 |
{1357}+{0246} = {01234567} = U |
||
Complement AND |
P ∧ ¬P ⇔ F |
A ∩ Ac = ∅ | x * x' = 0 |
{1357}*{0246} = {} |
||
Complement |
¬F ⇔ T |
∅c = U |
0' = 1 |
|
{}' = U |
|
Complement |
¬T ⇔ F |
Uc = ∅ | 1' = 0 |
U' = {} |
||
Involution |
¬¬P ⇔ P |
Acc = A |
x'' = x |
= = |
{1357}'' = {0246}' = {1357} |
|
DeMorgan's Law NOT OR |
¬(P ∨ Q) ⇔ ¬P ∧ ¬Q |
(A ∪ B)c = Ac ∩ Bc |
(x + y)' = x' * y' |
= = |
=
|
{123567}' = {04} ={0234}*{0145} |
DeMorgan's Law NOT AND |
¬(P ∧ Q) ⇔ ¬P ∨ ¬Q |
(A ∩ B)c = Ac ∪ Bc |
(x * y)' = x' + y' |
= = |
=
|
{37}' = {012456} = {0234}+{0145} |
Implication |
P → Q ⇔ ¬(P ∧ ¬Q) ⇔ ¬P ∨ Q ⇔ ¬Q → ¬P |
A ⊆ B = (A ∩ Bc)c = Ac ∪ 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} |