Transcript discrete structures

DISCRETE STRUCTURES
LOGICAL STRUCTURE
• Logic - study of reasoning
- focuses on the relationship among statements
as opposed to the content of any particular statement.
Logical methods are used in mathematics to prove
theorems and in computer science to prove that
programs do what they are alleged to do.
ex.
All mathematicians wear sandals.
Anyone who wears sandals is an algebraist.
Therefore, all mathematicians are algebraist.
LOGICAL STRUCTURE
Propositions – A sentence that is either true or
false, but not both.
Examples:
• 1+1=3
• 2+2=4
- A fact-based declaration is a proposition,
even if no one knows whether it is true.
LOGICAL STRUCTURE
- A statement cannot be true or false unless it is
declarative. This excludes commands and
questions.
examples:
• What time is it?
• Go home.
LOGICAL STRUCTURE
Definition
Let p and q be propositions
• The conjunction of p and q, denoted by p ᴧ q,
is the proposition p and q
• The disjunction of p and q, denoted p ᴠ q, is
the proposition p or q
LOGICAL STRUCTURE
Compound proposition – combination of
propositions
Example :
p: 1+1 = 3
q: a decade is 10 years
then:
conjunction: p ᴧ q : 1+1 = 3 and a decade is 10
years.
disjunction: p ᴠ q : 1+1 = 3 or a decade is 10 years
LOGICAL STRUCTURE
Each sentence or the propositions has a truth
value of either true or false. The truth values
of propositions can be described by truth
tables.

