《离散数学》双语教学 第一章 真值表,逻辑和证明

10

～

12

14

～

28

30

～

40

48

～

52

54

～

56

第

15

页

共

47

页

2010-12-27

《离散数学》双语教学

第一章

真值表，逻辑和证明

1.4 Axiomatic Systems: Arguments and Proofs

Much of mathematics deals with theorems and proofs of theorems.

Theorems are “true” statements about the mathematical system being

considered.

A theorem is a statement that can be shown to be true. We

demonstrate that a theorem is true with a sequence of statements that

form an argument (

证明～推理

).

Two important questions will arise in the study of mathematics are:

(1) When is a mathematical argument valid(correct)? (2) What

methods can be used to construct a valid mathematical argument?

An argument consists of a collection of statements called hypotheses

and a statement called its conclusion. A valid

argument is an argument whose conclusion true whenever all the

hypotheses are true.

To construct proofs, methods are needed to derive new statements

from old ones. The statements used in a proof can include axioms(

公

理

) or postulates(

公设

), the hypotheses of the theorem to be proved,

and previously proved theorems. The rules of inference(

推理规则

),

which are means used to draw conclusions from other assertions, tie

together the steps of a proof.

In a mathematical system, all of the information necessary to prove

a theorem must be contained in axioms and previously proven theorems.

推理就是从一组已知的命题出发～按照一组推理 规则推出新的命题的过程

.

已知命题称为推理的前提～推出的命题称为推理的结论

.

推理过程是一个有限

公

式序列～它以一个前提开始

.

它的最 后一个公式是结论～其余的公式或者是一

个

< br>公理、公设或给定的前提～或者是由若干个在它前面出现的公式的有效结论

.

定义

1.4.1 Suppose that the implication H?H?…?H ?C is a 12n

第

16

页

共

47

页

2010-12-27

《离散数学》双语教学

第一章

真值表，逻辑和证明

tautology, we say that C logically follows from H,H,…,H

. 12n

Virtually all mathematical theorems are composed of implications of

the type

H?H?…?H?C 12n

,The H are called the hypotheses(

假设

) or premises(

前提

), si

and C is called the conclusion.

To prove the theorem, we are trying to show that C will be true if

all the H are true. i

The first method of showing that an argument is valid is to

construct a truth table and show that whenever all of the hypotheses are

true, then the conclusion is true too.

例

1.4.1 Determine whether the following argument are valid or not:

,(1) pq

, pr

, qr

？

r

,(2) pq

, qr

r

？

p

解

例

1.4.1

The second is to use the rules of inference to prove the validity of

the conclusion. The various steps in a mathematical proof of a theorem

must follow from the use of various rules of inference, and a

mathematical proof of a theorem must begin with the hypotheses, proceed

through various steps, each justified by some rule of inference,

第

17

页

共

47

页

2010-12-27

《离散数学》双语教学

第一章

真值表，逻辑和证明

and arrive at the conclusion.

In fact, in order to prov

e a theorem of the typical form H?H?…?H?C,

we begin with the hypotheses H,H,…,H and show 12n12n

that some result C logically follows. Then, using H,H,…,H,C, we

112n1

show that some other result C logically follows. We continue this 2

process, producing int

ermediate statements C,C,…,C, called steps in

12k

the proof, until we can finally show that the conclusion C logically

follows H,H,…,H, C,C,…,C. Each logical step must be justified by

12n12k

some valid proof technique, based on the rules of inference or

some other rules that come from tautological implications,

永真蕴涵

式

,.

In all, a valid argument is formally a sequence of statements each

of which is

(1) A hypothesis

(2) An axiom or postulate

(3) A previously proven theorem or proposition

(4) A statement implied by previous statements as a conclusion of

a valid argument

(5) Logically equivalent to a previous statement

前面讲过的逻辑等价式和永真蕴含式都可以适当地变成可用的推 理规则

.

常

用的有

:

(1) Addition rule(

附加规则

)

p

？

,pq

(2) Specialization rule(

化简规则

)

p,q

？

p

(3) Modus ponens (law of detachment,

假言推理

,

肯定律

)

p

p,q

第

18

页

共

47

页

2010-12-27

《离散数学》双语教学

第一章

真值表，逻辑和证明

？

q

(4) Modus tollens (

拒取式

,

否定律< /p>

)

，

q

p,q

？，

p

(5) Disjunctive syllogism (

析取三段论

)

，

p

p,q

？，

q

(6) Syllogism(

假言三段论

)

p,q

q,r

,

？

pr

(7) Conjunction rule(

合取引入

)

p

q

？

,pq

例

1.4.2 Is the following argument valid?

If you invest in the stock market, then you will get rich.

If you get rich, then you will be happy.

？

If you invest in the stock market, then you will be happy.

例

1.4.3 Is the following argument valid?

Smoking is healthy.

If smoking is healthy, then cigarettes are prescribed by

physicians.

？

Cigarettes are prescribed by physicians.

例

1.4.4 Is the

following argument valid?

If taxes are lowered, then income rises.

Income rises.

第

19

页

共

47

页

2010-12-27

《离散数学》双语教学

第一章

真值表，逻辑和证明

？

Taxes are lowered.

There are several different proof techniques: direct method(

直接证明

法

), indirect method(

间接证明法

), proof by contradiction(

反证法

), and

mathematical induction(

数学归纳法

).

An important proof techniques is indirect method(

间接证明法

). It

,,,q)(

，

q

，

p), which means that an based on the tautology (p

implication is equivalent to its contrapositive.

2

例

1.4.5 Let n be an integer. Prove that if n is odd, then n is odd.

Another important proof technique is proof by contradiction(

反

,,,

证法

). It is based on the tautology ((pq)

，

q)

，

p. To prove that C

logically follows from H,H,…,H, we show that H?H?…?H?，

C 12n12nimplies

a contradiction.

例

1.4.6 Prove there is no rational number whose square is 2. In

other

words, show that 2 is irrational.

定义

1.4.2 Let A be a logical expression that includes only

，～

and ,.

Interchanging and , T and F(if there are some) in A, we will ,,,

*have the antithesis of A, and we denote it A.(

设< /p>

A

是仅含，～和这

,,

< br>三种命题联结词的公式～在

A

中将和互换、

T

和

F(

若有的话