CS 064 DIscrete Structures - Week 3
CS 064 DIscrete Structures - Week 3 CS 064
Popular in Discrete Structures
Popular in ComputerScienence
This 4 page Class Notes was uploaded by Lindsay Ross on Tuesday February 9, 2016. The Class Notes belongs to CS 064 at University of Vermont taught by in Winter 2016. Since its upload, it has received 18 views. For similar materials see Discrete Structures in ComputerScienence at University of Vermont.
Reviews for CS 064 DIscrete Structures - Week 3
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/09/16
CS 064 Notes 2/2/16 Proof Template 3: to disprove an “if P then Q” proposition, find an instance that makes P true and Q false. Proof template 4: Proof of logical equivalence 1) To show that two Boolean expressions are equivalent, construct a truth table that evaluates each expression for every possible value of its arguments. 2) Verify that the two expressions are equal in every row of the truth table. DeMorgan’s Law: ( ¬ = not ) 1) ¬ (x ∨y) ¬ (x)∧¬( y) 2)¬ (x ∧y) =¬(x) ∨¬( y) x y x ∨y ¬ (x ¬ x ¬ y (¬ x)∧ ∨y) (¬ y) T T T F F F F T F T F F T F F T T F T F F F F F T T T T Since the highlighted columns match, by proof template 4, ¬ (x ∨y) and¬(x)∧ ¬ y) are logically equivalent Theorem: if x, y, z are Boolean variabl¬s,(x ∨y) = (¬ x)∧ ¬ y) x y z y ∨z x ∧( y x ∧y x∧z (x ∧y) ∨ ∨z) (x∧z) T T T T T T T T T T F T T T F T T F T T T F T T T F F F F F F F F T T T F F F F F T F T F F F F F F T T F F F F F F F F F F F F Since the highlighted columns match, by proof template 4, x ∧( y ∨z) and (x ∧y) ∨ (x∧z) are logically equivalent. Proposition: x+(yz)=(x+y)(x+z) Counter-example: x=2, y=3, z=4 2+(3*4)=(2+3)(2+4) 14=30 By proof template 3, proposition false Theorem: x ∨ ( y ∧z) = (x ∨y) ∧ (x∨z) x y z y ∧z x ∨( y x ∨y x∨z (x ∨y) ∧ (x∨z) ∧z) T T T T T T T T T T F F T T T T T F T F T T T T T F F F T T T T F T T T T T T T F T F F F T F F F F T F F F T F F F F F F F F F Since the highlighted columns match, by proof template 4, x ∨ ( y ∧z) and (x ∨y) ∧ (x∨z) are logically equivalent. Theorem 7.2: x ∧y = y ∧x commutative laws x ∧(y ∧z)=( x ∧y) ∧z associative laws CS 064 Notes 2/6/16 The multiplication principle- in order to count a number of lists of length k, where k is an element of that can be constructed when o n =number of choices for the first item in the list 1 o n =2umber of choices for the second item in the list o n =3umber of choices for the third item in the list o n =kumber of choices for the “k” item in the list multiply n 1 n *2n … 3 n k ex. number of lists of length 2 when o x can be one of 1, 2, 3, 4 o y can be one of 9,10 (1, 9) (1, 10) (2, 9) (2, 10) (3, 9) (3, 10) (4, 9) (4, 10) ex. Constructing a password k=8, 62 symbols (uppercase, lowercase, symbols) 62*62*62*62*62*62*62*62= 218 * 10 12 ex. ordering 2 scoop ice cream (cone, scoop1, scoop2) six types of cones, n =6 1 sixteen flavors, n 216 sixteen flavors, n 316 k=3 6*16*16=1536 ex. ordering 2 scoop ice cream (cone, scoop1, scoop2) six types of cones, n =1 sixteen types of cones, n =12 sixteen flavors, option of no flavor, n =37 k=3 6*16*17=1632 ex. Constructing a password, where you can’t use the same character twice k=8, 62 symbols (uppercase, lowercase, symbols) 62*61*60*59*58*57*56*55 This type of multiplication is called a falling factorial, written: 62(8) Theorem 8.6: The number of lists of length k, where elements are chosen from a pool of n possible elements: k o n if repetitions are allowed o n (k)f repetitions are not allowed, where n =(n(k)*(n-2)*(n-3)*(n- 4)…*(n-(k-1))
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'