LOGICAL STRUCTURE
Definition
The truth value of the compound proposition
p ᴧ q is defined by the truth table
p q pᴧq
T T T
T F F
F T F
F F F
- states that the conjunction p ᴧ q is true provided
that p and q are both true; p ᴧ q is false
otherwise.
LOGICAL STRUCTURE
Definition
The truth value of the compound proposition p ᴠ q is
defined by the truth table
p
q
pᴠq
T
T
T
T
F
T
F
T
T
F
F
F
- states that the disjunction p ᴠ q is true if either p or q
or both are true; false if both p and q are false
LOGICAL STRUCTURE
Definition
The negation of p denoted by ¬p is the proposition not p.
The truth value of the proposition ¬p is defined by the
truth table
p
¬p
T
F
F
T
In other words, the negation of a proposition has the
opposite truth value from the proposition itself.
LOGICAL STRUCTURE
Example
p: Blaise Pascal invented several calculating
machines.
q: The first all-electronic digital computer was
constructed in the 20th century.
r: П was calculated to 1M decimal digits in 1954
LOGICAL STRUCTURE
• represent the proposition:
Either Blaise Pascal invented several
calculating machines and it is not the case
that the first all electronic digital computer
was constructed in the 20th century; or П was
calculated to 1M decimal digits in 1954.
LOGICAL STRUCTURE
Definition:
If p and q are propositions, the compound
propositions if p then q is called conditional
proposition and is denoted by p→ q.
• The proposition p is called the hypothesis (or
antecedent) and the proposition q is called
the conclusion (or consequent)
LOGICAL STRUCTURE
example:
p: The Math Dept. gets an additional Php 200,00.
q: The Math Dept. hires one new faculty member
p→ q: If the Math Dept. gets an additional
Php 200,000, then it will hire one new faculty
member.
LOGICAL STRUCTURE
p→ q
• if p then q
• p implies q (q is implied by p)
• whenever p, q (q whenever p)
• q unless ¬p
• p only if q (if not q then not p)
• ¬q implies ¬p
• p is a sufficient condition for q
• q is a necessary condition for p
LOGICAL STRUCTURE
examples
1. If 3+3=7, then you are the pope.
2. If the Lakers win the NBA, then they sign Artest.
A necessary condition for the Lakers to win the
NBA is that they sign Artest.
3. If John takes calculus, then he passed algebra.
John may take calculus only if he passed algebra.
4. If Jane goes to EK, then she visits Laguna.
A sufficient condition for Jane to visit Laguna is
that she goes to EK.
LOGICAL STRUCTURE
Definition:
The truth value of the conditional proposition
p→ q is defined by the following truth table.
p
q
p→q
T
T
T
T
F
F
F
T
T
F
F
T
LOGICAL STRUCTURE
Examples:
1. p: 1>2
False
q: 4<8
True
p→ q
?
q→ p
?
2. Given p is true, q is false, r is true, find the truth
value of:
a. (pᴧq)→r
b. (pᴠq)→¬r
LOGICAL STRUCTURE
NOTE:
• Converse: The proposition q→ p is the converse
of the proposition p→ q.
• Inverse: The proposition ¬p→¬q is the inverse of
the proposition p→ q.
• Contrapositive: The contrapositive (or
transposition) of the conditional proposition
p→ q is the proposition ¬q→¬p.
LOGICAL STRUCTURE
Example:
“The home team wins whenever it is raining”
(“If it is raining, then the home team wins.”)
Converse: “ If the home team wins, then it is
raining.”
Inverse: “ If it is not raining, then the home team
does not win.”
Contrapositive: “If the home team does not win,
then it is not raining.”
LOGICAL STRUCTURE
Definition
If p and q are propositions, the compound
proposition p if and only if q is called a
biconditional proposition and is denoted by
p↔ q.
LOGICAL STRUCTURE
p↔ q
• p is equivalent to q
• p iff q
• p is a sufficient and necessary condition for q
• p →q and q→ p (p implies q and q implies p)
LOGICAL STRUCTURE
Definition
The truth value of the proposition p↔ q is
defined by the following truth table.
p
q
p↔q
T
T
T
T
F
F
F
T
F
F
F
T
Example: 1<5 iff 2<8
LOGICAL STRUCTURE
Derfinition
Suppose that the compound propositions P
and Q are made up of the propositions
p1,p2,…,pn . We say that P and Q are logically
equivalent and write P ≡ Q , provided that
given any truth values of p1,p2,…,pn , either P
and Q are both true or P and Q are both false.
LOGICAL STRUCTURE
example:
1. De Morgan’s Laws for Logic
¬ (pᴠq) ≡ ¬p ᴧ ¬q
2. ¬(p→q) ≡ pᴧ¬q
3. State whether P ≡ Q
a. P = pᴧ(¬qᴠr) ; Q = pᴠ(qᴧ¬r)
b. P = (p→q)→r ; Q = p→(q→r)
Note: The conditional proposition p→q and its
contrapositive ¬q→¬p are logically equivalent.
LOGICAL STRUCTURE
Exercises:
A. Let p,q,r be the following sentences
p: John is at the office.
q: Joan is at the office.
r: Laura is at the office.
Use logical connectives to express the following
sentences:
1. John is not at the office.
2. If Joan and Laura are at the office then John is at
the office.
LOGICAL STRUCTURE
3. If John is at the office then either Joan or Laura
is at the office.
4. John, Joan and Laura are all at the office.
5. Joan is not at the office and either John or
Laura are at the office.
6. If Laura is not at the office then John and Joan
are both at the office.
LOGICAL STRUCTURE
B. Translate the following into logical expression.
1. “ You can access the internet from campus
only if you are a computer science major or
you are not a freshman.”
2. “ You cannot ride the roller coaster if you are
under 4 feet tall unless you are older than 16
years old.”
LOGICAL STRUCTURE
C. Solve a Crime
Four friends have been identified as suspects for
an unauthorized access into a computer system.
They have made statements to the investigating
authorities. Alice said “Carlos did it.” John said “ I
did not do it .” Carlos said “ Diana did it.” Diana
said “Carlos lied when he said that I did it.”
If the authorities also know that exactly one of the
four suspects is telling the truth, who did it?
LOGICAL STRUCTURE
Theorem
The following list of logically equivalent
properties can be established using truth tables.
1. Indempotent Laws
pᴧp ≡ p
pᴠp ≡ p
2. Double Negation
¬(¬p) ≡ p
3. De Morgan’s Laws
¬ (pᴠq) ≡ ¬p ᴧ ¬q
¬ (pᴧq) ≡ ¬p ᴠ ¬q
4. Commutative properties
pᴧq ≡ qᴧp
pᴠq ≡ qᴠp
LOGICAL STRUCTURE
5. Associative properties
pᴧ(qᴧr) ≡ (pᴧq)ᴧr
pᴠ(qᴠr) ≡ (pᴠq)ᴠr
6. Distributive properties
pᴧ(qᴠr) ≡ (pᴧq)ᴠ(pᴧr)
pᴠ(qᴧr) ≡ (pᴠq)ᴧ(pᴠr)
7. Equivalence of Contrapositive
p→q ≡ ¬q→¬p
8. Other useful properties
p→q ≡ ¬pᴠq
p↔q ≡ (p→q)ᴧ(q→p)
LOGICAL STRUCTURE
QUANTIFIERS
Definition
Let P(x) be a statement involving the variable x
and let D be a set. We call P a propositional
function (with respect to D) if for each x in D,
P(x) is a proposition. We call D the domain of
discourse of P.
LOGICAL STRUCTURE
P(x): value of the propositional function P of x.
Example:
“x>5” these statement is not a proposition
because whether it is true or false depends on
the value of x.
Once a value has been assigned to the variable
x, the statement P(x) becomes a proposition
and has a truth value.
LOGICAL STRUCTURE
In general, a statement involving n variables x1,
x2,…,xn can be denoted by P(x1, x2,…,xn ). A
statement of the form P(x1, x2,…,xn ) is the value
of the propositional function P at the n-tuples
(x1, x2,…,xn ) and P is also called a predicate.
LOGICAL STRUCTURE
To create proposition from a propositional
function:
• Assign values to the variables
• Quantification
types: 1. universal quantification
2. existential quantification
LOGICAL STRUCTURE
Definition
The universal quantification of P(x) is the proposition
“P(x) is true for all values of x in the domain of
discourse.”
Notation:
• xP(x) denotes the universal quantification of P(x)
•  called the universal quantifier
• xP(x) read as “for all x P(x)” ; “for every x P(x)”
• true if P(x) is true for every x
• false if P(x) is false for at least one x in the Domain
LOGICAL STRUCTURE
Examples: Domain for x is the set of real numbers
1. P(x): “x+1>x”
2. P(x): “x>5”
3. Q(x): “x2 >= x”
Note: xP(x) is false if P(x) is false for at least one
x in D. A value x in the domain of discourse
that makes P(x) false is called a
counterexample to the statementxP(x) .
LOGICAL STRUCTURE
Definition
The existential quantification of P(x) is the
proposition “There exist an element x in the
domain of discourse such that P(x) is true.
Notation:
• xP(x) denotes the existential quantification of x
•  is called the existential quantifier
• xP(x) read as “there is an x s.t. P(x)”
“there is at least one x s.t. P(x)”
“for some x, P(x)”
LOGICAL STRUCTURE
• true if P(x) is true for at least one x in the
domain
• false if P(x) is false for every x in the domain
Examples: Domain is the set of real numbers
1. P(x): x>3
2. Q(x): x = x+1
x
3. P(x): x  1
2
LOGICAL STRUCTURE
Exercises. Give the domain.
2

