数学语言与证明方法

1、第一章 数学语言与证明方法1集合的概念和运算（4学时）【教学目的】了解、掌握集合的基本概念及例子【教学要求】掌握集合的基本概念及例子；掌握集合五种运算和集合相等证明；【教学重点】掌握集合五种运算和集合相等证明；【教学难点】如何正确的证明集合之间包含和相等关系【教学方法】讲练结合教学法、提问式与启发式相结合教学法。【教学手段】传统板书与多媒体课件辅助教学相结合。【课型】新授课教学过程集合是一切数学的基础，每一门数学的讨论都离不开集合，为此，我们必须掌握集合的基本定义及运算规律，掌握集合的证明方法，这对于学习离散数学将有极大的帮助。除此以外，在离散数学中，序列、整除、矩阵也将是十分重要的基础知识。

2、下面就从6个知识点来加以阐述。1.1 集合与元素集合是任意客体(对象)的聚集。客体称为这个集合的“成员”或“元素”，元素a要么属于集合A，要么不属于集合A,记为：a此时，要充分的认识“任意客体”和“聚集”的含义。1.2 集合与集合的关系 (1) B包含A中（或A包含B）,记为BA（2）集合A与集合B相等，记为A=B. 此时，两个集合各自包含的对象一一对应相等（或者说完全相等），该定义称为集合的外延性定理。，此时，也称集合B不是集合A的子集。（4）集合A与集合B不相等，记为AB。 (5) 集合B真包含在集合A中或集合A真包含集合B,记为B。 ，此时，也称集合B是集合A的真子集。 （6）集合B不被

3、A所真包含， 在集合中，常常涉及到集合之间的包含与集合之间相等的证明。证明时，常依据上述定义，采用离散数学中特有的按定义证明方法来加以证明。由于离散数学中的很多定义，都是由两部分构成，即“如，则”，我们把定义中的前半部分叫“已知”，后半部分叫“结论”，所以，所谓按定义证明方法就是首先叙述出你所要证明问题的定义，利用定义中的“已知”条件，加上题目中的其他的已知条件，推出定义中的“结论”。1.3 特殊的集合(1) 空集：不含任何元素的集合叫做空集，记为。空集是绝对唯一的，且是任何集合的子集。证明一个集合是空集，或证明集合的唯一性，常采用反证方法，即假设该集合不是空集，或不唯一，导致与已知条件的矛盾

4、或导致唯一。（2） 全集：在一个具体的问题中，所研究的集合都是某个固定集合的子集，则称这个固定集合为全集，记为E或U。全集仅是相对唯一的。（3） 幂集：任一集合A的一切子集作为元素所构成的称谓A的幂集，记为P（A）， 显然|A|P（A）|，由此可知，集合中不存在最大的集合。1.4 集合的运算与定律1. 集合的运算 集合的基本运算有并，交，差，补，对陈差，其定义如下： 2. 运算的定律 1.5 有穷集合的计数 解决有穷集合的计数问题有两种方法：文氏图法和包含排斥原理。 设S是有穷集，p1,p2,pm是m条性质，S中的任何元素x对于对于性质pi(i=1,2,m)具有或者不具有，两种情况必居其一。令

5、表示S中不具有性质pi的元素构成的集合，则包含排斥原理可描述为： 1.6 无限集合 1 可数无限集合 自然数集合N=0，1，2，是一个可数（可列）无限集合，凡是与自然数集合等势的集合就是可数无限集合。如整数集合、奇数集合、偶数集合、素数集合有理数集合等。2.不可数集合 开区间（0，1）称为不可数集合，凡与（0，1）等势的集合都是不可数集合，如闭区间0，1，实数集合、无理数集合、复数集合等。 3.有限集合和无限集合的重要差别 （1）两个有限集合等势当且仅当它们有相同个数的元素； （2）有限集合不和其任何真子集等势； （3）无限集合可以和其真子集等势； （4）如A，B是两个有限集合，且|A|=|B

6、|，则A=B。1.7 序列 1.序列 一个序列就是按某种顺序排列的一张表。 2.增序列 设S是一个序列，如对任意的n，有：SnSn+1 ,则序列S称为增序列；如对任意的n,有Sn+1Sn，则序列S称为减序列。 3.子序列 对于n=m,m+1,令Sn是一个序列，且令n1,n2,n3,是一个增序列，对于所有的值在m,m+1,.中的k值，满足nk0，则有m=qn+r,其中q,r是整数，且0。q称为商，r称为余数。 一个大于1的正整数p被称为素数，如果仅有p自身和数字1能整除p. 2. 最大公因子 如果a,b和k都是正整数，且k|a,k|b,则称k是a和b的公因子。如果d是最大的这种k,则d被称为最大

