离散—屈婉玲、耿素云

1、离散数学数学与信息科学学院n第一部分 数理逻辑n第二部分 集合论n第三部分 图论n第四部分 抽象代数离散数学第一部分 数理逻辑数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科。推理是由一个或几个判断推出一个新判断的思维形式。数学方法是指建立一套表意符号体系，对具体事物进行抽象的形式研究的方法。n第一章 命题逻辑基本概念n第二章 命题逻辑等值演算n第三章 命题逻辑的推理理论n第四章 一阶逻辑基本概念n第五章 一阶逻辑等值演算与推理第一部分 数理逻辑n1.1 命题和命题联结词n1.2 命题公式及其赋值n2.1 等值式n2.2 析取范式与合取范式n2.3 联结词的完备集n3.1 推理的形

2、式结构n3.2 自然推理系统P命题逻辑1. 命题：能判断真假的陈述句。包含两层意思：（1）必须是陈述句。 （2）能够确定（分辨）其真值。不等式等式自然语言中的陈述句万根。如：张校长的头发有一。是否知道真假是不同的注意：能否分辨真假与 1.1 命题和命题联结词）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。）三角形的内角和等于87658014）火星上有生命。）面积大。）海洋的面积比陆地的例：3962211.1 命题和命题联结词2. 命题的真值：判断结果表示。或一般用命题,:iiqprqp注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。假命题假真命题真真值：真用T

3、或1表示，假用F或0表示。3.命题和真值的符号化1.1 命题和命题联结词1.1 命题和命题联结词火星上有生命。积大。海洋的面积比陆地的面例：:962:rqp）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。三角形的内角和等于8765801:s）火星上有生命。）面积大。）海洋的面积比陆地的例：396221）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。）三角形的内角和等于87658014原子命题：不能被分解为更简单的陈述句复合命题：原子命题通过联结词联结而成例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。

4、P；2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。P不对；q且r；r或t；如果r，则s；r当且仅当s。1.1 命题和命题联结词4、命题联结词”。读作“非的否命题，记作称作复合命题，没有”等否定词组成的和“非”、“不”、“用命题否定词PPPP,).1不是质数。：是质数。如：的逻辑抽象。、“不”和“没有”等是自然语言中的“非”44:ppp pTFFT1.1 命题和命题联结词”。合取”或“与读作“组成的复合命题，记作和、是命题，由、合取词qqQPpppp,qq).2一面”等的逻辑抽象。、“一面但是”而且”、“虽然”、“不但又“既”、是自然语言中的“并且pqp qFFFFTFTF

5、FTTT：王化的品德很好。：王化的成绩很好。qp王化不但成绩好而且品德好。pq：1.1 命题和命题联结词”。或读作“组成的复合命题记作和命题、析取词qqpqp,).3的逻辑抽象。、“或者”中的可兼或是自然语言中的“或”pqp qFFFFTTTFTTTT：灯泡坏了。：开关坏了。qp1.1 命题和命题联结词开关坏了或灯泡坏了。pq：例：1.张晓婧爱唱歌或爱听音乐。 2.张晓婧是内蒙人或是陕西人。 3.张晓婧只能挑选202或203房间。1.1 命题和命题联结词注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也可抽象为。但为了方便起见一般不这样抽象。称作后件（结论）。，”。称为前件（前提）

6、条件或“”则读作“如果组成的复合命题记作和、由命题蕴涵词qqpqppqp,q).4的逻辑抽象。”，则”，“若，则是自然语言中的“如果pqp qFFTFTTTFFTTT有位父亲对儿子说：“如果我去书店，就一定给你买电脑报“。问：在什么情况下，父亲算失信呢？1.1 命题和命题联结词注意：“只要p，就q，因为p，所以q”，“p仅当q”，只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为pq。p，q可以没有任何内在联系。例：1.如果336，那么雪是白的。2.除非我能工作完成了，我才去看电影。3.只要天下雨，我就回家。4.我回家仅当天下雨。pq的逻辑关系为q是p的必要条件或p是q的充分条件。

