CMPSC 40 Lecture 18: Lecture 18 Final Exam Review
Document Summary
The foundations of discrete math: logic and proofs. A proof is a derivation that proceeds from a set of hypotheses (premises, axioms) in order to derive a conclusion, using a set of logical rules. Requires application of common sense, widely-known material, filling in obvious steps, etc. The standard procedure for establishing truth in mathematics is the axiomatic method. Start with basic assumptions -- propositions that are undeniably true. A proof is a sequence of logical deductions from axioms and previously-proved statements that concludes with the proposition in question. We need a formal way to represent knowledge and rules of inference that define valid logical deduction. Syntax defines the proper sentences in the language. Correspondence (isomorphism) between sentences and facts in the world. Sentences can be true or false with respect to the semantics. A proposition is a declarative sentence that is either true or false. A sentence in the form of a statement.