链接版第一章真值表、逻辑和证明

1、CHAPTER 1TRUTH TABLES, LOGIC, AND PROOFSGlossarystatement, proposition ：命题 logical connective: 命题联结词 compound statement ：复合命题 propositional variable ：命题变元 negation ：否定(式 ) truth table: 真值表conjunction: 合取 disjunction ：析取propositional function: 命题公式 fallacy ： 谬误syllogism ：三段论 universal quantification

2、：全称量词化 existential quantification:存在量词化hypothesis(premise) ： 假设，前提，前件 conditional statement ， implication ：条件式 , 蕴涵式 consequent, conclusion ：结论，后件converse: 逆命题 contrapositive ：逆否命题 biconditional, equivalence:双条件式 , 等价logically equivalent ：（逻辑）等价的contingency ：可满足式tautology ：永真式 （重言式 ） contradiction,

3、absurdity ：永假（矛盾）式 logically follow:是的逻辑结论argument ：论证axioms :公理 postulate: 公设 rules of reference :推理规则 modus ponens: 肯定律 modus tollens :否定律 reductio ad absurdum:归谬律proof by contradiction:反证法counterexample :反例 minterm :极小项disjunctive normal form :主析取范式 maxterm: 极大项conjunctive normal form:主合取范式本章内容及教

4、学要点：1.1 Stateme nts and Conn ectives教学内容：statements ( propositions) , compound statement,connectivesnegation ， conjunction,disjunction,truth tables1.2 Co nditio nal Stateme nts教学 内容：implications( conditionalstatements ) ,biconditionalequivalent,and quantifications1。3 Equivale nt Stateme nts教学 内容：log

5、ical equivale nee ， conv erse,i nv erse ， con trapositive tautology,contradiction(absurdity)，contingency ，properties of logicalconn ectives1。4 Axiomatic Systems: Arguments and Proofs教学内容:rulesof refere nee， augume nt， validargume nthypotheses,premises，law of detachment(modus ponens)，syllogism ，modus

6、 tollens， addition ， proof by contradiction1.5 Normal Forms教学内容：minterm ， disjunctivenormal form ， maxterm ，conjunctiveno rmal form定理证明及例题解答Logic, developed by Aristotle, has been used through the centuries in the development of many areas of learning including theology ， philosophy , and mathematic

7、s 。 It is the foundation on which the whole structure of mathematicsis built. Basically it is the science ofreasoning ， which may allow us to determine statements about mathematicswhether are true or false based on a set of basicassumptions called axioms 。 Logic is also used in computer science to c

8、onstruct computer programs and to show that programs do what theyare designed to do. 文档为个人收集整理，来源于网络 逻辑学是研究人的思维形式的科学。 而数理逻辑 是逻辑学的一个重要分支， 是用数学形式化的方法研究思维规律的一门学科。 由于它使用了一套符号来简洁 地表达出各种推理的逻辑关系 , 故它又称符号逻辑。数理逻辑用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系.数理逻辑的主要内容：逻辑演算（Ls和Lp）、公理化集合论、模型论、 构造主义与证明论。 数理逻辑在电子线路、机器证明、自动化系

9、统、编译理论、 算法设计方法方面有广泛的应用 .The rules of logic specify the meaning of mathematical， and itmachines, to, to computerother areas ofstatements 。 Logic is the basis of all mathematical reasoning has practical applications to the design of computing system specifications ， to artificial intelligence(AI )prog

10、ramming ， to programming languages ， and to computer science ， as well as to many other fields of study.1。1 Statements and Connectivess（命题和联结词）命题逻辑研究的对象是命题及命题之间的逻辑关系.Propositi onsare the basicbuild ingblocks of logic. Manymathematical stateme nts are con structed by combi ning one or more propositi

11、ons。定义 1 。 1.1 A propositi on is a stateme nt or declarative sentence thatis either true or false ， but not both（命题是一个非真即假的陈述句）。因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题.（1）The true or false value assigned to a statement is called its truthvalue ；（一个命题的真或假称为命题的真值。真用T或1表示，假用F或0 表示）（2）一个陈述句有真值与是否知道它的真假是两回事。例1。1.1

12、判断下列语句是不是 命题？若是，给出命题的真值：（1）陕西师大不是一座工厂（2）你喜欢唱歌吗？（3）给我一块钱吧！（4）我不是陕西师大的学生。（5）我正在说谎。Logical connectives（命题联结词）数理逻辑的特点是并不关心具体某个命题的真假，而是将逻辑推理变成类似数学演算的形式化过程 , 关心的是命题之间的关联性 . 因此需要进行 命题符号化 . 命题联结词的作用是为了将简单命题组合成复合命题。We will now introduce the logical connectives that are used to form new propositions from exis

