Key Concepts for CMSC 150

By: Nicholas Duchon, January 26, 2013; Dec 6, 2017.

Boolean Algebra Rules:

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
Binary
 A
 B
 A + B
 A * B
 A ⊕ B
 A'
00 = 0
 F
 F
 F
 F
 F
 T
01 = 1
 F
 T
 T
 F
 T
 T
10 = 2
 T
 F
 T
 F
 T
 F
11 = 3
 T
 T
 T
 T
 F
 F
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

Counting

Description
 Formula
 Characteristics
 An example
Permutation of n things taken k at a time
 k items from n where
order matters
without repetition
  • Select a sequence of 5 cards from a deck of 52
Combination of n things taken k at a time
 k items from a set of n where
order does not matter
without repetition
  • Select a hand of 5 cards from a deck of 52
    rearrangements are considered the same hand
k ordered things from a set of n elements with repetition
 nk
 k items from a set of n where
order matters
repetition allowed
  • Select a sequence of 5 cards,
    each card from a different deck
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
  • k people select n different kinds of fruit

Notions and Notations

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
 C = {}' = U
Complement
 ¬T ⇔ F
 Uc = ∅ 1' = 0
 C= U' = {}
Involution
 ¬¬P ⇔ P
 Acc = A
 x'' = x
 CC
= C
=
{1357}''
= {0246}'
= {1357}
DeMorgan's Law
NOT OR
 ¬(P ∨ Q)
⇔
¬P ∧ ¬Q
 (A ∪ B)c
=
Ac ∩  Bc
 (x + y)'
=
x' * y'
 C

=

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

=

= ∪
=
 {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}