x
(
x
 1)
1.
2.
True or False. Domain is the set of integers.
P(x): x>2
Q(x): x<2
1.
2.
LOGICAL STRUCTURE
Negation with Quantifiers
xP( x)  x P( x)
example
xP(x) : Every student in the class has taken a course in
P(x)
calculus.
:“x has taken a course in calculus”
Negation ofxP(x) : xP(x)
• It is not the case that every student in the class has taken a
course in calculus.
• There is a student in the class who has not taken a course in
calculus.
: x P(x)
LOGICAL STRUCTURE
xQ( x)  xQ( x)
Example
xQ(x) :There is a student in this class who has taken
a course in calculus.
Q(x)
:“x has taken a course in calculus”
xQ( x) : xQ( x)
Negation of
• It is not the case that there is a student in this class
who has taken a course in calculus.
• Every student in this class has not taken calculus.
: xQ(x)
LOGICAL STRUCTURE
RULES of INFERENCE
Definition (Argument)
An argument is a sequence of propositions
written as. The propositions p1,p2,…,pn are
called the hypotheses (or premises), and the
proposition q is called the conclusion. The
argument is valid provided that if p1 andp2 and
pn are all true, then q must also be true;
otherwise, the argument is invalid (or a fallacy).
LOGICAL STRUCTURE
Rules of inference- brief and valid argument used
within a larger argument such as proof
Example
Determine whether the argument is valid.
p→q
p
q
D:\DiscreteMath\QUANTIFIERS.doc
LOGICAL STRUCTURE
Example (A Logical Argument)
If I dance all night, then I get tired.
I danced all night.
Therefore I got tired.
Logical representation of the underlying variables:
p: I dance all night.
q: I get tired.
Logical analysis of the argument:
p→q
p
q
LOGICAL STRUCTURE
If I dance all night, then I get tired.
I got tired.
Therefore I danced all night.
Logical form of argument:
p→q
q
 p
