DOC PREVIEW
Berkeley COMPSCI 70 - Notes 1

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 70 Discrete Mathematics for CSSpring 2005 Clancy/Wagner Notes 1Purpose of the CourseCS 70 is a course designed as an alternative to Math 55. In comparison to Math 55, we will focus on fewertopics, and the topics covered will be motivated by computational tasks. We hope to make the course morerelevant to CS students and hence to instill a deeper and longer-lasting understanding of the underlyingmathematics.What we want to teach:• Precise, reliable, powerful thinking:will allow you to use and develop more complex and subtle ideas in CS, well beyond the obvious“brute force” approach to every problem, and will help you to avoid silly errors on all your CS finalexams.• The ability to state and prove nontrivial facts, in particular about programs:will enable you to write rigorously correct programs, which in turn provide solid building blocks forever-more-complex yet still reliable systems;• Mathematical foundations and ideas useful throughout CS:will provide familiarity with logic, inductively defined structures, integer and polynomial arithmetic,and probabilities—concepts that underly all of the more advanced courses in CS.Course outline (abbreviated).• Propositions and Proofs• Mathematical Induction: recursion, the stable marriage problem• Propositional Logic: automated proof and problem-solving• Arithmetic Algorithms: gcd, primality testing, the RSA cryptosystem• Polynomials and their Applications: error-correcting codes, secret sharing• Probability and Probabilistic Algorithms: load balancing, hashing, probabilistic constructions, condi-tional probability Bayesian inference• Diagonalization, Self-Reference, and UncomputabilityPropositions and ProofsMany of the unenlightened believe proofs to be pointless formal exercises in guessing a way through a mazeto reach a 2,400-year-old fortune cookie.Far from it. We all like to say things:CS 70, Spring 2005, Notes 1 1“This encryption system cannot be broken”“My program works efficiently in all cases”“There are no circumstances under which I would lie to Congress”“It is inconceivable that our legal system would execute an innocent person”and so on. Few of us like to say things that turn out to be false. Proof means never having to say you’resorry—it provides a means for guaranteeing your claims once and for all.1What we would like to do nowis to make these concepts more precise. (Most discrete mathematics courses just get on with doing proofs;this isn’t a bad idea, but does skip over some important concepts.)Proofs in mathematics and computer science (as opposed to law and politics) require a precisely statedproposition to be proved.A proposition is a sentence that is either true or false.2PROPOSITIONA theorem, informally speaking, is a proposition that is guaranteed by a proof.THEOREMExamples of propositions:(1a) Some mammals lay eggs. (1b) Some mammals have feathers.(2) The acceleration of a rigid body is proportional to the force applied.(3) The angles of a triangle add up to 180 degrees.(4) For all nonnegative integers n, n2+ n+ 41 is prime.(5) For all integers n, if n > 2 then there are no positive integers a, b, c such that an+ bn= cn.(6) For every even integer n > 2, there are two primes a and b such that a+ b = n.It is important to note that every proposition is true or false with respect to a possible world. A world (or aWORLDmodel in logical terminology) is, conversely, something with respect to which every proposition of interestMODELis either true or false—that is, it is completely specified.For physics, chemistry, biology, etc., which are empirical sciences, we are usually interested in truth withrespect to the real world—the one we actually live in. But of course, we don’t know which one that is. Forexample, (1a) happens to be true in the real world, but could easily have been otherwise; whereas (1b) mayor may not be true. [Exercise: what could we mean by this? Could one prove that (1b) is false?](2) is one of Newton’s laws. It was assumed to be incontrovertibly true for many years, and many explana-tions were given for why it could not possibly be otherwise; but it is in fact false in the real world.3Now mathematicians, physicists, and engineers have been proving theorems in Newtonian mechanics forcenturies and continue to do so. As a matter of physical fact, most of these theorems are false in the realworld. They are, however, still theorems in Newtonian mechanics. An incorrect proof is not a proof, but afalse theorem may still be a theorem provided it follows logically from a specified set of axioms. An axiomAXIOMSis a proposition that is assumed to be true without proof. In Newtonian mechanics, Newton’s laws are takenas axiomatic.Proof, therefore, is a means of showing that a theorem follows logically from a set of axioms.PROOF1“What about incorrect proofs?” you may ask. An incorrect proof is not a proof, any more than artificial grass is grass.2Sentences that are not propositions include questions and commands—these cannot be true or false, although they can beperceptive or absurd.3Many people state that Newton’s laws were disproved by Einstein. This is not the case; Einstein merely proposed laws that areinconsistent with Newton’s. Empirical laws such as Newton’s can only be disproved by observations or by discovering an internalinconsistency.CS 70, Spring 2005, Notes 1 2Now we have to explain what is meant by “follows logically.”A proposition B follows logically from another proposition A if B is true in all possible worldsFOLLOWS LOGICALLYin which A is true.This relationship is often written as A |= B, which can be pronounced “A logically entails B.” If one drawsa picture of the set of worlds where A holds and the set of worlds where B holds, the set where A holds willbe contained within the set where B holds whenever A |= B. More mathematically, let M(A) be the set ofworlds where A holds and M(B) the set of worlds where B holds (we call these worlds the models of A andMODELSB). ThenA |= B if and only if M(A) ⊆ M(B)This relationship is shown in Figure 1(a). The direction of the ⊆ may be somewhat counterintuitive: nor-mally we think of A being “stronger” or “bigger” than B if A entails B. One route to reain intuition is toremember that every axiom added to A reduces the set of possible worlds where A holds, so makes it morefeasible for this set to be contained within the set of B-worlds (Figure 1(b)).M(A)M(B)M(B)M(A)M(A’)(a)


View Full Document

Berkeley COMPSCI 70 - Notes 1

Documents in this Course
Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download Notes 1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Notes 1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Notes 1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?