tailieunhanh - The Mathematics for Computer Science

Constructivism is the bedrock on which the whole reform movement, especially the three NCTM volumes [N1]-[N3], rests. Roughly, this is the education philosophy which holds that the acquisition of knowledge takes place only when the external input has been internalized and integrated into one’s own mind. Thus learning requires the construction of a mental image in response to the external input. So far so good, except that current proponents of constructivism go further and stipulate that classroom time should be used for the students to re-discover or re-invent the concepts or the methods of solution in order to help along this mental construction, and that the best way to. | mcs 2013 1 10 0 28 page i 1 Mathematics for Computer Science revised Thursday 10th January 2013 00 28 Eric Lehman Google Inc. F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory Massachussetts Institute of Technology Akamai Technologies Albert R Meyer Department of Electrical Engineering and Computer Science and the Computer Science and AI Laboratory Massachussetts Institute of Technology Creative Commons 2011 Eric Lehman F Tom Leighton Albert R Meyer . mcs 2013 1 10 0 28 page ii 2 mcs 2013 1 10 0 28 page iii 3 Contents I Proofs Introduction 3 1 What is a Proof 5 Propositions 5 Predicates 8 The Axiomatic Method 8 Our Axioms 9 Proving an Implication 11 Proving an If and Only If 13 Proof by Cases 15 Proof by Contradiction 16 Good Proofs in Practice 17 References 19 2 The Well Ordering Principle 25 Well Ordering Proofs 25 Template for Well Ordering Proofs 26 Factoring into Primes 28 Well Ordered Sets 29 3 Logical Formulas 39 Propositions from Propositions 40 Propositional Logic in Computer Programs 43 Equivalence and Validity 46 The Algebra of Propositions 48 The sAt Problem 53 Predicate Formulas 54 4 Mathematical Data Types 75 Sets 75 Sequences 79 Functions 79 Binary Relations 82 Finite Cardinality 86 5 Induction 101 Ordinary Induction .