7、1.1 命题和命题联结词的逻辑抽象。条件”，“当且仅当”是自然语言中的“充要”。当且仅当读作“组成的复合命题记作和、由命题等价词qp,).5qpqppqp qFFTFTFTFFTTT1.1 命题和命题联结词p q的逻辑关系为p与q互为充要条件例：1.3是有理数当且仅当加拿大位于亚洲。2.两圆的面积相等，则他们的半径相等，反之亦然。6.q异或联结词指的是排斥或，当且仅当p、q的真值相异时，p为真。pqp qFFFFTTTFTTTF)()()2(qp1qpqpqppq等价于等价于）（有如下性质：由定义知1.1 命题和命题联结词例：今天第一节课上离散数学或数据结构。左往右的次序运算。）同级的联结词，

8、按从（省略不必要的括号。）按优先级书写，可以（。，）由强到弱依次是：（联结词的优先次序：32,1例：p：北京比天津人口多 q：224 r：乌鸦是黑色的pqpqrrqqp)2(1）（求以下命题的真值1.1 命题和命题联结词5、语句形式化）选择命题联结词。（命题）；）确定原子命题（简单（形式化的步骤：211.1 命题和命题联结词例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。P；2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。P不对；q且r；r或t；如果r，则s；r当且仅当s。跳墙。中的联结词，如：狗急）要善于识别自然语

9、言（，如：我和他是同学。）给定句子是否是命题（注意：21去郊游，否则就不去。如果明天天气好，我们表。选小陈或小周一人为代践经验。他虽有理论知识但无实。么你一定会成为近视眼如果你走路时看书，那自讨没趣。，那么你们俩都不会去如果你和他不都是傻子例. 5. 4. 3. 2. 11.1 命题和命题联结词命题常元：表示具体确定内容的命题。命题变元：表示不确定具体内容的命题。题公式。）得到的符号串都是命）、（）有限次的使用（也是命题公式；是命题公式，则、）若（公式；公式，称其为原子命题）单个命题变元是命题（命题公式的递归定义：定义213, qp,q21. 1qpqpqpqppp1.2 命题公式及其赋值rp

10、prqppqpqrrqqp)5()4()3()2(1 ）例（1.2 命题公式及其赋值同时约定：（1）最外层的括号可以省去。 （2）不影响运算次序的括号也可以省去。层公式，是，则公式或或或或层公式，且，分别是，）若公式（层公式；是，则层公式且是）若公式（层公式；其为为单个命题变元，则称）公式（命题公式的层次：定义),max(1nACBACBACBACBACBAjiCB31nABAnB20A1. 2jin 1.2 命题公式及其赋值pqpqrrqp)2(1 ）例（1.2 命题公式及其赋值rqp )(是有理数：是偶数，：是素数，：232rqp是无理数：是偶数，：是素数，：232rqp称为成假赋值。的成

11、真赋值，否则，则称其为的真值为若指定的一组值使的一组赋值或解释。对一组确定的取值，称为给的命题公式，为含有命题变元设定义A1Ap,p,. 32121AppppAnn的真值表。称为情况列成表，在其全部赋值下的真值将公式定义AA. 41.2 命题公式及其赋值1n1)1223FnFnnnn真值表的构造步骤：（ ）若公式 共有（个变元，则真值表第一行写出个变元，公式F写在第列。（ ）写出 个变元的所有可能取值（种）,按从低到高的顺序写出公式的各层次。（ ）在不同赋值下求出各层次的真值及 的真值。为可满足式。的值为真，则称）若至少有一组赋值使为永假式；为假，则称在所有赋值下的取值均）若为永真式；为真，则

12、称在所有赋值下的取值均若，公式定义AA3AA2AA) 1. 5A1.2 命题公式及其赋值pqpqrrqp)2(1 ）例（也是重言式。为重言式，则和若定理BABABA,. 11.2 命题公式及其赋值1.,ABABA BAB定义 设 和 是两个命题公式，若为重言式，则称公式是等值的公式，记作。1.p)();.qqpppp 例 证明（.qpq注意：和的区别是公式间的关系符号，如：p是命题联结词2.1 命题公式的等值式, ABAB ABBAABCABC ABCABCABCABACABCABAC交换律：结合律：分配律：)(),(),()pqpqpqrpqrpqr 例： （与基本等值式（基本等值式（A，B

13、，C为任意命题公式）为任意命题公式）2.1 命题公式的等值式0,110A,1, ,1.11,00(),AA AAAAAAAAAA AAA AAAAAAAA AAAAABA AABAABABABAB 同一律：互补律：，重补律：等幂律：零一律：A吸收律：德摩根律：2.1 命题公式的等值式, BABABBABABBAABABBAABABABABAB 蕴含等值式：A假言易位：等价等值式：A等价否定等值式：归谬论：(AB) (AB)A因A，B，C可以代入任意的命题公式，故以上等值式称为等值式模式。由已知的等值式推演出另外一些等值式的过程为等值演算。2.1 命题公式的等值式( )( )( ) ABA(B)

14、(A)AABBA 置换规则：设是含公式 的命题公式，是用公式 置换了中所有的 后得到的命题公式。若，则等值演算的应用： 1.验证等值式 2.判定公式的类型 3.解决工作生活中的判断问题 2.qpqqp 例 等值等价式p2.1 命题公式的等值式()()()pqprpqr(), (),()pqpqppqr ppqpq甲、已、丙3人根据口音对王教授是哪人进行了判断： 甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是苏州人结果3人中有一人全对，一人对一半，一人全错。问王教授是哪人？2.2 析取范式与合取范式定义：命题变元及其否定统称为文字。 仅由有限

15、个文字构成的析取式称为简单（质）析取式。 仅由有限个文字构成的合取式称为简单（质）合取式。,pp pq pq例：注意：单个文字既是简单析取式又是简单合取式。讨论：设A为含n个文字的简单析取式 若A中同时含pi和pi，则？若A为永真式，则？若A为永真式，则A中必同时含有pi和pi，反之亦然。同理有，若A为简单合取式，A为永假式的充要条件是A中同时含有pi和pi。定理1. 一个简单析取式是重言式当且仅当它同时含有某 个命题变元及其他的否定。 一个简单合取式是矛盾式当且仅当它同时含有某 个命题变元及其他的否定。2.2 析取范式与合取范式定义：由有限个简单合取式构成的析取式称为析取范式。 由有限个简单

