SP20:Lecture 4 prep
I plan to talk about proof techniques and to start covering the definitions for functions. Last semester, proof techniques were covered in lecture 4 and lecture 5, while function properties were covered in lecture 5 and lecture 6. We'll see how far we get.
There are no new definitions to know before this lecture. We will be primarily studying the following table of proof techniques, however the meaning of this table may not be clear until lecture:
Here is a table of proof techniques summarizing proof techniques for the basic logical connectives. These techniques will get you most of the way through most of the proofs in this course. There is also a convenient one-page pdf
|Proposition||Symbol||To prove it||To use it||Logical negation|
|P and Q||(P ∧ Q)||prove both P and Q||you may use either P or Q||(¬P) ∨ (¬Q)|
|P or Q||(P ∨ Q)||You may either prove P or prove Q||case analysis||(¬P) ∧ (¬Q)|
|P is false (or "not P")||¬ P||disprove P||contradiction||P|
|if P then Q (or "P implies Q")||P ⇒ Q||assume P, then prove Q||if you know P, conclude Q||P ∧ ¬ Q|
|for all x, P||∀x, P||choose an arbitrary value x||apply to a specific x||∃ x, ¬ P|
|there exists x such that||∃x, P||give a specific x||use an arbitrary x satisfying P||∀ x, ¬ P|
You can think of these as the valid outlines of a valid proof. When writing a 5-paragraph essay, the structure consists of an introductory paragraph, three supporting paragraphs, and a conclusion. Supporting paragraphs have their own structure (made up of sentences, which themselves have a structure...).
Similarly, a proof of a statement like "for all x, P" has an introduction of an arbitrary variable, followed by another proof (this time of P(x)). This proof in turn will have one of the structures in the table above, and so on.
Note that this process is recursive: most of these techniques say "to prove ..., do ... and then prove ...". In most cases, you must repeatedly apply these techniques to build a complete proof.