Theorem proving methods. Constructing mathematical proofs
Prove any statement- it means to show that this statement logically follows from the system of true and related statements.
Proof Is a logical operation, in the process of which the truth of any statement is substantiated with the help of other true and related statements. For this, a finite chain of inferences is built, and the conclusion of each of them (except for the last) is a premise in one of the subsequent inferences.
Basic laws of logic:
1. The law of identity. Every thought, repeating itself in reasoning, must be identical with itself.
The law of identity means that in the process of reasoning one cannot substitute one thought for another, one concept for another. Identical thoughts cannot be passed off as different, and different - as identical.
2. The law of consistency. A statement and its denial cannot be true at the same time; at least one of them is necessarily false.
If a formal-logical contradiction is found in the thinking (and speech) of a person, then such thinking is considered incorrect, and the judgment from which the contradiction follows is considered false.
3. The law of the excluded third. Of two contradictory statements about the same subject, one is true, and the other is false, the third is not given.
4. The law of sufficient reason. Any true statement must be substantiated with the help of other statements, the truth of which has been proven.
When it comes to mathematical proof, you must:
¾ have that statement, the truth of which needs to be proved;
¾ understand that proof is a chain of deductive inferences; it is performed according to the rules and laws of logic;
¾ understand what other true statements can be used in the process of proof.
According to the method of conducting, direct and indirect evidence are distinguished.
Direct proof of the statement A B is the construction of a chain of deductive inferences carried out sequentially from A to B in compliance with the rules and laws of logic and using a system of statements, the truth of which has been proven.
(If three corners are straight in quadrangles, then it is a rectangle)
An example of circumstantial evidence is proof by contradiction. Its essence is as follows. Suppose that it is required to prove Theorem A B. In the proof by contradiction, it is assumed that the conclusion of Theorem (B) is false, and, therefore, its negation is true. By joining sentence B to the set of true premises used in the process of proof (among which is condition A), they build a chain of deductive inferences until a statement is obtained that contradicts one of the premises and, in particular, condition A.
(a + 3> 10, then a ¹7)
Ticket 15 The concept of correspondence between sets. Methods for setting correspondences. Mutual - one-to-one correspondence. Equivalent sets. Examples of correspondences (including one-to-one).
Let's give an example of the use of incomplete induction in work with preschoolers: using the game "Wonderful bag" with volumetric geometric figures, we bark the task for the child: "Get the figure and name it." After several attempts, the child makes an assumption:
Ball. Ball. Ball. There are probably all the balls here.
Task 14
Suggest further reasoning to ensure that the statement is true (or false).
The importance of evidence in our lives and especially in science cannot be overemphasized. Everyone resorts to proofs, but they do not always think about what it means to “prove”. Practical skills of proof and intuitive ideas about it are sufficient for many everyday purposes, but not for scientific ones.
To prove any statement is to show that this logical statement logically follows from the system of true and related statements.
Proof is a logical operation of substantiating the truth of any statement with the help of other true and related statements.
There are three structural elements in the proof:
1) the statement to be proved;
2) a system of true statements, with the help of which the truth of what is being proved is justified;
3) a logical connection between pp. 1 and 2.
The main way of mathematical proof is deductive inference.
In its form proof is a deductive inference or a chain of deductive inferences leading from true premises to a proven statement.
In a mathematical proof, the order of the inference is important. According to the method of conducting, they distinguish direct and indirect evidence. Complete induction, which was discussed in Section 1.6, is a direct proof.
Full induction- a method of proof in which the truth of the statement follows from its truth in all special cases.
Full induction It is often used in games with preschoolers such as: "Name in one word."
An example of direct proof of the statement "The sum of the angles in any quadrangle is 360 °":
“Consider an arbitrary quadrangle. Having drawn a diagonal in it, we get 2 triangles. The sum of the angles of the quadrilateral will be equal to the sum of the angles of the two resulting triangles. Since the sum of the angles in any triangle is 180 °, then, adding 180 ° and 180 °, we get the sum of the angles in two triangles, it will be 360 °. Consequently, the sum of the angles in any quadrangle is 360 ", which is what was required to prove."
In the given proof, the following conclusions can be distinguished:
1. If the figure is a quadrangle, then a diagonal can be drawn in it, which will divide the quadrilateral into 2 triangles. This figure is a quadrilateral. Therefore, it can be split into 2 triangles by constructing a diagonal.
2. In any triangle, the sum of the angles is ISO. "These figures are triangles. Therefore, the sum of the angles of each of them is 180 °.
3. If a quadrilateral is composed of two triangles, then the sum of its angles is equal to the sum of the angles of these triangles. This quadrilateral is composed of two triangles with the sum of angles 180 ° each. 180 ° + 180 ° = 360 °. Therefore, the sum of the angles in this quadrilateral is 360 °.
All the above conclusions are made according to the rule of conclusion, therefore, they are deductive.
An example of circumstantial evidence is proof by contradiction. IN in this case admit that the conclusion is false, therefore its negation is true. Having attached this sentence to the totality of true premises, they carry out reasoning until they get a contradiction.
Let us give an example of a proof by contradiction of the theorem: “If two lines but and B are parallel to the third line c, then they are parallel to each other ":
“Suppose that straight but and b are not parallel, then they will intersect at some point A that does not belong to the line c. Then we get that through point A we can draw two straight lines a and b parallel to c. This contradicts the axiom of parallelism:
8. Formulate the rules for explicit identification through genus and species difference.
9. What definition is called:
Contextual;
Ostensive?
10. What is a statement, and what is a statement form?
11. When sentences of the types "A and B", "A or B", "Not A" are true, and when are they false?
12. List the quantifiers of generality and quantifiers of existence. How to set the truth value of sentences with different quantifiers?
13. When is there a following relation between sentences, and when is an equivalence relation? How are they designated?
14. What is inference? What inference is called deductive?
15. Using symbols, write down the rules of conclusion, the rule of negation, the rule of syllogism.
16. What inferences are called incomplete induction, and what inferences by analogy?
17. What does it mean to prove a statement?
18. What is mathematical proof?
19. Give the definition of complete induction.
20. What are sophisms?
Bibliographic description: Grigoriev K.V., Ochirova A.B., Sarangov A.A., Barlykova S.S., Muchkaeva G.M. A variety of methods of mathematical proof // Young scientist. - 2017. - No. 1. - S. 45-46..03.2019).
Speaking of proof, in everyday life, we mean the verification of the statement formulated. Directly in mathematics, the concepts of verification and proof are different in essence, although they carry a relationship.
Let's prove that if three angles in a quadrilateral are 90 degrees, then that quadrilateral is a rectangle.
Consider a quadrilateral with three angles equal to 90 degrees. Let's measure the fourth angle and find its degree measure. We come to the conclusion that it will also be direct. This kind of verification confirms this statement, but does not constitute evidence.
To prove this statement, it is necessary to consider an arbitrary quadrangle with three angles equal to 90⁰. Since in any convex quadrilateral the sum of the angles is 360⁰, therefore the sought angle is 90⁰ (360⁰ - 90⁰ * 3). A rectangle is a quadrangle with all corners straight. This means that this quadrilateral will be a rectangle. Q.E.D.
The meaning of the performed proof consists in the following sequence of true statements: theorems, axioms, definitions, from which the statement to be proved logically follows. To prove a statement means to show that a given statement follows logically from a number of true and related statements.
If the assertion in question logically follows from the already proven assertions, then it is justified and true. The deductive method serves as the basis for mathematical proof. And the proof itself acts as a chain of inferences, and the conclusion of each of them, except for the last, is a premise in one of the subsequent inferences.
In the considered proof, the following conclusions can be distinguished:
- in any convex quadrilateral, the sum of the angles is 360⁰; this figure is a convex quadrangle, therefore, the sum of the angles in it is 360⁰;
- if the sum of all angles of the quadrangle and the sum of three of them are known, then by subtracting you can find the value of the fourth; the sum of all the angles of this quadrilateral is 360⁰, the sum of three is 270⁰ (90⁰ · 3 = 270⁰), then by determining their difference, we find the desired angle equal to 90⁰;
- if all corners in a quadrangle are right, then this quadrangle is a rectangle; in our case, all corners in a quadrangle are right, hence it is a rectangle.
All considered inferences are executed according to the rule of conclusion and, accordingly, are deductive.
The simplest proof consists of one inference. This, for example, is the proof of the statement that 5
Considering the structure of a mathematical proof, we understand that it, first of all, includes a statement that is being proved, and a system of true statements by means of which the proof is conducted.
It is also important to note that mathematical proof is not just a set of inferences, but inferences arranged in a certain order.
According to the method of conducting, direct and indirect evidence are distinguished. The proof considered earlier is direct - in it, based on a separate true proposition and taking into account the conditions of the theorem, a chain of deductive inferences was connected, which directly led to a true conclusion.
An example of circumstantial evidence is contradictory proof. Its essence is as follows: let it be required to prove Theorem A ⇒ B. When proving by contradiction, it is assumed that the conclusion of Theorem (B) is false, and, therefore, its negation will be true. By attaching the sentence "not B" to the set of true premises used in the process of proof (among which there is also condition A), we carry out a chain of deductive inferences until we get a statement that contradicts one of the premises and, in particular, condition A. How only such a contradiction is established, the process of proof ends and one comes to the conclusion that the resulting contradiction proves the truth of Theorem A ⇒ B.
Problem 1. Prove that if х + 2> 10, then х ≠ 8. Method by contradiction.
Problem 2. Prove that if y2 is an even number, then y is even. Method by contradiction.
Problem 3. You are given four consecutive natural numbers. Is it true that the product of the means of this sequence is greater than the product of the extreme by 2? Incomplete induction method.
Full induction is a method of proof in which the truth of a statement follows from its truth in all special cases.
Problem 4. Prove that every composite natural number greater than 4 but less than 20 can be represented as a sum of two primes.
Thus, a mathematical proof is a reasoning for the purpose of substantiating the truth of any statement (theorem), a chain of logical inferences showing that, provided that a certain set of axioms and inference rules are true, the statement is true.
Literature:
- Geometry / 7-9 grades: textbook. For general education. Institutions / [L. S. Atanasyan, V. F. Butuzov, S. B. Kadomtsev]. - 21 ed. - M .: Education, 2011.
Lecture 10. Methods of mathematical proof
1. Methods of mathematical proof
2. Direct and indirect evidence. Proof by contradiction.
3. Key findings
In everyday life, when they talk about proof, they often mean just verification of the stated statement. In mathematics, verification and proof are two different things, albeit related. Suppose, for example, it is required to prove that if a quadrangle has three straight angles, then it is a rectangle.
If we take any quadrilateral with three straight angles, and, measuring the fourth, make sure that it is indeed straight, then this check will make this statement more plausible, but not yet proven.
To prove this statement, consider an arbitrary quadrangle in which three corners are straight lines. Since in any convex quadrilateral the sum of the angles is 360⁰, then in this one it is 360⁰. The sum of the three right angles is 270⁰ (90⁰ 3 = 270⁰), and therefore the fourth has a magnitude of 90⁰ (360⁰ - 270⁰). If all corners of a quadrilateral are straight, then it is a rectangle Therefore, this quadrilateral will be a rectangle. Q.E.D.
Note that the essence of the proof is in the construction of such a sequence of true statements (theorems, axioms, definitions), from which the statement to be proved logically follows.
Generally to prove a statement means to show that this statement logically follows from a system of true and related statements.
In logic, it is believed that if the statement in question logically follows from the statements already proven, then it is justified and just as true as the latter.
Thus, the basis of mathematical proof is deductive inference. And the proof itself is a chain of inferences, and the conclusion of each of them (except for the last) is a premise in one of the subsequent inferences.
For example, in the above evidence, the following inferences can be highlighted:
1. In any convex quadrilateral, the sum of the angles is 360⁰; this figure is a convex quadrilateral, therefore, the sum of the angles in it is 360⁰.
2. If you know the sum of all the angles of the quadrangle and the sum of three of them, then by subtracting you can find the value of the fourth; the sum of all the angles of this quadrangle is 360⁰, the sum of three is 270⁰ (90⁰ 3 = 270⁰), then the value of the fourth is 360⁰ - 270⁰ = 90⁰.
3. If in a quadrilateral all corners are right, then this quadrilateral is a rectangle; in this quadrilateral, all corners are right, therefore, it is a rectangle.
All the above inferences are made according to the rule of inference and, therefore, are deductive.
The simplest proof consists of one inference. This, for example, is the proof of the statement that 6< 8.
So, speaking about the structure of a mathematical proof, we must understand that it, first of all, includes a statement that is being proved, and a system of true statements with the help of which the proof is conducted.
It should also be noted that a mathematical proof is not just a set of inferences, it is inferences arranged in a certain order.
According to the method of conducting (in form), they distinguish direct and indirect proof of. The proof considered earlier was direct - in it, based on a certain true proposition and taking into account the conditions of the theorem, a chain of deductive inferences was built, which led to a true conclusion.
An example of circumstantial evidence is evidence by contradiction . Its essence is as follows. Suppose it is required to prove the theorem
A ⇒ B. In the proof by contradiction, it is assumed that the conclusion of Theorem (B) is false, and, therefore, its negation is true. By attaching the sentence "not B" to the set of true premises used in the process of proof (among which there is also condition A), they build a chain of deductive inferences until a statement is obtained that contradicts one of the premises and, in particular, condition A. How only such a contradiction is established, the process of proof is terminated and it is said that the resulting contradiction proves the truth of the theorem
Problem 1. Prove that if a + 3> 10, then a ≠ 7. Method by contradiction.
Problem 2. Prove that if x2 is an even number, then x is even. Method by contradiction.
Problem 3. You are given four consecutive natural numbers. Is it true that the product of the means of this sequence is greater than the product of the extreme by 2? Incomplete induction method.
Full induction- this is a method of proof in which the truth of a statement follows from its truth in all special cases.
Problem 4. Prove that every composite natural number greater than 4 but less than 20 can be represented as a sum of two primes.
Problem 5. Is it true that if a natural number n is not a multiple of 3, then the value of the expression n² + 2 is a multiple of 3? Complete induction method.
The brochure, in a language accessible to non-specialists, tells about some of the fundamental principles on which the science of mathematics is built: how the concept of mathematical proof differs from the concept of proof adopted in other sciences and in everyday life, what simple methods of proof are used in mathematics, how the idea of "Correct" proof of what the axiomatic method is, what is the difference between truth and provability.
For a very wide range of readers, starting with high school students.
MATHEMATICS AND PROOFS.
Even a person unfamiliar with mathematics, picking up a book on mathematics, can, as a rule, immediately determine that this book is really in mathematics, and not in some other subject. And the point is not only that there will necessarily be many formulas: there are formulas in books on physics, astronomy or bridge construction. The fact is that in any serious book on mathematics, there is certainly evidence. It is the provability of mathematical statements, the presence of proofs in mathematical texts - this is what most clearly distinguishes mathematics from other areas of knowledge.
The first attempt to cover all mathematics in a single treatise was made by the ancient Greek mathematician Euclid in the 3rd century BC. As a result, Euclid's famous "Principles" appeared. And the second attempt took place only in the XX century A.D. e., and it belongs to the French mathematician Nicholas Bourbaki, who began in 1939 to publish the multivolume treatise "Principles of Mathematics". With this phrase Bourbaki opens his treatise: "Since the time of the Greeks, to say 'mathematics' means to say 'proof'." Thus, "mathematics" and "proof" - these two words are declared almost synonymous.
TABLE OF CONTENTS
Mathematics and proof
On the accuracy and unambiguity of mathematical terms
Iterative proofs
Indirect evidence of existence. Dirichlet's principle
Evidence by contradiction
Least and Greatest Number Principles and the Infinite Descent Method
Induction
Proofs by mathematical induction
Full induction and incomplete induction
The idea of mathematical proof changes over time
Two axiomatic methods - informal and formal
Informal axiomatic method
Formal axiomatic method
Gödel's theorem.
Free download an e-book in a convenient format, watch and read:
Download the book The simplest examples of mathematical proofs, Uspensky V.A., 2009 - fileskachat.com, fast and free download.