CMPSC 40 Lecture Notes - Lecture 1: Number Theory, Discrete Mathematics, Mathematical Induction
Document Summary
Computer science is built upon ideas in logic, set theory, number theory, computability, etc. Can we determine important boundaries? i. e. minimum/maximum/average number of steps to solve a problem. Primary goal of course is to learn how to construct/read mathematical proofs. Important to have rigorous methods to check that programs/systems behave as expected. Important to have methods to analyze the complexity of programs. Proof = a derivation that proceeds form a set of hypotheses (premises, axioms) in order to derive a conclusion, using a set of logical rules. Axiomatic method = the standard procedure for establishing truth in mathematics. Start with basic assumptions (propositions that are undeniably true) Proof = sequence of logical deductions from axioms and previously-proved statements that concludes with the proposition in question. Propositional logic provides a good foundation for representing and reasoning about facts. Syntax defines the proper sentences in the language. Correspondence (isomorphism) between sentences and facts in the world.
