Ch 1 pp 1-35 : Question for Ch. 1
Ch. 1 mentions many methods for constructing proofs. Are there any other
methods of proof construction that are not covered in the text?
The book doesn't discuss the use of algebra. This is because
it is not that useful in most of automata and computability theory.
Most disciplines have their own special techniques and short cuts.
For example: "Proof by Intimidation" is used in many human endeavors.
"The Proof of the Pudding" may be the most popular method outside of
academe.
Here is a list of bad proofs that all odd numbers are prime.
Mathematician:
1 is prime, 3 is prime, 5 is prime, 7 is prime,
therefore, by induction, all odd numbers are prime.
Physicist:
1 is prime, 3 is prime, 5 is prime, 7 is prime,
9 is a bad data point, 11 is prime, 13 is prime...
Engineer:
1 is prime, 3 is prime, 5 is prime, 7 is prime,
9 is approximately prime, 11 is prime, 13 is prime...
Lawyer:
1 is prime, 3 is prime, 5 is prime, 7 is prime,
9 is lying, 11 is prime, 13 is prime...
Computer Scientist:
1 is prime, 1 is prime, 1 is prime, 1 is prime, 1 is prime, ...
With thanks to
[ Smart.html ]
, (for more math humor try
[ jokes.html ]
)
This book has enough methods for this class -- I hope.
What is the best way to choose a proof method?
Look for patterns in the statement of the problem.
Experience helps.
Is shortest possible way to prove always the best method?
Usually -- if you can find it.
Their is one catch: the level of detail, rigor, and
formality depends very much on your audience.
In this class your audience is me and
your colleagues. The book provides a good picture of the level
of rigor, detail, and formality I expect in this class
(in some courses I much more
informal, and in other more formal).
Surely you mean
QuaNTifiers
Ch pp 11 : Statements With Quantifiers
How are "for all" and "there exists" quantifiers used in proofs?
How and when are they used in each statement of a proof?
If you have a statement that "something exists with property P"
there is only one deduction you can validly make. Since you can not
be sure which thing is the "something" you must give it a name by
using an unused (free) variable. So for example, given
for some x, x is a distributed widget.
you can validly deduce
v is a distributed widget
as long as "v" is a free variable at that point in the argument.
But you can not argue
3.14159 is a distributed widget.
or use any other constant, formula, name, or bound variable in place of x.
Universal quantifiers let you substitute any expression, variable, or
value (of the right type) for the unknown. So if
we have deduced
for all widgets x, if x is round then x is distributed.
and you know that fubar is a widget then you can deduce
if fubar is round then fubar is distributed.
In my experience, the freedom to substitute anything for a
universally quantified variable means you often need inspiration
or luck to substitute the value/expression that proves the result you want.
Proving "for all": I use a block structure that starts by declaring
a new variable, then deduce the result I want and then close the proof
with the claim of success:
To prove that "all round widgets are distributed":
Let
- x be a round widget
- ...
- ...
- (above)|-x is distributed.
(Close Let )
- (above)|-all round widgets are distributed.
Sometimes an expanded form is used
Let
- x be a widget
- (let)|-x is round.
- ...
- ...
- (above)|-x is distributed.
(Close Let )
Proving a "for some" -- you have two approaches. (1) find an example
that fits. Or (2) prove by contradiction:
Let
- not for some x, foo(x),
- (above)|-for all x, not foo(x),
- ...
- ...
(Close Let )
- (above)|-for some blah, foo(blah)
For more on this see
[ ../maths/logic_2_Proofs.html#For all and some ]
There are four combinations of "If H then C":
(if_then):
- H=True, C=True
- H=True, C=False
- H=False, C=True
- H=False, C=False
According to the book, #1 evaluates to true and #2 evaluates to false,
which both make sense to me. Can you explain why #3 and #4 evaluate to
true as well?
Ch 1 pp 6-8 : Deductive Proofs
What is a deductive Proof. I do not understand the difference of the
deductive proof and the proof by induction.
A deductive proof is a series of steps where each proposition
is derived by more or less rigorous rules from one or more previous
steps. I have tabulated a set of such steps
[ ../maths/logic_25_Proofs.html ]
as part of my research on expressing rigorous math in ASCII and HTML.
I document steps like this
- (evidence)|- (label): statement.
The evidence is a list of previous labels.
Proof by induction is a special form of proof that works with integers
and strings. It always has two parts: basis and step:
- Prove Basis for n = 1.
- Prove step: if true of n then it is true of n+1.
Let- (induction_hypothesis): it is true of 1.
- derive truth of n+1
(Close Let )
See
[ Section 1.4 Induction ]
below.
1.2.3 If-then and iff
There is a variation to deductive proof at is used to prove
statements that have this form
- if P then Q
You prove it by assuming P as a temporary
hypothesis and deducing Q from it. I document this kind of
argument using ".Let"... and in HTML you see
Let
- P1.
- (let)|-P2.
- ...
- ...derivation
- (above)|-Q.
(Close Let )
The Ps are the hypotheses (hyp) and Q is the conclusion
that proves
- if P1 and P2 and ... then Q.
How to prove a proof using the induction process?
What are the general principles behind Proof by induction? In my previous
class' cs 431 and cs 500, we more or less focused on proof by construction
or contradiction.
I am bit rusty on the Proof By Induction, i know it, i understand it, but i
have a problem implementing it on the problems of higher complications.
So my question is, may you give us a hands on explanation of proofs by
induction on a more complicated question.
Can you also explain Question 2 of the Ex Sheet. AND IF POSSIBLE go over
all the homework questions.
I don't understand why the strategy for the induction
step was to subtract 3 from n+1.
I think this is because the basis step established 3 cases: 8,9, and 10.
If we could subtract 3, could we subtract 5 as well to
prove the induction step?
You would then have to base the induction on 5 cases: 8,9,10,11,and 12.
At the end of the induction step, we have
n + 1 = 3 + 3a + 5b which n + 1 can be written as a + 1 3's and b 5's.
That statement does not prove S(n + 1).
1.4.2 Noether
1.4.3 Structural induction and recursion
Ch 1 pp 023-024 : Induction, Structural Induction
While doing Finite Automata or Turing machines perhaps, would you please go
over Structural Induction in some more detail. We use it to prove several
theorems but I'm as confident on structural as perhaps on regular
induction.
I think we are going to do lots of these during the rest of the class.
Why do parts three and four of the basis step prove anything?
Looks like those cases of if_then are causing a problem here.
If I recall correctly functions that are o(f(n)) are strictly less than
a constant time f(n) for large enough n. So o(n) doesn't include
functions like 3n+1 which is O(n).
I think the words "upper bound" are misleading -- a metaphor.
The symbols didn't transfer very well.... help.
I imagine there are many other categories of graphs which also have special
properties that allow them to have their Hamiltonian paths found in
polynomial time.
So, even though we haven't been able to solve the TSP problem in the general
case in polynomial time (yet), is it considered practical to attempt graph
classification before applying heuristics to discover if a graph can be
solved in polynomial time? Or is graph classification an intractable
problem as well?
Probably.... by the end of the class I think you will know
the answer to this.