Transcript August 31, 2005

August 31, 2005
Homework Problem
•
•
•
•
•
•
•
•
•
Some information about homework problem.
C' is the conclusion - it is NOT a hypothesis
The problem CAN be done using our original statements (i.e. without
replacing T by K)
Here’s what the lawyer said
If my client is guilty, then the knife was in the drawer
Either the knife was not in the drawer or Jason Pritchard saw the knife.
If the knife was not there on October 10, it follows that Jason Pritchard did
not see the knife.
Furthermore, if the knife was there on October 10, then the knife was in the
drawer and also the hammer was in the barn.
But we all know that the hammer was not in the barn.
Therefore, ladies and gentlemen of the jury, my client is innocent.
Here are the variables used
• C client is guilty
K knife was in the drawer
T knife was there on October 10
S Jason Pritchard saw knife
H hammer was in the barn
• 1. C -> K
2. K' v S
3. T' -> S'
4. T -> (K ^ H)
5. H'
hypothesis
hypothesis
hypothesis
hypothesis
hypothesis
Proof
•
•
•
•
•
•
•
•
6. H’ v K’
7. (H ^ K)’
8. (K ^ H)’
9. T’
10. S’
11. S v K’
12 K’
13 C’
5. addition
6. DeMorgan’s
7. commutative
4,8 Modus Tollens
3,9 Modus Ponens
2 commutative
10,11 disjunctive syllogism
1,12 Modus Tollens
Statement of problem
• If the program is efficient, it executes
quickly
• Either the program is efficient, or it has a
bug.
• However, the program does not execute
quickly.
• Therefore it has a bug.
• Please use the letters E,Q,B
Propositional form
• (E → Q) ⋀ (E ⋁ B) ⋀ Q’→ B
A solution
•
•
•
•
•
1.
2.
3.
4.
5.
E→Q
E⋁B
Q’
E’
B
hyp (simplification)
hyp (simplification)
hyp (simplification)
1,3 Modus Tollens
2,4 Disjunctive syllogism
Another solution
•
•
•
•
•
•
•
1.
2.
3.
4.
5.
6.
7.
E→Q
hyp (simplification)
E⋁B
hyp (simplification)
Q’
hyp (simplification)
E’⋁ Q
1 implication
Q ⋁ E’
4 commutative
E’
3,5 Disjunctive syllogism
B
2,6 Disjunctive syllogism
Still another solution
•
•
•
•
•
•
•
•
1.
2.
3.
4.
5.
6.
7.
8
E→Q
hyp (simplification)
E⋁B
hyp (simplification)
Q’
hyp (simplification)
Q’→ E’ 1 contraposition
E’
4,3 Modus Ponens
(E’)’ ⋁ B 2 double negation
E’→ B
6 implication
B
7,5 Modus Ponens
And yet another one
•
•
•
•
•
•
•
•
•
•
•
•
•
1. E → Q
2. E ⋁ B
3. Q’
4. (E’)’ ⋁ B
5. E’→ B
6. E’ ⋁ Q
7. (E’ ⋁ Q) ⋀ Q’
8. Q’ ⋀ (E’ ⋁ Q)
9. (Q’ ⋀ E’) ⋁ (Q’ ⋀ Q)
10. (E’ ⋀ Q’) ⋁ 0
11. (E’ ⋀ Q’)
12. E’
13. B
hyp (simplification)
hyp (simplification)
hyp (simplification)
2 double negation
4 implication
1 implication
6,3 conjunction
7 commutative
8 distributive
9 complement property
10 identity property
11 simplification
5,12 Modus Ponens
MATH/CS-227 Outline:
Topic
Wks
Functions, relations & 2
sets
Logic (Part I)
3
Matrices
1
Elementary Number
Theory
2
Proof Techniques
2
Basics of Counting
2
Sub-Topics
Sets (Venn diagrams, complements, unions, intersections,
Cartesian products)
DeMorgan’s laws
Relations (reflexivity, symmetry, transitivity, equivalence
relations)
Functions (surjections, injections, inverses, composition)
Truth tables
Conjunction, disjunction, negation, implication (hypotheses,
conclusions, converses, contrapositives)
DeMorgan’s laws again
Natural Deduction (Modus Ponens, Modus Tollens, etc.)
Universal and existential quantification
Validity – implication
Addition
Multiplication
Inverses
Divisibility
Fundamental Theorem of Arithmetic
Gcd’s, lcm’s, number of divisors
Modular arithmetic
Bases (in particular, binary and hex)
Methods of proof: direct, indirect, contradiction
Counterexamples
The Principle of Mathematical Induction
Pigeonhole principle
Permutations & combinations
Basic probability
MATH/CS-228 Outline:
Topic
Logic (Part II)
Wks
3
Graph Theory
2
Discrete Probability
2
Digital Logic
1
Finite State Machines 1
Proof Techniques
1
Integer and Floating- 2
point Representations
Sub-Topics
Quick review of Part I
Natural deduction
Consistency
Completeness
Normal forms (conjunctive and disjunctive)
Trees
Undirected and directed graphs
Traversal strategies
Cyclic and acyclic paths
Spanning trees
Frequency
Distributions
Expected value
Conditional probability
Logic gates and circuits
Flip-flops
FSMs
State diagrams
FSMs as a virtual machine
FSMs as a representation of computation
Limits of deterministic FSMs
Induction (on graphs)
Ones' complement
Two’s complement
Signed magnitude
Floating point representation; IEEE 754
Definition: Compound proposition
• “a proposition constructed by combining
propositions using logical operators”
• Conjunction – and
• Disjunction - or
Definition:
dual of a compound proposition
• The dual of a compound proposition that
contains only the logical operators
∨,,¬, is the proposition obtained by
replacing each ∨ by , each  by ∨,
each T by F and each F by T.
Definition: NAND
• The proposition p NAND q is true when
either p or q or both are false; and it is
false when both p and q are true.
Definition: NOR
• The proposition p NOR q is true when
both p and q are false, and it is false
otherwise.
Page 27, problem 34
• Find a compound proposition involving the
propositions p,q and r that is true when p
and q are true and r is false, but false
otherwise.
•
Page 27, problem 35
• Find a compound proposition involving the
propositions p, q, and r that is true when
exactly two of p, q, and r are true and is
false otherwise.
• Hint: form a disjunction of conjunctions.
Include a conjunction for each combination
of values for which the proposition is true.
Each conjunction should include each of
the three propositions or their negation.
Modular Arithmetic
• a.k.a. clock arithmetic
• If a and b are integers and m is a positive
integer, then we way that a is congruent to
b modulo m if m divides a-b.
• We use the notation a≡b (mod m) to
indicate that a is congruent to b modulo m
• If they are not congruent, we write
• a≢ b (mod m)
Why do we care in c.s.?
• Applications:
– Stripping digits from a base 10 number
– Check digits on credit cards
– Hash codes for storing information
– Generation of pseudo-random numbers
– Cryptology
– Check digits on bar codes
• Enable error detection