7、公因子，记为 d=GCD(a,b)如果a,b是任何正整数，且GCD(a,b)=1，则我们称互质的。 3最小公倍数 如果a,b和k都是正整数，且a|k,b|k,则称k是a和b的公倍数。如果c是最小的这种k,则c被称为最小公倍数，记为 C=LCM(a,b)1.10 总结通过本章的学习，应达到下面的基本要求：（1） 能正确地表示一个集合，会画文氏图；（2） 能判定元素是否属于给定的集合；（3） 能利用安定以证明法证明两个集合之间的包含、相等、和真包含的关系；（4） 能熟练地作集合之间的并、交、差、补和对称差运算，掌握集合运算的定律；（5） 能熟练地计算P（A）；（6） 能求解与有穷集合计数相关的实际

8、问题；（7） 会求序列与子序列，并能进行序列的运算；（8） 能熟练地将一个数分解成素数的积，并能求两个数的最大公因子和最小公倍数；（9） 能熟练地进行矩阵的各类运算。第2章 命题逻辑命题逻辑(4学时)【教学目的】介绍命题逻辑的基本概念。掌握利用命题逻辑表示自然语言，描述概念、判断和推理。建立初步的语言形式化方法。【教学要求】1识记命题表示方法、真值判断、命题公式的递归定义。2领会联结词真值确定、翻译、命题公式的等价性和蕴涵性证明、任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。 3简单应用命题逻辑推理规则【教学重点】掌握数理逻辑中命题的翻译及命题公式

9、的定义；利用真值表技术和公式转换方式求公式的主析取范式和主合取范式；利用规则、基本等价和蕴涵公式、三种不同的推理方法完成命题逻辑推理；【教学难点】如何正确地掌握对语言的翻译，如何利用推理方法正确的完成命题推理【教学方法】讲练结合教学法、提问式与启发式相结合教学法。【教学手段】传统板书与多媒体课件辅助教学相结合。【课型】新授课教学过程课题导入数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机学科、人工智能、语言学等学科均有十分密切的联系，并且益显示出它的重要作用和更加广泛的应用前景。要很好地使用计算机，就必须学习逻辑。数理逻辑分五大部分。在离散数学中仅介绍命

10、题逻辑和谓词逻辑。命题逻辑是谓词逻辑的基础，只有掌握了命题逻辑，才能学好谓词逻辑。对于命题逻辑，下面从六个知识点来加以阐述。1.1 命题符号化及联系结词1 命题有确切真值的陈述句称为命题。所谓确切真值是指在具体的环境，具体的时间，具体的对象，具体的位置等情况下能唯一确定真值的。命题分为两种：(1) 简单命题：不能分解为更为简单的句子的命题。(2) 复合命题：能够分解为更为简单的命题。2 命题联结词联结词记号复合命题读法记法真值结果否定乛P是不对的P的否定乛P乛P为真当且仅当P为假合取P并且QP与Q的合取PQPQ为真当且仅当P，Q同为真析取P或者QP与Q的析取PQPQ为真当且仅当P，Q至少一个为

11、真蕴涵若P，则QP蕴涵QPQPQ为假当且仅当P为真，Q为假等价P当且仅当QP等价于QP QP Q为真当县仅当P，Q同为真假关于联结词，有如下几点提醒大家注意：（1）此联结词是联结的句子与句子之间的联结，而非单纯的名记号、形容词、数词等的联结；（2）此联结词是两个句子真值之间的联结词，而非句子的具体含义的联结，两句子之间可以无任何的内在联系；（3）联结词与自然语言之间的对应并非一一对应，如合取联结词“”对应了自然语言中的“既又”、“不仅而且”、“虽然但是”、“并且”、“和”、“与”等。如蕴涵联结词“”，PQ对应了自然语言中的“加P则Q”，“只要P就Q”，“P仅当Q”，“只有Q才P”，“除非Q否则

12、乛P”等。如等价联结词“ ”对应了自然语言中的“等价”、“并且仅当”、“充分必 ”等。如析取联结词是对应相容的或(中兼的或)。2.2 命题公式及分类一般称具有确切真值的简单命题叫命题常量，用P，Q，R，等表示。而没有赋予具体内容的简单命题称为命题变量（变元），此时的P，Q，R没有具体的真值。1合式公式（1）单个的命题变量或常量（含1或0）是合式公式；（2）若P是合式公式，则（乛P）也是合式公式；（3）若P，Q是合式公式，则（PQ）、（PQ）、（PQ）、（P Q）也是合式公式。只有有限次使用上述三步形式的符号串才是合式公式（命题公式），简称公式。为了简化公式，可按如下优先级别进行：“（）”“乛”

