SP20:Lecture 4 prep

From CS2800 wiki

Proof techniques handout

Last semester, proof techniques were covered in lecture 4 and lecture 5; I hope to cover this material in one lecture this semester but we'll see.

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. Feel free to familiarize yourself with it before lecture but I won't quiz you on it.

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 [math]P [/math] ∃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.

Parts of homework 1 will use the definition of a function or a partial function; if you want to get started early on those parts, you may refer to these definitions. They are discussed in more detail in last semester's lecture 2.