SP18:Lecture 4 Logic

From CS2800 wiki

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


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

For example, [math]3 \gt 5 [/math] is a proposition, as is [math]3 \lt 5 [/math]. "Professor George is taller than 5'" is a proposition. If [math]x [/math] is known to be 5, then "[math]x \gt 5 [/math]" is a proposition.

If a fact depends on a variable, we will not consider it to be a proposition. For example, "[math]x \gt 5 [/math]" by itself is not a proposition. Neither is "[math]x \gt x-1 [/math]". These statements are called properties of [math]x [/math], or predicates on [math]x [/math]. Similarly, we can have properties of two variables (e.g. [math]x \gt y [/math]).

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

For example, "for any sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]" is a proposition, as is "there exists some [math]x [/math] with [math]x \gt 0 [/math]".

This process can be repeated: "for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x \geq y [/math]" is a predicate, because it depends on [math]y [/math] (but not [math]x [/math]!). But "there exists [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] such that for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x ≥ y [/math]" is a proposition.

We are often lazy and leave off the quantification of a variable in a statement. When we have an undefined variable [math]x [/math] in a claim, we implicitly mean "for all [math]x [/math]". For example, if I ask you to prove or disprove that [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math], I implicitly mean to prove or disprove that, for all sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math].

Combining propositions

If you have propositions [math]P [/math], [math]Q [/math], and [math]R [/math], 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 [math]P [/math] and [math]Q [/math] are propositions, then "[math]P [/math] and [math]Q [/math]" is a proposition (written [math]P \href{/cs2800/wiki/index.php/%E2%88%A7}{∧} Q [/math]); it is true if both [math]P [/math] is true and [math]Q [/math] is true.

To prove "[math]P [/math] and [math]Q [/math]", you can separately prove [math]P [/math] and then prove [math]Q [/math].

If you have already proved (or assumed) [math]P [/math] and [math]Q [/math], you can conclude [math]P [/math]. You can also conclude [math]Q [/math].

To disprove "[math]P [/math] and [math]Q [/math]", you must either disprove [math]P [/math] or disprove [math]Q [/math]. Put another way, the logical negation of "[math]P [/math] and [math]Q [/math]" is "not [math]P [/math] or not [math]Q [/math]".

P or Q

If [math]P [/math] and [math]Q [/math] are propositions, then "[math]P [/math] or [math]Q [/math]" is a proposition (written [math]P \href{/cs2800/wiki/index.php/%E2%88%A8}{∨} Q [/math]); it is true if [math]P [/math] is true, or if [math]Q [/math] is true (or both).

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

To prove "[math]P [/math] or [math]Q [/math]", you can either prove [math]P [/math], or you can prove [math]Q [/math] (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 "[math]P [/math] or [math]Q [/math]", you must both disprove [math]P [/math] and disprove [math]Q [/math]. Put another way, the logical negation of "[math]P [/math] or [math]Q [/math]" is "not [math]P [/math] and not [math]Q [/math]".

P is false

If [math]P [/math] is a proposition, then "[math]P [/math] is false" (or more succinctly, "not [math]P [/math]", written [math]\href{/cs2800/wiki/index.php?title=%C2%ACP&action=edit&redlink=1}{¬P} [/math]) is also a proposition; it is true if [math]P [/math] is false, and false if [math]P [/math] is true.

  • To prove [math]P [/math] is false: disprove [math]P [/math]; To disprove "[math]P [/math] is false": prove [math]P [/math]. Put another way, the logical negation of "not [math]P [/math]" is [math]P [/math].
  • You can think of "proof by contradiction" as a way of using "not [math]P [/math]". If you are able to prove both [math]P [/math] and "not [math]P [/math]", 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 [math]P [/math] is false..." and usually ends "...this is a contradiction, and [math]P [/math] 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 [math]P [/math] is a predicate that depends on [math]x [/math], then "for all [math]x [/math], [math]P [/math]" is a proposition. It is true if every possible value of [math]x [/math] makes [math]P [/math] evaluate to true.

  • If your goal is to prove "for all [math]x\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A [/math], P", you can proceed by choosing an arbitrary value [math]x∈A [/math] and then proving that P holds for that [math]x [/math].

The fact that [math]x [/math] is arbitrary does not mean you get to pick [math]x [/math]; on the contrary, your proof should work no matter what [math]x [/math] you choose. This means you can't use any property of [math]x [/math] other than that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math].

  • If you know [math]P [/math] holds for all [math]x [/math], then you can conclude [math]P [/math] holds for any specific [math]x [/math]. For example, if you know for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ℝ [/math], [math]x^2 ≥ 0 [/math], then you can conclude [math]7^2 ≥ 0 [/math] (since [math]7 ∈ ℝ [/math]).