13、ting propositions 。 And once truth values have been assigned to simple propositions ， we can progress to more complicated compound statements 。A statement that contains no connectives is called a simple statement. We will use p,q , rto represent simple statements （简单命 题就是简单陈述句，用字母p , q,r（或带下标）表示）;So

14、metimes, the letters p ， q,r ， s, are used to denote propositional variables that can be replaced by statements（ 命题变元 :可以用 命题代替的变元 ）.A statement that contains logical connectives（ 命题联结词 ） is calledcompound statements （复合命题 ）. In general, a compound statement may have many component parts ， each of w

15、hich is itself a statement ， represented by some propositional variable. The truth of a compound proposition is determined by the truth or falsity of the component parts 。propositional constant （命题常元 ）：T（ 1 ）或 F（ 0） ，或者表示一个确 定的命题；propositional variable （命题变元 ）：可用一个特定的命题取代。指派（解释）：用一个具体命题或T、F代替一个命题变元.

16、常用的有五种命题联结词，先介绍三种：（1） negation connective否定联结词p （否定式）：非p （not p ）If p is a statement ， the negation of p is the statement not p, denoted by p。 p ：不，非，没有规定 p 是 T 当且仅当 p 是 F.（2 ） conjunction connective合取联结词p q（ 合取式） ： p 并且 q， p 合取 q:并且，且，既又，不仅而且If p and q are statements ， the conjunction of p and q （

17、p 和 q 的合 取） is the compound statement“ p an，dqden”oted by pq。 Theproposition p q is true when both p and q are true and is false otherwise.（规定 p q 是 T 当且仅当 p 和 q 都是 T.）（ 3 ） disjunction connective析取联结词p q（ 析取式 ） ： p 或者 q ， p 析取 q:或，或者说，不是就是，要么要么If p and q are statements， the disjunction of p and q（p

18、 和 q 的析取 ）is the compo und sta teme nt“ p or q" deno ted by p q。The propositi onp q is true when p or q are true and is false when both p and q are false.This is used in an inclusive sense 。（规定 p q 是 T 当且仅当 p， q 中至少一个是T或者p q是F当且仅当p，q都是F）。Now we will introduces truth table to decide how the trut

19、h of a compound proposition is determined by the truth or falsity of the component parts.A truth table lists all possible comb in ati ons（cases ） of the truthand falsity of the comp onent propositi on s.The truth table（真值表）of acompo undpropositi onis as follows : The left colu mns are thecomp onent

20、parts and their truth values, and the right colu mn are thetruth value of the compou nd proposition（左边部分是组成复合命题的各简单命题的真值指派；右边部分是复合命题的相应真值）.q, p q and p.例 1.1。2 The truth tables of ppqp qTTTTFFFTFFFFpqTTTFFTFFTppTTFTFTp qF例 1.1 。 3 The truth table of pr ）。p q rpT T TT TT T FT TTFTT TT F FT TF T TF FF

21、 T FF FF F TF TF F FF F1 *（q） r）FTFTFTFFTFTTTFFFFTFTFTFFTFTTTFFF2131ASSIGNMENTS ：PP69：12 ，14，28,30 ，34,40 ，58,601.2Con ditio nal Stateme nts（条件式）（4）conditional connective条件（蕴含）联结词 （）p q（条件式、蕴涵式）:如果p则qIn the implicati on p q, p is called the hypothsis（a ntecede nt or premise） and q is called the conc

22、lusion（consequenee）。 Theimplicati on p q is the propositi on that is false whe n p is true and q is false， and is true otherwise 。（规定 p q 是 F 当且仅当 p 是 T, q 是 F。 p 称为条件式的前件（前提），q称为条件式的后件（结论）:如果（若）就（则），只要就，若才能例 1 o 2。1 The truth table of pq.pqp qTTTTFFFTTFFTThe con diti onal is expressed in En glish i

23、n several ways: If p, the n q 。p is sufficie nt for q.p is a sufficie nt con diti on for q 。q is n ecessary for p 。q is a n ecessary con diti on for p.p only if q（ or only if q then p ）（5）biconditional connective双条件（等值）联结词 （）p q （双条件式）：p当且仅当qThe bic on diti onal pq is the propositi on that is true w

