This website uses cookies to ensure you have the best experience. Learn more

Proofs Of Discreet Mathematics Essay

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:
...

Other Papers Like Proofs of Discreet Mathematics

Metacognitive Essay

3093 words - 13 pages ). Metacognition in context: A study of collaborative metacognitive activity in a classroom community of mathematical inquiry, Unpublished doctoral thesis. The University of Queensland, Brisbane. Lakatos, I. (1976). Proofs and Refutations: The Logic of Mathematical Discovery. Cambridge: Cambridge University Press. National Council of Teachers of mathematics, (1989). Curriculum and evaluation standards for school mathematics. Reston, VA: NCTM

Biography of H.K.H. Weyl Essay

2236 words - 9 pages Hermann Klaus Hugo Weyl (9 November 1885 – 8 December 1955) was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski. His research has had major significance for theoretical physics as well as purely mathematical disciplines including

Frm Syllabus

1406 words - 6 pages 2011 FRM EXAM TRAINING SYLLABUS PART I Introduction to Financial Mathematics 1. Introduction to Financial Calculus a. Variables – Discrete and Continuous b. Univariate and Multivariate Functions – Dependent variable and Independent variable c. Physical representation of a function d. Linear and Non-Linear functions e. Limits of a function f. The number e and Natural Logarithm g. Differential Calculus – Differentiation, Interpretation

History of Algebra

912 words - 4 pages word algebra.) In the 9th century, the Arab mathematician al-Khwarizmi wrote one of the first Arabic algebras, a systematic exposé of the basic theory of equations, with both examples and proofs. By the end of the 9th century, the Egyptian mathematician Abu Kamil had stated and proved the basic laws and identities of algebra and solved such complicated problems as finding x, y, and z such that x + y + z = 10, x2 + y2 = z2, and xz = y2. Ancient

A Noon of Summer

3299 words - 14 pages formally verified, however, because such formal derivations are often much longer than the natural language proofs mathematicians commonly present. One verification project, Metamath, includes derivations of more than 10,000 theorems starting from the ZFC axioms and using first order logic. [edit] Areas of study Set theory is a major area of research in mathematics, with many interrelated subfields. [edit] Combinatorial set theory Main article

Btm8104 Unit 1

1288 words - 6 pages answers. a. The average height of all freshmen entering college in a certain year is 68.4 inches. Discreet as it can change from one instance to another. There is also a .4 involved in the description as well. b. The number of limbs on a 2-year-old oak tree is 21. Continuous as there is ever changing in the environment and will increase over the years. 3) Determine which of the four levels of measurement is

Art Of Conversation

3526 words - 15 pages move students forward, gently let them struggle, and valued their approaches. What a contrast to how I had taught and learned mathematics! With vivid memories of a number-theory course in which I memorized the proofs to 40 theorems for the final exam, I cautiously began teaching a number-theory course for prospective middle school teachers. My aha moment with these students was a semester long. We investigated number-theory ideas, I made sense of

Blaise Pasca

1439 words - 6 pages Blaise Pascal Considered one of the most advanced thinkers of his time in the areas of science and mathematics, Blaise Pascal is admired today mostly for his spiritual insights, argumentative style and form, and mastery of the French language (Bold, 1). His skepticism into matters both worldly and religious involved a uniform methodology, the creation of mathematical proofs, and focused especially on the difference of opinion between reason and

Isaac Newton

2472 words - 10 pages laws of motion. His amazing synthesis of ideas and unusual ability to rationalize them surely made him stand out in a world that was just seeing the birth of a modern science. Through his incredible mathematical analyses and inventions he single-handedly created the science of mechanics and explained the motion of planets. This, accompanied with his other work in mathematics set the stage for future analysis in the fields of mechanics

Mth/221 Discrete Math for Information Technology Week 4

1144 words - 5 pages * MTH/221 Week Four Individual problems: * * Ch. 11 of Discrete and Combinatorial Mathematics * Exercise 11.1, problems 8, 11 , text-pg:519 Exercise 11.2, problems 1, 6, text-pg:528 Exercise 11.3, problems 5, 20 , text-pg:537 Exercise 11.4, problems 14 , text-pg:553 Exercise 11.5, problems 7 , text-pg:563 * Ch. 12 of Discrete and Combinatorial Mathematics * Exercise 12.1, problems 11 , text-pg:585 Exercise

Topic: a Drastic Change Was Made to the Primary School Curriculum in 1999. 1. Explain the Rationale Behind the Need for Changes to the Curricula. 2. What Immediate and Long Term Impact Do These...

1494 words - 6 pages changes in 1999, thus making a significant difference in the quality of education that is presently being delivered at the primary level. The curriculum that existed previously before to1999 was specific in three basic areas. These were Mathematics, Reading and Writing. The content was based predominantly on the English system of education which was highly irrelevant to our society. It was dominated by the teacher wherein he was the center of all

Related Essays

English As A Second Language Education

3605 words - 15 pages than conceptual development. I believed that a lack of language skills would keep me from succeeding in mathematics. I lost my interest in learning mathematics because I could not explain the problems in English. My self-esteem decreased when I could not solve the proofs. The language directly affected my physical and mental abilities to succeed in math courses. My language proficiency has improved, but my understanding of mathematics is slowly

Consider The Extent To Which Complete Certainty Might Be Achievable In Mathematics And At Least One Another Area Of Knowledge

1025 words - 5 pages Mathematicians have the concept of rigorous proof, which leads to knowing something with complete certainty. Consider the extent to which complete certainty might be achievable in mathematics and at least one another area of knowledge. When we look at it at first mathematics and history seems to be two areas of knowledge where proof leads to absolute certainity on the subject. A large proportion of people believe that in

Pythagorean Theoram Essay

1418 words - 6 pages Pythagorean Theorem by Angie Head This essay was inspired by a class that I am taking this quarter. The class is the History of Mathematics. In this class, we are learning how to include the history of mathematics in teaching a mathematics. One way to include the history of mathematics in your classroom is to incorporate ancient mathematics problems in your instruction. Another way is to introduce a new topic with some history of the topic

History Of Trigonometry Essay

3835 words - 16 pages science * Computer science * Materials science | Medicine[hide] * Medicine | Navigational pages[hide] * Timelines * Portal * Categories | * v * t * e | Trigonometry is a field of mathematics first compiled by 2nd century BCE by the Greek mathematician Hipparchus. The history of trigonometry and of trigonometric functions follows the general lines of the history of mathematics. Early study of triangles can be traced to