CS 70 Discrete Mathematics for CSSpring 2008 David Wagner Note 2Lesson PlanIn order to be fluent in mathematical statements, you need to understand the basic framework of the languageof mathematics. This first week, we will start by learning about what logical forms mathematical theoremsmay take, and how to manipulate those forms to make them easier to prove. In the next few lectures, we willlearn several different methods of proving things.PropositionsA proposition is a statement which is either true or false.These statements are all propositions:(1)√3 is irrational.(2) 1+ 1 = 5.(3) Julius Caesar had 2 eggs for breakfast on his 10thbirthday.These statements are clearly not propositions:(4) 2+ 2.(5) x2+ 3x = 5.These statements aren’t propositions either (although some books say they are). Propositions should notinclude fuzzy terms.(6) Arnold Schwarzenegger often eats broccoli. (What is “often?”)(7) George W. Bush is popular. (What is “popular?”)Propositions may be joined together to form more complex statements. Let P, Q, and R be variables rep-resenting propositions (for example, P could stand for “3 is odd”). The simplest way of joining thesepropositions together is to use the connectives “and”, “or” and “not.”(1) Conjunction: P∧Q (“P and Q”). True only when both P and Q are true.(2) Disjunction: P∨Q (“P or Q”). True when at least one of P and Q is true.(3) Negation: ¬P (“not P”). True when P is false.CS 70, Spring 2008, Note 2 1Statements like these, with variables, are called propositional forms. If we let P stand for the proposition“3 is odd,” Q stand for “4 is odd,” and R for “5 is even,” then the propositional forms P∧R, P∨R and ¬Qare false, true, and true, respectively. Note that P ∨¬P is always true, regardless of the truth value of P. Apropositional form that is always true is called a tautology, a statement that is always true regardless of thetruth values of its variables. P∧¬P is an example of a contradiction, a statement that is always false.A useful tool for describing the possible values of a propositional form is a truth table. Truth tables are thesame as function tables. You list all possible input values for the variables, and then list the outputs giventhose inputs. (The order does not matter.)Here are truth tables for conjunction, disjunction and negation:P Q P∧QT T TT F FF T FF F FP Q P∨QT T TT F TF T TF F FP ¬PT FF TThe most important and subtle propositional form is an implication:(4) Implication: P =⇒Q (“P implies Q”). This is the same as “If P, then Q.”Here, P is called the hypothesis of the implication, and Q is the conclusion.1Examples of implications:If you stand in the rain, then you’ll get wet.If you passed the class, you received a certificate.An implication P =⇒ Q is false only when P is true and Q is false. For example, the first statement wouldbe false only if you stood in the rain but didn’t get wet. The second statement above would be false only ifyou passed the class yet you didn’t receive a certificate. In contrast, you might get wet without standing inthe rain (e.g., when you are showering), and that doesn’t contradict the first statement.1P is also called the antecedent and Q the consequent.CS 70, Spring 2008, Note 2 2Here is the truth table for P =⇒ Q:P Q P =⇒ Q ¬P∨QT T T TT F F FF T T TF F T TNote that P =⇒ Q is always true when P is false. This means that many statements that sound nonsensicalin English are true, mathematically speaking. Examples are statements like: “If pigs can fly, then horses canread” or “If 14 is odd then 1+2 = 18.” When an implication is stupidly true because the hypothesis is false,we say that it is vacuously true. Note also that P =⇒ Q is logically equivalent to ¬P∨Q, as can be seenfrom the above truth table.P =⇒ Q is the most common form mathematical theorems take. Here are some of the different ways ofsaying it:(1) If P, then Q.(2) Q if P.(3) P only if Q.(4) P is sufficient for Q.(5) Q is necessary for P.If both P =⇒ Q and Q =⇒ P are true, then we say “P if and only if Q” (abbreviated P iff Q). Formally, wewrite P ⇐⇒ Q. P if and only if Q is true only when P and Q have the same truth values.For example, if we let P be “3 is odd,” Q be “4 is odd,” and R be “6 is even,” then P =⇒ R, Q =⇒ P(vacuously), and R =⇒P. Because P =⇒R and R =⇒ P, we have P ⇐⇒ R (i.e., P if and only if R).Given an implication P =⇒ Q, we can also define its(a) Contrapositive: ¬Q =⇒ ¬P(b) Converse: Q =⇒ PThe contrapositive of “If you passed the class, you received a certificate” is “If you did not get a certifi-cate, you did not pass the class.” The converse is “If you got a certificate, you passed the class.” Does thecontrapositive say the same thing as the original statement? Does the converse?Let’s look at the truth tables:P Q ¬P ¬Q P =⇒ Q Q =⇒ P ¬Q =⇒ ¬P P ⇐⇒ QT T F F T T T TT F F T F T F FF T T F T F T FF F T T T T T TNote that P =⇒ Q and its contrapositive have the same truth values everywhere in their truth tables; propo-sitional forms having the same truth values are said to be logically equivalent. Many students confuse theCS 70, Spring 2008, Note 2 3contrapositive with the converse: note that P =⇒ Q and ¬Q =⇒ ¬P are logically equivalent, but P =⇒ Qand Q =⇒ P are not!When two propositional forms are logically equivalent, we can think of them as “meaning the same thing.”We will see next time how useful this can be for proving theorems.QuantifiersThe mathematical statements you’ll see in practice will not be made up of simple propositions like “3 isodd.” Instead you’ll see statements like:(1) For all natural numbers n, n2+ n+ 41 is prime.(2) If n is an odd integer, so is n3.(3) There is an integer k that is both even and odd.In essence, these statements assert something about lots of simple propositions all at once. For instance, thefirst statement is asserting that 02+ 0 + 41 is prime, 12+ 1 + 41 is prime, and so on. The last statement issaying that as k ranges over every possible integer, we will find at least one value for which the statement issatisfied.Why are the above three examples considered to be propositions, while earlier we claimed that “x2+3x = 5”was not? The reason is that these three examples are in some sense “complete”, where “x2+ 3x = 5” is“incomplete” because whether it is true or
View Full Document
Unlocking...