2434 words - 10 pages

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 ...view middle of the document...

• Conjecture - A statement whose truth value has not been proven. (A conjecture may be widely believed to be true, regardless.) • Theory – The set of all theorems that can be proven from a given set of axioms.

Graphical Visualization

A Particular Theory

A proof

…

The Axioms of the Theory

Various Theorems

Inference Rules - General Form

• An Inference Rule is

– A pattern establishing that if we know that a set of antecedent statements of certain forms are all true, then we can validly deduce that a certain related consequent statement is true.

• antecedent 1 antecedent 2 … ∴ consequent “therefore”

“∴” means

Inference Rules & Implications

• Each valid logical inference rule corresponds to an implication that is a tautology. • antecedent 1 Inference rule antecedent 2 … ∴ consequent • Corresponding tautology:

((ante. 1) ∧ (ante. 2) ∧ …) → consequent

Some Inference Rules

p ∴ p∨q • p∧q ∴p • p q ∴ p∧q • Rule of Addition Rule of Simplification Rule of Conjunction

Modus Ponens & Tollens

p p→q ∴q • ¬q p→q ∴¬p • Rule of modus ponens (a.k.a. law of detachment)

“the mode of affirming”

Rule of modus tollens

“the mode of denying”

Syllogism Inference Rules

p→q q→r ∴p→r • p∨q ¬p ∴q • Rule of hypothetical syllogism Rule of disjunctive syllogism

Aristotle (ca. 384-322 B.C.)

Formal Proofs

• A formal proof of a conclusion C, given premises p1, p2,…,pn consists of a sequence of steps, each of which applies some inference rule to premises or previously-proven statements (antecedents) to yield a new true statement (the consequent). • A proof demonstrates that if the premises are true, then the conclusion is true.

Formal Proof Example

• Suppose we have the following premises: “It is not sunny and it is cold.” “We will swim only if it is sunny.” “If we do not swim, then we will canoe.” “If we canoe, then we will be home early.” • Given these premises, prove the theorem “We will be home early” using inference rules.

Proof Example cont.

• Let us adopt the following abbreviations:

– sunny = “It is sunny”; cold = “It is cold”; swim = “We will swim”; canoe = “We will canoe”; early = “We will be home early”.

• Then, the premises can be written as: (1) ¬sunny ∧ cold (2) swim → sunny (3) ¬swim → canoe (4) canoe → early

Proof Example cont.

Step 1. ¬sunny ∧ cold 2. ¬sunny 3. swim→sunny 4. ¬swim 5. ¬swim→canoe 6. canoe 7. canoe→early 8. early Proved by Premise #1. Simplification of 1. Premise #2. Modus tollens on 2,3. Premise #3. Modus ponens on 4,5. Premise #4. Modus ponens on 6,7.

Inference Rules for Quantifiers

• ∀x P(x) ∴P(o) • P(g) ∴∀x P(x) • ∃x P(x) ∴P(c) • P(o) ∴∃x P(x) (substitute any specific object o) (for g a general element of u.d.)

(substitute a new constant c) (substitute any extant object o)

Common Fallacies

• A fallacy is an inference rule or other proof method that is not logically valid.

– A fallacy may yield a false conclusion!

• Fallacy of affirming the conclusion:

...

Beat writer's block and start your paper with the best examples