.Open Session 02 Math, Method, & Madness . Section 1.1 finite state machine. .Open Section 1.2 Proof . 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. .List 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, ... .Close.List With thanks to .See http://www.molad.com/gor/Smart.html , (for more math humor try .See http://home.earthlink.net/~djbach/jokes.html ) This book has enough methods for this class -- I hope. . Ch 1 pp 1-35 : Proof Methods What is the best way to choose a proof method? Look for patterns in the statement of the problem. Experience helps. . Ch 1 pp 1-35 : Proof Methods 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). . Ch pp 11 : Statements With Qualifiers Surely you mean .As_is 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 .As_is for some x, x is a distributed widget. you can validly deduce .As_is v is a distributed widget as long as "v" is a free variable at that point in the argument. But you can not argue .As_is 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 .As_is for all widgets x, if x is round then x is distributed. and you know that `fubar` is a widget then you can deduce .As_is 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 ... ... ()|- x is distributed. .Close.Let ()|- all round widgets are distributed. Sometimes an expanded form is used .Let x be a widget (let)|- x is round. ... ... ()|- 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), ()|- for all x, not foo(x), ... ... .Close.Let ()|- for some blah, foo(blah) For more on this see .See ../maths/logic_2_Proofs.html#For all and some . Ch 1 pp 14-15 : if-then statements There are four combinations of "If H then C": (if_then): .List H=True, C=True H=True, C=False H=False, C=True H=False, C=False .Close.List 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? . 1.2.1 Deductive proof . 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 .See ../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`: .Box 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 .Close.Box See .See Section 1.4 Induction below. . 1.2.2 Reduce to definition . 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 `P`s are the hypotheses (hyp) and Q is the conclusion that proves if P1 and P2 and ... then Q. .Close .Open Section 1.3: Sets & logic . 1.3.1 sets . 1.3.2 contrapositive . 1.3.3 contradiction, . 1.3.4 counterexample .Close .Open Section 1.4 Induction 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. . Ch 1 pp : Proof and Homework Can you also explain Question 2 of the Ex Sheet. AND IF POSSIBLE go over all the homework questions. . Ch 1 pp 22-23 : example 1.18 (Induction) 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.1 on integers . 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. . Ch 1 pp 27-27 : Mutual Inductions Why do parts three and four of the basis step prove anything? Looks like those cases of $if_then are causing a problem here. .Close .Open Section 1.5 Strings . 1.5.1 Alphabets . Ch 1 pp 29-29 : Powers of an Alphabet I think I understand how to calculate certain powers of an alphabet, but in what context is this useful? Could you give an example where such a calculation is used? The powers of an alphabet generate strings of different lengths. Thus they let us think and talk about `strings`. Which is what we need to discuss languages, input into a computer, output out of a machine,... Here is another example: we can take all the words in the English language to be an alphabet -- call it W. Then: .As_is The cat sat on the mat is a member of W^6. Notice that we can use powers of strings to express repetitions: "banana" = "ba" "na"^2 We can also apply powers to sets of strings (languages, problems...): {"ba", "na"}^2 = {"bana", "baba", "naba", "nana"}. Exercise: find `k` such that "banana" is in {"ba", "na"}^k. . 1.5.2 Strings . 1.5.3 Languages . 1.5.4 Problems .Close . BigO . "Big O notation" @ Wikipedia What is the difference between the "linear" O(n) and "sub-linear" o(n) orders? I'm tempted to say: we won't us o(.) in this class... 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). . Big O Notation If Big O Notation is the "Asymptotic Upper Bound," why is O of 4x^4 O(x^4) when x^4 is not the upper bound of 4x^4? I think the words "upper bound" are misleading -- a metaphor. So 4x^4 is O(x^4) even tho' 4x^4 > x^4 for all x except 0! . Ch 1 pp : BigO Notation The question is? What type problems are related to the following different notations Ù(n), ù(n), È(n). Is one better than other? The symbols didn't transfer very well.... help. . Graphs . Graph Theory and Induction I tried to do question 5(a) as an exercise in probability theory, for some reason I could not "port" it to induction. Would you please see where I'm missing the link. We will avoid probability until the end of the course! . wikipedia : Graph Theory When I was browsing Wikipedia's data graph theory, I ran across the Knight's tour problem, which is a subset of the graphs of the TSP problem which can be solved in linear time: .See http://mathworld.wolfram.com/KnightsTour.html 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. .Close . Ch 1+math pp : Deadline for class 02 Fewer points if your message is delivered after this one.