13、“”“ ”其中，为避免错误，合取与析取看成是同等优先级别，要改变或强调其优先级别，采用括号。另外，最外层的括号可以省掉，同级的按从左到右的顺序进行运算。2赋值或解释与真值表设G是命题公式，P1，P2，Pn (n/1)是出现在公式G中的所有命题变元，指定P1，P2，Pn一组真值，则这组真值称为G的一个解释或赋值。此时不同的赋值就有2n种。将此2n种不同的赋值下的取值情况列成的表称为G的真值表。3公式的分类设G为一公式，（1）如G在它所有的解释之下都为真，则称G为永真或重言式；（2）如G在它所有的解释之下都为假，则称G为永假或矛盾式；（3）如G在它所有的解释之下至少有一个为真，则称G为可满足式。2

14、.3 等价公式与演算1等价关系称公式G，H是等价的，如果在其任意的解释下，其真值相同，记为G=H。说明：G=H仅描述了两公式G，H之间的一种等价的关系，G=H本身并非是一个公式，它不能作直接计算。要判断G=H，可采用：G=H当且仅当公式G H 是一个永真式。2代入定理设G(P1，P2，Pn)是一个公式，G1(P1，P2，Pn)，Gn(P1，P2，Pn)为任意公式，若G是永真式或永假式，则用G1，G2，Gn取代公式G中的P1，P2，Pn后而得的新公式G(G1，Gn)G(P1，P2，Pn)仍是一个永真式或永假式。3运算定律设G，H，S是任意的公式，则有如下基本的运算定律：（1）幂等律：GGG，GG

15、G（2）结合律：(GH)SG(HS),（GH）SG（HS）（3）交换律：GHHG，GHHG（4）分配律：G（HS）（GH）（GS）， G（HS）（GH）（GS）（5）吸收律：G（GH）G，G（GH）G（6）同一律：G0=G，G1=G(0，1分别是关于运行，的幺元)（7）零 律：G1=1，G0=0(0，1分别是关于运算，的零元)（8）排中律，矛盾律：G乛G=1，G0=0(乛G又叫做G的补元)（9）D，M律：乛(GH)=乛G乛H，乛(GH)=乛G乛H（10）双重否定律：乛（乛G）G（11）蕴涵等值式：GH乛GH（12）等价等值式：G H（GH）（HG）（乛GH）（乛HG）（13）假言易位：GH乛H

16、乛G（14）等价否定等值式：G H乛G 乛H（15）归谬论：(G H)(G 乛H)乛G其中：只要将运处“乛”，“”，“”分别对应集合中的运算“”，“”、“”，真值“1”，“0”分别对应集合中的全集E和空集，集合对应于命题的公式，则定律(1)(10)就完全同集合中的定律(1)(10).另外,(11)(15)是命题逻辑中特有的公式,重点要求记住(11),(12).4等值演算利用等值定律到已有的公式中而推演出新的公式的过程称为等值演算。5置换规则设G(G1)是含子公式G1的公式，G(G2)是用G2置换了G(G1)之后的公式，若G1G2，则G(G1)G(G2)2.4 全功能联结词集1其他联结词表 2.

17、2P QU0 0U10 1U21 0U31 1U4设P，Q为两个命题元，U为其对应的联结词，则U作用于P，Q后的真值表如表22所示。由组合的意义，U1，U2，U3，U4的不同真值结果有2416种，即从0000到1111，为此除已有的五个联结词以外，还需引入下面四个联结词如表23所示。表中，在逻辑电路中称为异或门，与非门，或非门。2全功能联合词集合设S是联结词集合，用S中的联结词可表示任何的命题公式；且从S中删除任一个联结词后而得的新联结词集合S1，至少存在一个命题公式不能用S1中联结词表示。则称S是一个全功能联结词集合。如乛，乛，乛，等都是全功能联结词集合。表 2.3联结词记号复合命题读法记法

18、真值结果异或G不可兼或HG异或HGHAH为真当县仅当G.H不同为真假蕴涵否定G与H的蕴涵否定G蕴涵否定HGHG H为真当且仅当G为真，H为假与非G与H的与非G与非HGHGH为假当且仅当G, H同为真或非G与H的或非G或非HGHGH为真当且仅当G，H同为假2.5 范式1. 析取范式和合取范式(1) 称命题变元或其否定为文字；(2) 有限个文字的合取称为短语；(3) 有限个文字的析取称为子句；(4) 有限个短词的析取称为析取范式；(5) 有限个子句的合取称为合取范式。求一个公式G所对应的析取、合取范式一般通过公式的等值演算而得到。2. 主析取范式和主合取范式(1) 在含有n个命题变元P1, P2,

