# 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}