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}