SP18:Lecture 4 Logic
In this lecture, we will examine several forms of proposition; for each we will discuss how to prove it, how to disprove it, and how to use it in a proof (if it is already known to be true).
For example,is a proposition, as is . "Professor George is taller than 5'" is a proposition. If is known to be 5, then " " is a proposition.
We are often lazy and leave off the quantification of a variable in a statement. When we have an undefined variable in a claim, we implicitly mean "for all ". For example, if I ask you to prove or disprove that , I implicitly mean to prove or disprove that, for all sets and , .
If you have propositions , , and , you can combine them in natural ways to form new propositions. The structure of these combined propositions can help you determine how to prove them, or how to use them if you know they are true. We will examine several of these combined propositions today; we will summarize them in the next lecture in a table of proof techniques.
You can view this overview as a guide to doing what it says, and using what you know. At any point in a proof, there is a current set of facts that you've already proven (or assumed), and there is a particular proposition that you are trying to show. You can apply these strategies to those propositions to make progress.
Note on notation
We are introducing symbols for words like "and", "or", and "not". These symbols are helpful when talking about logic itself, but I find they make proofs much harder to read, so I avoid them when writing proofs. This is a matter of style.
P and Q
To prove "and ", you can separately prove and then prove .
If you have already proved (or assumed) and , you can conclude . You can also conclude .
P or Q
To prove "or ", you can either prove , or you can prove (your choice!)
If you know that "P or Q" is true for some statements P and Q, and you wish to show a third statement R, you can do so by separately considering the cases where P is true and where Q is true. If you are able to prove R in either case, then you know that R is necessarily true.
This technique is often referred to as case analysis.
P is false
- To prove disprove ; To disprove " is false": prove . Put another way, the logical negation of "not " is . is false:
- You can think of "proof by contradiction" as a way of using "not ". If you are able to prove both and "not ", then you must have made contradictory assumptions at some point; this means you can go back to your most recent assumption and conclude that it was invalid. This is useful to rule out cases when doing case analysis.
It is often a good way to start a proof: assume that what you are trying to prove is false, and then find a contradiction. At that point, you know your assumption was incorrect, so the original claim must be true.
This style of proof usually starts "Assume for the sake of contradiction, that is false..." and usually ends "...this is a contradiction, and must have been true in the first place." It is a useful approach when the claim you are trying to prove already has a logical negation in it, for example if you are trying to prove that something is not injective or not countable. You assume that it is injective or countable, and then you have a fact that you can work with.
For all x, P
- If your goal is to prove "for all , P", you can proceed by choosing an arbitrary value and then proving that P holds for that .
The fact that arbitrary does not mean you get to pick ; on the contrary, your proof should work no matter what you choose. This means you can't use any property of other than that .is
- If you know for all , then you can conclude holds for any specific . For example, if you know for all , , then you can conclude (since ). holds
- To disprove that a predicate holds for all , you only need to choose a specific (called a counterexample) and show that is false. Put another way, the logical negation of "for all , " is "there exists an such that is false".For all and there exists are quantifiers: they describe how to interpret a variable in a predicate.