19、 , Pn的公式中，一个短语或一个子句如果恰当包括所有这n个命题变元或其否定，且排列顺序与P1, P2, , Pn一致，则称此短语或子句为关于P1, P2, , Pn的一个有小项或极大项。此时极小项有2n个，极大项也有2n个；(2) 由有限个极小项组成的析取范式称为主析取范式；(3) 由有限个极大项组成的合取范式称为主合取范式。求一个公式G所对应的主析取、主合取范式可采用真值表技术、公式的等值演算、公式的主析取与主合取范式之间的转换。其中，最方便、最直观、最不易出错的方法是真值表技术。该方法为：设G（P1, P2, , Pn）是一个公式，建立该公式所对应的真值表。(4) 在真值表中，公式G取值

20、为真的所有行所对应解释之极小项的析取为该公式G的主析取范式。(5) 在真值表中，公式G取值为假的所有行所对应解释之极大项的合取为该公式G的主合取范式。其中，极小项与解释之间的对应为：如P值为0，在极小项中则还原为乛P，如P值取1，在有小项中则还原为1，如P,Q,R之解释为010，则对应的有小项为乛P乛Q乛R；极大项与解释之间的对应为：如P取值0，在极大项中则还原为P，如P取值1，在极大项中则还原为0，如P,Q,R之解释为110，则对应的极大项为乛P乛QR。3、主要定理(1) 任一命题公式都存在与其等值的析取范式和合取范式；(2) 任一命题公式都存在与其等值的主析取范式和主合取范式；(3) 如果

21、一个命题公式是永真公式它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为空；(4) 如果一个命题公式是永假公式它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为空；(5) 两个命题公式是相等的它们所对应的主析取范式上等和主合取范式相等；(6) 任一公式对应主析取范式包括的极小项的个数加对应主合取范式包括的极大项的个数为2n。2.6 推理理论1. 推理的形式结构设G1, G2, , Gn，H是命题公式，称G1G2GnH为推理的形式结构，其中G1, G2, , Gn为前提，H为结论。当G1G2GnH为永真式时，则此时推理正确，并称G1, G2, , Gn逻辑蕴涵H是

22、G1, G2, , Gn的逻辑结果，并且记为G1G2GnH或记为G1, G2, , GnH。说明：G1, G2, , GnH仅描述了公式G1, G2, , Gn与公式H之间的逻辑蕴涵关系，G1, G2, , GnH本身并不是一个公式，它不能作直接的计算。要判断G1, G2, , GnH可采用：G1, G2, , GnH当且仅当G1G2GnH是一个永真公式。2. 判断推理是否正确的方法(1) 真值表法：利用真值表法，可建立如下推理定律：设G，H，S是任意的命题公式，则： 附加定律：GGH，HGH 化简定律：GHG，GHH 合并定律：G，HGH 假言推理：G，GHH 拒取式：GH，乛H乛G 析取三

23、段论：GH，乛GH 假言三段论：GH，HSGS 二难推论：GH，GS，HSS 等价三段论：GH；HSGS(2) 等值演算法；(3) 主析取（主合取）范式法；(4) 构造证明法。 推理规则：规则P（前提引入规则）：在推导的过程中，可以随时引入前提集合中的任一前提及附加前提。规则T（逻辑结果引用规则）：在推导的过程中，可以随时引用公式S，该公式S是由其前的一个或多个公式推导出的逻辑结果。规则P（附加前提规则）：如果能从给定理前提集合P与公式P推导出S，则能从此前提集中P推导出PS。 直接证明方法：此证明法是一个描述推理过程的命题公式序列C1, C2, , Cn，其中C1, C2, , Cn或者为已

24、知的前提和附加前提，或者是由某些前提或中间结论应用推理规则得到的中间结论或结论，Cn为最终的结论。 间接证明法（反证法或归谬法）：要证明G1, G2, ,GnH，等价地证明G1, G2, , Gn， 乛HR乛R，其中R可以是任意的公式，此时证明G1, G2, , Gn, 乛HR乛R即可采取直接证明方法。 带CP规则的直接证明方法：带CP规则的证明法主要是针对结论为PS（或乛PS）的公式十分方便，即要证明G1, G2, , GnPS，等价地证明G1, G2, , Gn，PS，此时证明G1, G2, , Gn, PS可采用直接证明方法（此时P为附加前提）。当推出结论S后，采用CP规则，即可由G1,

