[理学]离散数学李盘林版第一到5章

离散数学的内容,数理逻辑 集合论 图论 代数结构,数理逻辑,数理逻辑又称符号逻辑、数学逻辑 ,是用数学方法研究符号化、形式化的逻辑演绎规律的数学分支。数理逻辑的主要分支包括：逻辑演算(包括命题演算和谓词演算)、模型论、证明论、递归论和公理化集合论。,数理逻辑简史,数理逻辑是古典逻辑的发展, 古典逻辑又称形式逻辑，从亚里士多德的三段论起已有2000多年的历史。古典逻辑分析语言所表达的逻辑维形式。但人们的语言中常有含糊不清不易判别的语句引起歧义，甚至争论。 17世纪德国哲学家、数学家G.W.莱布尼兹提出用数学符号式的“通用语言”来进行思维演算，使人们能够证明思维的正确性，从而避免争论，这是数理逻辑最早的萌芽。,数理逻辑简史,到19世纪初英国数学家G.布尔终于成功地构造了一种思维的代数，后来被称为布尔代数，初步实现了莱布尼兹的部分设想，又经过不少数学家的努力，布尔代数被发展为具有逻辑蕴涵式的命题演算，成为最简单的公理化的逻辑系统。布尔同时代的英国数学家A.德摩根，采用符号表示命题中的谓词，使数学中的“关系”，“函数”都可以在逻辑命题中出现，加强了逻辑的表现力。经过G.弗雷格等数学家的改进，最终建立了公理化的谓词演算，成为数理逻辑的基础。,2009年学历类考试MBA(MPA),14并非小张既高又胖。 如果上述断定是真的，那么，下述哪项断定必定是真的? A小张高但不胖 B小张胖但不高 C小张既不高也不胖 D如果小张高，那么他一定不胖 E如果小张不高，他一定胖,2009年公务员考试行测,2：某珠宝店失窃，甲、乙、丙、丁四人涉嫌被拘审。四人的口供如下： 甲：案犯是丙。 乙：丁是罪犯。 丙：如果我作案，那么丁是主犯。 丁：作案的不是我。 四个口供中只有一个是假的。 如果上述断定为真，那么以下哪项是真的？ A说假话的是甲，作案的是乙。 B说假话的是丁，作案的是丙和丁。 C说假话的是乙，作案的是丙。 D说假话的是丙，作案的是丙。 E说假话的是甲，作案的是甲。,第1章 命题逻辑,1基本概念,1.命题逻辑：研究人类思维和推理规律的一门学科。数理逻辑：用数学的方法（即建立一套符号系统）研究思维和推理规律的一个逻辑分支。包括命题逻辑与谓词逻辑命题：能判明真假的陈述句。 真命题的真值用1或者T表示，假命题的真值用0或者F表示.简单命题：只含有一个内容的命题。用单个字母表示。复合命题：含有多个内容的命题。它是用一些连接词将多个简单命题连接起来的复合句。需要引进符号表示这些连接词。,举例,（1）3+2=5 （2）郑州是河北的省会。（3）中国承办二零零八奥运会。（4）53=1（5）X+2=5（6) 2+3=5并且23=5（7）如果2+3=4，那么雪是黑的。（8）今天下雨吗？（9）多美丽的凤姐呀！ (10)不要迷恋哥，哥只是个传说！ (11)我在说谎。 （1）（4）是简单命题。 （6）（7）是复合命题。 （1）（3）（7）真值为1。 （2）（6）真值为0。 （5）（8）（9）(10) (11) 不是命题。,思考的问题,复合命题是用一些连接词将多个简单命题连接起来的复合句。那么 1 如何引进符号表示这些连接词？ 命题变元：用小写字母 p,q,r,p1 ,q1 等表示任意的是一个简单命题。命题变元是待定的简单命题，可以用具体的简单命题来代换，从而具有确定的真值。2 哪些连接词要符号化？,2. 逻辑连接词,否定连接词 p p 0 1 1 0“非” “不”“没有” “是不对的”,合取连接词 p q pq 0 0 0 0 1 0 1 0 0 1 1 1 “与” “并且” “不但， 而且”,析取连接词 p q pq 0 0 0 0 1 1 1 0 1 1 1 1“或者” “要么 要么”,条件连接词 p q pq 0 0 1 0 1 1 1 0 0 1 1 1 “若，则” “如果，那么”,双条件连接词 p q pq 0 0 1 0 1 0 1 0 0 “当且仅当” 1 1 1 “充要条件”,符号化命题,（1）郑州不是河北省的省会。解:令p表示“郑州是河北的省会”，则该命题可表示为 p （2）2+3=5并且235。解: 令p表示“2+3=5”，q表示“23=5” ，则该命题可表示为p q,（3）今天刮风或者下雨。解: p令表示“今天刮风”，q表示“今天下雨”，则该命题可表示为p q（4）如果2+3=5，那么2+4=6。解:令p表示“2+3=5”，q表示“2+4=6”，则该命题可表示为p q（5）3-20当且仅当32。解:令p表示“3-20”，q表示“32” ，则该命题可表示为p q,注意的问题,1符号化自然语言时，不能只凭字面意思翻译.比如：2119次火车6点或7点开.张三或李四都可以做这件事情。 张辉和王丽都是三好学生张辉和王丽是同学.2符号化自然语言时，不要被语义所迷惑，我们只关注形式。比如：如果樱桃是红的，那么雪是黑的。如果樱桃是白的，那么雪是黑的。如果樱桃是白的，那么雪是白的。,3. 命题公式,命题公式（递归定义） （1）一个字母（命题变元）是命题公式。（即原子公式）。 （2）若A，B是命题公式，则A，AB， AB，AB，AB也都是命题公式。 （3）每个命题公式都是有限次使用（1）,（2）产生的。 注：命题公式中的逻辑连接词的优先级依次为 ， ， ,4. 真值指派与真值表,真值指派：给每个命题变元都指定一个真值。 n个命题变元共有2n种真值指派。真值表：对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。成真指派：使命题公式为真的真值指派。,用归纳法不难证明，对于含有n个命题变元的公式，有2n个真值指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下： 命题变元按字典序排列。 对每个指派，以二进制数从小到大或从大到小顺序列出。 若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。,1. p q 的真值表： p q p q 0 0 0 0 1 0 1 0 1 1 1 0,举例,2. pq r的真值表： p q r pq r 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0,复杂公式的真值表见例1.1.9,5. 公式的类型,重言式（永真式）：在每种真值指派下的真值均为1的公式。矛盾式（永假式）：在每种真值指派下的真值均为0的公式。可满足公式：非矛盾式的公式。 (至少存在一个指派，公式 A 相应 确定真值为真，称 A 为可满足式) 真值表可用于判别公式的类型。,由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,重言式的性质,（1）若公式A，B是重言式，则公式 A， A B，A B ， A B ，A B均是重言式。 （以上性质均可用重言式定义证明）（2）若公式A， A B是重言式，则公式B也是重言式。（证明见定理1.1.1 ）（3）代入规则：若公式A是重言式，则用任意公式替代A中某个命题变元的所有出现得到的公式B也是重言式。（证明见定理1.1.2。 例1.1.10 ）,2 公式的等价关系,1. 等价的概念公式A与B公式等价：若A B为重言式. 记为A B 。 注意 与 的不同。 A B 当且仅当 A与B在每种真值指派下 的真值均相同。,p q pq pq （pq）（pq） 重言式 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1,例：AB AB 因为pq pq,注意和的区别,是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。,2. 基本等价式,交换律 AB B A AB BA 结合律 （A B）C A (BC） （AB）C A（B C）分配律 A（ BC ）（AB）（A C） （ BC ）A （BA）（CA） A（B C) （ AB）（AC） （ BC ）A （BA）（CA） 吸收律 A（AB ) A A（AB） A,双重否定律 AA幂等律 AAA AAA同一律 A1A A0A囿律 （0-1律） A00 A11矛盾-排中律 AA0 AA1德摩根律 （AB）AB （AB）AB等价式 ABAB 等价式 AB（AB）（BA） （ AB ）（ BA） （AB）（AB）,等价替换规则：若A 有子公式A，而A B，则A中的子公式A（一处或多处） 用B代换后得到公式B，则A B 。代入和替换有两点区别： 代入是对原子命题变元而言的，而替换可对命题公式实行。 代入必须是处处代入，替换则可部分替换，亦可全部替换。,(1)（pq)pq; (2) (p(pq)r; (3) p(pq)p)q).解: (1) （pq)pq (pq)pq (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q (1(qp)q (qp)q (qq)p 1p 1 故 (pq)pq是重言式。,用等值演算判断下列公式的类型,(蕴含等值式)(蕴含等值式)(德摩根律)(德摩根律)(分配律)(排中律)(同一律）(交换律，结合律）（排中律）（零律）,(2) (p(pq)r (ppq)r (pp q)r (0q)r 0r 0 故 (p(pq)r是矛盾式。,(蕴含等值式，结合律） (德摩根律）(矛盾律）(零律)(零律）,p(pq)p)q) p(pq)p)q) (蕴含等值式) p(pp)(qp)q) (分配律) p(0(qp)q) (矛盾律) p(qp)q) (同一律) p(qp)q) (德摩根律，双重否定律) p(qq)p) (交换律，结合律) p(1p) （排中律） p1 （零律） p （同一律） 可见，（3）中公式不是重言式，因为00，01 都是成假赋值；它也不是矛盾式，因为10，11 都是其成真赋值，故它是可满足式。,在某次研讨会的休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人。 乙说王教授不是上海人，是苏州人。 丙说王教授不是上海人，也不是杭州人。听完3人的判断，王教授笑着说，他们3人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？,解： 设命题 p, q, r分别表示 ： 王教授是苏州、上海、杭州人。则p, q, r中必有一个真命题，两个假命题。甲的判断为： A1= pq; 乙的判断为：A2= pq; 丙的判断为：A3= q r 。,甲的判断全对： B1= A1= pq 甲的判断对一半：B2=(pq)(pq) 甲的判断全错： B3=pq 乙的判断全对： C1= A2= pq 乙的判断对一半： C2=(pq)(pq) 乙的判断全错： C3=pq 丙的判断全对： D1= A3=qr 丙的判断对一半： D2=(qr)(qr) 丙的判断全错： D3=qr,由王教授所说 E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B3C1D2) (B3C2D1) 为真命题B1C2D3=(pq) (pq)(pq)(qr) (pqqr) (pqpr)0B1C3D2=(pq)(pq)(qr)(qr) (pqr) (pqqr) pqrB2C1D3=(pq)(pq) (pq)(qr) (pppqqr) (pqqr) 0,类似可得 B2C3D10, B3C2D10 B3C1D2pqr由同一律可知 E(pqr) (pqr)但因为王教授不能既是苏州人，又是杭州人，因而pqr0 。于是 Epqr 为真命题，因而必有p,r为假命题，q为真命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错。 思考一个有趣的逻辑题目：假设你是一名逻辑学家，现在你被关在一个监狱里，共有两道门，一道是生门，一道是死门，有两个看守，一个只说真话，一个只说假话，如果只给你一次机会提问，你能否脱险 ？,P:被问战士是诚实人； Q:被问战士的回答是“是”R:另一名战士的回答是“是”S:这扇门是死亡门。,逻辑学家手指一门问身旁的一名战士说:“这扇门是死亡门，他(指另一名战士)将回答是,对吗？”,当被问战士回答“对”,则逻辑学家开启所指的门从容离去,当被问的战士回答“否”,则逻辑学家开启另一扇门从容离去。,设计实例 一家航空公司为保证安全，用计算机复核飞行计划.每台计算机都能给出飞行计划正确或者有误的回答出于计算机有可能发生故障, 因此采均3台计算机同时复核. 由所给答案, 根据“少数服从多数”的原则作出判断 设C1，C2，C3分别表示3台计算机的答案，S表示判断结果，根据题意得下面真值表,在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映。 对偶式:设A是仅含有， 的公式，将A中的换为 ，的换为，0换为1， 1换为0后得到的公式称为A的对偶式，记为Ad。对偶原理：若A B则Ad Bd 。（证明见定理1.2.3）利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。,举例,化简下面公式并求其对偶式 pq q r (pq ) ( q r) (等价式） ( p q )( q r) （德摩根律） ( q p) ( q r) （交换律 ） q ( p r) （分配律）其对偶式为: q ( p r)思考：等价置换到何时为标准的对偶式？,3 范式,文字：命题变项及其否定统称作文字。短语：仅由有限个文字构成的合取式（也称作简单合取式）例如： p; p; qq; pqr; ppr子句：仅由有限个文字构成的析取式（也称作简单析取式）例如： p; p; qq; pq; pqr析取范式：有限个短语的析取式。例如：(pq)(qr)r合取范式：有限个子句的合取式。例如： (pqr)(pq)r,（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。,证明：1 首先由蕴含等值式和等价等值式可知：ABAB, AB(AB)(AB)。2 由双重否定律和德摩根律可知：AA, (AB)AB, (AB)AB。3 利用分配律，可得: A(BC)(AB)(AC)，A(BC)(AB)(AC)。 使用这些等值式，便可将任一公式化成与之等值的析取范式或合取范式。,求范式的步骤,求给定公式的范式的步骤：(1) 消去联结词和；(2) 否定号的消去(双重否定) 或内移(德摩根律)；(3)利用对的分配律求合取范式； 利用对的分配律求析取范式。,举例,求下面公式析取范式和合取范式。 pq q r (pq ) ( q r)( p q ) ( q r) （析取范式） ( pq ) (qr)(pp) （析取范式） pq q r (pq ) ( q r) ( q p) ( q r) q ( p r) （合取范式） q ( p r) ( p p) （合取范式）,解: (1)合取范式：(pq)r (pq) r (pq) r)(r(pq) (pq)r)(r(pq) (pq)r)(pqr) (pr)(qr)(pqr) (2) 析取范式(pq)r (pq)r)(pqr) (pqp)(pqq)(pqr)(rp)(rq)(rr) (pqr)(pr)(qr),(消去),(消去),(消去),(否定号内移, 结合律, 交换律),(对的分配律),(见上述第一至四步),求公式(pq)r的析取范式与合取范式。,注：1 在演算过程中，利用交换律，可使每个简单析取式或简单合取式中命题变项都按字典序出现。 2. 单个文字既是简单析取式又是简单合取式。 因此形如pqr的公式既是由一个简单合取式构成的析 取范式，又是由三个简单析取式构成的合取范式。3. 述求析取范式的过程中，会有不同的析取范式。这说明命题公式的析取范式是不唯一的。 同样，合取范式也是不唯一的。为了得到唯一的规范化形式的范式，需要定义主析取范式和主合取范式。为此，先引入如下极小项和极大项概念。,极小项:关于n个变元p1,p2,pn 的极小项是短语 q1 q2 q n ， 其中qi 为pi 或 pi。 关于n个变元p1， p2pn 的极小项共有2n个。 关于n个变元p1， p2pn 的2n个极小项互不等价。 每个极小项有且只有一组指派使其为真。 故可将其编码为这组指派组成的二进制数， 从 而对应于一个十进制数。例如关于p,q的极小项 p q , pq , p q, p q分别对应于00，01，10，11（或0，1，2，3或m0，m1， m2，m3 ）。,极大项：关于n个变元p1, p2,pn的极大项是子句 q1 q2 q n ， 其中qi 为pi 或 pi。 关于n个变元p1， p2pn 的极大项共有2n个。 关于n个变元p1， p2pn 的2n个极大项互不等价。 每个极大项有且只有一组指派使其为假。 故可将其编码为这组指派组成的二进制数， 从而对应于一个十进制数。例如关于p,q的极大项 p q , pq , p q, p q分别对应于11，10，01，00（或3，2，1，0或M3，M2，M1，M0）。,2.主范式,主析取范式 ：若干互异极小项的析取式。主合取范式： 若干互异极大项的合取式。定理（1）任何一个非矛盾式的公式均可等价于惟一一个主析取范式 （2）任何一个非重言式的公式均可等价于惟一一个主合取范式。,求公式主范式的方法步骤,方法一 等价变换法步一：求出公式的析取范式（或合取范式）。步二：去掉析取范式中的永假式短语（或合取范式中的永真式子句）。步三：将非极小项短语（或非极大项子句）通过同一律添加其缺少的变元。步四：用分配律变成极小项（极大项）。再合并同类项即得主析取范式（或主合取范式） 。,求pq 的主析取范式和主合取范式解: (1) 主合取范式 pq pq M2 (2) 主析取范式 pq (pq ) (p(qq )(pp)q) (pq)(pq)(pq)(pq) (pq)(pq)(pq) m0m1m3,举例,pq qr (pq ) (qr) (pq） (q r) （析取范式） （pq ）（ rr) ） （( p p ) (q r)） (pqr)(pqr)(pqr) 0，1，4 （主析取范式）pq qr q(p r) （合取范式） 2，3，5，6，7 （主合取范式）,主合取范式可由主析取范式直接得到。设公式A含有n个变项，A的主析取范式为,未在主析取范式中出现的极小项设为,事实上，因,则A的主合取范式为：,故,方法二 真值表法步一：列出公式的真值表。步二：由成真指派写出其对应的极小项（或极大项）。步三：将写出所有的极小项（或极大项）析取（或合取）即得主析取范式（或主合取范式）。,真值表法求公式pq r的主析取范式和主合取范式 p q r pq r 极小项 极大项 0 0 0 1 (pqr) 0 0 1 1 (pqr) 0 1 0 1 (pqr) 0 1 1 0 (pqr) 1 0 0 1 ( pqr) 1 0 1 0 (pqr) 1 1 0 1 ( pqr) 1 1 1 0 (pqr) 主析取范式为(pqr) (pqr) (pqr) ( pqr) ( pqr) 0，1，2，4，6 主合取范式为3，5，7,（以主析取范式为例) 1. 求公式的成真与成假赋值 对含有n个变项的命题公式A，若其主析取范式含s (0s2n)个极小项，则A有s个成真赋值，它们是极小项下标的二进制表示，其余2n s个赋值都是成假赋值。,范式的用途,2. 判断公式的类型设公式A中含n个变项，则(1) A为重言式当且仅当A的主析取范式含全部2n 个极小项；(2)A为矛盾式当且仅当A的主析取范式不含任取极小项。(此时，记A的主析取范式为0)。(3) A为可满足式当且仅当A的主析取范式中至少含一个极小项。,(1) (pq)q; (2) p(pq); (3) (pq)r解：(1) (pq)q (pq)q pqq 0. (2) p(pq) ppq (p(qq)(p(qq)(pp)q) (pq)(pq)(pq)(pq)(pq)(pq) (pq)(pq)(pq)(pq) m0m1m2m3,利用公式的主析取范式判断公式的类型：,注：另一种推演：p(pq) ppq 1q 1 m0m1m2m3,该主析取范式含全部22 个极小项，故p(pq)是重言式。,故 (pq)q 是矛盾式。,(3)（pq)r (pq)r (pq)r (pq(rr)(pp)(qq)r) (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0 m1 m3 m5m7 故该公式是可满足式, 但不是重言式。,3. 判断两公式是否等值 设公式A, B共有n个变项。按n个变项求出A, B的主析取范式。若A与B有相同的主析取范式，则AB; 否则 AB不成立。例 判断下面两组公式是否等值。 (1) p与(pq)(pq); (2) (pq)r 与 (pq)r解: (1) pp(qq)(pq)(pq)m2m3 而 (pq)(pq) m2m3， 故 p(pq)(pq） (2) 因(pq)rm1m3m4m5m7 而(pq)rm0m1m2m3m4m5m7 故 (pq)r(pq)r不成立,某单位欲从三人A,B,C中挑选12人出国进修。由于工作需要选派时要满足以下条件(1)若A去，则C同去；(2)若B去，则C不能去；(3)若C不去，则A或B可以去。问应如何选派？解：设p: 派A去；q：派B去；r: 派C去。由条件得： (pr)(q r)(r(pq)经演算得其主析取范式为：m1m2m5 m1= pqr; m2 = pqr ; m5 = pqr由此可知, 有3种选派方案： (1) C去，A, B都不去；(2) B去，A, C都不去； (3) A,C同去，B不去。,4.利用主析取范式和主合取式解决应用问题,4 公式的蕴涵关系,1. 蕴含公式A蕴含B公式：若A B为重言式. 记为A B 注意 与 的不同。 A B 当且仅当 在每种真值指派下 若A的真值为1则 B 的真值也为1。 当且仅当 在每种真值指派下 若B的真值为0则A的真值也为0。,如 pq p,p q （p q） p 0 0 1 0 1 1 1 0 1 1 1 1,2 证明蕴含关系A B的方法,（1）用定义 :验证AB是重言式。（2）逻辑内容解释法:即证 若A的真值为1 ，则B 的真值也为1。 或 若B的真值为0， 则A的真值也为0。 例1.4.2（3）等价变换法:性质1.4.3 1.4.6 即 A A1 A2 An B 例1.4.3（4）范式法:先求A，B的主析取范式或主合取范式， A B 当且仅当A的主析取范式中的极小项都是B的主析取范式中的极小项 或 B的主合取范式中的极大项都是A的主合取范式中的极大项。,3 基本蕴含式,（AB) A 化简律 A（AB） 附加律（AB）A B 假言推理（AB）B A 拒取式（AB）B A 析取三段论（AB）（BC )（AC） 假言三段论（AB）（CD）（AC）（BD） 构造性二难推理（AB）（CD）（BD) （A C） 破坏性二难推理,半费之讼,普罗泰哥拉曾招收一位名叫欧提勒视的的学生跟他学诉讼。两人订有契约：欧提勒士毕业时付给普罗泰哥拉一半学费，另一半学费等欧提勒士第一次出庭打赢官司时付清。但是，欧提勒士毕业后并不出庭打官司，普罗泰哥拉等的不耐烦，诉诸法庭，向欧提勒士提出：假若我打赢这官司，根据判决你要付另一半学费假若我输了这官司，根据契约你也要付另一半学费或者我赢了这官司，或者我输了这官司所以，你都要付另一半学费 欧提勒士对普罗泰哥拉提出以下的反诉：假若我打赢这官司，根据判决我不该付另一半学费假若我输了这官司，根据契约我也不该付另一半学费或者我赢了这官司，或者我输了这官司所以，我都不该付另一半学费,4 论证,论证（推理）：由若干前提命题得到一个结论命题 论证形式：公式序列A1，A2， ，An；B n个前提 结论无效论证：若前提皆为真命题而结论为假命题。有效论证：若前提皆为真命题而结论也为真命 题；或者前提不全为真命题。例1.4.5,在逻辑学中，最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据:有效的推理不一定产生真实的结论;产生真实结论的推理过程未必一定是有效的;有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提;但是，如果前提全是真，则有效结论也应该真而绝非假。,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。,定理 论证形式 A1，A2， ，An；B 是有效的当且仅当 A1A2 An B 详细证明见17页 判断一个自然语言表达的论证是否有效，首先将此论证符号化成论证形式 A1，A2， ，An；B，然后验证蕴含式A1A2 An B是否成立即可。,举例,判断下面论证是否有效，并说明理由 1）例题1.4.6 2）如果函数f不连续，则f不可导。而函数f是可导的。所以函数f是连续的。 令 p表示“函数f是连续”， q表示“函数f是可导” ， 则该论证可符号化成下面论证形式 p q ， q ； p 而（ p q ） q p 故该论证是有效的。,6 半形式化推导方法,自然推理系统P由以下三部分要素组成: 1. 字母表: (1) 命题变项符号: p, q, r, (2) 联结词符号: , , (3)逗号与括号: ，, ( ) 2. 合式公式集 3. 推理规则:(1) P规则(前提引入规则) : 在证明的任何步骤上都可引入前提;(2) T规则(结论引入规则) : 在证明的任何步骤上所得到的结论都可做为后续证明的前提.(3) 置换规则: 在证明的任何步骤上, 命题公式中的子公式都可以用与之等值的公式置换.例题1.6.1 1.6.2,推理规则,(4)假言推理规则AB _A_ B,（6）化简规则 AB_ A,（7）拒绝式规则AB _B_ A,(5)附加规则 _A_ AB,(8)假言三段论规则AB _BC_ AC,(9)析取三段论规则AB _B _ A,（10）构造性二难推理规则ABCD _AC_ BD,(12)合取引入规则A _B_ AB,（11）破坏性二难推理规则AB CD _BD_ AC,构造证明的两个技巧1CP规则(附加前提证明法): 要证明H1H2HnPQ 只须证明H1H2HnPQ即可 H1H2Hn(PQ) (H1H2Hn)(PQ)H1H2HnPQ (H1H2HnP)QH1H2HnPQ所以 H1H2Hn(PQ)永真等价于H1H2HnPQ永真 即 H1H2HnPQ等价于H1H2HnPQ,举例,(1) 证明由p(qs),rp,q能有效推出rs证明: (1) rp P (2) r 附加前提 (3) p T ,(1), (2) (4) p(qs) P (5) qs T ,(3), (4) (6) q P (7) s T ,(5) (6) (8) rs CP,2反证法：,要证H1H2HnC，只需证明H1H2Hn CR RH1H2HnC即H1H2HnC永真 (H1H2Hn)C永真 (H1H2Hn) C永假 (H1H2Hn) C （R R）永真,（2） 证明 RQ，RS，SQ，PQP证明：用反证法（1） P P（附加前提）（2） P T，（1）（3） PQ P（4） Q T，（2），（3）（5） RQ P（6） R T，（4），（5）（7） SQ P （8） S T，（4），（7） (9) RS T，（6），（8） (10) （RS） T，（9） (11) RSP (12) （RS）（RS） T，（10），（11） (13) FT,（12）,第一章小结,1.命题的符号化：简单命题，复合命题，逻辑连接词2.公式的真值表：真值指派，公式的真值3.公式的类型：重言式，矛盾式及可满足公式4.公式间的等价：定义，基本等价式，等价代换5.公式的范式：合取范式，析取范式，主合取范式，主析取范式