Difference between revisions of "SP18:Lecture 5 Functions"
(→Proof techniques continued) |
(→Function examples) |
||
| Line 33: | Line 33: | ||
==== direct specifications ==== | ==== direct specifications ==== | ||
| − | + | {{Example:x^2 is a function}} | |
| − | |||
| − | |||
==== drawings ==== | ==== drawings ==== | ||
Revision as of 16:06, 17 February 2018
We finished our list of proof techniques, adding implication () and existentials (). We then defined functions and discussed some examples.
- Reading: MCS 4.3 — 4.5
- This material was covered in lectures 2 (modeling problems) and 4 (functions) in 2017sp.
- File:Lec05-board.pdf
Contents
Proof techniques continued
There exists x such that P
If is a predicate depending only on , then "there exists such that P" (written or ) is a proposition. It is true if there is some value that makes evaluate to true.
is sometimes called the existential quantifier.
- To prove that there exists an such that holds, it suffices to give a specific and then prove that is true for that . Such a proof usually starts "let ", and then goes on to prove that holds for the given . is sometimes referred to as a witness for .
- If you know there exists some satisfying , you can use it in a proof by treating as an arbitrary value. is arbitrary because the only thing you know about is that it exists, not what its value is.
- To disprove that there exists an satisfying , you must disprove for an arbitrary . Put another way, the logical negation of "there exists an such that " is "for all x, not P".
When trying to prove an existential statement , you need to give a specific value of (a witness).
Often, in a proof, it is not immediately obvious what the witness should be. Finding one often involves solving some equations or combining some known values.
One nice technique for finding a witness is to simply leave a blank space for the value of and continue on with your proof of . As you go, you may need to satisfy certain properties (for example, maybe you need at one point, and later you need ). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want to satisfy. Once you've completed your proof, you can go back and find a specific value of (say, ) that satisfies all of your wishes.
If P then Q
If and are propositions, then "if then " (written or " implies ") is a proposition. It is true if either is false, or if is true.
- If you know "if then ", and you also know , you can conclude . This technique is sometimes referred to as "modus ponens".
- To disprove "if then ", you must show that is true and that is false (" implies " only makes a claim about the world where is true; an example where is false doesn't contradict the claim).
Logical negation
If is a proposition, the logical negation of is the proposition that is equivalent to "not ".
For example, to disprove " and ", it suffices to either disprove or to disprove . This is the same thing as proving "not or not ," so the logical negation of " and " is "not or not ."
For further examples, see the table of proof techniques.
Table of proof techniques
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.
Functions
When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input.
The output of a function is unambiguous if there is only one output for any input. It is especially important to check this when the input of the function can be written in different ways. For example, given by , , and is not unambiguous, because so it is not clear if or .
Specifying functions
When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input. There are many, many ways to do this, as long as the output is clear. We gave a few examples during lecture:
direct specification
We can define the output of the function directly:
let be given by . The domain and codomain of are both ; the image is .
drawings
We can draw a function:
The domain of is , and the codomain of is .
We might also write this as is given by , , and .
tables
Another way to draw a function is with a table:
| x | |
|---|---|
| a | 1 |
| b | 1 |
| c | 1 |
This almost describes a function; the domain is clearly (because if there were any other domain elements, would not be a function); and the rule is clear. However, the codomain is not clear: is it ? Or ? Or , or ? When describing a function with a table, the codomain should be specified somewhere.
function description
A function need not have an algorithm for constructing the output; a description of the output is also fine. For example, let give, on input , the closing Dow-Jones Industrial average on day .
Function examples
You can write a function in many different ways; the important thing is that the domain is clear, the codomain is clear, and the output is clear (and unambiguous).
direct specifications
We can define the output of the function directly:
let be given by . The domain and codomain of are both ; the image is .
drawings
We can draw a function:
The domain of is , and the codomain of is .
We might also write this as is given by , , and .
tables
Another way to draw a function is with a table:
| x | |
|---|---|
| a | 1 |
| b | 1 |
| c | 1 |
This almost describes a function; the domain is clearly (because if there were any other domain elements, would not be a function); and the rule is clear. However, the codomain is not clear: is it ? Or ? Or , or ? When describing a function with a table, the codomain should be specified somewhere.
