# 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).

# Propositions

Definition: Proposition
A proposition is a statement that is either true or false.

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.

If a fact depends on a variable, we will not consider it to be a proposition. For example, "" by itself is not a proposition. Neither is "". These statements are called properties of , or predicates on . Similarly, we can have properties of two variables (e.g. ).

Predicates can be turned into propositions by quantifying them; stating that they must be true either for all or for some .

For example, "for any sets and , " is a proposition, as is "there exists some with ".

This process can be repeated: "for all , " is a predicate, because it depends on (but not !). But "there exists such that for every , " 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 , .

# Combining propositions

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

If and are propositions, then " and " is a proposition (written ); it is true if both is true and is true.

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 .

To disprove " and ", you must either disprove or disprove . Put another way, the logical negation of " and " is "not or not ".

## P or Q

If and are propositions, then " or " is a proposition (written ); it is true if is true, or if is true (or both).

Note that this is somewhat different from the use of "or" in colloquial English; if both and are true, we still consider or to be true. This saves us work: we can prove or by just proving ; we don't have to also disprove .

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.

To disprove " or ", you must both disprove and disprove . Put another way, the logical negation of " or " is "not and not ".

## P is false

If is a proposition, then " is false" (or more succinctly, "not ", written ) is also a proposition; it is true if is false, and false if is true.

• 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 is a predicate that depends on , then "for all , " is a proposition. It is true if every possible value of makes evaluate to true.

The fact that is 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 .

• If you know holds for all , then you can conclude holds for any specific . For example, if you know for all , , then you can conclude (since ).