LOGICAL STRUCTURE
Examples:
1. Show that the hypotheses “ If you send me an
email message, then I will finish writing the
program,” If you do not send me an email
message, then I will go to sleep early,” and “If I
go to sleep early, then I will wake up feeling
refreshed “ lead to the conclusion “If I do not
finish writing the program, then I will wake up
feeling refreshed.”
LOGICAL STRUCTURE
2. Show that the hypotheses "It is not sunny this
afternoon and it is colder than yesterday," "We
will go swimming only if it is sunny," "If we do
not go swimming, then we will take a canoe
trip, " and " If we take a canoe trip, then we will
be home by sunset" lead to the conclusion "We
will be home by sunset. "
FUNCTIONS
FUNCTIONS
Definition
Let A and B be sets. A function f from A to B
is an assignment of exactly one B element to
each element of A . We write f(a)=b if b is
the unique element of B assigned by the
function f to the element a of A. If is a
function from A to B, we write f:A→B.
FUNCTIONS
Definition
If f is a function from A to B, we say that A is
the domain of f and B is the codomain of f.
If f(a)=b, we say that b is the image of a and
a is a pre-image of b. The range of f is the set
of all images of elements of A. Also, if f is a
function from A to B , we say that f maps A
to B .
FUNCTIONS
A function f from A to B is said to be one-toone, or injective if for each bϵ B, there is at
most one aϵA with f(a)=b. A function is said
to be an injection if it is one-to-one.
A function f from A to B is called onto, or
surjective if and only if for every element bϵB
there is an aϵA element with f(a)=b . A
function is said to be surjection if it is onto.
FUNCTIONS
The function f is a one-to-one correspondence,
or bijection, if it is both one-to-one and onto.
Example:Let S={1,2,3,4,5} and T={a,b,c,d}. For each
question below if your answer is yes, give an
example; if your answer is no, explain briefly.
1. Are there any one-to-one functions from S to T?
2. Are there any functions mapping S onto T?
3. Are there any one-to-one correspondences
between S and T?
FUNCTIONS
Definition(Inverse)
Let f be a one-to-one correspondence from
the set A to the set B. The inverse function of
f is the function that assigns to an element b
belonging to B the unique element a in A
such that f(a)=b . The inverse function of f is
denoted by f¯¹. Hence, f¯¹ (b)=a when f(a)=b .
FUNCTIONS
Definition(Composition)
Let g be a function from the set A to the set
B and let f be a function from the set B to the
set C. The composition of the functions f and
g , denoted by f◦g
is defined by
(f◦g)(a)=f(g(a)).
(not defined unless the range of g is a subset of
the domain of f)
FUNCTIONS
Examples: Let A= {1,2,3,4,5} B={6,7,8,9}
C={10,11,12,13} D={□,∆,◊,∂}
Let R  AxB, S  BxC and T  CxD be defined by
R = {(1,7),(4,6),(5,6),(2,8)}
S = {(6,10),(6,11),(7,10),(8,13)}
T = {(11, ∆),(10, ∆),(13, ∂),(12, □),(13, ◊)}
Compute the relations
FUNCTIONS
Definition
The floor function that assigns to the real
number x is the largest integer that is less
than or equal to x . The value of the floor
function at is denoted by Lx˩ . The ceiling
function assigns to the real number x the
smallest integer that is greater than or equal
to x. The value of the ceiling function at is
denoted by Гx˥.
COMBINATORIAL STRUCTURES
COUNTING
Examples
1. How many positive integers of two different
digits can be formed from the integers 1,2,3,
and 4?
2. How many different arrangements of six
distinct books each can be made on a shelf
with space for six books?
COUNTING
Multiplication Principle
If an activity can be constructed in t
successive steps and step1 can be done in n1
ways, step 2 can be done in n2 ways, … , and
stept can be done in nt ways, then the
number of different possible activities is
n1∙n2∙∙∙nt
COUNTING
Example
Given:
APPETIZERS
Nachos
MAIN COURSES BEVERAGES
Hamburger
Tea
Salad
Cheeseburger
Fish Fillet
Milk
Soda
Root Beer
1. List all possible dinners consisting of one main
course and one beverage.
2. List all possible dinners consisting of one
appetizer, one main course and one beverage.
3. List all possible dinners consisting of one main
course and an optional beverage.
COUNTING
Examples
1. How many different arrangements of each
consisting of four different letters can be
formed from the letters of the word
“PERSONAL” if each arrangement is to begin
and end with a vowel.
2. Suppose that three of six books are math
books and three are art books.
a. How many different arrangements of the six
books can be made on the shelf if book on the
same subject are to be kept together?
COUNTING
b. How many different arrangements of the
six books can be made on the shelf if math
books are to be kept together but three art
books can be placed anywhere?
3. In how many ways can we select two books
from different subjects among five distinct
computer science books, three distinct math
books and two distinct art books?
COUNTING
Definition (Permutation)
A permutation of n distinct elements x1,…,xn is
an ordering of the n elements x1,…,xn .
COUNTING
Definition (Permutation)
Let S be a set containing n elements and
suppose r is a positive integer such that r≤n .
Then a permutation of r elements of S is an
arrangement in a definite order, without
repetitions, of r elements of S .
notations: nPr; P(n,r); Pn,r ;
“permutations of n taken r”
COUNTING
Theorem
The number of permutations n of elements
taken r at a time is given by either of the
following formulas:
a. nPr = n(n-1)(n-2)…(n-r+1)
b. nPr = n!/(n-r)!
COUNTING
Example
1. A bus has seven vacant seats. If three
additional passengers enter the bus, in how
many ways can they be seated?
2. In how many ways can four boys and four
girls be seated in a row containing eight
seats if
a) a person may sit in any seat
b) boys and girls must alternate seats
COUNTING
Theorem
If we are given n element, of which exactly m1
are alike of one kind, exactly m2 are alike of a
second kind, …, and exactly mk are alike of the
kth kind, and if n = m1 + m2 +…+ mk then the
number of distinguishable permutations that
can be made of the n elements taking them all
n!
at one time is
.
m1! m2 !...mk !
COUNTING
Example
1. How many strings can be formed using the
following letters MISSISSIPPI?
2. How many different signals each consisting of
eight flags hung one above the other , can be
formed from a set of three indistinguishable
red flags, two indistinguishable blue flags,
two indistinguishable white flags and one
black flag?
COUNTING
Definition(Combination)
Let S be a set containing n elements and
suppose r is a positive integer such that r < n.
Then a combination of r elements of S is a
subset of S containing r distinct elements.
COUNTING
Theorem
The number of combinations of n elements
taken r at a time is given by
nCr = nPr / r!
= n! /(n-r)! r!
COUNTING
Example
1. A football conference consists of eight
teams. If each team plays every other team,
how many conference games are played?
2. A student has ten posters to pin up on the
walls of her room, but there is space for
only seven. In how many ways can the
student choose the posters to be pinned
up?
COUNTING
3. In how many ways can we select a committee of
two women and three men from a group of 5
distinct women and 6 distinct men?
4. How many poker hands contain cards all of
the same suit?
5. From 6 history books and 8 language books,
in how many ways can a person select two
history books and three language books and
arrange them on a shelf?
COUNTING
Binomial Theorem
If n is any positive integer, then
a  b n C0a n C1a
n
n
n1
n2 2
nr r
bn C2a b  ...n Cr a b  ...n Cnb
n
PROBABILITY
PROBABILITY
•
•
•
•
Random experiment
Sample space
Event as a subset of sample space
Likelihood of an event to occur- probability of
an event
PROBABILITY
Features of a Random Experiment
• all outcomes are known in advance.
• The outcome of any one trial cannot be
predicted with certainty.
• Trials can be repeated under identical
conditions.
PROBABILITY
Examples (Random Experiment)
• Rolling a die and observing the number of dots
on the upturned face.
• Tossing a coin and observing the upturned
face.
PROBABILITY
Sample Space
It is a set such that each element denotes an
outcome of a random experiment.
It is usually denoted by Ω or S.
Example.
Rolling a die and observing the number of dots
on the upturned face.
S = {1,2,3,4,5,6}
PROBABILITY
Event
A subset of the sample space whose
probability is defined.
Example
S = {1,2,3,4,5,6}
a. An event of observing odd number of dots in
a roll of a die : E1 = {1,3,5}
b. An event of observing even number of dots in
a roll of a die : E2 = {2,4,6}
PROBABILITY
Two events are mutually exclusive if the two
events cannot occur simultaneously.
Example
Coin toss: either a head or a tail, but not both.
The events head and tail are mutually
exclusive.
PROBABILITY
Definition(Probability)
The probability of an event E , which is a
subset of a finite sample space S of equally
likely outcomes is P(E) = |E|/|S|
note: A probability function P assigns to each
outcome x in a sample space S a number P(x)
so that 0 < P(x) < 1 for all x in S and
∑ P(x) = 1 .
PROBABILITY
Example:
If we select a card at random from a well
shuffled deck of cards then,
P(ace in a deck of cards)= 4/52
Note: Probability of a joint event, A and B
P(A and B) = P(A∩B)
Example
P(red card and Ace) = 1/26
PROBABILITY
Theorems
1. Let E be an event. The probability of Ē, the
complement of E , satisfies P(E) +P(Ē) = 1 .
2. Let E1 and E2 be events. Then
P(E1 U E2) = P(E1) + P(E2) – P(E1∩ E2)
note: If E1 and E2 are mutually exclusive
events, P(E1 U E2) = P(E1) + P(E2)
PROBABILITY
Exercises
1. Find errors in each of the ff assignments of
probabilities.
a. The probabilities that a student will have 0,1,2, or
3 or more mistakes are 0.51, 0.47, 0.24, and -0.12
respectively.
b. The probability that it will rain tomorrow is 0.46
and the probability that it will not rain tomorrow
is 0.55.
PROBABILITY
2. P(King or Spade)
3. P(King or Queen)
4. If two dice are thrown, what is the probability
of obtaining sum of 7? of 5?
5. What is the probability of obtaining a sum of 7
or 5 if the two dice are thrown?
PROBABILITY
Definition(Conditional Probability)
Let E and F be events with P(F)>0. The
conditional probability of E given F ,
denoted by P(E|F) is defined as
P(E|F) = P(E∩F)/P(F)
note: If E and F are independent events
P(E) = P(E|F)
The events E and F are independent if and
only if: P(E∩F) = P(E)P(F)
PROBABILITY
From a deck of 52 cards, P(Ace|red) = ?
A Deck of 52 cards
Type
Ace
Non-Ace
Total
Color
Red
Black
2
2
24
24
26
26
Total
4
48
52
PROBABILITY
Example:
What is the probability of getting a sum of 10,
given that at least one die shows 5, when two
fair dice are rolled?
PROBABILITY
Solution:
Let E be the event of getting a sum of 10
F be the event that at least one die shows 5
P(E∩F) – probability of getting a sum of 10 and
at least one die shows 5
PE  F 1 36
1
PE | F 


