Methods of proof

Сентябрь 14, 2022

Содержание

2. Some terminology A theorem is a statement that can be shown to be true. In mathematical
3. Терминология We demonstrate that a theorem is true with a proof. A proof is a valid
4. Some terminology The statements used in a proof can include axioms (or postulates), which are statements
5. Some terminology Axioms may be stated using primitive terms that do not require definition, but all
6. Some terminology Rules of inference, together with definitions of terms, are used to draw conclusions from
7. Some terminology A less important theorem that is helpful in the proof of other results is
8. Some terminology A corollary is a theorem that can be established directly from a theorem that
9. Some terminology A conjecture is a statement that is being proposed to be a true statement,
10. Methods of proof In practice, the proofs of theorems designed for human consumption are almost always
11. Methods of proof Informal proofs can often explain to humans why theorems are true, while computers
12. Methods of proof The methods of proof discussed here are important not only because they are
13. Methods of proof Consequently, understanding the techniques used in proofs is essential both in mathematics and
14. Methods of proof
15. Methods of proof There are several standard methods of proof, including the following: direct argument, contrapositive
16. Direct argument
17. Contrapositive argument
18. Proof by contradiction
19. Example 1 Use a direct method of proof to show that if х and у are
20. Example 2 Let n be a positive integer. Prove, using the contrapositive, that if n2 is
21. Example 3 Use a proof by contradiction to show that if x2 = 2 then x
22. Example 3 Use a proof by contradiction to show that if x2 = 2 then x
23. Mathematical induction In computing a program is said to be correct if it behaves in accordance
24. Mathematical induction Consider the following recursive algorithm, intended to calculate the maximum element in a list
25. Mathematical induction To see how the algorithm works consider the input list a1 = 4, a2
26. Mathematical induction The output is М = 8, which is correct. Notice that after each execution
27. Mathematical induction So does the algorithm for all lists of any length n? Consider an input
28. Mathematical induction By condition 1) the algorithm works for any list of length 1, and so
29. Mathematical induction
30. Mathematical induction
31. Mathematical induction
32. Mathematical induction
33. Mathematical induction
34. Mathematical induction Example 3 A sequence of integers x1, x2, …, xn is defined recursively as
36. Скачать презентацию

Слайд 2

Some terminology
A theorem is a statement that can be shown to

be true.
In mathematical writing, the term theorem is usually reserved for a statement that is considered at least somewhat important.
Less important theorems sometimes are called propositions.
A theorem may be the universal quantification of a conditional statement with one or more premises and a conclusion.

Слайд 3

Терминология
We demonstrate that a theorem is true with a proof.
A

proof is a valid argument that establishes the truth of a theorem.

Some terminology

Слайд 4

Some terminology
The statements used in a proof can include
axioms (or

postulates), which are statements we assume to be true,
the premises, if any, of the theorem,
and previously proven theorems.

Слайд 5

Some terminology
Axioms may be stated using primitive terms that do not

require definition, but all other terms used in theorems and their proofs must be defined.

Слайд 6

Some terminology
Rules of inference, together with definitions of terms, are used

to draw conclusions from other assertions, tying together the steps of a proof. In practice, the final step of a proof is usually just the conclusion of the theorem.

Слайд 7

Some terminology
A less important theorem that is helpful in the proof

of other results is called a lemma (plural: lemmas or lemmata).
Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually.

Слайд 8

Some terminology
A corollary is a theorem that can be established directly

from a theorem that has been proved.

Слайд 9

Some terminology
A conjecture is a statement that is being proposed to

be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert.
When a proof of a conjecture is found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they are not theorems.

Слайд 10

Methods of proof
In practice, the proofs of theorems designed for human

consumption are almost always informal proofs,
where more than one rule of inference may be used in each step, where steps may be skipped,
where the axioms being assumed and the rules of inference used are not explicitly stated.

Слайд 11

Methods of proof
Informal proofs can often explain to humans why theorems

