Cell Phones in the Hands of Drivers: A Risk or a Benefit?
26
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
26
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
- cours - matière potentielle : name
- expression écrite
- scientific reports on the relation between cell phone use
- highway traffic safety administration
- reckless driving
- cell phones
- drivers
- laws
- road
- use
Discrete Mathematics
Lecture 5
Harper Langston
New York UniversityEmpty Set
2• S = {x ˛ R, x = -1}
• X = {1, 3}, Y = {2, 4}, C = X ˙ Y
(X and Y are disjoint)
• Empty set has no elements ˘
• Empty set is a subset of any set
• There is exactly one empty set
• Properties of empty set:
– A ¨ ˘ = A, A ˙ ˘ = ˘
c c– A ˙ A = ˘, A ¨ A = U
c c– U = ˘, ˘ = USet Partitioning
• Two sets are called disjoint if they have no
elements in common
• Theorem: A – B and B are disjoint
• A collection of sets A , A , …, A is called 1 2 n
mutually disjoint when any pair of sets from this
collection is disjoint
• A collection of non-empty sets {A , A , …, A } is 1 2 n
called a partition of a set A when the union of
these sets is A and this collection consists of
mutually disjoint setsPower Set
• Power set of A is the set of all subsets of A
• Example on board
• Theorem: if A ˝ B, then P(A) ˝ P(B)
• Theorem: If set X has n elements, then
nP(X) has 2 elements (proof in Section 5.3
– will show if have time)Cartesian Products
• Ordered n-tuple is a set of ordered n
elements. Equality of n-tuples
• Cartesian product of n sets is a set of n-
tuples, where each element in the n-tuple
belongs to the respective set participating
in the productÛ
Û
Ù
Û
Û
Ù
Ú
Û
à
Ù
Ù
Set Properties
• Inclusion of Intersection:
A ˙ B ˝ A and A ˙ B ˝ B
• Inclusion in Union:
A ˝ A ¨ B and B ˝ A ¨ B
• Transitivity of Inclusion:
(A ˝ B B ˝ C) A ˝ C
• Set Definitions:
x ˛ X ¨ Y x ˛ X y ˛ Y
x ˛ X ˙ Y x ˛ X y ˛ Y
x ˛ X – Y x ˛ X y ˇ Y
cx ˛ X x ˇ X
(x, y) ˛ X · Y x ˛ X y ˛ YSet Identities
• Commutative Laws: A ˙ B = A ˙ B and A ¨ B = B ¨ A
• Associative Laws: (A ˙ B) ˙ C = A ˙ (B ˙ C) and (A ¨ B) ¨ C = A ¨ (B ¨
C)
• Distributive Laws:
A ¨ (B ˙ C) = (A ¨ B) ˙ (A ¨ C) and A ˙ (B ¨ C) = (A ˙ B) ¨ (A ˙ C)
• Intersection and Union with universal set: A ˙ U = A and A ¨ U = U
c c• Double Complement Law: (A ) = A
• Idempotent Laws: A ˙ A = A and A ¨ A = A
c c c c c c• De Morgan’s Laws: (A ˙ B) = A ¨ B and (A ¨ B) = A ˙ B
• Absorption Laws: A ¨ (A ˙ B) = A and A ˙ (A ¨ B) = A
c• Alternate Representation for Difference: A – B = A ˙ B
• Intersection and Union with a subset: if A ˝ B, then A ˙ B = A and A ¨ B =
BProving Equality
• First show that one set is a subset of
another (what we did with examples
before)
• To show this, choose an arbitrary
particular element as with direct proofs
(call it x), and show that if x is in A then x
is in B to show that A is a subset of B
• Example (step through all cases)Disproofs, Counterexamples and
Algebraic Proofs
• Is is true that (A – B) ¨ (B – C) = A – C?
(No via counterexample)
• Show that (A ¨ B) – C = (A – C) ¨ (B – C)
(Can do with an algebraic proof, slightly
different)Boolean Algebra
• A Boolean Algebra is a set of elements
together with two operations denoted as +
and * and satisfying the following
properties:
Commutative: a + b = b + a, a * b = b * a
Associative: (a + b) + c = a + (b + c), (a * b) *c = a * (b * c)
Distributive: a + (b * c) = (a + b) * (a + c), a * (b + c) = (a *
b) + (a * c)
Identity: a + 0 = a, a * 1 = a for some distinct unique 0 and
1
Complement: a + ã = 1, a * ã = 0