PF
11 36 11
PROBABILITY
Example:
Weather records shows that the probability of
high barometric pressure is 0.80, and the
probability of rain and high barometric
pressure is 0.10. What is the probability of rain
given high barometric pressure?
PROBABILITY
Solution:
R – denotes the event of “rain”
H – denotes the event of “ high barometric
pressure”
PR  H 0.10 1
PR | H 


PH
0.80 8
PROBABILITY
Example (Independent Events)
1. Tossing a coin: What is the probability that
head on first toss and tail on second?
2. Are the events that a family with 3 children
has children of both sexes, and that a family
with three children has at most one boy,
independent? Assume that the eight ways a
family can have 3 children are equally likely.
PROBABILITY
3. Joe and Olivia take a final exam in discrete
structures. The probability that Joe passes is
0.70 and the probability that Olivia passes is
0.95. Assuming that the events “Joe passes”
and “Olivia passes” are independent, find the
probability that Joe or Olivia passes or both
passes the final exam?
PROBABILITY
Baye’s Theorem
Suppose that the possible classes are C1,…,Cn.
Suppose further that each pair of classes is
mutually exclusive and each item to be
classified belongs to one of the classes. For a
feature set F, we have


P Cj | F 

 
P F | Cj P Cj
n
 PF | C PC 