are true, while computers are perfectly happy producing formal proofs using automated reasoning systems.

Слайд 12

Methods of proof
The methods of proof discussed here are important not

only because they are used to prove mathematical theorems, but also for their many applications to computer science.
These applications include
verifying that computer programs are correct, establishing that operating systems are secure,
making inferences in artificial intelligence,
showing that system specifications are consistent, and so on.

Слайд 13

Methods of proof
Consequently, understanding the techniques used in proofs is essential

both in mathematics and in computer science.

Слайд 14

Methods of proof

Слайд 15

Methods of proof
There are several standard methods of proof, including the

following:
direct argument,
contrapositive argument,
proof by contradiction.

Слайд 16

Direct argument

Слайд 17

Contrapositive argument

Слайд 18

Proof by contradiction

Слайд 19

Example 1 Use a direct method of proof to show that

if х and у are odd integers, then ху is also odd.

Слайд 20

Example 2 Let n be a positive integer. Prove, using the

contrapositive, that if n2 is odd, then n is odd.

Слайд 21

Example 3 Use a proof by contradiction to show that if

x2 = 2 then x is not a fraction.

Solution
By way of contradiction, assume that х is a fraction and write х = m/n where n and m are integers, n is not equal to 0 and n and m have no common factors. Since x2 = 2, we have that (m/n)2 = 2. Therefore, m2 = 2 n2. But this implies that m2 is an even integer. Therefore, т is an even integer. Hence, т = 2р for some other integer р.

Слайд 22

Example 3 Use a proof by contradiction to show that if

x2 = 2 then x is not a fraction.

Слайд 23

Mathematical induction
In computing a program is said to be correct if

it behaves in accordance with its specification. Whereas program testing shows that selected input values give acceptable output values, proof of correctness uses formal logic to prove that for any input values, the output values are correct.
Proving the correctness of algorithms containing loops requires a powerful method of proof called mathematical induction.

Слайд 24

Mathematical induction
Consider the following recursive algorithm, intended to calculate the maximum

element in a list a1, a2, …, an of positive integers.
begin
г:=0;
М:=0;
while г < n do
begin
r :=r+1;
M:=max(M, ar);
end
еnd

Слайд 25

Mathematical induction
To see how the algorithm works consider the input list

a1 = 4, a2 = 7, a3 = 3 and a4 = 8. The trace table is given in the next table.

Слайд 26

Mathematical induction
The output is М = 8, which is correct. Notice

that after each execution of the loop, М is the maximum of the elements of the list so far considered.

Слайд 27

Mathematical induction
So does the algorithm for all lists of any length

n?
Consider an input a1, a2, …, an of length n and let Mk be the value of М after k executions of the loop.
For an input list a1 of length 1, the loop is executed once and M is assigned to be the maximum of 0 and a1,which is just a1. It is the correct input.
If after k executions of the loop, Mk is the maximum element of the list a1, a2, …, ak then after one more loop Mk+1 is assigned the value max(Mk, ak+1 ) which will then be the maximum element of the list a1, a2, …, ak+1.

Слайд 28

Mathematical induction
By condition 1) the algorithm works for any list of

length 1, and so by condition 2) it works for any list of length 2. By condition 2) again it works for any list of length 3, and so on. Hence, the algorithm works for any list of length n and so the algorithm is correct.
This process can be formalised as follows.

Слайд 29

Mathematical induction

Слайд 30

Mathematical induction

Слайд 31

Mathematical induction

Слайд 32

Mathematical induction

Слайд 33

Mathematical induction

Слайд 34

Mathematical induction
Example 3
A sequence of integers x1, x2, …, xn

is defined recursively as follows:
x1 = 1 and xk+1 = xk + 8k for к >= 1.
Prove that
xn = (2n – 1)2 for all n >= 1.
Solution
Let Р(n) be the predicate xn = (2n – 1)2. In the case n = 1, (2n – 1)2 = (2 • 1 – 1)2 = 1. Therefore, Р(1) is true.