Transcript class01

Textbook
Discrete Mathematics and Its Applications,
Rosen
6th Edition
McGraw Hill
2006
CSci 2011
Overview
Much of the basic mathematical machinery useful in
computer science will be presented, with
applications.
Students will learn actively the art of creating realworld proofs in these areas,
 preparing them for diverse regions of computer science
such as architecture, algorithms, automata, programming
languages, cryptography, and
 increasing their general problem-solving abilities in all areas.
CSci 2011
Problems solved using Discrete Math
How many secure passwords?
Probability of winning Texas Hold’em?
How can I encrypt a message?
Shortest paths between two cities using public
transportation?
How many steps required to sort 10,000 numbers?
Is this algorithm correct?
How to design a circuit that multiply two integers?
CSci 2011
Why study Discrete Maths?
Proof
Ability to understand and create mathematical
argument
Gateway to more advanced CS courses
Data structures, algorithms, automata theory,
formal languages
Database, networks, operating system, security
CSci 2011
Course content
very approximately in temporal order
Ch.
Ch.
Ch.
Ch.
Ch.
Ch.
Ch.
1:
2:
3:
4:
5:
6:
8:
Logic and Proofs
Sets, Functions, Sequences and Sums
Algorithms, the Integers, and Matrices
Induction and Recursion
Counting
Discrete Probability
Relations
CSci 2011
Propositions
A proposition is a statement that can be
either true or false
“Yongdae has an Apple laptop.”
“Yongdae is a professor.”
“3 = 2 + 1”
“3 = 2 + 2”
Not propositions:
“Are you Bob?”
“x = 7”
“I am heavy.”
CSci 2011
Propositional variables
We use propositional variables to refer to
propositions
Usually are lower case letters starting with p (i.e.
p, q, r, s, etc.)
A propositional variable can have one of two
values: true (T) or false (F)
A proposition can be…
A single variable: p
An operation of multiple variables: p(qr)
CSci 2011
Introduction to Logical Operators
About a dozen logical operators
Similar to algebraic operators + * - /
In the following examples,
p = “Today is Friday”
q = “Today is my birthday”
CSci 2011
Logical operators: Not
A “not” operation switches (negates) the
truth value
Symbol:  or ~
p
p
p = “Today is not Friday”
T
F
F
T
CSci 2011
Logical operators: And
An “and” operation is true if both operands
are true
Symbol: 
It’s like the ‘A’ in And
pq = “Today is Friday and
today is my birthday”
p
q
pq
T
T
T
T
F
F
F
T
F
F
F
F
CSci 2011
Logical operators: Or
An “or” operation is true if either operands
are true
Symbol: 
pq = “Today is Friday or
today is my birthday (or
possibly both)”
p
q
pq
T
T
T
T
F
T
F
T
T
F
F
F
CSci 2011
Logical operators: Conditional 1
A conditional means “if p then q”
Symbol: 
pq = “If today is
p
q
Friday, then today
T
T
is my birthday”
T
F
p→q=¬pq
the
antecedent
pq
T
F
F
T
T
F
F
T
the
consequence
CSci 2011
Logical operators: Conditional 2
Let p = “I am elected” and q = “I will lower taxes”
I state: p  q = “If I
am elected, then I
will lower taxes”
Consider all
possibilities
p
q
pq
T
T
T
T
F
F
F
T
T
F
F
T
Note that if p is false, then
the conditional is true regardless of whether q is
true or false
CSci 2011
Logical operators: Conditional 3
Alternate ways of stating a conditional:
p implies q
If p, q
p only if q
p is sufficient for q
q if p
q whenever p
q is necessary for p
CSci 2011
Logical operators: Conditional 4
Conditional
Inverse
Converse
Contrapositive
p q
p
q
pq
pq
qp
qp
T T
F
F
T
T
T
T
T F
F
T
F
T
T
F
F T
T
F
T
F
F
T
F F
T
T
T
T
T
T
CSci 2011
Logical operators: Bi-conditional 1
A bi-conditional means “p if and only if q”
Symbol: 
Alternatively, it means
pq
p
q
“(if p then q) and
T
T
T
(if q then p)”
T
F
F
Note that a bi-conditional
F
T
F
has the opposite truth values
F
F
T
of the exclusive or
CSci 2011
Logical operators: Bi-conditional 2
Let p = “You take this class” and q = “You
get a grade”
pq
p
q
Then pq means
T
T
T
“You take this class if
and only if you get a
T
F
F
grade”
F
T
F
Alternatively, it means “If
F
F
T
you take this class, then
you get a grade and if you get a grade then
you take (took) this class”
CSci 2011
Boolean operators summary
not
not
and
or
xor
conditional
Bi-conditional
p
q
p
q
pq
pq
pq
pq
pq
T
T
F
F
T
T
F
T
T
T
F
F
T
F
T
T
F
F
F
T
T
F
F
T
T
T
F
F
F
T
T
F
F
F
T
T
Learn what they mean, don’t just memorize
the table!
CSci 2011
Precedence of operators
Just as in algebra, operators have
precedence
4+3*2 = 4+(3*2), not (4+3)*2
Precedence order (from highest to lowest):
¬→↔
The first three are the most important
This means that p  q  ¬r → s ↔ t
yields: (p  (q  (¬r)) → s) ↔ (t)
Not is always performed before any other
operation
CSci 2011
Translating English Sentences
 Question 7 from Rosen, p. 17
 p = “It is below freezing”
 q = “It is snowing”
 It is below freezing and it is snowing
pq
 It is below freezing but not snowing
p¬q
 It is not below freezing and it is not snowing
¬p¬q
 It is either snowing or below freezing (or both)
pq
 If it is below freezing, it is also snowing
p→q
 It is either below freezing or it is snowing, ((pq)¬(pq))(p→¬q)
but it is not snowing if it is below freezing
 That it is below freezing is necessary and
p↔q
sufficient for it to be snowing
CSci 2011
Translation Example 2
Heard on the radio:
A study showed that there was a correlation
between the more children ate dinners with their
families and lower rate of substance abuse by
those children
Announcer conclusions:
If children eat more meals with their family, they will
have lower substance abuse
If they have a higher substance abuse rate, then they
did not eat more meals with their family
CSci 2011
Translation Example 3
“I have neither given nor received help on
this exam”
Let p = “I have given help on this exam”
Let q = “I have received help on this exam”
¬p¬q
CSci 2011
Translation Example 4
You can access the Internet from campus
only if you are a computer science major or
you are not a freshman.
a  (c   f)
You cannot ride the roller coaster if you are
under 4 feet tall unless you are older than 16
years old.
(f   s)   r
r  ( f  s)
CSci 2011
Boolean Searches
(2011 OR 5471) AND yongdae AND “computer science”
Note that Google requires you to capitalize
Boolean operators
Google defaults to AND; many others do not
CSci 2011
Bit Operations
Boolean values can be represented as 1
(true) and 0 (false)
A bit string is a series of Boolean values.
Length of the string is the number of bits.
10110100 is eight Boolean values in one string
We can then do operations on these Boolean
strings
Each column is its own
Boolean operation
01011010
10110100
11101110
CSci 2011