25、 Gn推出PS。上述三种方法对命题逻辑中的任何推理问题都是适用的，只是不同的逻辑推理问题采用不同的方法其方便程度不同而已。2.7 总结通过本章的学习，应达到下面的基本要求：(1) 要弄清命题与陈述句之间的关系与差别。命题都是陈述句；但陈述句不一定都是命题，只有陈述句所表达的判断结果查惟一确定的，它才是命题；(2) 掌握并能熟练应用6种基本的联结词（乛，）来对复合命题进行翻译及判断真值；(3) 记住24个基本的等价公式，并能熟练地应用到公式的转换中；(4) 会利用真值表技术和公式的演算方法求一公式所对应的主析取范式和主合取范式，并能利用范式判断两公式是否相等，是否为永真式、永假式、可满足式；(5

26、) 掌握并能熟练地应用推理的三种证明方法。命题逻辑例题例5.1 设P表示命题“天下雨”，Q表示命题“他骑自行车上班”，R表示命题“他乘公共汽车上班”，试以符号形式写出下列命题（西南交大1995年考研试题）：（1）只要不下雨，他才骑自行车上班；（2）只要不下雨，他就骑自行车上班；（3）除非下雨，否则他就骑自行车上班；（4）他或者骑自行上班，或者乘公共汽车上班。分析 对于命题只要Q才P，只要P就Q，除非Q，否则P等，都可以翻译成PQ，所以上述(1)，(2)，(3)分别可翻译为：(1) Q乛P，(2) 乛PQ，(3) 乛QP。句子(4)可翻译为QR。例5.2 (1) 使用连接词乛，构造三个命题变项P

