CS 70 Discrete Mathematics and Probability TheoryFall 2011 Rao Note 1Course OutlineCS70 is a course on discrete mathematics and probability theory, especially tailored for EECS students. Thepurpose of the course is to teach you about:• Fundamental ideas in computer science and electrical engineering:- Boolean logic- Modular arithmetic, public-key cryptography, error-correcting codes, secret sharing protocols- The power of randomization (“flipping coins”) in computation: load balancing, hashing, inference,overcoming noise in communication channels- Uncomputability and the halting problemMany of these concepts form a foundation for more advanced courses in EECS. science.• Precise, reliable, powerful thinking:- Proofs of correctness. These are essential to analyzing algorithms and programs- Induction and recursion- Probability theory• Problem solving skills:- These are emphasized in the discussion sections and homeworks.Course outline (abbreviated):• Propositions, propositional logic and proofs• Mathematical induction, recursion• The stable marriage problem• Modular arithmetic, the RSA cryptosystem• Polynomials over finite fields and their applications: error-correcting codes, secret sharing• Probability and probabilistic algorithms: load balancing, hashing, expectation, variance, Chebyshevbounds, conditional probability, Bayesian inference, law of large numbers, Central Limit Theorem.• Diagonalization, self-reference, and uncomputabilityGetting StartedIn 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.CS 70, Fall 2011, Note 1 1PropositionsA 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) Barack Obama 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.Statements 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 regardless of the truth values of its variables is called a tautology. Astatement such as P∧¬P, which is always false, is called a contradiction.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.)CS 70, Fall 2011, Note 1 2Here 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 interpreted as “If P, then Q.” It islogically equivalent to (¬P)∨Q. In other words, P =⇒Q is a more concise (and possibly moreintuitive) way of writing (¬P) ∨Q, but it has exactly the same meaning.In the expression P =⇒Q, 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.Here 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.1P is also called the antecedent and Q the consequent.CS 70, Fall 2011, Note 1 3P =⇒ 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 ⇐⇒ 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 certificate,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
View Full Document
Unlocking...