Transcript Introduction - SIUE Computer Science

MATH 224 – Discrete Mathematics
Why Study Discrete Math
Determination of the efficiency of algorithms, e.g., insertion sort versus selection
sort. Can you provide an example?
Boolean expressions for controlling loops and conditional statements are based on the
propositional calculus and Boolean algebra. What is an example in C++?
The building blocks of computers – logic gates implement Boolean expressions.
Design of programs and algorithms is similar to developing mathematical proofs.
Conversion of high level languages to machine code makes use of formal language
theory. Name some high level languages. What is machine code?
Induction and recursion are the basis for algorithms and programs that use repeated
instructions, e.g., for statements, while statements and recursive functions.
4/1/2016
1
MATH 224 – Discrete Mathematics
Why Study Discrete Math Continued
Security including encryption and authentication make use of math concepts. Can
you give an example of where encryption is used? What is authentication?
Many data structures make use of trees, e.g., heaps, binary search trees, databases.
The theory behind caching and paging uses mathematics. Do you know what these
are?
Graph theory is used in communication networks, artificial intelligence, computer
games, computer animation among others.
And much much more.
 Perquisite for CS 340 − Required for ABET accreditation
4/1/2016
2
MATH 224 – Discrete Mathematics
Propositions
Propositions correspond to Boolean expressions in C++. They are statements,
sometimes represented by variables, that may be either true or false. Examples of
proposition like expressions (actually conditional statements) in C++ include:
X <= Y
Z > 10 && Z <= 20
!(Z <= 10 || Z > 20)
Flag
-- where Flag is a Boolean variable
!Flag || X % 2 == 0
-- When is X % 2 == 0 ?
4/1/2016
3
MATH 224 – Discrete Mathematics
Common Logical (connectives) Operators
Note that the conditional is not quite the same as the if statement in C++. In
programming languages the condition is not a proposition but a statement about
what code should be executed based on whether or not a Boolean expression is
either true or false. Can you give an example of a conditional statement in C++?
How can the other operators (→, ↔ and + ) be expressed in C++?
4/1/2016
4
MATH 224 – Discrete Mathematics
The Meaning of Logical Operators Using Truth Tables
These are called compound propositions or propositional clauses.
Can you create a similar table with one or both of P replaced by ¬P and Q
replaced by ¬Q?
Bitwise operators are among the others use & (and) | (or) and ^ (xor) in C++.
These are not the same as the logical operators. Read the text on this topic (pages
15 and 16) and be prepared to answer questions.
4/1/2016
5
MATH 224 – Discrete Mathematics
Using Truth Tables
More complex clauses may be created using multiple truth connectives. In the
truth
table below the third and fourth columns show the truth values for two
.
clauses with a single operator and then the result when these two clauses are
combined with a third operator. What would the truth values be if the left and
right side of the conditional were to be reversed?
4/1/2016
6
MATH 224 – Discrete Mathematics
Contrapositive
On page 8 of our textbook there is a discussion of the terms converse, contrapositive
and .inverse. The contrapositive is the one most commonly used in proofs since it has
the same truth value as the original proposition. The contrapositive of p → q is
¬q → ¬p.
For example consider : If x = 2 then the √x is irrational (equivalent to p → q).
The contrapositive would be : if the √x is rational then x ≠ 2 (¬q → ¬p)
Assume that √x = a/b a rational number in reduced form. Then since a2/b2 = x, x ≠ 2.
Note that a and b have no common factors unless b = 1. Thus the original proposition
is true. Why is b ≠ 1? Can you prove for all integers x that the √x is either an
integer or irrational?
4/1/2016
7
MATH 224 – Discrete Mathematics
Reasoning that is Incorrect
Both the general theory of relativity and string theory can be used to explain gravity.
Physicist A shows that general relativity is incorrect. Based on this result, physicist B
concludes that string theory must be correct. What is wrong with B’s conclusion.
One controversial topic involves intelligent design versus evolution.
Is a proof that evolution is false sufficient to prove that intelligent design is true?
Is a proof that evolution is true sufficient to prove that intelligent design is false?
Another controversy involves climate change. What is wrong with the following?
The sun is the most important factor in determining the global climate. Therefore, the
burning of fossil fuels does not cause global climate change.
A mother tells her son that if he makes his bed he can have some ice cream after dinner.
After dinner Billy’s mother gives him some ice cream.
Can you conclude that Billy made his bed?
4/1/2016
8
MATH 224 – Discrete Mathematics
Logic Puzzles
Example 18 (pages 13-14): Knights are always truthful and knaves always lie. A
says B is a Knight and B says we are different. If A is a knight then B must also be
a knight. But that leads to a contraction since they must be different. If A is a knave
then B must be a knave since knaves lie. B says they are different which would be a
lie if B is a knave. Thus the two statements are consistent. Both A and B are
knaves.
Problem 43 (page 19): Given statements 1 through 100, “Exactly n statements are
false.” Which statement must be true?
If instead we have, “at least n statements are false.” Which statements are true?
What would be the case if there are 99 statements instead of 100? Note that it is
possible to have a statement that either contradicts itself or a group of statements
that are contradictory. This is called a paradox.
4/1/2016
9
MATH 224 – Discrete Mathematics
More Logic Puzzles
Problem 46 (pages 20): Each member of a group of cannibals either lies or does
not lie. An explorer must determine if a given cannibal tells the truth or not. Why
does asking him if he is a liar not help? What yes or no question should the explorer
ask?
How would you go about analyzing this type of problem? One of the tricks that
often works is the use of a double negative, i.e., the negation of a negation.
4/1/2016
10
MATH 224 – Discrete Mathematics
More Logic Puzzles
Dr. Who was a British television program from the 1960s and 70s. He was an
explorer who used an old telephone booth as his spaceship. In one episode he had
to choose between two doors. One door led to freedom and the other to his certain
death. There were two robots in the room. One always lied and one always told
the truth. What single yes or no question should Dr. Who ask of one of the robots
in order to determine which door to take?
4/1/2016
11
MATH 224 – Discrete Mathematics
More Logic Puzzles
Evaluating a While Statement
A jar contains both white and black beans. You take two beans from the jar. If
both of them are black you return one black bean to the jar. If one is black and
one is white you return the white bean. If both are white you take both of them
and add a black bean to the jar. You repeat this step until you are tired or until the
jar has only one bean in it. Will this process ever stop? How many beans will be
left at the end? Can you say anything about the original number of black and
white beans based on the beans that are left? These properties are called
preconditions. Are there any invariant properties?
4/1/2016
12
MATH 224 – Discrete Mathematics
Semi-formal Proofs
By using propositional clauses that have already been shown to be true it is
possible to derive equivalent propositions or to prove that a proposition is a
tautology (always true). Below is an example of a rather trivial derivation.
4/1/2016
13
MATH 224 – Discrete Mathematics
Semi-formal Proofs
Here is a more complex derivation.
Using p ↔ q ≡ (p → q) ^ (q → p) show that p ↔ q ≡ (p ^ q) v (¬p ^ ¬q)
p↔q
≡
(p → q) ^ (q → p)
Given
≡
(¬p V q) ^ (¬q V p)
Table 7, Page 25
≡
(¬p ^ ¬q)v(¬p ^ p)v(¬q ^ q)v(q ^ p)
distributive laws
Table 6, Page 24
≡
(¬p ^ ¬q) v F v F v (q ^ p)
negation law, Table 6
≡
(p ^ q) v (¬q ^ ¬p)
identity law, Table 6
≡
(p ^ q) v (¬p ^ ¬q)
commutative law, Table 6
Is (p ↔ q) ↔ [(p ^ q) v (¬p ^ ¬q)] a tautology? Explain your answer.
4/1/2016
14