24、he n p and qhave the same truth values, and is false otherwise.（规定 p q 是 T 当且仅当p，q或者都是T,或者都是F.）例 1。2.2 The truth table of pq.pqp qTTTTFFFTFFFTThe bic on diti onal is also expressed in En glish in several ways:p if and on ly if q 。p is n ecessary and sufficie nt for q.p is a n ecessary and sufficie n

25、t con diti on for q。Tran slat ing senten ces into logical expressi ons removes ambiguity.Once we have translated sentences from English（Chinese， etc。） intological expressions we can analyzethem to determine their truthvalues, man ipulate them， and use rules of refere nee to reas on abutthem.（命题符号化的目

26、的在于用五个联结词将日常语言中的命题转化为数理逻 辑中的形式命题，其关键在于使用适当的联结词。对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解：（1）确定语句是否是一个命题；(2) 找出句中连词，用适当的命题联结词表示.)例1。2。3 试将下列命题符号化：(1) 若你不看电影，则我也不看电影。(2) 小王一边吃饭，一边看书.(3) 只有在生病时，我才不去学校。(4) 当且仅当我生病时，我才不去学校.解例例 1.2.4Change each of the followi ng to the form pq or q(1) He will succeed only if he wo

27、rks hard。(2) Having money is sufficie nt for being happy.(3) Sam will play golf if and only if it is warm.(4) Having money is n ecessary for being happy.(5) Sam will play golf if and only if it is warm.(6) Being lucky is a necessaryand sufficientconditionforsuccessful 。命题表达式(logical expression)一个命题越

28、复杂，符号化该命题所需的命题变元和联结词就越来越多安排这么多的东西使之有意义呢？一个命题表达式是由下列方式递归定义的：(1)命题常元或命题变元是一个命题表达式；(2) 若A是一个命题表达式，则(A)也是一个命题表达式；(3) 若A、B是命题表达式,则(A B)、(A B )、(A B )和(A B)p:being如何均为命题表达式;(4) 只有经过有限次地应用 (1) 、(2 )、(3)所得的结果才是命题表达式 . 注：1、对于一个命题表达式， 数理逻辑的目的在于利用这些形式化的表达式来研 究命题之间的逻辑关系 . 这种逻辑关系是用真假来表示的 ; 只有对其所有的 变元 指派 以确定的真值后，

