×

### Let's log you in.

or

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

×

or

## Discrete Math

by: Ophelia Ritchie

18

0

15

# Discrete Math EECS 203

Ophelia Ritchie
UM
GPA 3.8

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

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

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
15
WORDS
KARMA
25 ?

## Popular in Engineering Computer Science

This 15 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 203 at University of Michigan taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/231553/eecs-203-university-of-michigan in Engineering Computer Science at University of Michigan.

×

## Reviews for Discrete Math

×

×

### 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: 10/29/15
Recursive de nitions of sets 0 We saw last time how to de ne the set of proposi tional expressions recursively o The method extends to other kinds of sets Let S be the subset of N de ned by the following rules 1 3 E S 2 imeSandyESthenstryES 3 No number is in S unless it can be shown to be there using 1 and 0 Example 3 Srule1 63368by1andrule2 96SESby2 andrule2 Using induction along with recursive de nitions Proposition The set S on the last sltde ts the set of postttve multiples of 5 Proof Let P be the set of positive multiples of 3 We show P g S and S g P For the rst inclusion7 we show that every integer of the form 3717 for n 2 17 is in S We do this by induction on n Basis When n 17 the number 3 1 E S by rule 1 Induction step Assume that 3k is in S We want 3k 1 E S But 3k l 3k 3 By inductive hypothesis 3k E S7 and 3 is already in S7 so 3k 3 E S by rule 2 Proof continued S g P To show this7 we rely on rule 37 which says nothing is in S unless you can show it in a nite number of uses of rules 1 and 2 Let n be the number of uses of these rules We show by induction on n that the integer proved to be in S is in fact a positive multiple of 3 Basis We just apply one rule7 which has to be rule 1 This rule shows 3 E S7 and 3 is a positive multiple of 3 Induction step strong form Assume that when ever we show that p E S by using k or fewer steps7 then p is a positive multiple of 3 Consider a proof using k 1 steps The last rule used in this proof is rule 27 which says that if 13 and y are in S7 so is 33 11 Now 13 was shown in S by g k steps7 and so was y By inductive hypothesis twice7 we know that 13 and y are positive multiples of 37 and therefore so is a y Relations Chapter 6 o lntuitively7 relations are properties that hold among things in a world 0 For example loves uncleof friend of left of small 0 All except the last of these hold between two things They are called binary relations Small is a unamy relation 0 You can also have ternary relations7 etc Relations involving more than one world 0 For example7 students and courses John EECSSOS Ed EECS 37 6 John EECS28O Mary Math606 Mary Math747 Paul Math747 John Math606 0 You can look at each row of the table as an ordered pair7 and the table as a set of ordered pairs 0 That7s the o icial de nition of binary relation be tween two sets77 Of cial Relation De nitions 0 De nition Let AB be sets A binary relation between A and B is a subset R of A x B A binary relation on A is a subset ofA X A 0 Example S J0hn Ed Mary Paul C E203 E376 E280 M606 M747 ENROLLED John E203 John E376 Ed E280 Mary M606 Mary M747 Paul M747 0 The relation ENROLLED g S X C 0 Notation we write a B b to mean 11 E B Thus John ENROLLED E376 Picturing Relations COU RS ES STU D ENTS EECS203 J h EECSS76 Ed EECSZSO Mary Math606 Math747 Paul Enrollment a relation between students and courses EECSZOS EECS376 EECS EECSZBO 39 ath Math606 Ling Math747 COURSES DEPARTMENTS quotOfferedbyquot a relation between courses and departments Array matrix representation of relations 0 The enrolled information can be presented SC E203 E376 E280 M606 M747 John 1 1 O O 0 Paul O O O O 1 Mary 0 O O 1 1 Ed 0 O 1 O O o This can be seen as a function from S X C to 0 1 1 if 56 E ENR 0 otherwise FENRltS C Relations as maps to a powerset o A relation from A to B can be thought of as a func tion from A to 733 John H E203 E376 Paul gt M 606 Mary H M606 M747 Ed H E280 c There are lots of mathematical ways to model rela tions Relations on a set 0 The set can be in nite 0 Example A N DIV m n m divides 0 Some ordered pairs 11036420 0 We write m I n to indicate that mm E DIV Thus110 36 420 o The less than or equal td7 relation on R is another example of a binary relation on an in nite set Picturing a relation on a nite set A Don tneedtwocopiesof theset A V SupposeAabcdeand Rdadcabbcbeee JustworkwithonecopyofA Properties of Relations on a set 0 De nition A binary relation R on a set A is said to be reflexive if Va E Aa R a o In terms of the graph picture7 there is a self loop at every node 0 O 0 Example On every set A there is the identity relation idA aa la E A o Other examples the less than or equal td7 relation 3 on R the subset relation on 73X7 because Y g Y for any set Y the divides relation on N5 Symmetric Relations 0 De nition A binary relation R on a set A is said to he symmetric if VabEAaRb gtbRa o In terms of pictures Symmetric Not Symm elric Got Symmetric 0 Example The mutual friend 0 relation is symmetric The sister relation isn t The sib ling relation is The identity relation is The relation isn t 77 Transitive Relations 0 De nition A binary relation R on a set A is said to be transitive if Vabc AaRbbRc gtaRc o The pictures This picture holds evenwhere This is ok This isn t

×

×

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

Kyle Maynard Purdue

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made \$280 on my first study guide!"

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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