DOC PREVIEW
Berkeley COMPSCI 70 - n2

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 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 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 2ProofsIntuitively, the concept of proof should already be familiar. We all like to assert things, and few of us like tosay things that turn out to be false. A proof provides a means for guaranteeing such claims.Proofs in mathematics and computer science require a precisely stated proposition to be proved. But whatexactly is a proof? How do you show that a proposition is true? Recall that there are certain propositionscalled axioms or postulates, that we accept without proof (we have to start somewhere). A formal proof is asequence of statements, ending with the proposition being proved, with the property that each statement iseither an axiom or its truth follows easily from the fact that the previous statements are true. For example,in high school geometry you may have written two-column proofs where one column lists the statementsand the other column lists the justifications for each statement. The justifications invoke certain very simplerules of inference which we trust (such as if P is true and Q is true, then P∧Q is true). Every proof has theseelements, though it does not have to be written in a tabular format. And most importantly, the fact that eachstep follows from the previous step is so straightforward, it can be checked by a computer program.A formal proof for all but the simplest propositions is too cumbersome to be useful. In practice, mathemati-cians routinely skip steps to give proofs of reasonable length. How do they decide which steps to include inthe proof? The answer is sufficiently many steps to convince themselves and the reader that the details caneasily be filled in if desired. This of course depends upon the knowledge and skill of the audience. So inpractice proofs are socially negotiated.1During the first few weeks of the semester, the proofs we will write will be quite formal. Once you get morecomfortable with the notion of a proof, we will relax a bit. We will start emphasizing the main ideas in ourproofs and sketching some of the routine steps. This will help increase clarity and understanding and reduceclutter. A proof, for the purposes of this class, is essentially a convincing argument. Convincing to whom?First, to you, the author, second, to your classmates, third, to your professor and your TA.In this lecture you will see some examples of proofs. The proofs chosen are particularly interesting andelegant, and some are of great historical importance. But the purpose of this lecture is not to teach you aboutthese particular proofs (and certainly not for you to attempt to memorize any of them!). Instead, you shouldsee these as good illustrations of various basic proof techniques. You will notice that sometimes when it ishard to even get started proving a certain proposition using one proof technique, it is easy using a differenttechnique. This will come in handy later in the course when you work on homework problems or try toprove a statement on your own. If you find yourself completely stuck, rather than getting discouraged youmight find that using a different proof technique opens doors that were previously closed.We now begin with a few definitions pertaining to proofs.A theorem, informally speaking, is a true proposition that is guaranteed by a proof. If you believe that astatement is true but can’t prove it, call it a conjecture, essentially an educated guess.A concept useful for writing up complicated proofs is that of a lemma, which is a little theorem that you usein the proof of a bigger theorem. A lemma is to proofs what a subroutine is to programming.1Those interested in exploring this issue in more detail may like to read the influential paper “Social Processes and Proofs ofTheorems and Programs" by DeMillo, Lipton and Perlis, Communications of the ACM 22 (1979) pages 271–280.EECS 70, Spring 2014, Note 2 1An axiom is a statement we accept as true without proof.There are many different types of proofs, as we shall see. The basic structure of these different types ofproofs is best expressed in terms of propositional logic.Direct ProofLet us start with a very simple example.Theorem: If x is an odd integer, then x + 1 is even.Following the notation introduced in the previous Note, this statement is equivalent to(∀x ∈ Z)(x is odd =⇒ x + 1 is even).(Here Z denotes the set of all integers.) For each x, the proposition that we are trying to prove is of theform P(x) =⇒ Q(x). A direct proof of this starts by assuming P(x) for a generic value of x and eventuallyconcludes Q(x) through a chain of implications:Direct Proof of P =⇒ QAssume P...Therefore QLet us proceed with a direct proof of the simple example given above:Proof: Assume x is odd. Then by definition, x = 2k + 1 for some k ∈ Z. Adding one to both sides, we getx + 1 = 2k + 2 = 2(k + 1). Therefore, by definition, x + 1 is an even number. ♠Before turning to our next example, we recall that integer d divides n (denoted d|n) iff there exists someinteger q such that n = dq.Theorem: Let n be a positive integer. If the sum of the digits of n is divisible by 9, then n is divisible by 9.As in the previous example, this statement is equivalent to(∀n ∈ Z+)(sum of n’s digits divisible by 9 =⇒ n divisible by 9).(Here Z+denotes the set of positive integers, {1,2,. ..}.) So once again we start by assuming, for a genericvalue of n, that the sum of n’s digits is divisible by 9. Then we perform a sequence of steps to conclude thatn itself is divisible by 9. Actually, to keep the notation simple, we will restrict attention to the case wheren < 1000; the proof for general n is essentially the same. Here is the proof:Proof: Suppose we have n < 1000 such that the sum of the digits of n is divisible by 9. Let a be thehundred’s digit of n, b the ten’s digit, and c the one’s digit. Then n = 100a + 10b + c. Now suppose that thesum of the digits of n is divisible by 9. Then,a + b + c = 9k, k ∈ Z.Adding 99a + 9b to both sides of the equation, we get100a + 10b + c = n = 9k + 99a + 9b = 9(k + 11a + b).EECS 70, Spring 2014, Note 2 2So n is divisible by 9. ♠Exercise: Generalize the above proof so that it works for any positive integer n. [HINT: Suppose n has kdigits, and write aifor the digits of n, so that n =∑k−1i=0ai×10i.]In this case the converse of the theorem is also true: If n is divisible by 9, the sum of its digits is divisibleby 9, too. In other words, the sum of the digits of n is


View Full Document

Berkeley COMPSCI 70 - n2

Documents in this Course
Notes 1

Notes 1

12 pages

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

n1

n1

5 pages

Load more
Download n2
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 n2 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 n2 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?