×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Lindsay Ross

18

0

4

# CS 064 DIscrete Structures - Week 3 CS 064

Marketplace > University of Vermont > ComputerScienence > CS 064 > CS 064 DIscrete Structures Week 3
Lindsay Ross
UVM
GPA 3.8

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Notes from week 3 of Discrete Structures
COURSE
Discrete Structures
PROF.
TYPE
Class Notes
PAGES
4
WORDS
CONCEPTS
Math, Discrete Structures, Discrete math, Computer Science, Mathematics, Discrete Mathematics
KARMA
25 ?

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

×

×

### What is Karma?

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

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com