Week 1 - Review of Discrete Structure 1 - Presentation - PDF - 2

Review of Discrete Structures 1
Discrete Structures 2
Why Study Discrete Mathematics?
• Computers use discrete structures to represent and
manipulate data.
• Computer Science is not Programming
• Computer Science is not Software Engineering
• Edsger Dijkstra: “Computer Science is no more about
computers than Astronomy is about telescopes.”
• Computer Science is about problem solving.
Why Study Discrete Mathematics?
• Mathematics is at the heart of problem solving
• Defining a problem requires mathematical rigor
• Use and analysis of models, data structures, algorithms requires a
solid foundation of mathematics
• To justify why a particular way of solving a problem is correct or
efficient (i.e., better than another way) requires analysis with a well-
defined mathematical model.
Problem Solving requires Mathematical Rigor
• Your boss is not going to ask you to solve
• an MST (Minimal Spanning Tree) or
• a TSP (Travelling Salesperson Problem)
• Rarely will you encounter a problem in an abstract setting
• However, he/she may ask you to build a rotation of the company’s
delivery trucks to minimize fuel usage
• It is up to you to determine
• a proper model for representing the problem and
• a correct or efficient algorithm for solving it
Scenario I
• A limo company has hired you/your company to write a computer program
to automate the following tasks for a large event
• Task1: In the first scenario, businesses request
• limos and drivers
• for a fixed period of time, specifying a start data/time and end date/time and
• a flat charge rate
• The program must generate a schedule that accommodates the maximum
number of customers
Scenario II
• Task 2: In the second scenario
• the limo service allows customers to bid on a ride
• so that the highest bidder gets a limo when there aren’t enough limos available
• The program should make a schedule that
• Is feasible (no limo is assigned to two or more customers at the same time)
• While maximizing the total profit
Scenario III
• Task 3: Here each customer
• is allowed to specify a set of various times and
• bid an amount for the entire event.
• The limo service must choose to accept the entire set of times or reject it
• The program must again maximize the profit.
What’s your job?
• Build a mathematical model for each scenario
• Develop an algorithm for solving each task
• Justify that your solutions work
• Prove that your algorithms terminate.Termination
• Prove that your algorithms find a solution when there is one.
Completeness
• Prove that the solution of your algorithms is correct Soundness
• Prove that your algorithms find the best solution (i.e., maximize profit).
Optimality (of the solution)
• Prove that your algorithms finish before the end of life on earth.
Efficiency, time & space complexity
The goal of this course
• Give you the foundations that you will use to eventually solve these
problems.
• Task1 is easily (i.e., efficiently) solved by a greedy algorithm
• Task2 can also be (almost) easily solved, but requires a more
involved technique, dynamic programming
• Task3 is not efficiently solvable by any known technique. It is
believed today that to guarantee an optimal solution, one needs
to look at all (exponentially many) possibilities
Why Care about Discrete Structures?
• Digital computers are based on discrete “atoms” (bits).
• Therefore, both a computer’s
• structure (circuits) and
• operations (execution of algorithms)
can be described by discrete mathematical structures.
Mathematical Appetizers
• Useful tools for this course:
(Knowledge on)
• Logic
• Set Theory
• Functions
• Sequences
Logic
• Crucial for mathematical reasoning
• Used for designing electronic circuitry
• Logic is a system based on propositions.

• A proposition is a statement that is either true or false (not both).
• We say that the truth value of a proposition is either true (T) or false (F).
• Corresponds to 1 and 0 in digital circuits

The Statement/Proposition Game
“Elephants are bigger than mice.”
Is this a statement? yes
Is this a proposition? yes
What is the truth value true

of the proposition?
“520 < 111”

What is the truth value false

of the proposition?
“y > 5”
Is this a proposition? no
Its truth value depends on the value of y, but this value is