27、,Q,R的公式L（P,Q,R），使得：乛L（P,Q,R）=L(乛P,Q,R)=L(P,乛Q,R)=L(P,Q,乛R)（2）求（1）中公式L（P,Q,R）的主合取范式，（北师大2001年考研试题）。解 (1) 设L（P,Q,R）=其中，Mi为关于P,Q,R的极大项。则乛L(P,Q,R)= L(乛P,Q,R)= a0M4a1M5a2M6a3M7a4M0a5M1a6M2a7M3L(P,乛Q,R)= a0M2a1M3a2M0a3M1a4M6a5M7a6M1a7M2L(P,Q,乛R)= a0M1a1M0a2M3a3M2a4M5a5M4a6M7a7M6由乛L(P,Q,R)=L(乛P,Q,R)=L(P,乛Q

28、,R)=L(P,Q,乛R)对应极大项Mi的系数应相等，为此有：(1-a0)= a4= a2= a1，(1-a4)= a0= a6= a5(1-a1)= a5= a3= a0，(1-a5)= a1= a7= a4(1-a2)= a6= a0= a3，(1-a6)= a2= a4= a7(1-a3)= a7= a1= a2，(1-a7)= a3= a5= a6所以 a0= a3= a5= a6 a1= a2= a4= a7如令 a0= a3= a5= a6=0，则a1= a2= a4= a7=1此时 L(P,Q,R)=M1M2M4M7= 乛(乛M1乛M2乛M4乛M7)= 乛(乛(PQ乛R)乛(P乛

29、QR)乛(乛PQR) 乛(乛P乛Q乛R)如令 a0= a3= a5= a6=1，则a1= a2= a4= a7=0此时 L(P,Q,R)=M0M3M5M6=乛(乛M0乛M3乛M5乛M6)= 乛(乛(PQR)乛(P乛Q乛R)乛(乛PQ乛R) 乛(乛P乛QR) (2) L(P,Q,R)=M1M2M4M7=(PQ乛R)乛(P乛QR)(乛PQR)(乛P乛Q乛R)主合取范式=M0M3M5M6=(PQR)(P乛Q乛R)(乛PQ乛R)(乛P乛QR)主合取范式例5.3 没有命题P：明天上午七点下雨 Q：明天上午七点下雪 R：我将去学校符号化下列语句：（1）除非明天上午七点不下雨且不下雪，否则我将不去学校；（2

30、）只要明天上午七点不下雨或不下雪，我就去学校；（3）只有明天上午七点不是雨夹雪，我才去学校；（4）明天上午七点我将雨雪无阻一定去学校。分析 根据命题PQ的定义，它可对应语句除非Q，否则乛P；只要P，就Q；只有Q才P。所以上述（1），（2），（3）可分别对应符号化为：（1）R（乛P乛Q）（2）乛P乛QR（3）R乛（PQ）句子（4）是雨雪无阻一定去学校，即无论任何天气都不影响去学校，即去学校与天气无关，因此，句子（4）可简单地符号化为：R但为了完整的表达出该句子的全部意思，应将雨雪无阻符号化。所谓雨雪无阻即是：（PQ）（乛PQ）（P乛Q）（乛P乛Q）所以句子（4）完整地符合号为：（PQ）（乛PQ）

31、（P乛Q）（乛P乛Q）R或 （PQR）（乛PQR）（P乛QR）（乛P乛QR）说明 由于雨雪无阻与R是同时发生，没有因果关系，所以天气与去学校之间用合取。例5.4 求公式G1(P，Q，R)5(PQ)(PQ)G2(P，Q)5(PQ)(PQ)的主析取范式和主合取范式。分析 公式G1，G2的右端虽然是相同的，但公式的左岸表明两个公式所含的命题变元不同，在求主析取，主合取范式时，由于其极小项，极大项依赖于命题变元，所以不能仅根据右端的公式来求，还应该根据该公司所含的命题变元的情况来求。因此，上述两个公式的主析取范式，主合取范式安全不同。下面采用两种方式来求。方法1 采用真值表技术。建立公式G1(P，Q，

32、R)5(PQ)(PQ)的真值表如表24所示。表24P，Q，R(PQ)(PQ)0 0 01 0 00 0 11 0 00 1 01 0 00 1 11 0 01 0 00 0 01 0 10 0 01 1 01 1 11 1 11 1 1则公式G1(P，Q，R)所对应的主析取范式、主合取范分别为：G1（P，Q，R）5（PQ乛R）（PQR）主析取范式G1（P，Q，R）5（PQR）（PQ乛R）(P乛QR)(P乛Q乛R) （乛PQR）（乛PQ乛R）主合取范式建立公式G2(P，Q)5（PQ）（PQ）的真值表如表25所示。表25P Q（PQ）（PQ）0 01 0 00 11 0 01 00 0 01 11

33、 1 1则公式G2(P，Q)所对应的主析取范式、主合取范式分别为：G2（P，Q）=（PQ）主析取范式G2（P，Q）=（PQ）（乛PQ）（P乛Q）主合取范式方法2 采用公式转换法。G1（P，Q，R）5（PQ）(PQ)5（乛PQ）PQ5PQ5PQ(乛RR)5（PQ乛R）（PQR）主析取范式G1（P，Q，R）5乛（乛G1(P，Q，R)）5乛（(P乛QR)(乛PQR)(P乛Q乛R)（乛PQ乛R）（乛P乛QR）（乛P乛Q乛R）5(乛PQ乛R)（P乛Q乛R）（乛PQR）(乛PQR)（PQ乛R）（PQR）5(PQR)（PQ乛R）（P乛QR）（P乛Q乛R）(乛PQR)（乛PQ乛R）主合取范式G2（P，Q）5（

34、PQ）（PQ）5（乛PQ）PQ5（PQ）主析取范式G2（P，Q）5乛（乛G2(P，Q)）5乛（(P乛Q)(乛PQ)(乛P乛Q)）5（乛PQ）（P乛Q）（PQ）5（PQ）（乛PQ）（P乛Q）主合取范式从上可以看出，两个公式的主析取，主合取范式安全不同。例5.5 判断下面公式的类型（重言式，矛质式，可满足式）（1）（PQ）（乛Q乛P）（2）（P Q）乛（PQ）（北师大2000年考研试题）解 判断一个公式是否是重方式、矛盾式，可满足公式，可采用三种方式：(1)真值表技术；(2)公式等值演算；(3)求主析取，主合取范式。下面分别采用三种方法：方法1 真值表技术。建立公式(1)，(2)的真值表如表26所

35、示。表26P Q（PQ）（乛Q乛P）（P Q）乛（PQ）0 01 1 11 1 10 11 1 10 1 01 00 1 00 1 01 11 1 11 0 0由上述真值可知，公式(1)是重言式，公式(2)是可满足式。方法2 公式等值演算。 （PQ）（乛Q乛P）5（P Q）乛（PQ）5乛（乛PQ）（乛PQ）51所以公式是永真式（重言式）。方法3 求公式的主析取、主合取范式。（P Q）乛（PQ）5乛（P Q）乛（PQ）5 乛（PQ）乛（QP）（乛P乛Q）5 乛（乛PQ）乛（乛QP）（乛P乛Q）5 （P乛Q）（乛PQ）（乛P乛Q）主析取范式5 乛（乛(P Q)乛(PQ)）5乛（PQ）5（乛P乛Q）

36、主合取范式显然公式所对应的主析取范式不包括所有的极小项，所以不是重言式，公式所对应的主合取范式不包括所有的极大项，所以不是矛盾式，因此，仅是可满足式。例5.6 符号化下列命题，并证明其结论：一公安人员审查一件盗窃案，已知事实如下：（1）张平或王磊盗窃了机房的计算机一台；（2）若张平盗窃了计算机，则作案时间不可能发生在午夜之前；（3）若王磊的证词正确，则午夜时机房里的灯未灭；（4）若王磊的证词不正确，则作案时间发生在午夜之前；（5）午夜时机房灯光灭了。问：盗窃计算机的是张平？王磊？分析 首先将事实符号化：设P：张平盗窃了计算机； Q：王磊盗窃了计算机； R：作案时间发生在午夜前；S：王磊的证词正

37、确；T：午夜时灯光灭了。则前提可符号化为：PQ，P 乛R，S 乛T，乛S R，T证明的结论为P或Q。证明 （1）TP（2）S 乛TP（3）乛ST，(1)，(2)，I（4）乛S RP（5）RT，(3)，(4)，I（6）P 乛RP（7）乛PT，(5)，(6)，I（8）PQP（9）QT，(7)，(8)，I此结论说明是王磊盗窃了机房的计算机。例5.7 符号化下列命题，并用演译法加以证明：如果6是偶数，则2不能整除7；或者5不是素数，或2整除7；5是素数。因此，6是奇数。解 首先将上述事实符号化设P：6是偶数 Q：2能整除7 R：5是素数则命题可符号化为P乛Q，乛RQ，R乛P证明 （1）乛RQP（2）R

38、P（3）QT，(1)，(2)，I（4）P乛QP（5）乛PT，(3)，(4)，I说明 本例的证明十分简单，但该例却说明了一个十分重要的情况：该列的结论是一个错误的结论。我们不能误认为该推导是错误的，或认为该前提不能逻辑地蕴涵结论。实际上，在逻辑推理中，完全允许在错误的假设下逻辑推导出一个错误的结论。一问题正是在错误的前提下（如6是偶数，则2不能整除7），导致了错误的结论，它们之间仍有逻辑蕴涵关系。例5.8 符号化下列句子，并用反证法（归谬法）加以证明。（1）如果A因病缺了许多课，那么也中学考试不及格；（2）如果A中学考试不及格，则他没有知识；（3）如果A读了许多书，则他有知识。（4）所以，A没有

39、缺很多课或没有读很多书。解 首先将事实符号化：设P：A因病缺了许多刘；Q：他中学考试及格；R：他有知识；S：他读了许多书。则上述句子可符号化为：P乛Q，乛Q乛R，SR乛P乛S证明 采用归谬法就是将结论的否定作为附加前提加入到前提集合之中，导致与已知条件的矛盾。（1）乛（乛P乛S）P(附加前提)（2）PST，(1)，(2)，E（3）PT，(2)，I（4）ST，(2)，I（5）P乛QP（6）乛QT，(3)，(5)，I（7）SRP（8）RT，(4)，(7)，I（9）乛Q乛RP（10）QT，(8)，(9)，I（11）Q乛QT，(6)，(10)，I所以，由归谬法知：P乛Q，乛Q乛R，SR乛P乛S。例5.

40、9 设前提集合为P5PQ，PR，QS，G5SR，证明PG。解 对于该题分别有用三种证明方法加以证明。证法1 直接证明法。（1）PQP（2）乛PQT，(1)，E（3）QSP（4）乛PST，(2)，(3)，I（5）乛SPT，(4)，E（6）PRP（7）乛SRT，(5)，(6)，I（8）SRT，(7)，E证法2 带CP规则的直接证明法。因G5 SR5乛SR，为此，可将乛S作为附加前提加入前提集合中，如能证明P，乛SR，则由CP规则知：P乛SR即PSR。（1）乛SP(附加前提)（2）QSP（3）乛QT，(1)，(2)，I（4）PQP（5）PT，(3)，(4)，I（6）PRP（7）RT，(5)，(6)，

41、I（8）乛SRCP，(1)，(7)（9）SRT，(8)，E证法3 归谬法。（1）乛（SR）P(附加前提)（2）乛S乛RT，(1)，E（3）乛ST，(2)，I（4）乛RT，(2)，I（5）PRP（6）乛PT，(4)，(5)，I（7）QSP（8）乛QT，(3)，(7)，I（9）乛P乛QT，(6)，(8)，I（10）乛（PQ）T，(9)，E（11）PQP（12）（PQ）乛(PQ)T，(10)，(11)，I例5.10 证明P(QS)是P(QR)，R(QS)的逻辑结果。分析 对于这类问题(结论是蕴涵的形式)，采用带CP规则的直接证明法最方便。（1）PP(附加前提)（2）P（QR）P（3）QRT(1)，(

42、2)，I（4）R（QS）P（5）Q（QS）T，(3)，(4)，I（6）QP(附加前提)（7）QST，(5)，(6)，I（8）P（QS）CP，(1)，(7)例5.11 一个排队线路，输入为A，B，C，其输出分别为FA，FB，FC，在同一时间内只能有一个信号通过。如果同时有两个或两个以上信号通过时，则按A，B，C的顺序输出，例如：A，B，C同时输入时，只能A有输出，写出FA，FB，FC的逻辑表达式，并化成全功能集中的表达式。解 设P：A输入 Q：B输入 R：C输入由提所给的条件，易写出FA，FB，FC的真值表如表2.7所示。表2.7PQRFAFBFC000011110011001101010101

43、000011110011000001000000由真值表知：它们的主析取范式分别为：FA5（PQR）（PQ乛R）（P乛QR）（P乛Q乛R）5（PQ）（R乛R）（P乛Q）（R乛R）5（PQ）（P乛Q）5 P（Q乛Q）5 P 15 P 5乛乛（PP）5乛（PP）5（PP）（PP）FB（乛PQ乛R）（乛PQR）5（乛PQ）（乛RR）5 乛PQ5乛乛（乛PQ）5乛（P乛Q）5P乛Q5P（QQ）FC（乛P乛QR）5乛（PQ）R5（PQ）R5乛乛（PQ）乛乛R5乛（乛（PQ）乛R）5乛（PQ）乛R5（PQ）（PQ）（RR）例5.12 某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，

44、也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁。经实验鉴定后发现，其中一人两个判断正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。分析 设P：矿样是铁；Q：矿样是铜；R：矿样是锡。则上述情况可能有：F1：甲全对、乙对一半，丙全错；F2：甲全对、乙全错、丙对一半；F3：甲对一半、乙全对、丙全错；F4：甲对一半、乙全错、丙全对；F5：甲全错、乙全对、丙对一半；F6：甲全错、乙对一半、丙全对。由于F（一人全对）（一人对一半）（一人全错），所以，上述F1，F2，F6这六种情况应有一种发生，即：FF1F2F3F4F5F61根据命题的表示：F1，F2，F6中分别表示如下：F1（乛P乛

45、Q）（乛P乛R）（PR）（R乛P）（乛P乛QR乛P乛P乛R）（乛P乛QR乛PPR）000F2（乛P乛Q）（P乛R）（乛R乛P）（RP）0（乛RP）（RP）0F3（P乛Q）（乛PQ）（乛PR）（R乛P）（P乛Q乛PRR乛P）（乛PQ乛PRR乛P）=0（乛PQR）= 乛PQRF4（P乛Q）（乛PQ）（P乛R）（乛RP）=（P乛QP乛R乛RP）（乛PQ乛PRR乛P）=（P乛Q乛R）05（P乛Q乛R）F5（PQ）（乛PR）（RP）（乛R乛P）=（PQ乛PR）（RP）（乛R乛P）= 0（RP）（乛R乛P）= 0F6（PQ）（乛P乛R）（PR）（乛RP）=（PQ乛P乛R乛RP）（PQPR乛RP）=00 =

46、 0所F00（乛PQR）（P乛Q乛R）00（乛PQR）（P乛Q乛R）= 1但矿样即不可能既是铜又是锡，所以Q，R中必有假命题，即Q，R不能同为真，所以乛PQR = 0，因而必有P乛Q乛R = 1所以P为真，乛Q为真，乛R为真，即P为真，Q为假，R为假，即矿样为铁。例5.13 用P规则和T规则证明下列命题演算的推理关系。（1）乛PQ，乛QR，RSPS（2）A（BC），D（B乛C），AD是不相容的（人大2001年考研试题）证明（1）乛PQP PQT，E 乛QRP QRT，E PR T，I RSP PST，I故 乛RQ，乛QR，RSPS（2）QDP A（BC） P AT，I BCT，I D（B乛C）

47、P DT，I （B乛C）T，I BT，I CT，I乛CT，I11 C乛CT，I第3章 谓词逻辑一阶谓词逻辑（4学时）【教学目的】掌握数理逻辑中谓词的翻译及公式的解释；利用规则、基本等价和蕴涵公式、三种不同的推理方法完成谓词逻辑的推理。【教学要求】1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。3. 掌握谓词演算的等值式和重言蕴含式 (六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词，的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。4. 了解前束范式的概念，会求公式的前束范式。5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(