LOGICAL INFERENCE & PROOFs
Debdeep Mukhopadhyay Dept of CSE, IIT Madras

Defn
• A theorem is a mathematical assertion which can be shown to be true. A proof is an argument which establishes the truth of a theorem.

Nature & Importance of Proofs
• In mathematics, a proof is:
– a correct (well-reasoned, logically valid) and complete (clear, detailed) argument that rigorously & undeniably establishes the truth of a mathematical statement.

• Why must the argument be correct & complete?
– Correctness prevents us from fooling ourselves. – Completeness allows anyone to verify the result.

• In this course (& throughout mathematics), a very high standard for correctness and completeness of proofs is demanded!!

Overview
• Methods of mathematical argument (i.e., proof methods) can be formalized in terms of rules of logical inference. • Mathematical proofs can themselves be represented formally as discrete structures. • We will review both correct & fallacious inference rules, & several proof methods.

Applications of Proofs
• An exercise in clear communication of logical arguments in any area of study. • The fundamental activity of mathematics is the discovery and elucidation, through proofs, of interesting new theorems. • Theorem-proving has applications in program verification, computer security, automated reasoning systems, etc. • Proving a theorem allows us to rely upon on its correctness even in the most critical scenarios.

Proof Terminology
• Theorem
– A statement that has been proven to be true.

• Axioms, postulates, hypotheses, premises
– Assumptions (often unproven) defining the structures about which we are reasoning.

• Rules of inference
– Patterns of logically valid deductions from hypotheses to conclusions.

More Proof Terminology
• Lemma - A minor theorem used as a steppingstone to proving a major theorem. • Corollary -