16、析取式构成的合取式称为合取范式。 析取范式与合取范式称为范式。,()()pp pq pqpqpq 例：注意：单个文字、简单析取式、简单合取式都既是析取范 式又是合取范式。2.2 析取范式与合取范式定理2. 一个析取范式是矛盾式当且仅当它的每个简单合 取式为矛盾式。 一个合取范式是重言式当且仅当它的每个简单析 取式为重言式。定理3.任一命题公式都存在与之等值的析取范式和合取范式。范式的求法：消去公式中的蕴涵、等价和异或联结词 使用双重否定律和德摩根律，将公式中出现 的否定 词移到命题变元之前。 利用分配律、结合律将公式化为合（析）取 范式。,()rpqrp例：(pq)范式形式不唯一。2.2 析取

17、范式与合取范式定义：在含有n个命题变元的简单合（析）取式中，若每个 命题变元和 它的否定式不同时出现，而二者之一必 出现且仅出现一次，且第 i个命题变元或它的否定是 出现在从左算起的第i位上（字典序），称这样的简 单合（析）取范式为极小（大）项。,()pqpq pq pqpq 例：性质：n个变元可以形成2n个极小（大）项； 每个极小（大）项有且仅有一个成真（假）赋值； 每组赋值下仅有一个极小（大）项为真（假）； 所有极小（大）项的析（合）取为真（假）；2.2 析取范式与合取范式将极小项的成真赋值对应的二进制数转化为十进制数为i，将对应的极小项记为mi。将极大项的成假赋值对应的二进制数转化为十进

18、制数为i，将对应的极大项记为Mi。定义：设由n个命题变元构成的析（合）取范式中所有的简 单合（析）取式都是极小（大）项，则称该析取范 式为主析（合）取范式。2.2 析取范式与合取范式定理.任何命题公式都存在与之等值的主析取范式和主合取范 式，并且是唯一的。2.2 析取范式与合取范式公式法：求析取范式 用同一律补进未出现的命题变元 消去永假或重复出现的变元和极小项 将极小项按下标从小到大排列真值表法：列出公式及各极小项的真值表，将每组赋值下 公式及极小项真值都为真的极小项进行析取。主合取范式的求法：1.公式法2.真值表法2.2 析取范式与合取范式应用：1.求公式的成真、成假赋值 成真赋值为析取范

19、式中所含极小项的编码的二进制数 成假赋值为合取范式中所含极大项的编码的二进制数12i, m;iiiiMp pMMmin定理.设m 与是,p 形成的极小项、极大项，则，由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的极小项 2求出与1中求出的极小项下标相同的极大项 3做2中极大项之合取2.2 析取范式与合取范式3.判断两公式是否等值 若A，B共含有n个命题变元，按n个命题变元求出A与B的主析取范式A、B，若AB，则AB.2.判断公式的类型 设A含有n个命题变元A为重言式当且仅当A的主析取范式含全部2n个极小项； A为矛盾式当且仅当A的主析取范式不含任何极小项，此 时记为0；A为可满

20、足式当且仅当A的主析取范式中至少含一个极小项。例：要在A，B，C中挑选2名出国进修，选派时满足下列条件： 若A去，则C同去 若B去，则C不能去 若C不去，则A或B可以去问有几种选派方案，分别是什么？4.解决实际问题2.2 析取范式与合取范式2.3联结词的完备集.0,10,1n.nF定义称 ：为 元真值函数0,101nn中的元素为由 ， 组成的长为 的符号串n个命题变元可以形成22n个不同的真值函数对于每个真值函数，都可以找到许多与之等值的命题公式，而每个命题公式对应唯一的与之等值的真值函数。定义.设S是一个联结词集合，如果任何n（n1）元真值 函数都可以由仅含S中的联结词构成的公式表示，则 称

21、S是联结词完备集。. , , ThS 是联结词完备集.345S , , , , , ,SSS 12推论：以下联结词集都是完备集 , , ,S., p qpq定义设为两个命题，复合命题“ 与（或） 的否定式”称作p,q的与（或）非式，记作pq(pq). , Th 也是联结词完备集.2.3联结词的完备集222222, ,A AA BA AA BAAAAAABA AABA AAB1k1k1k1k1k1k定义.设,都是公式，若，的任意 一组赋值，或者为假，或者和 同为真，则称由前提，推出 的推理 是有效的或正确的，称，为前提集合为 有效结论.22,| A AABA AAB1k1k由，推 ，记作，推理的

