Difference between revisions of "SP20:Lecture 4 prep"

From CS2800 wiki
(Created page with "Last semester's notes Please come to lecture with the following definitions: {{:Function definition}} {{:Surjection definition}} {{:Inj...")
 
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
[[FA19:Lecture 4 Proof techniques|Last semester's notes]]
+
[[Media:sp20-lec04-handout.pdf|Proof techniques handout]]
  
Please come to lecture with the following definitions:
+
Last semester, [[proof technique]]s were covered in [[FA19:Lecture 4 Proof techniques|lecture 4]] and [[FA19:Lecture 5 Function properties|lecture 5]]; I hope to cover this material in one lecture this semester but we'll see.
  
{{:Function definition}}
+
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.
  
{{:Surjection definition}}
+
<blockquote>
 +
{{:Table of proof techniques}}
 +
</blockquote>
  
{{:Injection definition}}
+
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 [[FA19:Lecture 2 Set and function definitions|lecture 2]].
 
 
{{:Bijection definition}}
 

Latest revision as of 16:09, 29 January 2020

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.