29、它才有真值 ;2、命题表达式无限多；3 、Precedence of logical connectives(命题联结词的优先级) 在一个复杂的命题表达式中，常常有许多括号和联结词, 为了简便起见，规定下列运算顺序：，。从而外层括号可以省略；在不会引起混淆的情形中， 可以省略命题表达式中的一些括号 .若命题表达式Ai是命题表达式A的一部分，则称Ai是A的子命题表达式。例1。2。5 求命题表达式(p(q s)(p s)的子命题表达式。定义1.2.1 设命题表达式A(p i， P2，Pn)含有n个命题变元pi, p2, Pn， Pj1， Pj2，,/是其中的r个不同命题变元.用命题表达式Bi， B

30、2, Br 同时分别代替 pj1， pj2, , jpr 在 A 中每一次出现所得到的命题表达式 B 称为A 的一个 代入实例 。例1.2.6 设命题表达式A (p,q,s )为(卩 q s)(p s),B为p q，则用 B 代入 A 中的 p 所得的代入实例为命题表达式( (p q ) (q s )(p q) s).若C为q p，则用B和C分别取代A中的p和s所得的代入实例为命题表达式( (p q) (q (q p) ) ( (p q) (q p)。在命题逻辑中，还有一种所谓的 替换. 但代入是对命题变元 来进行的 . 而替 换则是对某一子命题表达式来进行的，它只要求对该 子命题表达式的某一

31、处出现 或某几处出现进行 替换 。例 1 o 2 o 7 设公式 A(p,q)为(p(q s)(p s) , B 为 p s，则用 B代入A中的子公式 (p A s)所得的公式为(p (q s)(ps).Assignments ：PP11-13 ：6， 8,40 ， 44,48（等价命题）If two compound statements p and q are true in exactly the samecases, the n they are said to belogically equivale nt（逻辑等价的或等价的），or we say that p is equival

32、e nt to q 。We will denote this by p q。We can establish their equivale nee by con struct ing truth tables for them and then comparing the two truth tables。 Or by using the tautologies, which we will in troduce in the followi ng text。例 1.3 o 1p q and （p q） are logically equivale nt, i。e. p q （P q）.Ass

33、ociated with the conditionalstatement p q are three otherstateme nts : its conv erse, inv erse, and con trapositive.q p is the conv erse（逆命题）of p q.q p is the con trapositive（逆否命题）of p q.p q is the inv erse（否命题）of p q.例 1。3。2 Let the implicati on be“If it is raining, the n I get wet.its conv erse ,

34、in verse and con trapositive。A stateme nt that is true in every case is called atautology 。 Astateme nt that is always false in every case is called acon tradicti onor an absurdity . And a statement that can be true or false, depending on the truth values of its comp onent parts, is called a conting

35、ency （设A是一个命题表达式，若 A在任何指派下都为T,则称为永真式（重言式）;若A在任何指派下都为F,则称A为永假式（矛盾式）;若至少存在一个指派使A为T,则称A为可满足式）。例1。3。3判断下列几个公式的类型：pp,p p,p q。例1。3。4用真值表决定公式（p q） p的类型。解例1.3。4注：1、永真式必为可满足式，反之则不然；永真式的否定是永假式，反之亦然；2、决定一个公式是否是一个永真式、永假式或可满足式 有两种方法：真值表法（适用于变元少而简单的公式）和公式推理（等价取代）法；3、共有22个不同的n元真值表；4、永真式的合取、析取、蕴含和等值式都是 永真式定理 1.3 。

36、1 p is equivale nt to q if and only if pq is a tautology.定理1。3。2 p q是永真式当且仅当条件式p q和q p都是永真式.定理 1。3。3 The connectivesfor propositions have the followingproperties （命题运算满足下列性质）：Idempote nt laws（等幕律）:ppp, pppDouble negation law（双否律）: （p） pDe Morgan ' s laws（ 德。摩根律）:q）（p q）p qCommutative laws（交换律）As

37、sociative laws（ 结合律）：p (q r )(p q) r， p (q r) (p q ) rDistributive laws( 分配律 ) ：p ( q r)( p q ) (p r) ， p (q r) (p q) (p r)Identity laws(同一律 ） ：p T p ，pFpDomination laws( 零一律 ): p T T, p F FAbsorption laws（吸收律） ：p (p q )p, p (p q) pNegation laws(有补律）：p p T,p p FLogical equivalences involving implica

38、tions:pq pq （条件式转化律）， pq qp （ 逆否律） ,（pq）(pr ) p(q r)(p r) (q r ) (p q) rLogical equivalences involving biconditionals:pq（pq ）（qp），pq（ p q）（pq） （ 双条件式转化律）where T canrepresentany tautologyand F can representanycontradiction.Any component of a compound statement can be replaced by any statement logical

39、ly equivalent to that statement without changing the truth value of the statement 。定理 1.3.4 （代入原理） 永真（假 ）式的代入实例 是永真（假）式. 定理1.3 。5 （替换原理） 设A为命题公式C的子命题公式，若 A B,且将C 中A的一处或若干处出现用 B代替得到D，贝U C D。替换和代入虽都是从一个命题公式变换得到另一个新的命题公式，但代入是 对命题变元进行的，且必须同时替换某变元的所有出现（处处代入 ）；而替换的对 象贝是子命题公式，且只需取代某子命题公式的一处或若干处出现 （部分替换 ）.

40、例 1 。 3.5 Establishes the equivalence ：（q r） （p r）（p q） rAssignments ：PP17-19 ：8， 10， 12， 14,28,30,40 ， 48， 52， 54,561。4 Axiomatic Systems : Arguments and ProofsMuch of mathematics deals with theorems and proofs of theorems.Theorems are“ true" stateme nts about the mathematical system beingcon

41、sidered.A theorem is a statement that can be shown to be true. We dem on strate that a theorem is true with a seque nee of stateme nts that form an argument （证明，推理）.Two important questions will arise in the study of mathematics are:（1）When is a mathematical argume ntvalid （correct） ?（2） Whatmethods

42、can be used to con struct a valid mathematical argume nt?An argument consists of a collection of statementscalledhypotheses and a statement called its conclusion 。 A valid argumentis an argument whose conclusion true whenever all thehypotheses are true 。To con struct proofs, methods are n eeded to d

43、erive new stateme ntsfrom old ones 。The stateme nts used in a proof can in cludeaxioms （公理） or postulates（公设）,the hypotheses of the theorem to be proved,and previously proved theorems. Therules of inference（推理规贝U）,which are mea ns used to draw con clusi ons from other asserti ons, tie together the s

44、teps of a proof.In a mathematical system , all of the informationnecessary toprove a theorem must be contained in axioms and previously prove n theorems.推理就是从一组已知的命题出发，按照一组推理规则推出新的命题的过程。已知命题称为推理的 前提,推出的命题称为推理的 结论.推理过程是一个有限公式序列，它以一个前提开始。它的最后一个公式是结论，其余的公式或者是一个公理、公设或给定的前提，或者是由若干个在它前面出现的公式的有效结论定义 1。4.1

45、Suppose that the implication Hi A H2 人人 Hn f C is atautology, we say that C logically follows from H1 , H2, ,Hn。Virtually all mathematical theorems are composed of implicati onsof the typeH1 A H2 A A Hnf CThe H i s are called the hypotheses (假设)or premises( 前提)，and C is called thecon clusi on。To pro

46、ve the theorem , we are trying to show that C will be true ifall the H i are true.The first method of showing that an argumentis valid is tocon struct a truth table and show that whe never all of the hypothesesare true , then the conclusion is true too 。例 1。4。1Determine whether the following argumen

47、t are valid or not:(1) p qp rq rr(2) p qq rr解例1.4 。 1The sec ondis to use the rules of inference to prove the validity ofthe con clusi on。The various steps in a mathematical proof of a theoremmust followfrom the use of variousrulesofinference ，and amathematicalproof of a theorem mustbeg inwiththe hy

48、potheses ，proceed through various steps, eachjustifiedby somerule ofinference ，and arrive at the con clusi on.In fact , in order to prove a theorem of the typical form H1 A H2 人人 HnC , we begin with the hypotheses HH2,Hn and show that some result C 1 logically follows 。 Then , using H 1, H2,Hn, C1,

49、we show that some other result C2 logically follows. We continuethis process , produci ng in termediate stateme nts C1 ,C2, ,Ck, calledsteps in the proof , un til we can fin ally show that the con clusi onClogically follows H 1 ,H 2, ，Hn, C1 , C2, ，Ck. Each logical step must be justified by some val

50、id proof tech nique, based on the rules ofinference or some other rules that come from tautological implications（永真蕴涵式）.文档为个人收集整理，来源于网络In all ， a valid argument is formally a sequenee of statements eachof which is（1）A hypothesis（2）An axiom or postulate（3）A previously prove n theorem or propositi on（

51、4）A stateme nt implied by previous stateme nts as a con clusi on of a valid argume nt（5 ） Logically equivale nt to a previous stateme nt前面讲过的逻辑等价式和永真蕴含式都可以适当地变成可用的推理规则 .常 用的有：（1 ） Additi on rule（附加规则）_P_p q（2）Specialization rule（化简规则）p qp（3）Modus ponens（ law of detachme nt,假言推理，肯定律）pp qq（4）Modus tol

52、lens （拒取式，否定律）qp qp（5）Disju nctive syllogism（析取三段论）pp qq(6) Syllogism(假言三段论)p qq rP r（7）Conjunction rule（合取引入）Pqp q例 1。4。2Is the following argument valid?If you inv est in the stock market, the n you will get rich.If you get rich, the n you will be happy.If you in vest in the stock market, the n you

53、 will be happy。例 1。4.3Is the following argument valid?Smok ing is healthy 。If smok ing is healthy , the n cigarettes are prescribed by physicia ns.Cigarettes are prescribed by physicia ns。例 1。4。4Is the following argument valid?If taxes are lowered, the n in come rises.In come rises 。Taxes are lowere

54、d 。There are several differe nt proof tech niq ues:direct method（ 直接证明法），in direct method（间接证明法）,proof by con tradictio n（反证法）， and mathematical induction（数学归纟内法）。An importa nt proof tech niq ues is in direct method（间接证明法）.Itbased on the tautology （pq）（q p） , which means that ancon trapositive.impli

55、cati on is equivale nt to its例 145 Let n be an integer. Prove that if n 2 is odd , then n is odd 。Ano ther importa nt proof tech nique isproof by con tradictio n(反证法).It is based on the tautology (pq) q)p。 To prove thatC logically follows from H 1 ,出，Hn, we show that H 1 A H2人人 HnA C implies a con tradicti on例 1。4。6 Prove there is no rational number whose square is 2。 Inother words , show that 2 is irrational。定义 1.4。2 Let A be a logical expression t