not specified.
We call this type of statement a propositional function or
open sentence.
“Today is January 32 and 99 < 5.”
What is the truth value false
of the proposition?
“Please do not fall asleep.”
Is this a statement? no
It’s a request.
Is this a proposition? no
Only statements can be
propositions.
“If elephants were red, they could hide in cherry
trees.”
What is the truth value probably false
of the proposition?
“x < y if and only if y > x.”
… because its truth value does not
depend on specific values of x and
y.
What is the truth value true
of the proposition?
Combining Propositions
•As we have seen in the previous examples, one or more propositions can
be combined to form a single compound proposition.
•We formalize this by denoting propositions with letters such as p, q, r, s, and

introducing several logical operators.
Logical Operators (Connectives)
•We will examine the following logical operators:
• Negation (NOT)
• Conjunction (AND)
• Disjunction (OR)
• Exclusive or (XOR)
• Implication (if – then)
• Biconditional (if and only if)
• Truth tables can be used to show how these operators can combine propositions to
compound propositions.
Negation (NOT)
Unary Operator, Symbol: 
P P
true false
false true
Conjunction (AND)
Binary Operator, Symbol: 
P Q PQ
true true true
true false false
false true false
false false false
Disjunction (OR)
Binary Operator, Symbol: 
P Q PQ
true true true
true false true
false true true
false false false
Exclusive Or (XOR)
Binary Operator, Symbol: 
P Q PQ
true true false
true false true
false true true

false false false
Implication (if - then)
Binary Operator, Symbol: 
P Q PQ
true true true
true false false
false true true

false false true
Biconditional (if and only if)
Binary Operator, Symbol: 
P Q PQ
true true true
true false false
false true false

false false true
Statements and Operators
Statements and operators can be combined in any way to
form new statements.
P Q P Q (P)(Q)
true true false false false
true false false true true
false true true false true

false false true true true
Statements and Operations
Statements and operators can be combined in any way to
form new statements.
P Q PQ  (PQ) (P)(Q)
true true true false false

true false false true true
false true false true true
false false false true true
Equivalent Statements
The statements (PQ) and (P)(Q) are logically equivalent, because
(PQ)(P)(Q) is always true.
P Q (PQ) (P)(Q) (PQ)(P)(Q)
true true false false true
true false true true true
false true true true true
false false true true true

Tautologies and Contradictions
• A tautology is a statement that is always true.
• Examples:
R(R)
(PQ)(P)(Q)
• If ST is a tautology, we write ST.

• If ST is a tautology, we write ST.
Tautologies and Contradictions
• A contradiction is a statement that is always false.
• Examples:
• R(R)
• ((PQ)(P)(Q))
• The negation of any tautology is a contradiction, and the negation of any

contradiction is a tautology.
Assignment
We already know the following tautology:
(PQ)  (P)(Q)
Nice home exercise:
Show that (PQ)  (P)(Q).
These two tautologies are known as De Morgan’s laws. Answer Assignment

001 by indicating the truth value in each of the unknown cell in the truth
table.

Week 1 - Review of Discrete Structure 1 - Presentation - PDF - 2

Uploaded by

Copyright:

Available Formats

Week 1 - Review of Discrete Structure 1 - Presentation - PDF - 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Week 1 - Review of Discrete Structure 1 - Presentation - PDF - 2

Uploaded by

Copyright:

Available Formats

Review of Discrete Structures 1

• Logic is a system based on propositions.

• Corresponds to 1 and 0 in digital circuits

Is this a proposition? yes

What is the truth value true

Is this a statement? yes

What is the truth value false

Its truth value depends on the value of y, but this value is

•We formalize this by denoting propositions with letters such as p, q, r, s, and

true false true

false true true

true false false

false true true

true false false

false true false

true false false true true

false true true false true

P Q PQ  (PQ) (P)(Q)

true true true false false

P Q (PQ) (P)(Q) (PQ)(P)(Q)

true true false false true

true false true true true

false true true true true

false false true true true

• If ST is a tautology, we write ST.

• The negation of any tautology is a contradiction, and the negation of any

Nice home exercise:

Show that (PQ)  (P)(Q).

These two tautologies are known as De Morgan’s laws. Answer Assignment

You might also like