i
i 1
i
PROBABILITY
Example
1. At a call center company, David, Rose, and Lea
make calls. The following table shows the
percentage of calls each caller makes and the
percentage of persons who are annoyed and
hang up on each call.
Caller
% calls
% hang ups
David
40
20
Rose
25
55
Lea
35
30
PROBABILITY
Let D – event “David made the call”
R – event “Rose made the call”
L – event “Lea made the call”
H - event “the caller hang up”
Find P(D), P(R), P(L), P(H|D), P(H|R), P(H|L),
P(D|H), P(R|H), P(L|H), P(H).
PROBABILITY
2. The sample space S is described as “the integers 1
to 15” and is partitioned into:
E1 – “the integers 1 to 8”
E2 – “the integers 9 to 15”
If E is the event “even number”, what is P(E1|E)?
3.Of all the smokers in a town, 40% prefer brand A
and 60% prefer brand B. Of those smokers who
prefer brand A, 30% are female, and of those who
prefer brand B, 40% are female. What is the
probability that a randomly selected smoker
prefers brand A, given that the person selected is
female.
Pigeonhole Principle
Pigeonhole Principle (Dirichlet drawer principle)
Suppose that a flock of pigeons flies into a set
of pigeonholes to rest. The pigeonhole
principle states that if there are more pigeons
than pigeonholes, then there must be at least
one pigeonhole with at least two pigeons in it.
Theorem
If k+1 or more objects are placed into k boxes,
then there is at least one box containing two
or more objects.
Pigeonhole Principle
Examples
1. Among any group of 367 people, there must
be at least two with the same birthday.
2. In any group of 27 English words, there must
be at least two that begin with the same
letter.
3. How many students must be in a class to
guarantee that at least two students receive
the same score on the final exam, if the exam
is graded on the scale from 0 to 100 points?
Pigeonhole Principle
4. Each week a man goes to a shopping center
where there are seven stores, and shops at
two of the stores. If he goes to the shopping
center for 43 weeks, prove that he must shop
at some pair of stores at least three times.