22、形式结构3.1推理的形式结构1212,|,|A ABA ABkk若推理正确，则记作,A 否则，记作,A注意：推理正确实际是排除前提真结论假的情况推理是否正确与前提的排列顺序无关推理正确并不能保证B一定为真1212.,BBkkA AAAAA定理公式推 的推理正确当且仅当 （）为永真式。3.1推理的形式结构12121212,|),|)A ABAABA ABAABkkkk推理的形式结构,A 转为(A 将,A 转为(A1212,AABA ABkk用（A ）作为推理的形式结构，证明时要先写成前提：,A结论：12)AABk论证推理是否正确，就是判断(A是否为永真式真值表法方法有 等值演算法主范式法3.1推

23、理的形式结构例：若下午温度超过30度，则王晓燕必去游泳。若她去游 泳，她就不会去看电影。所以若王晓燕没去看电影， 下午温度必超过了30度。p：温度超过30度q：王晓燕去游泳r：王晓燕去看电影,pq qrrp 前提：结论：3.1推理的形式结构,()() AABABAABABABBAABBAABBCACABBCACABCDACBDABABAABABCDBDAC 附加律：化简律：假言推理：拒取式：析取三段论：假言三段论：等价三段论：构造性二难：破坏性二难：3.1推理的形式结构注意：以上都是蕴含式模式若某推理的形式结构与某定律一致，则推理正确成立的等值式可产生两条定律推理定律可产生相应的推理规则3.1

24、推理的形式结构3.2自然推理系统P定义.一个形式系统I由以下4部分组成： 非空的字母表，记作A(I) A(I)中符号构成的合式公式集，记作E(I) E(I)中特殊的公式组成的公理集，记作Ax(I) 推理规则集，记作R(I)自然推理系统形式系统公理推理系统任给的前提，应用规则得到结论（可能真）任给的公理，应用规则得到结论（永真）P, , , ,2.1.63.1(P)iiip q rp q r 定义.自然推理系统或1.字母表， ， ，（）和，合式公式定义中所定义的所有命题公式推理规则（）前提引入规则：证明的任何步骤上都可以引入前提3.2自然推理系统P(2)结论引入(T)规则：证明的任何步骤上所得的

25、结论都可作为 后继证明的前提（3）置换规则：在证明的任何步骤上，命题公式中的子公式都 可以用与之等值的公式置换ABABABAB(4)假言推理规则：若序列中已出现和 ，则可将 引入序列中(5)附加规则;（6）化简规则;（7）拒取式（8）假言三段论规则;（9）析取三段论规则（10)构造性二难规则;（11）破坏性二难规则（12）合取引入规则：若序列中出现了 和 ，则可将引入序列中3.2自然推理系统P,()pq qr pssrpq例：前提： 结论：例：若小王是理科生，则他的数学成绩一定很好。如果 小王不是理科生，他一定是文科生。小王的数学成绩 不好。所以小王是文科生。p：小王是理科生q：小王是文科生r

26、：小王的数学成绩很好,prpqrq 前提：结论：3.2自然推理系统P12121.()()()kkAAAABAAAAB附加前提证明法若推理形式为，则可转换为例：如果小张和小王去看电影，则小李也去看电影。小赵 不去看电影或小张去看电影。小王去看电影。所以， 当小赵去看电影时，小李也去。p：小张去看电影q：小王去看电影r：小李去看电影s：小赵去看电影(),pqrsp qsr 前提：结论：3.2自然推理系统P1212()( )()kkAAABAAAB 2.归谬法将结论的否定作为前提引入，能推出矛盾来，则推理正确例：如果马会飞或羊不吃草，则母鸡就会是飞鸟。如果母 鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭

27、子不会 跑。所以羊吃草。p：马会飞q：羊吃草r：母鸡是飞鸟s：烤熟的鸭子会跑(),pqr rssq前提：结论：3.2自然推理系统P所有的人总是要死的。苏格拉底是人。所以苏格拉底是要死的。p:q:r:, p qr前提：结论：()pqr推理形式：谓词逻辑谓词逻辑n4.1一阶逻辑命题符号化n4.2一阶逻辑公式及解释n5.1一阶逻辑等值式与置换规则n5.2一阶逻辑前束范式n5.3一阶逻辑的推理理论4.1一阶逻辑命题符号化个体常项个体变项, , ,iiia b ca b c用表示, , ,iiix y zx y z用表示1.个体词所研究对象中可以独立存在的具体的或抽象的客体（事物）表示具体的或特定的客体

28、表示抽象或泛指的客体个体变项的取值范围称为个体域，用D表示宇宙间一切事物组成的称为全总个体域1,2,3,N R有穷，无穷，谓词常项：具体性质或关系的词谓词变项：抽象或泛指的性质或关系的词2.谓词用来刻划个体词性质及个体词之间相互关系的词,iiiF G HF G H用,表示2是有理数x是无理数小王与小李同岁x与y具有关系L是有理数是无理数与同岁与具有关系LF：G：H：L：4.1一阶逻辑命题符号化3.量词：个体词之间的数量关系（1）全称量词 “一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都” 记作(2) 存在量词 “存在”，“有一个”，“有的”，“至少有一个”记作4.符号化 确定个体域

29、确定个体词、量词和谓词确定联结词4.1一阶逻辑命题符号化例：所有的人都是要死的。 有的人用左手写字。注意：全称量词的特性谓词必须作为蕴涵式的前件引入存在量词的特性谓词必须作为合取式的合取项引入同一命题，不同的个体域符号化的形式可能不同未指明个体域即为全总个体域4.1一阶逻辑命题符号化例：在美国留学的学生未必都是亚洲人。 有的兔子比所有的乌龟跑的快。 对任意的整数x，都存在整数y是的xy10。注意：多个量词出现时，顺序一般不能随便换有些命题符号化形式不唯一4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释.F(1), , ,(2), , , , ,(7) ( ),iiiiiiiiiiiia b c

30、a b cx y zx y zf g hf g hF G HF G H 定义一阶语言 的字母表个体常项：，个体变项：，(3)函数符号：，(4)谓词符号：，(5)量词符号： ，(6)联结词: , , ,和121212( ,)n, , ,n( , ,)(3)(1)(2)nnnx xxt ttt tt定义.一阶语言的项的定义(1)个体常项和个体变项是项；(2)若,是任意的 元函数, 是一阶语言的任意 个项，则,是项；所有的项都是有限次使用得到的。121212.( ,)n, , ,n( , ,)nnnR x xxt ttR t tt定义设，是一阶语言的任意 元谓词, 是一阶语言的任意 个项，则称，是

31、一阶语言的原子公式。4.2一阶逻辑公式及解释.(1)(2)()(3),(4),(5)AAA BAB AB AB ABAxAxA定义一阶语言的合式公式的定义原子公式是合式公式；若 是合式公式，则也是合式公式；若是合式公式，则也是合式公式；若 是合式公式，则也是合式公式；只有有限次地应用(1)(4)构成的符号串才是合式公式。合式公式也成谓词公式，简称公式4.2一阶逻辑公式及解释.,xAxAxxAxAxA定义在公式中，称 为指导变元，A为相应量词的辖域。在的辖域中， 的所有出现称为约束出现， 中不是约束出现的变元均称为自由出现。( ( , )( , ) ( ( )( )( )( , , )x F x

32、 yG x zx F xG yy H xL x y z 例：.AAA定义设 是任意的公式，若 中不含自由出现的个体变项，则称 为封闭的公式，简称闭式。4.2一阶逻辑公式及解释( ( )( ) ( ( )( )( , )( ( , ), ( , )x F xG xx y F xF yG x yH f x yg x y 例：12.I(1)(2) ,(3)| ,1(4)| ,1.IIinIinIiDDa aaDfi nDFi n定义一阶语言的解释 由以下部分组成非空个体域；中一些特殊元素的集合,；上特定函数集合；上特定谓词集合4.2一阶逻辑公式及解释I(1)(2)(3)(4).IinniinniiD

33、affFF对 的说明：公式中的个体变项均取值于；若含个体变项就解释为 ；若含函数就解释为 ；若含谓词就解释为4.2一阶逻辑公式及解释I(1) D=N=0,1,2, (2) 0(3) ( , ), ( , )(4) ( , )af x yxy g x yxyF x yxy例：解释 ：为(1) ( ( , ), ( , )(2)( ( , ), )(3)( ( , ), )( , )F f x y g x yxF g x a xxF g x a xF x y定理.闭式在任何解释下都变成命题。4.2一阶逻辑公式及解释.AAAAAAA定义设 为公式 若 在任何解释下均为真，则称 为永真式(逻辑有效式)

34、. 若 在任何解释下均为假，则称 为永假式(矛盾式). 若至少有一个解释使 为真，则称 为可满足式。0121200., n(1),nniiAp ppA AAAinApAA 定义设是含命题变项， 的命题公式，是个谓词公式，用处处代替 中的所得公式 为 的代换实例。4.2一阶逻辑公式及解释( )( , )( )( )( )( )( ( )( )( ( )( )xF xx yG x yxF xxF xyG yyG yx F xG xx F xG x 例：定理.重言式的代换实例都是永真式，矛盾式的代换 实例都是矛盾式。( )( )( ( )( )( )xF xxF xx F xG xyG y4.2一阶

35、逻辑公式及解释5.1一阶逻辑等值式与置换规则A BABABAB定义.设 , 是一阶逻辑中任意两个公式，若是永真式， 则 与 等值，记作1212121.D= ,( )()()()( )()()()nnna aaxA xA aA aA axA xA aA aA a消去量词等值式 ,第一组第一组 命题逻辑中等值式模式的代换实例都是一阶逻 辑的等值式模式第二组第二组 一阶逻辑中特殊的等值式 , , ,( )( ),( , )Da b cxF xyG yx yF x y 2.( )( )( )( )xA xx A xxA xx A x 量词否定等值式3.(1)( ( )( ) ( ( )( ) ( (

36、)( ) ( )( )x A xBxA xBx A xBxA xBx A xBxA xBx BA xBxA x 量词辖域收缩与扩张等值式(2)( ( )( ) ( ( )( ) ( ( )( ) ( )( )x A xBxA xBx A xBxA xBx A xBxA xBx BA xBxA x 5.1一阶逻辑等值式与置换规则( ( )( )( )( )( ( )( )x A xB xxA xxB xx A xB xxA xxB x 4.量词分配等值式( )( )x A xB xxA xxB xx A xB xxA xxB x 5.量词分配蕴涵式（ ） （ ）（ ）（ ）（ ） （ ）（ ）（

37、 ）D=N，F(x)：x是奇数 G(x)：x是偶数5.1一阶逻辑等值式与置换规则( )( ),( )( )AABBAAABAB 置换规则 设是含公式 的公式，是用 取代 (中的所有的 之后的公式。若则。AAAA换名规则 设A为一公式，将 中某量词辖域中某约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个体变项的符号，公式中其余部分不变，设所得公式为,则5.1一阶逻辑等值式与置换规则AAAAA代替规则 设 为一公式，将 中某自由出现的个体变项的所有出现用A中未曾出现过的某个体变项的符号代替，公式中其余部分不变，设所得公式为,则( , , )( , , ) ( ( , )( ,

38、, )xF x y zyG x y zx F x yyG x y z例：( ( )( )( ( )( ) ( ( )( )( , )( ( )( )( , )x F xG xx F xG xx y F xG yL x yx y F xG yL x y 证明：5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式为了方便使用谓词公式进行定理证明和逻辑推理，需要把谓词公式变换为便于使用的规范形式，就是范式。 112233kki112233kk.AAQ x Q x Q xQ x BQBAQ x Q x Q xQ x B定义 设 为一个一阶逻辑公式，若 具有 形式，其中每个为量词 或 ， 为不含量词的

39、谓词公式，则称 为前束范式，称为公式的首标， 为公式的尾部。)()()(),()2();,()()() 1 (1yQxRxQyxPzyxzxRyQxPzyx：例定理1：任一谓词公式都可以化成为与之等值的前束范式。1(B23求前束范式的步骤：、消去可能出现的多余量词 在 中无相应变项的量词）；、利用换名或代入规则使所有约束变元的符号均不相同，并且自由变元与约束变元的符号也不相同；、利用量词辖域的扩张和收缩律，将所有量词以在公式中出现的顺序移到公式的最前面，扩大量词的辖域至整个公式。5.2一阶逻辑前束范式( )( )( , )( , )( , )( )( , , )xF xxG xxF x yyG

40、 x yxF x yyG yxH x y z例：5.2一阶逻辑前束范式5.3一阶逻辑的推理理论1212,BBkkA AAAAA从,推出结论 的推理形式在一阶逻辑中，称永真的蕴涵式为推理定律。若一个推理的形式结构正是某条推理定律，则该推理显然是正确的。第一组第一组 命题逻辑推理定律的代换实例第二组第二组 由基本等值式生成的推理定律第三组第三组 以下重要定律( )( )( ( )( )( ( )( )( )( )( ( )( )( )( )( ( )( )( )( )xA xxB xx A xB xx A xB xxA xxB xx A xB xxA xxB xx A xB xxA xxB x 第

41、四组第四组 消去量词和引入量词的推理规则1、全称量词消去规则（UI）5.3一阶逻辑的推理理论)()(yAxxAUI规则成立的条件： （1）取代x的y应为任意不在A(x)中约束出现的个体变项； （2）用y取代A(x)中自由出现的x时，必须将所有的自由出现x都取代； （3）自由变元y也可替换为个体域中任意的个体常元c，c为任意不在A(x)中出现过的个体常项。)()(cAxxA5.3一阶逻辑的推理理论),( : :1yxyLxyxL(x,y)RD：例含义：如果个体域的所有个体都具有性质A，则个体域中的任一个个体都具有性质A。 2、存在量词消去规则（EI）)()(cAxxA含义：如果个体域存在有性质A

42、的个体，则个体域中必有某一个个体具有性质A。 5.3一阶逻辑的推理理论ES规则成立的条件： （1）c是个体域中使A为真的特定的个体常项； （2）c不曾在A(x)或前面的推导公式中出现过； （3）A（x）中除x外还有其他自由变元时，不能用此规则1xxA ND2）：（：例),( : :3yxyLxyxL(x,y)RD：例5.3一阶逻辑的推理理论）（）（是偶数）：（是奇数）：（：例xxQxxPxxQ xxP ND43、全称量词引入规则（UG）( )( )A yxA x UG规则成立的条件： （1）y在A（y）中自由出现，且y取任何值时A均为真；（2）x不在A（y）中约束出现。 含义：如果个体域的任意

43、个体都具有性质A，则个体域中的所有个体都具有性质A。 ),(A(x) : :5yxyLyxL(x,y)RD：例5.3一阶逻辑的推理理论4、存在量词引入规则（EG）( )( )A cxA x EG规则成立的条件： （1）c是个体域中某个确定的个体；（2）代替c的x不在A（c）中出现过。 含义：如果个体域有某一个个体c具有性质A，则个体域中必存在具有性质A的个体。 ), 8(A(8) : :6yyLyxL(x,y)RD：例5.3一阶逻辑的推理理论定义.一阶逻辑自然推理系统F的定义 1.字母表：同一阶语言的字母表 2.合式公式：同一阶语言合式公式的定义 3.推理规则 a.前提引入规则 b.结论引入规

44、则 c.置换规则 d.假言推理规则 e.附加规则 f.化简规则 g.拒取式规则 h.假言三段论规则 i.析取三段论规则 j.构造性二难规则 k.合取引入规则 l. UI，EI，UG，EG5.3一阶逻辑的推理理论例7：证明逻辑三段论 所有的人总是要死的。 苏格拉底是人。所以苏格拉底是要死的。( ( )( ( )( )( )( ( )( )x F xG yH xxF xx F xH x例8：已知前提，证明结论：5.3一阶逻辑的推理理论5.3一阶逻辑的推理理论例10：如果一个人怕困难就不会获得成功。每一个人或者获得成功或者是失败的。有些人未曾失败过，所以有些人不怕困难。（个体域是人的集合）判断这个推

45、理是否正确。 例9：根据前提集合：同事之间总是有工作矛盾的，张平和李明没有工作矛盾，能得出什么结论？第二部分 集合论n第六章 集合代数n第七章 二元关系n第八章 函数n第九章 集合的基数第六章 集合代数n6.1 集合的基本概念n6.2 集合的运算n6.3 集合恒等式一、集合的概念集合（set)的含义：一个集合是作为整体识别的、确定的、互相区别的一些事物的聚集（全体或总体等)。构成一个集合的每个事物，成为这个集合中的元素或成员。集合一般用A、B、C表示，集合中的元素用a、b、c表示。但这不是绝对的，因为一个集合可以作为另一个集合的元素。如果x是集合s的一个元素,记作 ; y不是集合s的元素，记作

46、 sxsy6.1集合的基本概念例1： 1.偶素数集合。2.二进制的基数集合。3.英文字母的集合。4.全体实数的集合。5.自然数集合。6.整数集合。7.有理数集合。8.素数集合。6.1集合的基本概念6.1集合的基本概念集合的表示方法: 1.列举法（枚举法、外延法）把集合的所有元素（元素较少时）写在一个花括号内;列出足够多的元素（元素很多或无穷时）以反映集合中元素的特征。如例1中的1、2、3、5可分别表示为：20，1a，b，cz，A，B，CZ1，2，36.1集合的基本概念2.描述法（概括法）将集合中的元素的性质用一个谓词公式来描述，S=X|P(X),意义为:集合S由且仅由满足为此公式P(X)的对象

47、组成，即 ，当且仅当p(a)为真。如例1中的4、6、7可表示为：sa|Rxx|Ixx|Qxx3.文氏图用图形图像直观的描述集合之间的相互关系和有关运算。6.1集合的基本概念几个常见集合的表示符号：N：自然数集合，N=0，1，2，3；I：整数集合；P：素数或质数集合；Q：有理数集合；R：实数集合；C：复数集合；6.1集合的基本概念集合的特性:A.互异性：一个集合的个元素是可以区分开的，即每一 元素只出现一次。B.无序性：集合中元素排列顺序无关紧要，即集合表示 形式的不唯一性。例2：a，b，c=b，c，a=c，a，b=a，c，b=b，a，c=c，b，a6.1集合的基本概念C.确定性：任一事物是否属

48、于某一集合，回答是确定的。例3：“好书”的全体，这不构成集合。注意：一个集合是已知的，指的是对任一元素，利用某种方法可以判断它是否是这个集合的元素，而不是把集合的每一个元素都给出来。6.1集合的基本概念集合的元素可以是任何具体或抽象的事物，包括别的集合，但不能是本集合自身。例4：在一个住着一些人家的偏僻孤岛上，岛上只有一个理发师a，a给且只给岛上所有不能自己理发的人理发。问谁给a理发？定义1.设A和B是两个集合，若A中的每一个元素都是B的元素，则称A是B的子集，也称B包含A,记作)(ABBA6.1集合的基本概念定义2.设A和B是任意两个集合，若A包含B且B包含A，则称A与B相等，记作A=B.即

49、，ABBABA|BxAxxBA二、集合的关系6.1集合的基本概念定义3.若A是B的子集且 ，则称A为B的真子集，或称B真包含A，记作，B称为A的超集。是集合间的包含关系。、；是元素与集合间的关系的区别：和、注意BABA BABABA. 2 . 15中国人台湾人台湾人都是中国人。：例CRQN集合的相等关系的性质：。，则且传递性：若）（；，则对称性：若）（；自反性：CACBBAABBAAA.3.2).1 (设A,B,C为3个集合，集合的包含关系的性质:。，则且传递性：若）（；，则且反对称性：若）（；自反性：CACBBABAABBAAA.3.2).1 (6.1集合的基本概念, 01x|xA62Rx：

50、例定义4.不包含任何元素的集合称为空集，记作或推论：空集是唯一的。集。：空集是一切集合的子定理1 .7.6 .5.4 ).3().2( .17）（）（；）（）（；）（：判断下列命题的真假例6.1集合的基本概念三、特殊集合定义4：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E。 。，；例：210 1 0定义5.集合中元素的个数称为基数或势，用|A|表示。基数是有限数的集合称为有限集，否则称为无限集。全集是相对的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集 。6.1集合的基本概念6.1集合的基本概念含n个元素的集合简称n元集，其含有k(kn)个元素的子集称为

51、它的k元子集。定义6.由集合S的所有子集组成的集合，称为集合S的幂 集，记作P（S）。表示为：.|)(SAASP有限集S ，|P（S）|=2|S|例：Aa，b，c，d，c6.2 集合的运算一、集合的基本运算BxAx|xBA BA BABA1.且。的交集，记作与称为，的公共元素组成的集合和，由和设有集合定义 BA| . B. 2BxAxxBABABAABA或的并集，记作与称为，的所有元素组成的集合和，由和设有集合定义.iiiiAA与分别记为，算推广到任意多个集合将集合的交运算和并运| . . 3BxAxxBABAABBABA且的相对补集，记作对称为，的一切元素组成的集合但不属于，由属于、设有集合

52、定义6.2 集合的运算|.BxxBxExxBEBBBEB且的绝对补集，记作的相对补集，称为对全集)()( )()( | .BA . 4BABAABBAAxBxBxAxxBABAABBABA且，或且的对称差，记作与的集合，称为元素组成的但不属于，或属于但不属于，由属于、设有集合定义CABACABACBACBCBA)( ,),(,63851321求，、，、，：例定义5.设A 为集合， A 的元素的元素构成的集合称为A的广义并，记作A 。6.2 集合的运算A x|z (zA xz)若A A1,A2,，An，则A A1A2 An 定义6.设A 为非空集合， A 的所有元素的公共元素构成的集合称为A的广

53、义交，记作A 。A x|z (zA xz)若A A1,A2,，An，则A A1 A2 An 例：Aa，b，c，a，b，e B=a C=a，c，d集合运算的优先级：高级：广义并、广义交、绝对补、求幂集；同级按从右向左的顺 序进行低级：并、交、相对补和对称差；同级按从左向右的顺序进行6.2 集合的运算6.2 集合的运算 文氏图可以用来描述集合间的关系及其运算.在文氏图中,全集用矩形表示,子集用圆形表示,阴影部分表示运算结果的集合.二、文氏图ABBABABAABBAB ABA 6.2 集合的运算A A使用文氏图可以方便地解决有穷集的计数问题。已知条件文氏图：每条性质决定一个集合，若无特殊说明任何两个

54、集合都画成相交的。将已知集合的元素数填在相应的区域，从交集填起。例：P106，18三、有限集合元素的计数。）（；）（）；，（）（；各式成立由集合运算的定义下列都是有限集合和设BABABABABABABABABABA243min2) 1 (:,6.2 集合的运算设S为有穷集，P1、P2、Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi，两种情况必具其一。令Ai表示S中具有性质Pi的元素构成的集合，则S中不具有性质P1、P2、Pm的元素数为|A1A2Am|6.2 集合的运算|) 1(|2111121mmmkjikjimjijimiimAAAAAAAAASAAA|) 1(|S21

55、111121mmmkjikjimjijimiimAAAAAAAAAAAA元素数为：中至少具有一条性质的由此可以得到，容斥原理例2.对100名大学生进行的结果是：34人爱好围棋，24人爱好美术，48人爱好音乐；13人既爱好围棋又爱好音乐，14人既爱好围棋又爱好美术，15人既爱好美术又爱好音乐；有25人这三种爱好都没有，问这三种爱好都有的大学生人数是多少？。定理。定理32133221321321212121 . 2 . 1AAAAAAAAAAAAAAAAAAAAA6.2 集合的运算6.3 集合恒等式一、集合运算定律以下列出集合性质中最主要的几条基本定律，对于全集E的任意子集A，B，C，有：A;BB

56、AA,BB AABBA , ) 1 (交换律;) , )2(CBACB A C,BAC(BACBACBA结合律 C);(AB)(AC)(B A, CABACBA,CABACBACABACBA ,)3( 分配律A;A A,-A A,A ,A )4(EA同一律;AA , 5EAA）互补律（；）重补律（AA 6; ,7AAAAAA）等幂律（; , , ,)8(AAAAAEEA零一律; ,)9(ABAAABAA吸收律）；（德摩根律CABACBACABACBABABABABA()()( ),()()(,)( ,)10().()( )()( )()(,11BABAABBABABABABABA）功能完备律（

57、6.3 集合恒等式1、基本定义法根据集合相等的充要条件等式两边互为子集或由定义进行等价推理。2、公式法利用已证明过的恒等式去证明另外的恒等式。若表达式中出现形为A-B的差集时，用功能完备律先将运算“-”转化为运算“ ”和“”。3、集合成员表示法用表格的方式描述集合的交、并、补集运算的定义。在表的列中，0表示元素x不属于集合s ，1表示元素x属于集合s ，这种表格称为集合成员表。SxSx二、集合恒等式证明6.3 集合恒等式).()()(:1CABACBA证明分配律例)()()()()()()()()(:CABAxCAxBAxCxAxBxAxCxBxAxCBxAxCBAx证明6.3 集合恒等式).

58、()()(:2CABACBA证明德摩根律例)()()()()()()()()()()(:CABAxCAxBAxCxAxBxAxCxBxAxCxBxAxCBxAxCBxAxCBxAxCBAx证明6.3 集合恒等式)()()(:3CABACBA证明例CBACBACBA)()(:证明CBACBACBAABACABACABACABA)()()()()()()()()(6.3 集合恒等式.)4(;)3(;)2(;) 1 (:,:4BAABABABBABA价的证明以下四个命题是等为集合和设例)(: )2() 1 (:BBABxBAxBxAxAx用循环法证明证明6.3 集合恒等式ABABAAxBxAxBAx

59、即)(: )3()2(BAABAxBxAxBABxAx即反之)(,6.3 集合恒等式)(: )4()3(ABABBABABABBBABABBA)(: ) 1 ()4(6.3 集合恒等式.,;,:S. 1SxSxSxSxS则若则若定义如下的补集集合定义定义2.任意有限集合S在其所有集合的可能赋值下的表称为集合S的成员表.6.3 集合恒等式当集合的成员数目不大时,可以用集合成员表证明集合恒等式。构造成员表的步骤如下：（1）列出有限集合S中所有集合S1，S2，Sn所有可能的赋值，不同的赋值共有2n个。（2）按照从内到外的顺序写出集合s的各层次。（3）对应每个赋值，计算集合s的各层次值，直到最后计算出

60、整个集合s的值。6.3 集合恒等式利用集合成员表，可以判断集合的性质及集合间的关系。（1）若集合是全集，则其成员表必全为1，即所有集合都是它的成员。（2）若集合是空集，则其成员表必全为0，即没有集合是它的成员。（3）若集合A和B相等，则他们的成员表对应行的值必相同。若集合A是B的子集，则当A的值为1时，B的对应行的值必为1.)(. 5BABA根律用集合成员表证明德摩例6.3 集合恒等式小 结集合的概念集合的特性集合的表示方法:列举法、描述法、文氏图集合的运算：并、交、补、差、求幂集合间的关系：包含、相等集合恒等式的证明：定义法、公式法、成员表法第七章二元关系n7.1 有序对与笛卡儿积n7.2