求下列各式的真值。
（1）?xP(x，3)
，y) （2）?yP(1y)
（3）?x?yP(x，y) （5）?x?yP(x， y) （4）?x?yP(x，y) （6）?y?xP(x，3)?1。 解（1）因为P(3，3)?1，所以?x(P(x，，3)?0，所以?y(P(1，y)?0。 （2）因为P(1，3)?0，所以?x?yP(x，y)?0。 （3）因为P(1y)?1。 （4）因为P(3，3)?1，所以?x?yP(x，y)??x(P(x,1)?P(x,2)?P(x,3)) （5）?x?yP(x，?(P(1,1)?P(1,2)?P(1,3))?(P(2,1)?P(2,2)?P(2,3))?(P(3,1)?P(3,2)?P(3,3)) y)??x(P(x,1)?P(x,2)?P(x,3)) （6）?x?yP(x，?(P(1,1)?P(1,2)?P(1,3))?(P(2,1)?P(2,2)?P(2,3))?(P(3,1)?P(3,2)?P(3,3)) ?1?1?1?1
4. 设下面所有的个体变元的个体域都是整数集合，用自然语言表达下列各式并确定其2?n(n?0) （1）2?n(n?2) （2）真值。
解（1） 对任意的整数n有n?0。其值为1。
2（2）存在整数n使得n?2。其值为 0。
2（3）对任意的整数n有n?n。其值为1。
（3）?n(n?n) 2（4）?n?m(n?m) （6）?n?m(n?m?0) （8）?n?m(n?m?5) （10）?n?m(n?m?4?n?m?1) （12）?n?m?k(k?(n?m)/2) 2222?n?m(n?m)
（5）（7）?n?m(n?m?m)
（9）?n?m(n?m?6)
22（11）?n?m(n?m?4?n?m?2) 2（4）对任意的整数n，存在整数m使得n?m。其值为1。
（5）存在整数n使得对任意的整数m都有n?m。其值为0。
（6）对任意的整数n，存在整数m使得n?m?0。其值为1。 （7）存在整数n使得对任意的整数m都有n?m?m。其值为1。
22（8）存在这样的整数n，m使得n?m?5。其值为1。
22（9）存在这样的整数n，m使得n?m?6。其值为0。 22（10）存在整数n使得对任意的整数m都有n?m?4且n?m?1。其值为 0。
（11）存在整数n使得对任意的整数m都有n?m?4且n?m?2。其值为 0。
（12）对任意的整数m，n，存在整数k使得k?(n?m)/2。其值为 0。
5. 令谓词P(x，y)表示“x访问过y”，其中x的个体域是学校全体学生，y的个体域（1）P(方元，www.)。 是所有网站的集合。用自然语言表达下列各式。
.com)。 （2）?xP(x，www.google（3）?yP(冯友，y)。 （4）?y(P(吴笛，y)?P(钱华，y))。 （P(黄帅，z)?P(y，z)))。 （5）?y?z(y?黄帅?（6）?x?y?z((x?y)?(P(x，z)?P(y，z)))。 解（1）方元访问过www.。
（2）至少有一个学生访问过。
（3）冯友至少访问过一个网站。
（4）至少有一个网站是吴笛和钱华都访问过的。
（5）有另外一个学生访问过黄帅访问过的所有网站。
（6）至少有两个不同的学生访问过的网站完全相同。
6. 令谓词P(x)表示“x说德语”，Q(x)表示“x了解计算机语言C++”，个体域为杭电全体学生的集合。用P(x)、Q(x)、量词和逻辑联接词符号化下列语句。
（1）杭电有个学生既会说德语又了解C++。 （2）杭电有个学生会说德语，但不了解C++。 （3）杭电所有学生或会说德语，或了解C++。 （4）杭电没有学生会说德语或了解C++。 假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”。用P(x)、Q(x)、M(x)、量词和逻辑联接词再次符号化上面的4条语句。 解 个体域为杭电全体学生的集合时： （1）?x(P(x)?Q(x)) （2）?x(P(x)??Q(x)) （3）?x(P(x)?Q(x)) （4）??x(P(x)?Q(x))
若个体域为全总个体域，谓词M(x)表示“x是杭电学生”，则： （1）?x(M(x)?P(x)?Q(x)) （2）?x(M(x)?P(x)??Q(x)) （3）?x(M(x)?(P(x)?Q(x))) （4）??x(M(x)?(P(x)?Q(x)))
7. 令谓词P(x，y)表示“x爱y”，其中x和y的个体域都是全世界所有人的集合。用P(x，y)、量词和逻辑联接词符号化下列语句。
8. 令谓词P(x，y)表示“x给y发过电子邮件”，Q(x，y)表示“x给y打过电话”，其中x和y的个体域都是实验班所有同学。用P(x，y)、Q(x，y)、量词和逻辑联接词符号化下列语句。
（1）周叶从未给李强发过电子邮件。 （2）方芳从未给万华发过电子邮件，或打过电话。 （3）实验班每个同学都给余涛发过电子邮件。 （4）实验班没有人给吕键打过电话。 （5）实验班每个人或给肖琴打过电话或给他发过电子邮件。 （6）实验班有个学生给班上其他人都发过电子邮件。 （7）实验班有个学生给班上其他人或打过电话，或发过电子邮件。 （8）实验班有两个学生互发过电子邮件。 （9）实验班有个学生给自己发过电子邮件。 （10）实验班至少有两个学生，一个给另一个发过电子邮件，而另一个给这个打过电话。 解（1）?P(周叶，李强) （2）?(P(方芳，万华)??Q(方芳，万华)) （3）?xP(x,余涛) （4）?x?Q(x,吕键) （1）每个人都爱王平。
（2）每个人都爱某个人。 （4）没有人爱所有的人。 （6）有个人人都不爱的人。 （8）成龙爱的人恰有两个。 （10）有人除自己以外谁都不爱。 （2）?y?xP(x,y)。 （4）??x?yP(x,y)。 （6）?y?x?P(x,y)。 （3）有个人人都爱的人。
（5）有个张键不爱的人。
（7）恰有一个人人都爱的人。
（9）每个人都爱自己。 （3）?y?xP(x,y)。
解（1）?xP(x,王平)。
（5）?y?P(张键，y)。
（7）?y(?xP(x,y)??v((?uP(u,v))?v?y))（每个人都爱这个人）或
?x(?yP(x,y)??u((?vP(u,v))?u?x))（这个人爱每个人）
（10）?x?y(P(x,y)?x?y)。 （8）?x?y(x?y?P(成龙,x)?P(成龙,y)??z(P(成龙,z)?(z?x?z?y)))。 （9）?xP(x,x)。
（5）?x(P(x,肖琴)?Q(x,肖琴)) （6）?x?y(y?x?P(x,y)) （7）?x?y(y?x?(P(x,y)?Q(x,y))) （8）?x?y(x?y?P(x,y)?P(y,x)) （9）?xP(x,x) （10）?x?y(x?y?P(x,y)?Q(y,x))
谓词公式及其解释 习题2.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。
（1）?x(P(x)?Q(x，y)) （2）?xP(x，y)??yQ(x，y) （3）?x?y(P(x，y)?Q(y，z))??xR(x，y，z) 解 （1）?x中的x是指导变元；量词?x的辖域是P(x)?Q(x,y)；x是约束变元，y是自由变元。 （2）?x中的x，?y中的y都是指导变元；?x的辖域是P(x，y)，?y的辖域是Q(x，y)；P(x，y)中的x是?x的约束变元，Q(x，y)中的x是自由变元，y是自由变元；y是?y的约束变元。 （3）?x中的x，?y中的y 以及?x中的x都是指导变元；?x的辖域是?y(P(x，y)?Q(y，z))，?y的辖域是P(x，y)?Q(y，z)，?x的辖域是R(x，y，z)；P(x，y)中的x，Q(y，z)中的y是约束变元；R(x，y，z)y都是约束变元；z是自由变元，中的x为约束变元，y，z是自由变元。
，2}，请给出两种不同的解释I1和I2，使得下面谓词公式在I1下都2. 设个体域D?{1是真命题，而在I2下都是假命题。 （1）?x(P(x)?Q(x))
（2）?x(P(x)?Q(x)) ，2}，P(x):x?0,Q(x):x?0。 解（1）解释I1：个体域D?{1，2}，P(x):x?0,Q(x):x?2。 （2）解释I2：个体域D?{1 3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）?x(P(x)??y(Q(y)?R(x，y))) （2）?x?y(P(x)?Q(y)?R(x,y)) 解 （1）成真解释：个体域D＝{1,2,3},P(x):x?0,Q(y):y?2,R(x,y):x?y?3。
成假解释：个体域D＝{1,2,3},P(x):x?0，Q(y):y?2，R(x,y):x?y?1。
（2）成真解释：个体域D＝{1,2,3}，P(x):x?0，Q(y):y?2，R(x,y):x?y?3。
成假解释：个体域D＝{1,2,3},P(x):x?0，Q(y):y?0，R(x,y):x?y?1。
4. 给定解释I如下：
个体域D?R（这里R为实数集合）。 个体常元a?0。 二元函数f(x，y)?x?y。 二元谓词P(x，y)：x?y，Q(x，y)：x?y。 在解释I下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又（1）?x?y(Q(x，y)??P(x，y)) （2）?x?y(P(f(x，y)，a)?Q(x，y)) （3）?x?y(Q(x，y)??P(f(x，y)，a)) （4）?x?y(Q(f(x，y)，a)?P(x，y)) 解（1）公式被解释成“?x?y(x?y?x?y)”，为真命题。
（2）公式被解释成“?x?y(x?y?0?x?y)”，为假命题。 （3）公式被解释成“?x?y(x?y?x?y?0)”，为真命题。 （4）公式被解释成“?x?y(x?y?0?x?y)”，为假命题。
5. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。
（1）P(x)??xP(x) （3）P(x)??xP(x)
（2）?xP(x)?P(x)
（4）?xP(x)?P(x) （6）?x?yP(x，y)??y?xP(x，y) （8）?x?yP(x，y)??x?yP(x，y) （10）?x?y(P(x，y)?P(y，x)) 2如何？
（5）?x(P(x)??P(x))
（7）?x?yP(x，y)??x?yP(y，x)
（9）?x?yP(x，y)??y?xP(x，y)
解（1）因为当存在某个x使P(x)取1时?xP(x)一定取1，所以公式是为永真式。 （3）取解释I1：个体域为自然数集合，P(x)：x?0。在I1下公式的前件与后件均为真，所以公式为真，即不是永假式。取解释I2：个体域仍为自然数集合，但P(x)取为x?0。在I2下公式不成为命题，即不是永真式。综合知公式为可满足式。 2IP(x)：x?0。在I1下，对任意的x，P(x)1（5）取解释：个体域为自然数集合，为真而?P(x)为假，所以公式为假，即不是永真式。取解释I2：个体域仍为自然数集合，2但P(x)取为x?0。在I2下，对任意的x，P(x)为假而?P(x)为真，所以公式为真，即不是永假式。综合知公式为可满足式。 （7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得?x?yP(x，y)取1而?x?yP(y，x)取0。?x?yP(y，x)取0表明存在某对x0,y0使离散数学及应用_甜梦文库
离散数学及应用
淘汰赛有101个人参加乒乓球淘汰赛（每一轮比赛 在参加人数是奇数时，让一人轮空），共需 进行多少场比赛方可决出优胜者（一场比赛 指两人的一次对垒）解（一）第一轮 50场， 剩50名优胜者 1名轮空 第二轮 25场， 剩25名优胜者 1名轮空 第三轮 13场， 剩13名优胜者 第四轮 6场， 剩6名优胜者 1名轮空 第五轮 3场， 剩3名优胜者 1名轮空 第六轮 2场， 剩2名优胜者 第七轮 1场， 剩1名优胜者 共计 50+25+13+6+3+2+1=100场解（二）用一一对应技术 一场比赛对应一个被淘汰者，反之也真，那 么比赛场数与被淘汰者人数是相等的。由于 优胜者只有一人，全部被淘汰者是100人， 因此要进行100场比赛方可决出优胜者。土耳其商人和帽子的故事? 这是著名物理学家爱因斯坦出过的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商， 有两个人前来应聘，这个商人为了试一试哪一个聪明些，就 把两个人带进一间漆黑的屋子里，他打开电灯后：“这张桌 子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我 把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人 摸一顶帽子戴在头上，在我开灯后，请你们尽快的说出自己 头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉， 然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶 帽子藏了起来，接着把电灯打开，这时，那两个有应试者看 到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便 喊到：“我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的？聪明的囚徒? 古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并他自恃聪明的做出一 种规定：囚徒可以说一句话，并且这句话是马上可 以验证其真假。如果囚徒说的是真话，那么处以绞 刑，如果囚徒说的是假话，那么处以砍头。许多囚 徒或者是因为说了假话而被砍头或者因为说了真话 而被处以绞刑。 有一位极其聪明的囚徒，当轮到他来选择处死方法 时，他说出一句巧妙的话，结果使这个国王按照哪 种方法处死他，都违背自己的决定，只得将他放了。 试问：这囚徒说的是句什么话？七桥问题哥尼斯堡城位于普雷格尔河畔，河中有两个岛，七 座桥使两个河心岛及两岸彼此相连。十八世纪的城中居 民热衷于这样一个问题：游人从四块陆地中的任何一地 出发，能否找到一条路线，通过每桥一次且仅一次，最 后返回原地？? 欧拉对七桥问题的解 1736年，著名数学家欧拉研究了七桥问题，他将这 个问题用结点和弧边组成的图来表示，问题归结为从 图中任一结点出发，经过每边一次且仅一次的回路是 否存在？他找到了存在这样一条回路的充分必要条件， 并由此判断七桥问题无解而结束了哥尼斯堡城民的烦 恼。同构四色问题任何一平面地D，如果相 遥仨T上不同的色以便 清界，t至多只要四N色就 搞定了，不管@地D有多N奇特 }s。lF者 @是在西元1852年，由I於英敦大W的弗朗 西斯 (Francis Guthrie)lF的。r他正在英 郡的地D，而lF了@有趣的F象。格里斯X得@其 中一定有什NW妙，於是便信告V他那W很好的哥 哥佛德雷克(Frederick Guthrie)。佛德雷克百思不得 其解，又求教於他的老----W家摩根(Morgan)。摩 根也o法_定@f法ΣΓ妒怯信o他的好朋 友哈D(Hamilton)，希望他要嘛就C明出@f法 是正_的，要不就e一反例，建出一需要5 N 色的地D怼４的哈D耗了13年心血，仍一I 莫展，抱憾而逝。
公_徵答 1878年，英W家Cayley ⑸鲜}曝光取名椤杆 色猜想」(因檫不_定ΣΓ哉f是猜想)，公_徵求解 答。 }一鞒鲠幔R上就有了回1879年和1880年， Kempe 和Tait 分el表文C明了四色}。Z右r的 度K於平息。不料事隔11年後，一名叫Heawood 的年p人指 出了Kempe C明中的e`，K利用Kempe 的方法C明出若用5 N色就保C一定能^分出地D上相^域。m然四色} 未被破解，但是至此算是~出了一大步。而另一方面，Tait 的文亦被mmlF多e`，甚至最後一e`是一直 到1946年才被lF的。@e我可看出@些人的研究精神是 多N可敬，被lFe`的|西K未被之如敝屣般G在一旁， 仍f不嘤腥巳パ芯克踔潦窃谑赂舭多世o之後。 然@善e`的文在W上仍然有其I，不可小U。解}花絮 一番LL雨雨下恚纳}更加受到目了。由於 Heawood 的「五色定理」的C明K不y，因此就有S多人 也小看了「四色}」的y度。最有趣的是以下@例子。 1902年秋天，h可夫斯基教授(Hermann Minkowsky， ，垡蛩固沟W)在上拓W的n堂上 就著W生面前f：「四色}之所以尚未被解Q是因 世界上第一流的W家都]空去研究它。」而且d之所 至，鼍妥C了起恚坏了好黑板，s依f未能 得C。接下星期的n，他^mC下去，n一堂一堂 地^去了，他如身陷泥沼，仍fo法C明出怼ＫK於投 降，承J自己也o能榱α恕＞驮谶@r候，天空正好霹 Z一巨，他感@地f：「上帝在湮业目裢　谷 後就^m上他的拓阏n了。
? 离散数学是现代数学的一个重要绪 言分支，是计算机科学与技术的基 础理论的核心课程之一。离散数 学与计算机科学中的数据结构、 操作系统、编译理论、算法分析、 逻辑设计、系统结构、机器定理 证明等课程息息相关。 ? 基本内容包括数理逻辑、集合论、 代数系统、图论等几大部分。离散数学? 离散数学(Discrete Mathematics)：&研究离散结构的数学分科。& --《辞海》79年版, P355 ? 用一组基本的指令来编制一个计算机程序， 非常类似于从一组公理来构造一个数学证明。 --D.E.Knuth(克纽斯)1974年Turing奖获得者。? 离散数学左孝凌等上海科技文献出版社? 离散数学耿素云等清华大学出版社参 考 书 目? 离散数学方世昌主编 西安电子科大出版社? Discrete Mathematics StructuresBemard Kolman Robert C. Busby Sharon Ross Prentice-Hall International,Inc. 1997.11 (英文原版影印)清华大学出版社? 离散数学是培养抽象思维和逻辑推理的学科，学 习 方 法 建 议因此要重视基本概念的学习，一定要认真研读 教材，特别要从实例和习题中搞清众多概念的 涵义。? 适当多做习题，至少要按时完成作业，强迫自己通过特定条件下运用所学的概念和理论，才 能真正掌握和理解它们，提高分析和解决问题 的能力。? 与教材配套的习题解答是离散数学的初学者必备的参考书，钻研习题解答，从中领会典型问 题的解题方法。不会求解的作业题，可以看习 题解答，但务求读懂，决不可一抄了事，养成 依赖习惯，白白浪费宝贵的时光！约 法 三 章? 手机（关机） ? 作业（及时）? 考试（改革）第一篇 预备知识第2章 计数问题2.0 内容提要1 乘法原理和加法原理2排列与组合 容斥原理与鸽笼原理 离散概率3 45递归关系电子科技大学离散数学课程组――国家精品课程离散数学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院日星期五2.1 本章学习要求重点掌握 11乘法原理和加 法原理 2排列组合的计 算 3利用容斥原理 计算有限集合的 交与并一般掌握了解 31 离散概率 2 离散概念的计 算公式及性质21 鸽笼原理 2 鸽笼原理的简 单应用 3 递归关系 4 递归关系的建 立和计算表2.2.1开胃食品 主食 种类 种类 价格 价 (元) 格 玉米片 2.15 汉堡(H) 3.2 (Co) 5 色拉(Sa) 1.90 三明治 3.6 (S) 5 鱼排(F) 3.1 5饮料 种类 价 格 茶水 0.7 (T) 0 牛奶 0.8 (M) 5 可乐 0.7 (C) 5 0.72.2.1 乘法原理如果一些工作需要t步完成，第一步有n1种 不同的选择，第二步有n2种不同的选择，? ， 第t步有nt种不同的选择，那么完成这项工作 所有可能的选择种数为：n1 ? n2 ??? nt例2.2.2 Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统 资源的方法来破坏计算机系统，通过以含恶意 宏的字处理文档为附件的电子邮件传播。当字 处理文档被打开时，宏从用户的地址本中找出 前50个地址，并将病毒转发给他们。用户接收 到这些被转发的附件并将字处理文档打开后， 解 根据Melissa病毒的扩散原理，经过四次转发， 病毒会自动继续转发，不断往复扩散。病毒非 共有 常快速地转发邮件，将被转发的邮件临时存储 50×50×50×50+50×50×50+50×50+ 50 +1 在某个磁盘上，当磁盘占满后，系统将会死锁 = 6377551个接收者。 甚至崩溃。问经过四次转发，共有多少个接收 者？
例2.2.3在一幅数字图像中，若每个像素点用8位进行编 码，问每个点有多少种不同的取值。 分析 用8位进行编码可分为8个步骤：选择第 一位，选择第二位，? ，选择第八位。每一个 位有两种选择，故根据乘法原理，8位编码共有 2×2×2×2×2×2×2×2 = 28 = 256种取值。 解 每个点有256( = 28) 种不同的取值。2.2.2 加法原理假定X1, X2, ?, Xt均为集合，第i个集合Xi 有ni个元素。如{X1, X2, ?, Xt}为两两不相交 的集合，则可以从X1, X2, ?, Xt中选出的元 素总数为： n1 + n2 + ? + nt。即集合X1∪X2∪…∪Xt含有n1 + n2 + … + nt个元素。例2.2.4由Alice、Ben、Connie、Dolph、Egbert和 Francisco六个人组成的委员会，要选出一个 主席、一个秘书和一个出纳员。 （1）共有多少种选法？ （2）若主席必须从Alice和Ben种选出，共 有多少种选法？ （3）若Egbert必须有职位，共有多少种选 法？ （4）若Dolph和Francisco都有职位，共有
多少种选法？例2.2.4 解（1）根据乘法原理，可能的选法种数为 6×5×4= 120； （2）[法一] 根据题意，确定职位可分为3个 步骤：确定主席有2种选择；主席选定后， 秘书有5个人选；主席和秘书都选定后，出 纳有4个人选。根据乘法原理，可能的选法 种数为2×5×4 = 40；例2.2.4 解(续)[法二] 若Alice被选为主席，共有5×4 = 20种方法 确定其他职位；若Ben为主席，同样有20种 方法确定其他职位。由于两种选法得到的集 合不相交，所以根据加法原理，共有20＋20 = 40种选法；例2.2.4 解(续)(3)[法一] 将确定职位分为3步：确定 Egbert的职位,有3种方法；确定余下的较 高职位人选, 有5个人选；确定最后一个 职位的人选, 有4个人选。根据乘法原理， 共有3×5×4 = 60种选法；例2.2.4 解(续)[法二] 根据(1)的结论，如果Egbert为主席， 有20种方法确定余下的职位；若Egbert为秘 书，有20种方法确定余下的职位；若Egbert 为出纳员，也有20种方法确定余下的职位。 由于三种选法得到的集合不相交，根据加法 原理，共有 20＋20＋20 = 60种选法；例2.2.4 解(续)（4）将给Dolph、Francisco和另一个人指定职 位分为3步： 给Dolph指定职位，有3个职位可选； 给Francisco指定职位，有2个职位可选； 确定最后一个职位的人选，有4个人选。 根据乘法原理，共有3×2×4 = 24种选法。2.3 排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选 同一职位。为了使选票上人名的次序不对投票 者产生影响，有必要将每一种可能的人名次序 打印在选票上。会有多少种不同的选票呢？ 从某个集合中有序的选取若干个元素的问题， 称为排列问题。2.3.1 排列问题定义2.3.1 从含n个不同元素的集合S中有序选 取的r个元素叫做S的一个r -排列，不同的排列 总数记为P(n, r)。如果r = n，则称这个排列为S 的一个全排列，简称为S的排列。 显然，当r&n时，P(n, r) = 0。例2.3.1从含3个不同元素的集合S中有序选取2个元素 的排列总数。 解 从含3个元素的不同集合S中有序选取2个元 素的排列总数为6种。 如果将这3个元素记为A、B和C，则6个排列为 AB, AC, BA, BC, CB, CA。定理2.3.1对满足r≤n的正整数n和r有P(n,r) ? n ? (n ? 1)?(n ? (r ? 1))第1位 第2位 第3位 n n-1 n-2…… 图2.3.1第r-1位第r位n-(r-2) n-(r-1)推论2.3.2n个不同元素的排列共有n！种，其中n! ? n ? (n ? 1) ? ?2 ? 1例2.3.2A,B,C,D,E,F组成的排列中， （1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解 (1)将DEF看成一个对象，根据推论2.3.2，满 足条件的排列为A,B,C,DEF的全排列，共有4！ =24种； （2）根据题意，满足该条件的排列分为两步： 第一步确定D, E和F三个字母的全排列，有3！ 种排列，第二步将已排序的D, E和F看成一个整例2.3.36个人围坐在圆桌上，有多少种不同的坐法？通 过转圈得到的坐法视为同一种坐法。 F E 解 6个人围坐在圆桌上， A B 有120种不同的坐法。DC 图2.3.2n个人围坐圆桌上，有(n-1)！种不同的坐法，我们称 这种排列为环排列，从n个人中选出r个人为圆桌而坐 称为环形r -排列。定理2.3.3含n个不同元素的集合的环形r-排列数Pc(n,r)是 。 P(n, r) (2.3.3) n!Pc (n, r)= r ? r ? (n ? r)!例2.3.4求满足下列条件的排列数。 (1)10个男孩和5个女孩站成一排，无两个女孩 相邻。 (2)10个男孩和5个女孩站成一圆圈，无两个女 孩相邻. 解 (1)根据推论2.3.2，10个男孩的全排列为10!， 5个女孩插入到10个男孩形成的11个空格中的 插入方法数为P(11, 5)。根据乘法原理，10个 男孩和5个女孩站成一排，没有两个女孩相邻 的排列数为：
例2.3.4 解（续）（2） 根据定理2.3.3，10个男孩站成一个圆 圈的环排列数为9！，5个女孩插入到10男孩 形成的10个空中的插入方法数为P(10, 5)。 根据乘法原理，10个男孩和5个女孩站成一 个圆圈，没有两个女孩相邻的排列法为： 9!× P(10, 5) =（9!×10!)/5!。2.3.2 组合问题定义2.3.2 从含有n个不同元素的集合S中无序 选取的r个元素叫做S的一个r -组合，不同的组 合总数记为C(n, r)。 当n≥r = 0时，规定C(n, r) = 1。 显然，当r&n时，C(n, r) = 0。定理2.3.4对满足0& r ≤n的正整数n和r有，即n! C(n, r) ? r!(n ? r)!证明 先从n个不同元素中选出r个元素， 有C(n, r)种选法，再把每一种选法选出 的r个元素做全排列，有r！种排法。定理2.3.4（续）根据乘法原理，n个元素的r排列数为：即P(n, r) ? r!C(n, r)P(n, r) n! C(n, r) ? ? r! r!(n ? r)!例2.3.5一副52张的扑克牌含有4种花色：梅花、方 片、红桃和黑桃；各有13种点数，分别为A, 2―10, J, Q, K。试求满足下列条件的组合数。 （1）手中持有5张牌称为一手牌，一手牌共 有多少种可能的组合？ （2）一手牌中的5张都是同一花色，共有多 少种可能的组合？ （3）一手牌中有3张牌点数相同，另外两张 牌点数相同，共有多少种可能的组合？
例2.3.5 解（1）一手牌可能的组合数等于从52张牌中 选出5张的可能组合数，有C(52,5)种可能的 组合； （2）选同一花色的5张牌分两步进行：一选 花色，有C(4, 1)种，二在选定的花色中选5 张牌，有C(13, 5)种。据乘法原理，有 C(4,1)×C(13,5)种；例2.3.5 解（续）（3）该组合问题需四步完成： 一选第一个点数，有C(13,1)种； 二选第二个点数，有C(12,1)种： 三选第一点数的3张牌，有C(4, 3)种； 四选第二点数的2张牌，有C(4,2)种。 根据乘法原理，共有C(13,1)×C(12, 1)×C(4, 3)×C(4, 2)= 13×12×4×6=3744 种选法。2.4 容斥原理与鸽笼原理容斥原理是研究若干有限集合交与并的计数 问题 鸽笼原理则是研究某些特定对象的存在性问 题。2.4.1 容斥原理定义2.4.1 所谓容斥，是指我们计算某类物 体的数目时，要排斥那些不应包含在这个计数 中的数目，但同时要包容那些被错误地排斥了 的数目，以此补偿。这种原理称为容斥原理 (The Principle of Inclusion-exclusion)，又称 为包含排斥原理。定理2.4.1设A和B是任意有限集合，有 U A |A∪B| = |A|＋|B|－|A∩B|。 B 分析 由图2.4.1容易看出， 图2.4.1 A∪B = (A - B)∪(A∩B)∪(B - A)， A = ( A - B)∪(A∩B)， B = (A∩B)∪(B - A)。A-BB-A|A∪B| = |A-B|+|A∩B|+|B-A||A| = |A-B|+|A∩B| 推论2.4.2 设U为全集，A和B是任意有限集合，则 |B| = |A∩B|+|B-A|A ? B ? U ?( A ? B) ? A ?B例2.4.1对所给的集合验证定理2.4.1。 （1）A = {1,2,3,4}，B = {2,3,5,6,8}； （2）A = {1,2,3,4}，B = {5,6,7,8}。 解 (1)∵ A∪B={1,2,3,4,5,6,8}，A∩B={2,3} 根据定理2.4.1， 分析 ∴ |A∪B| = 7,|A∩B|=2。 需先计算A∪B和A∩B， 又∵ |A|=4, |B|=5， 再计算|A|,|B|和|A∪B|， ∴ |A|＋|B|－|A∩B|=4＋5－2=7= |A∪B|即 然后代入公式(2.4.1)两端，验证等式即 定理2.4.1成立； 可。(2)略。三个集合的情形定理2.4.3 设A，B和C是任意三个有限集合，有 (2.4.3) ? C ) ? A ? B ? C A ? B?C ? ( A ? B ? C) ?( A ?B ? A ?C ? B 推论2.4.4 设U为全集， A，B和C是任意有限 集合，则 (2.4.4)A?B?C ? U ?(A ? B ? C) ?(A?B ? A?C ? B?C)? A?B?C例2.4.2调查260个大学生，获得如下数据：64人 选修数学课程，94人选修计算机课程，58人 选修商贸课程，28人同时选修数学课程和商 贸课程，26人同时选修数学课程和计算机课 程，22人同时选修计算机课程和商贸课程， 14人对三种课程都选修。问 （1）调查中三种课程都不选的学生有多少？ （2）调查中只选修计算机科学课程的学生 有多少？例2.4.2 解设A、B、C分别表示选修数学课程，计算 机课程和商贸课程的人构成的集合， 则三种课程都不选的学生集合为 ? C ，只选 A?B 修计算机科学课程学生的集合为 。 A? B?CU A C 图2.4.2B例2.4.2 解（续）（1）∵|U|=260, |A|=64, |B|=94, |C|=58,| A∩C|=28 ,|A∩B|=26 ,|B∩C|=22, |A∩B ∩ C|=14，所以利用容斥原理得 A ? B ? C ? U ? ( A ? B ? C ) ? ( A ? B ? A =106;C ) ? A ? B ? C ?C ? B? （2） ? B ? C ? B ? A ? B ? B ? C ? A ? B ? C ? 94 ? 26 ? 22 ? 14 ? 60 A容斥原理的推广定理2.4.5 设A1, A2, ?, An是任意n个有限集合， 则A1 ? A 2 ??? A n ? ? Ai ? ? Ai ? A j ?i ?1 i? j n i ? j? k? A ?A ?Ai jk推论2.4.6 设U为全集，A1, A2, ?, An是任意n 个有限集合，则A1 ? A 2 ? ? ? ?A n ? S ? ? Ai ? ? Ai ? A j ?i ?1 i? j m i ? j? k? ? ? (?1)n ?1 A1 ? A 2 ??? A n 。?Ai ? A j ? A k? ? ? ? ? (?1) n A1 ? A 2 ? ? ? ? ? A n 。例2.4.3对24名科技人员进行掌握外语情况的调查， 其统计资料如下：会英、日、德、法语的人数 分别为13、5、10和9。其中同时会英语、日语 的人数为2；同时会英语和德语、同时会英语 和法语、同时会德语和法语两种语言的人数均 为4；会日语的人既不会法语也不会德语。试求(1)只会一种语言的人数各为多少？例2.4.3 解设A、B、C、D分别为会英、日、德、法语的 人的集合，由已知条件可知： |A|＝13，|B|＝5，|C|＝10，|D|＝9， |A∩B|＝2，|A∩C|＝|A∩D|＝|C∩D|＝4， |B∩C|＝|B∩D|＝0, |A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0， |A∩B∩C∩D|＝0，|A∪B∪C∪D|＝24，例2.4.3 解（续）利用容斥原理，并代入已知条件得 24＝13＋5＋10＋9－2－4－4－4－0－0 ＋0＋0＋0＋|A∩C∩D|－0。 得:|A∩C∩D|＝1，即同时会英、德、法语的只有1 人。例2.4.3 解（续）设只会英、日、德、法语的人数分别为x1,x2,x3,x4， 则 x1＝|A|－|(B∪C∪D)∩A| ＝|A|－|(B∩A)∪(C∩A)∪(D∩A)| 对B∩A、C∩A、D∩A应用容斥原理，得 |(B∩A)∪(C∩A)∪(D∩A)| ＝2＋4＋4－0－0－1＋0＝9 故，x1＝13-9＝4。 类似地可求出：x2＝3，x3＝3，x4＝2。
2.4.2 鸽笼原理鸽笼原理（Pigeonhole Principle）又称为 抽屉原理、鸽舍原理，是指如下定理。 定理2.4.7(鸽笼原理) 若有n+1只鸽子住进n个 鸽笼，则有一个鸽笼至少住进2只鸽子。 证明(反证法) 假设每个鸽笼至多住进1只鸽子， 注意： 则n个鸽笼至多住进n只鸽子，这与有n+1只鸽 （1）鸽笼原理仅提供了存在性证明； 子矛盾。故存在一个鸽笼至少住进2只鸽子。（2）使用鸽笼原理，必须能够正确识别鸽子(对象) 和鸽巢(某类要求的特征)，并且能够计算出鸽子数和 鸽巢数。例2.4.4抽屉里有3双手套，问从中至少取多少只，才能保证配成一双？答：4只。例2.4.5设1到10中任意选出六个数，那么其中有两 个数的和是11。 证明 (1)构造5个鸽笼： A1={1,10}，A2={2,9}，A3={3,8}， A4={4,7}，A5={5,6} (2)选出的6个数为鸽子. 根据鸽笼原理，所选出的6个数中一定有两 个数属于同一个集合，这两个数的和为11。定理2.4.5若有n只鸽子住进m(n&m)个鸽笼，则存在一个鸽笼至少住进? n ? 1? ? m ? ? ?? x? ? ? +1只鸽子。这里， 表示小于等于x的最大整数。例2.4.6如果一个图书馆里30本离散数学书共有12003 页，那么必然有一本离散数学书至少有401页。 证明 设页是鸽子，离散数学书是鸽笼，把每页 分配到它所出现的离散数学书中，根据定理 2.4.5，则存在一个鸽笼至少住进?(12003 ? 1) / 30? ? 1 ? 401 即结论得证。2.5 离散概率简介概率(Probability)是17世纪为分析博弈游戏而发 展起来的学科，最初计算概率仅有计数一种方 法。 本节主要介绍离散概率的基本概率、基本性质 和概率计算的简单例子。2.5.1 基本概念问题：掷出一个各面同性的骰子，求掷出偶 数的概率。其中“各面同性”是指当骰子掷 出时，各个面出现的机会均等。 定义2.5.1 假如骰子的六个面分别标记为1, 2, 3, 4, 5, 6， 能生成结果的过程称为实验(experiment)； 当掷出一个骰子时，一定能掷出6种结果中的一种， 我们称掷出骰子的过程为实验，掷出的结果(假如 实验的结果或结果的组合称为事件(event)， 掷出2)或结果的组合(假如掷出两个骰子，一个掷 包含所有可能结果的事件称为样本空间 出1，一个掷出3)称为事件，当掷出一个骰子时得 (sample space)。到的6种可能1, 2, 3, 4, 5, 6称为样本空间。例2.5.1请举例说明下列实验可能发生的事件，并列出 其样本空间。 （1）掷出一个六个面的骰子； （2）从1000个微处理器中随机抽取5个； （3）在北京人民医院选取一个婴儿。例2.5.1 解可能发生的事件举例如下： （1）掷出一个六个面的骰子，得到的点数是 4； （2）从1000个微处理器中随机抽取5个，没 有发现次品； （3）在北京人民医院选取了一个女婴。 各实验的样本空间为： （1）1, 2, 3, 4, 5, 6； （2）从1000个微处理器中选取5个的所有组
合；定义2.5.2有限样本空间S中的事件E的概率P(E)定义为： E 。? (2.5.1) P(E) S 其中|E|, |S|分别表示集合E和S的基数。例2.5.2掷出一个各面同性的骰子，求掷出偶数的概 率。 解 设掷出偶数这个事件为E，样本空间为S， 则根据题意|E| = 3, |S| = 6。代入式(2.5.1)， 得 P(E) = 3/6 = 1/2。例2.5.3掷出两个各面同性的骰子，求点数之和为10 的概率。 解 设点数之和为10这个事件为E，样本空间 为S，则根据题意|E| = 3, |S| = 36。代入式 (2.5.1)，得P(E) = 3/36 = 1/12 。例2.5.4在福利彩票中，若彩民从1～52个数中选取的6 个数与随机生成的中奖数字相同(不计顺序)， 则可以赢得大奖。求一张彩票赢得大奖的概率。 解 从52个数字中选取6个共有C(52, 6)种选法， 即|S| = C(52, 6)，而得大奖的组合只有一种， 即|E| = 1，根据式(2.5.1)，得： P(E) = 1/ C(52, 6) = 0.。2.5.2 离散概率函数定义2.5.3 如果函数P将样本空间S的每一个结 果x映射为实数P(x)，且对任意的x∈S，满足 （1）0≤P(x)≤1； （2） 。 ? P(x) ? 1 x?S 则称函数P是概率函数。说明 条件(1)保证一个结果的概率为非负数且不超过1； 条件(2)保证所有结果的概率之和为1，即进行实验 后，必出现某个结果。例2.5.5一个一面较重的骰子，2～6以相同的机会出 现，1出现的机会是其他数字的3倍。试求出 1～6的概率函数值。 解 设P(2) = P(3) = P(4) = P(5) = P(6) = a， 则P(1) = 3a。又因为P(1)+ P(2)+ P(3)+ P(4)+ P(5)+ P(6) = 1，所以有5a＋3a = 1， 即a = 1/8。从而P(2) = P(3) = P(4) = P(5) = P(6) =1/8 ，P(6) =3/8。概率函数定义2.5.4 设E是一个事件，E的概率函数P(E) 定义为 P(E) ? 。 ? P(x) 在例2.5.5中，出现奇数点的概率则为 P(1)+ P(3)+ P(5) =5/8 。 定理2.5.1 设E是一个事件，E的补的概率满 足 。 (2.5.2)x?EP(E) ? P E ? 1? ?例2.2.6 生日问题n个人中，求至少有两个人生日相同(同月同 日不计年)的概率。假定出生在某天的概率均 等，忽略2月29日。 解 设E表示“至少两个人生日相同”，则 表示“没有两个人生日相同”，则 n ? 1) 365 ? 364 ? ? ? (365 ?事实上，随着天数n的增加，至少两个人 P E ? 365n 。 生日相同的概率也随着增加，当n≥23时，365 ? 364 ? ? ? (365 ? n ? 1) P(E) ? 1 ? 。 365nE? ?从而至少有两个人生日相同的概率大于1/2。两个事件并的概率定理2.5.2 设E1和E2是两个事件，则 P(E1∪E2)=P(E1)＋P(E2)－P(E1∩E2) (2.5.3) 如果E1∩E2=Φ，即E1与E2为不相交的事件，则 有下面的推论。 推论2.5.3 设E1和E2是两个不相交的事件，则 P(E1∪E2) = P(E1)＋P(E2) (2.5.4)例2.5.7掷出两个各面同性的骰子，得到“一对”(两 个骰子点数相同)或点数和为6的概率是多少？ 解 设E1表示事件“一对”，E2表示事件 “点数和为6”，则样本空间大小是36， 事件E1的种数为6,即 (1,1),(2, 2),(3,3),(4,4),(5,5),(6,6), 事件E2的种数为5，即 (1,5),(2,4),(3,3),(4,2),(5, 1)。 E1∩E2的种数为1。例2.5.7 解（续）从而 P(E1) =1/6 , P(E2) = 5/36, P(E1∩E2) = 1/36 。 根据式(2.5.3)，有 P(E1∪E2)=1/6＋5/36－1/36=5/18 。 即得到“一对”或点数和为6的概率是5/18 。2.6 递归关系递归关系可用于解决一些特定的计数问题。 递归关系是序列中第n个元素与它相邻前若干个 元素之间的关系。 例如 递归关系 第一个数是5； 2、将前一项加3得到后一项。 5, 8, 11, 14, ? a = 5，1an = an-1+3定义2.6.1对序列a0, a1, a2, ?,an - 1, ?， 用a0,a1,a2, ?,an - 1中的某些项表示an的等式称 为递归关系(recurrence relation)。显示地给出 序列a0, a1, a2, ?的有限项的值，称为初始条件 (initial condition)。 显然，递归关系和确定的初始条件一起，才能 确定一个序列。例2.6.1某人投资1000元，每年可收益12％。An表示他 在第n年末的总资产。求出定义序列{An}的递归 关系和初始条件。 解 序列{An}的递归关系和初始条件分别为： An = An - 1＋0.12×An -1= 1.12 An -1, n≥1 , A0 = 1000例2.6.2Sn表示不含子串“111”的n位字符串的个数。 求出序列{Sn}的递归关系和初始条件。 解 序列{Sn}的递归关系和初始条件分别为： Sn = Sn-1＋Sn-2＋ Sn-3，n≥4, S1 = 2, S2 = 4, S3 = 7。2.7 计数问题的应用例2.7.1 7个科学工作者从事一项机密的技术研 究，他们的工作室装有电子锁，每位科学工作 者都有打开电子锁用的“钥匙”。为了安全起 见，必须有4位在场时才能打开大门。试问该电 子锁至少应具备多少个特征？每位科学工作者 的“钥匙”至少应有多少种特征？ 解 为了使任意3个人在场时至少缺少一个特征 而打不开门，该电子锁至少应具备C(7,3)=35种 特征；每个科学工作者的“钥匙”至少要有 C(6,3)= 20种特征。例2.7.2某一制造铁盘的工厂，由于设备和技术的原因 只能将生产盘子的重量控制在a克到（a+0.1） 克之间。现需要制成重量相差不超过0.005克的 两铁盘来配制一架天平，问该工厂至少要生产 多少铁盘才能得到一对符合要求的铁盘。例2.7.2 解将铁盘按重量分类， 所有a克到a+0.005克的分为第一类； a+0.005克到a+0.01克的分为一类； a+0.01克到a+0.015克的又为一类，?.， 最后，a+0.095克到a+0.1克为一类，共计20 类， 由鸽笼原理知，若该工厂生产21个铁盘，那 么就能得知有两个铁盘属于同一类，因而它 们之间的重量差将不超过0.005克。例2.7.3 Fibonacci数列假定一对新出生的兔子一个月又成熟，并且再 过一个月开始生出一对小兔子。按此规律，在 没有兔子死亡的情形下，一对初生的兔子，一 年可以繁殖成多少队兔子？ 解 因为Fn = Fn-1 + Fn-2，所以根据迭代法，有 F12 = F11 + F10 = 2F10 + F9 = 3F9 + 2F8 = 5F8 + 3F7 = 8F7 + 5F6 = ? = 89F2 +55F1 = 89 + 55 =143 。例2.7.4计算下面算法中基本操作的次数算法 输入：s1, s2, ? ,sn和序列的长度。 输出：s1, s2, ? ,sn，按非递减顺序排列。例2.7.4 （续）1. selection_sorts(s,n){ 2. //基本情况 3. if (n= =1) 4.return 5. //找到最大的元素 6. max_index = 1 //初始时认为s1是最大的元素 7. for i=2 to n 8. if (si&smax_index)//比较得到较大的元素，并更 新最大元素 9. max_index = i 10. //将最大的元素移至序列尾 11. swap((sn, smax_index) 12. selection_sort(s, n-1)
例2.7.4 解设计算n个数排序的比较执行次数为bn，则该算 法中的比较语句的执行次数的递归关系为： bn= bn-1 + n C 1， 其初始条件为：b1 = 0。例2.7.4 解（续）用迭代法求解该递归关系： bn=bn-1+nC1 =bn-2+nC2+n-1 =bn-3+nC3+nC2+nC1 = ? = b1 + 1 + 2 + ? +nC3 + nC2 + nC1 = 0 + 1 + 2 + ? +n C 3 + nC2 + nC1 = n(n-1)/2。2.8 本章总结1、乘法原理和加法原理的基本含义； 2、r-排列，全排列，环形r排列，环排列，r组合的基本概念，它们之间关系和相应的计 算公式； 3、容斥原理和鸽笼原理的基本概念及正确使 用； 4、实验、事件、样本空间、概率函数的基本 概念，离散概率的计算； 5、递归关系、初始条件的概念、递归关系的
建立和求解。习题类型（1）基本概念题：涉及离散概率的基本概念； （2）计算题：涉及排列数与组合数的计算，利 用容斥原理的计算，离散概率的计算和递归关 系的建立与求解； （3）证明题：涉及对鸽笼原理的应用。习题第44-45页 2. 6. 8. 11. 14. 19. 20. 21. 24. 26. 27.http://202.115.21.136:8080/lssx/离散数学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院日星期五第二篇 数理逻辑?数理逻辑（Mathematical Logic）――是研究演绎推理的一门学科，用数学 的方法来研究推理的规律统称为数理逻辑。第二篇 数理逻辑?主要研究内容：推理――着重于推理过程是否正确――着重于语句之间的关系? 主要研究方法：数学的方法――就是引进一套符号体系的方法，所以 数理逻辑又叫符号逻辑（Symbolic Logic）。总结什么是数理逻辑 ？ 用数学的方法来研究推理的规律统称为数理 逻辑。 为什么要研究数理逻辑？程序＝算法＋数据算法＝逻辑＋控制第二篇 数理逻辑主要研 究内容推理与证明技术命题逻辑命题的基本概念命题联结词命题公式 命题的范式谓词逻辑谓词的基本概念 谓词公式 公式的标准型命题逻辑推理理论 谓词逻辑推理理论 数学归纳法 按定义证明法第三章 命题逻辑命题逻辑也称命题演算，或语句逻辑。研究内容：（1）研究以命题为基本单位构成的前提 和结论之间的可推导关系 （2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？第三章 命题逻辑命题逻辑的特征： 在研究逻辑的形式时，我们把一个命 题只分析到其中所含的命题成份为止， 不再分析下去。不把一个简单命题再分 析为非命题的集合，不把谓词和量词等 非命题成份分析出来。第三章 命题逻辑1 2 3 4命题基本概念集合的表示方法 命题联结词 命题公式命题范式3.1 本章学习要求重点掌握 1 1、五种基本 联结词 2、24个基本 的等价公式 3 掌握求命题 范式的方法一般掌握了解 3 联结词完备集2公式的代入规 则和替换规则的理解和学习3.2 命题与命题联结词3.2.1 命题 定义3.2.1?具有确切真值的陈述句称为 命题, 该命题可以取一个“值”，称为真 值。 真值只有“真”和“假”两种， 分别用“Ｔ”(或“１”)和“Ｆ”(或 “０”)表示。例3.2.1（1）太阳是圆的； （2）成都是一个旅游城市； （3）北京是中国的首都； （4）这个语句是假的； （5）1＋1＝10； （6）ｘ+y&０； （7）我喜欢踢足球； （8）3能被2整除； （9）地球外的星球上也有人； （10）中国是世界上人口最多的国家；T T T 非命题 T/F 非命题 T/F F T/F T T例3.2.1（续）（12）把门关上； （13）滚出去！ （14）你要出去吗？ （15）今天天气真好啊！注意： 一切没有判断内容的句子都不能作为命题，如命令 句、感叹句、疑问句、祈使句、二义性的陈述句等。非命题 非命题 非命题 非命题约定： 在数理逻辑中像字母“x”、“y”、“z”等字母总 是表示变量。 结论：?命题一定是陈述句，但并非一切陈述句都是命题。?命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。例3.2.2下列语句是否是命题？并判断其真值结果？（1）四川不是一个国家；（2）3既是素数又是奇数；（3）张谦是大学生或是运动员；（4）如果周末天气晴朗，则我们将到郊外旅 游； （5）2+2=4当且仅当雪是白的。命题的分类一般来说，命题可分两种类型：1) 原子命题(简单命题)：不能再分解为更为简单命题的命题。2) 复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或 者”、“并且”、“不”、“如果... 则...”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。例3.2.31) 今天天气很冷。2) 今天天气很冷并且刮风。3) 今天天气很冷并且刮风，但室内暖和。通常用大写的带或不带下标的英文字母Ａ、Ｂ、 Ｃ、...P、Q、R、... Ai、Bi 、Ci、...Pi、Qi、 Ri、...等表示命题3.2.2 命题联结词设命题P,Q表示任意两个命题,则最常见的命题联结词有：联接词 记 复合命1.否定 2.合取 3.析取读法P的否定记法┐P真值结果┐P=1? P=0号┐ ∧非P题P并且Q P与Q的合取 P∧Q P∧Q=1?P=1且Q=1 P或者Q P与Q的析取 P?Q P∨Q=1?P=1或Q=1 若P,则Q?→ ?4.蕴涵5.等价P蕴涵QP→Q P→Q=0? P=1,Q=0P当且仅当Q P等价于Q P?Q P?Q=1?P=1,Q=1或P=0,Q=0例如：命题P：2是素数；Q：北京是中国的首都总结P Q ┐P 0 0 1 0 1 1 1 0 0 1 1 0 P∧Q 0 0 0 1 P∨Q 0 1 1 1 P→Q 1 1 0 1P?Q1 0 0 1说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结； 2、联结词是两个句子真值之间的联结，而非 句子的具体含义的联结，两个句子之间可以 无任何地内在联系；说明3、联结词与自然语言之间的对应并非一一对 应； 联结词 自然语言∧ →? ?既?又?、不仅?而且?、虽然?但 是?、并且、和、与，等等； 如P则Q、只要P就Q、P仅当Q、只有 Q才P、除非Q否则?P，等等 等价、当且仅当、充分必要、等等；相容（可兼）的或例3.2.4符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停 电了； （4）如果周末天气晴朗，那么学院将组织我 们到石像湖春游； （5）两个三角形全等当且仅当三角形的三条
边全部相等。例3.2.4 解（1）设Ｐ：四川是人口最多的省份。则命题（1）可表示为┐Ｐ。 （2）设Ｐ：王超是一个思想品德好的学生； Ｑ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为Ｐ∧Ｑ∧R。 （3）设Ｐ：教室的灯不亮可能是灯管坏了Ｑ：教室的灯不亮可能是停电了例3.2.4 解(续)（4）设Ｐ：周末天气晴朗；Ｑ：学院将组织我们到石像湖春游。则命题（4）可表示为Ｐ→Ｑ。 （5）设Ｐ：两个三角形全等； Ｑ：三角形的三条边全部相等。 则命题（5）可表示为Ｐ?Ｑ。约 定为了不使句子产生混淆，作如下约定，命题 联结词之优先级如下：1. 否定→合取→析取→蕴涵→等价 2. 同级的联结词，按其出现的先后次序(从左 到右) 3. 若运算要求与优先次序不一致时，可使用 括号；同级符号相邻时，也可使用括号。 括号中的运算为最优先级。例3.2.5设命题 P：明天上午七点下雨； Q：明天上午七点下雪；可符号化为： R：我将去学校。(P∧Q∧R)∨(┐P∧Q∧R)∨ 符号化下述语句：(P∧┐Q∧R)∨(┐P∧┐Q∧R)。 1) 如果明天上午七点不是雨夹雪，则我将去 或 可符号化为：┐(P∧Q)→R。 可符号化为:(P∨Q)→┐R。 学校((P∧Q)∨(┐P∧Q)∨(P∧┐Q) ∨(┐P∧┐Q))∧R。 2) 如果明天上午七点不下雨并且不下雪，则 可符号化为:(┐P∧┐Q)→R。 我将去学校3) 如果明天上午七点下雨或下雪，则我将不例3.2.6设命题P：你陪伴我； Q：你代我叫车子； R：我将出去。R→(P∨Q) 或 (P∧Q)→R ┐(P∨Q)→┐R (┐P∨┐Q)→┐R符号化下述语句：⑴．除非你陪伴我或代我叫车子，否则我将不 出去 ⑵．如果你陪伴我并且代我叫辆车子，则我将 出去例设P:雪是白色的;Q:2+2=4。将下列命题符号 化： （1）因为雪是白色的，所以2+2=4； P→Q （2）如果2+2=4，则雪是白色的； Q→P （3）只有雪是白色的，才有2+2=4； Q→P （4）只有2+2=4，雪才是白色的； P→Q （5）只要雪不是白色的，就有2+2=4； ? P→Q3.2.4 命题联结词的应用例 3.2.7 用复合命题表示如下图所示的开 关电路：P Q P Q P图3.2.1图3.2.2图3.2.3设：?Ａ：开关Ｐ闭合；Ｂ：开关Ｑ闭合。A∧BA∨BA例 3.2.8用复合命题表示如下图所示的逻辑电路： ? P ? P?Q Q ? ? ? P P?Q Q ? ?P P图3.2.4 图3.2.5 图3.2.6解:设P：输入端Ｐ为高电位,Q：输入端Ｑ为高电位,则 “与门”对应于P∧Q； “或门”对应于P∨Q； “非门”对应于P。3.3 命题公式、解释与真值表定义3.3.1 一个特定的命题是一个常值命题， 它不是具有值“T”(“1”)，就是具有值 “F”(“0”)。而一个任意的没有赋予具体内容的原子命题是 真值函数 一个变量命题，常称它为命题变量(或命题变 元)，该命题变量无具体的真值，它的变域是 集合{T，F}(或{0，1})注意(1)复合命题为命题变元的“函数”,其函数值3.3.1?命题公式定义3.3.2 (命题公式)1. 命题变元本身是一个公式； 2. 如G是公式，则(┐G)也是公式； 3. 如G，H是公式，则(G∧H)、(G∨H)、(G→H)、(G?H)也是公式；4. 仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、?等表示。例3.3.1符号串：((P∧(Q∨R))→(Q∧(┐S∨R))))；? (┐P∧Q)； (P→(┐(P∧Q)))；? (((P→Q)∧(R→Q))?(P→R))。 等都是命题公式。 例3.3.2?符号串： (P→Q)∧┐Q)； (P→Q；(┐P∨Q∨(R；P∨Q∨。等都不是合法的命题公式。例3.3.3试用符号形式写出下列命题：（1）虽然今天天气晴朗，老陈还是不来；（2）除非你陪伴我或代我叫车子，否则我将不 出去； （3）停机的原因在于语法错误或者程序错误；（4）若a和b是偶数，则a+b是偶数；（5）我们要做到身体好、学习好、工作好，为 祖国四化建设而奋斗。例3.3.3 解（1）P：今天天气晴朗,Q：老陈要来,则有： P∧Q； （2）P：你陪伴我； Q：你代我叫车子；R： 我出去。则有：R→P∨Q或P∧Q→R； （3）P：停机的原因在于语法错误，Q：停机 的原因在于程序错误，则有：P ∨ Q； （4）P：a是偶数；Q：b是偶数，R：a+b是偶 数，则有：P∧Q→R； ? （5）P：我们要做到身体好,Q：我们要做到学例3.3.4公式(P∧(Q∨R))→(Q∧(┐S∨R))可表示如下：(P∧(Q∨R))→(Q∧(┐S∨R))P∧(Q∨R)???P Q∨R QQ∧(┐S∨R)?Q? ┐S∨R ┐S S RR?3.3.2 公式的解释与真值表定义3.3.3 设P1、P2、?、Pn是出现在公式G 中的所有命题变元，指定P1、P2、?、Pn一 组真值，则这组真值称为G的一个解释,常记 为Ｉ。 一般来说，若有ｎ个命题变元，则应有2n 个不同的解释。 如果公式G在解释Ｉ下是真的，则称Ｉ满足 G；如果G在解释Ｉ下是假的，则称Ｉ弄假G。定义3.3.4 将公式G在其所有可能解释下的真例3.3.5求下面公式的真值表： Ｇ＝(P→((?P?Q)∧R))∨Q 其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命题变元。P Q R ? P ?P?Q ((?P?Q)∧ P→((?P?Q)∧ R R) G0 0 0 0 0 1 0 1 1 0 1 0
1 10 1 0 1 0 1 01 1 1 1 0 0 00 0 1 1 1 1 00 0 0 1 0 1 01 1 1 1 0 1 01 1 1 1 0 1 1例3.3.5（续）进一步化简为： P Q R0 0 0 0 1 1 1 10 0 1 1 0 0 1 10 1 0 1 0 1 0 1(P→((?P?Q)∧R))∨ Q 1 1 1 1 0 1 1 1例3.3.6求下面这组公式的真值表： Ｇ1＝ ?(Ｐ→Ｑ)→Ｐ； Ｇ2＝(Ｐ→Ｑ)∧Ｐ； Ｇ3＝ ?(Ｐ∧?Ｑ)? ?(Ｐ→Q)。 P Q ?(Ｐ→Ｑ)→ Ｐ 0 0 1 0 1 1 1 0 1 1 1 1(Ｐ→Ｑ)∧Ｐ ?(Ｐ∧?Ｑ)? ?(Ｐ →Q) 0 0 0 0 0 0 1 0结论从这三个真值表可以看到一个非常有趣的 事实：? 公式G1对所有可能的解释具有“真”值 ? 公式G3对所有可能的解释均具有“假”值 ? 公式G2则具有“真”和“假”值定义3.3.51. 公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。2. 公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。3. 公式G称为可满足的，如果它不是永假的。结论从上述定义可知三种特殊公式之间的关系：1) 永真式G的否定?G是矛盾式；矛盾式G的否定?G是 永真式。2) 永真式一定是可满足式,可满足式不一定是永真式 3) 可满足式的否定不一定为不可满足式(即为矛盾式)例3.3.7写出下列公式的真值表，并验证其公式是重 言式、矛盾式、可满足公式。 （1）G1=(Ｐ→Ｑ)?(?Ｐ∨Ｑ)； （2）G2=(Ｐ?Q)?(?(Ｐ→Q)∨?(Q→Ｐ))； （3）G3=(P→?Q)∨?Q。例3.3.7 解三个公式的真值表如下：P Q (Ｐ→Ｑ) ?(?Ｐ∨ (Ｐ? Q)? ?(Ｐ Ｑ) →Q)∨?(Q→Ｐ) (P→?Q)∨? Q0 0 1 10 1 0 11 1 1 1永真公式0 0 0 01 1 1 0可满足公式永假公式分析公式（1）若将其看成两个公式，分别令：Ｇ＝Ｐ→Ｑ， Ｈ＝┐Ｐ∨Ｑ。则Ｇ?Ｈ是一个永真公式，即这两个公式对 任何解释都必同为真假，此时，说Ｇ和Ｈ相 等，记为Ｇ＝Ｈ。为此可定义： 定义3.3.6 设G、H是公式，如果在任意解释Ｉ下，G与H的真值相同，则称公式G、H是等价的， 记作G＝H。定理3.3.1公式G、H等价的充分必要条件是公式G?H是 永真公式 证明:“?”假定G，H等价，则G，H在其任意 解释Ｉ下或同为真或同为假，于是由“?”的 意义知，G?H在其任何的解释Ｉ下，其真值 为“真”，即G?H为永真公式。 “?”假定公式G?H是永真公式，Ｉ是它的 任意解释，在Ｉ下，G?H为真，因此，G、H 或同为真，或同为假，由于Ｉ的任意性，故有
“＝” 与“?”的区别首先，双条件词“?”是一种逻辑联结词， 公式G?H是命题公式，其中“?”是一种逻 辑运算，G?H的结果仍是一个命题公式。而 逻辑等价“＝”则是描述了两个公式G与H之间的一种逻辑等价关系，G＝H表示“命题公式G等价于命题公式H”，G＝H 的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即G＝H那是办不到的，然而D=‖的性质由于“=”不是一个联结词，而是一种关系， 为此，这种关系具有如下三个性质： （1）自反性 G=G；（2）对称性 若G=H，则H=G；（3）传递性 若G=H，H=S，则G=S。这三条性质体现了“=”的实质含义。3.3.4 命题公式的基本等价 关系例3.3.8 证明公式G1＝(Ｐ?Ｑ)与公式G2＝ (P→Q)∧(Q→P)之间是逻辑等价的。 解：根据定理3.3.1，只需判定公式G3＝(Ｐ ?Ｑ) ?((P→Q)∧(Q→P))为永真公式。P Q G3＝(Ｐ?Ｑ) ?((Ｐ→Q)∧(Q→ Ｐ)) 1 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 10 0 1
10 1 0 1基本等价公式设G，H，S是任何的公式，则：1) Ｅ1：G∨G＝GＥ2：G∧G＝G 2) Ｅ3：G∨H＝H∨G Ｅ4：G∧H＝H∧G 3) Ｅ5：G∨(H∨S)＝(G∨H)∨S (结合律) (吸收律) (交换律)(幂等律)Ｅ6: G∧(H∧S)＝(G∧H)∧S 4) Ｅ7：G∨(G∧H)＝ G Ｅ8：G∧(G∨H)＝ G基本等价公式（续）5) Ｅ9：G∨(H∧S)＝(G∨H)∧(G∨S) 配律） Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S) (分6) Ｅ11：G∨０＝GＥ12：G∧１＝G(同一律) (零律） (排中律)7) Ｅ13：G∨１＝１Ｅ14：G∧０＝０8) Ｅ15：G∨┐G＝1基本等价公式（续）10) Ｅ17：┐(┐G)＝G Ｅ19：┐(G∧H)＝┐G∨┐H。 (双重否定律)11) Ｅ18：┐(G∨H)＝┐G∧┐H (De MoRGan定律) 12) Ｅ20: (G?H)＝(G→H)∧(H→G)13) Ｅ21：(G→H)＝(┐G∨H) 14) E22：G →Ｈ＝?Ｈ→?G。 15) E23：G ?Ｈ＝?G??Ｈ。 16) E24：(G →Ｈ) ∧(G→?Ｈ)＝?G(等价)(假言易位)(蕴涵) (等价否定等式) (归谬论)命题与集合之间的关系这种图是将G，H理解为某总体论域上的子 集合，而规定G∧H为两集合的公共部分 （交集合），G∨H为两集合的全部（并集 合），┐G为总体论域（如矩形域）中G的补 集，将命题中的真值“1”理解为集合中的 总体论域（全集），将命题中的真值“0” U U U 理解为集合中的空集，则有： A A B A BG∧HG∨H┐GD∪‖ 对“∨”与“∩”对“∧”的对 比等幂律 Ａ∪Ａ＝Ａ;Ａ∩Ａ＝Ａ 交换律 Ａ∪Ｂ=Ｂ∪Ａ Ａ∩Ｂ=Ｂ∩Ａ 结合律 A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C G∨G＝G G∧G＝G G∨H＝H∨G G∧H＝H∧G G∨(H∨S)=(G∨H)∨S G∧(H∧S)=(G∧H)∧S恒等律 Ａ∪Φ＝Ａ；Ａ∩Ｕ＝Ａ； G∨０＝G G∧１＝G 零 律 Ａ∪Ｕ＝Ｕ；Ａ∩Φ＝Φ G∨１＝１ G∧０＝０A?A 吸收律 A∩(A∪B)=AA∪(A∩B)=A 否定律G∨(G∧H)=G G∧(G∨H)=G ┐(┐G)＝G分配律 A∩(B∪C)=(A∩B)∪(A∩ G∨(H∧S)=(G∨H)∧(G定理3.3.2(代入定理)设G(P1,P2,?,Pn)是一个命题公式，其中： P1、P2、?、Pn是命题变元， G1(P1,P2,?,Pn)、G2(P1,P2,?,Pn)、...、 Gn(P1,P2,?,Pn)为任意的命题公式，分别用 G1、G2?、Gn取代G中的P1、P2、?、Pn 后得到新的命题公式： G(G1,G2,?,Gn)＝G′(P1,P2,?,Pn)例3.3.9设Ｇ(Ｐ, Ｑ)＝(Ｐ∧(Ｐ→Ｑ))→Ｑ，证明 公式G是一个永真公式。另有两个任意公 式： Ｈ(Ｐ, Ｑ)＝(Ｐ∨?Ｑ)；P Q (Ｐ∧(Ｐ→Ｑ))→Ｑ 解 建立公式 进一步验证代入定理的正确性。 1 0 0 G的真值表如 0 1 1 右所示。可见 1 0 1 为永真公式。 1 1 1 Ｓ(Ｐ, Ｑ)＝(Ｐ?Ｑ)。例3.3.9（续）将Ｈ，Ｓ代入到Ｇ中分别取代G中的命题变元 P、Q，所得到的公式Ｇ＇为： Ｇ＇(P, Q) = G(H, S) = (H∧(H→S))→S = ((Ｐ∨?Ｑ)∧((Ｐ∨?Ｑ)→(Ｐ?Ｑ)))→(Ｐ? Ｑ)((Ｐ∨?Ｑ)∧((Ｐ∨?Ｑ)→(Ｐ?Ｑ)))→(Ｐ 建立新公式Ｇ＇(P, Q)的真值表。 ?Ｑ) 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1
0 P Q定理3.3.3(替换定理)设G1是G的子公式(即 G1是公式G的一部分) ，H1是任意的命题公式，在G中凡出现G1处 都以H1替换后得到新的命题公式H，若G1＝ H1，则G＝H。利用24个基本等价公式及代入定理和替换定 理，可完成公式的转化和等价判定。例3.3.10利用基本的等价关系，完成如下工作：（1）判断公式的类型：证明 ((Ｐ∨Ｑ)∧? (?Ｐ∧(?Ｑ∨?Ｒ)))∨(? Ｐ∧?Ｑ)∨(?Ｐ∧?Ｒ)是一个永真公式。 （2）证明公式之间的等价关系：证明Ｐ→(Ｑ→Ｒ) = (Ｐ∧Ｑ)→Ｒ（3）化简公式：证明(?P∧(?Ｑ∧R))∨((Ｑ∧R)∨(P∧R)) = R例3.3.10 证明（1）((Ｐ∨Ｑ)∧? (?Ｐ∧(?Ｑ∨?Ｒ)))∨(?Ｐ∧?Ｑ)∨(?Ｐ ∧?Ｒ) = ((Ｐ∨Ｑ)∧(Ｐ∨(Ｑ∧Ｒ)))∨?((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)) = ((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)))∨? ((Ｐ∨Ｑ)∧(Ｐ∨ Ｒ)) = ((Ｐ∨Ｑ)∧(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨ ?( (Ｐ∨Ｑ)∧(Ｐ∨ Ｒ)) = ((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨?((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)) = T即:((Ｐ∨Ｑ)∧? (?Ｐ∧(?Ｑ∨?Ｒ)))∨(?Ｐ∧?Ｑ)∨(?Ｐ ∧?Ｒ)为永真公式；
例3.3.10 证明（续）（2） P→(Q→R)=?P∨(Q→R)=?P∨(?Q∨R)=(?P∨?Q)∨R=?(P∧Q)∨R=(P∧Q)→R即有: P→(Q→R)=(P∧Q)→R；（3） (?P∧(?Q∧R))∨((Q∧R)∨(P∧R)) = (?P∧?Q)∧R)∨((Q∨P)∧R)= (?(P∨Q)∧R)∨((Q∨P)∧R)= (?(P∨Q)∨(Q∨P))∧R= T∧R = R3.3.6 命题公式的应用例3.3.11 利用基本的等价关系，化简下列电 P 路图 & QPQ R P R R P Q S P S S T & ≥1 ≥1 &解：上述电路图可描述为： （1）((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S)) （2）((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)例3.3.11（续）利用24个基本等价关系，化简公式(1)、(2)可 得： （1） ((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S)) = ((P∧Q∧(R∨S))∧(P∧(R∨S)) = P∧Q∧(R∨S)； （2）((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T) R P = (P∨Q∨S)∧(P∧S∧T) = P∧S∧T 。 & Q P QS S例3.3.12将下面程序语言进行化简。If A then if B then X else Y else if B then X else YStart T FAB T F F B T解：执行X的条件为： (Ａ∧Ｂ)∨(?Ａ∧Ｂ) 执行Y的条件为： (Ａ∧?Ｂ)∨(?Ａ∧?Ｂ)XYEnd例3.3.12(续）执行X的条件可化简为： (Ａ∧Ｂ)∨(?Ａ∧Ｂ) ＝Ｂ∧(Ａ∨ ?Ａ)＝Ｂ 执行Y的条件可化简为： (Ａ∧?Ｂ)∨(?Ａ∧?Ｂ)End X T A Y StartF＝ ?Ｂ∧(Ａ∨?Ａ)＝?Ｂ 程序可简化为：If B then X else Y例3.3.13有一逻辑学家误入某部落，被拘于劳狱，酋 长意欲放行，他对逻辑学家说： “今有两门，一为自由，一为死亡，你可任 意开启一门。为协助你脱逃，今加派两名战 士负责解答你所提的任何问题。惟可虑者， 此两战士中一名天性诚实，一名说谎成性， 今后生死由你自己选择。” 逻辑学家沉思片刻，即向一战士发问，然 后开门从容离去。该逻辑学家应如何发问？例3.3.13 解P:被问战士是诚实人； Q:被问战士的回答是“是” R:另一名战士的回答是 “是” 逻辑能够从容离去吗？ S:这扇门是死亡门。P 0 0 1 1 Q 0 1 0 1 R 1 0 0 1 S 1 0 1 0逻辑学家手指一门问身旁的一名战士说:“这扇门是 死亡门，他(指另一名战士)将回答‘是’,对吗？”当被问战士回答“对”,则逻辑学家开启所指的门从容离去当被问的战士回答“否”,则逻辑学家开启另一扇门从容离 去。例3.3.14一家航空公司，为了保证安全，用计算机复核 飞行计划。每台计算机能给出飞行计划正确或 有误的回答。由于计算机也有可能发生故障， 因此采用三台计算机同时复核。由所给答案， 再根据“少数服从多数”的原则作出判断，试 将结果用命题公式表示，并加以简化，画出电 路图。例3.3.14 解设C1，C2，C3分别表 示三台计算机的答案。 S表示判断结果。则根据真值表，利用联结 词的定义，S可用C1，C2， C3所对应的命题公式表示 出来，同时可画出该命题 公式所对应的电路图。 真值表C1 C2 C3 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1S 0 0 0 1 0 1 1 1例3.3.14 解（续）S= (?C1∧C2∧C3)∨(C1∧?C2∧C3)∨(C1∧C2∧?C3)∨(C1∧C2∧C3)=((C1∨?C1)∧C2∧C3)∨(C1∧(C2∨?C2)∧C3)∨(C1∧C2∧(C3∨?C3)) =(C2∧C3)∨(C1∧C3)∨(C1∧C2) C1&≥1 C2 & ≥1 SC3&3.5 公式的标准型――范式3.5.1 析取范式和合取范式定义3.5.1 （1）命题变元或命题变元的否定称为文字 （2）有限个文字的析取称为析取式(也称为 子句） （3）有限个文字的合取称为合取式(也称为 短语）（4）P与? P称为互补对。例子（1）Ｐ、?Ｐ是文字；（2）Ｐ∨Ｑ∨Ｒ是子句；（3）Ｐ∧Ｑ∧Ｒ是短语。┐P是一个子句，这种说法正确么？一个命题变元或者其否定既可以是简单 的子句，也可以是简单的短语。 因此，Ｐ，?Ｐ不但是文字，也是子句、短语定义3.5.2（1）有限个短语的析取式称为析取范式 （2）有限个子句的合取式称为合取范式一个不含最外层括号的短语（子句）也 可以是析取范式（合取范式）。例子（1）Ｐ、?Ｐ是析取范式、合取范式； （2）Ｐ∨Ｑ∨?Ｒ是子句、析取范式、合取范 式， (Ｐ∨Ｑ∨ ?Ｒ)仅是子句、合取范式；（3） ?Ｐ∧Ｑ∧Ｒ是短语、析取范式、合取 范式， (Ｐ∧Ｑ∧Ｒ)仅是短语、析取范式；（4）(Ｐ∧Ｑ)∨(?Ｐ∧Ｑ)是析取范式；总结（1）单个的文字是子句、短语、析取范式，合 取范式 （2）单个的子句是析取范式；（3）单个的短语是合取范式；（4）若单个的子句（短语）无最外层括号，则 是合取范式（析取范式）；（5）析取范式、合取范式仅含联结词集{?，∧， ∨}范式的求解方法定理3.5.1 对于任意命题公式，都存在与其 等价的析取范式和合取范式。 转换方法：（1）利用等价公式中的等价式和蕴涵式将公式中 的→、?用联结词? 、∧、∨来取代，这可利用 如下等价关系： (Ｇ→Ｈ) = (?Ｇ∨Ｈ)； (Ｇ?Ｈ) = (Ｇ→Ｈ)∧(Ｈ→Ｇ) = (?Ｇ∨Ｈ)∧(?Ｈ∨Ｇ)。范式的求解方法(续)（2）重复使用德?摩根定律将否定号移到各 个命题变元的前端，并消去多余的否定号， 这可利用如下等价关系：?(?Ｇ) =Ｇ；?(Ｇ∨Ｈ) = ?Ｇ∧ ?Ｈ；（3）重复利用分配律，可将公式化成一些合取式的 析取，或化成一些析取式的合取，这可利用如下等 价关系：Ｇ∨(Ｈ∧Ｓ) = (Ｇ∨Ｈ)∧(Ｇ∨Ｓ)； Ｇ∧(Ｈ∨Ｓ) = (Ｇ∧Ｈ)∨(Ｇ∧Ｓ)。?(Ｇ∧Ｈ) = ?Ｇ∨ ?Ｈ。例3.5.1求公式：(Ｐ→?Ｑ)∨(Ｐ?R)的析取范式和合取 范式 解 (Ｐ→?Ｑ)∨(Ｐ?R)= (?Ｐ∨?Ｑ)∨((?Ｐ∨R)∧(?R∨P))= (?Ｐ∨?Ｑ)∨(?Ｐ∨R)) ∧((?Ｐ∨?Ｑ)∨(? R∨P))= (?Ｐ∨?Ｑ∨?Ｐ∨R)∧(?Ｐ∨?Ｑ∨? R∨P）= (?Ｐ∨?Ｑ∨R)――合取范式 = ?Ｐ∨?Ｑ∨R――析取范式范式的不惟一性考虑公式： (Ｐ∨Ｑ)∧(Ｐ∨Ｒ)， 其与之等价的析取范式： Ｐ∨(Ｑ∧Ｒ)； (Ｐ∧Ｐ)∨(Ｑ∧Ｒ)； Ｐ∨(Ｑ∧?Ｑ)∨(Ｑ∧Ｒ)； Ｐ∨(Ｐ∧Ｒ)∨(Ｑ∧Ｒ)。这种不惟一的表达形式给研究问题带来了不3.5.2 主析取范式和主合取范式1 极小项和极大项定义 3.5.3 在含有n个命题变元P1、P2、P3、?、 Pn的短语或子句中，若每个命题变元与其否定不同时 存在，但二者之一恰好出现一次且仅一次，则称此 短语或子句为关于P1、P2、P3、?、Pn的一个极小项 或极大项。对于n个命题变元，可构成2n个极小项和2n个极大项例子（1）一个命题变元P， 对应的极小项有两项：P、? P； 对应的极大项有两项：P、? P。 （2）两个命题变元P、Q， 对应的极小项有四项： P∧Q、? P∧Q、P∧? Q、? P∧? Q； 对应的极大项有四项：P∨Q、? P∨Q、P∨? Q、? P∨? Q。例子（续）（3）三个命题变元P、Q、R， 对应的极小项有八项： ?Ｐ∧?Ｑ∧?Ｒ、?Ｐ∧?Ｑ∧Ｒ ?Ｐ∧Ｑ∧?Ｒ、?Ｐ∧Ｑ∧Ｒ、Ｐ∧?Ｑ ∧?Ｒ Ｐ∧?Ｑ∧Ｒ、Ｐ∧Ｑ∧?Ｒ、Ｐ∧Ｑ∧Ｒ； 对应的极大项有八项： ?Ｐ∨?Ｑ∨?Ｒ、?Ｐ∨?Ｑ∨Ｒ两个命题变元的所对应极小项真 值表P 0 0 1 1 Q ┐P∧┐Q 0 1 1 0 0 0 1 0 ┐P∧Q P∧┐Q P∧Q 0 0 0 1 0 0 0 1 0 0 0 1注意：（1）没有等价的两个极小项； m00(m0) ?Ｐ∧?Ｑ→{0、0}为真→ {0 0} →（2）使该极小项的真值为真的指派是唯一的； ?Ｐ∧Ｑ→{0 1}为真→{0 1} → m01(m1)（3）使极小项为真的那组指派为对应极小项的编码； Ｐ∧ ?Ｑ→{1 0}为真→{1 0} → m10(m2)（4）命题变元与1对应，命题变元的否定与0对应。 Ｐ∧Ｑ→{1 1}为真→{1 1} → m11(m3)两个命题变元的所对应极大项 真值表P 0 0 1 1 Q ┐P∨┐Q 0 1 1 1 0 1 1 0注意：（1）没有等价的两个极大项；(M ) Ｐ∨Ｑ→{0、0}为假→ {0 0} → M00 0 （2）使该极大项的真值为假的指派是唯一的； Ｐ∨?Ｑ→{0 1}为假→{0 1} → M (M )01 1┐P∨Q P∨┐Q P∨Q 1 1 0 1 0 1 0 1 1 1 1 1（3）使极大项为假的那组指派为对应极大项的编码； ?Ｐ∨Ｑ→{1 0}为假→{1 0} → M10(M2) （4）命题变元与0对应，命题变元的否定与1对应。 ?Ｐ∨?Ｑ→{1 1}为假→{1 1} → M (M )11 3三个命题变元的极小项和极大项P Q 0 0 R 极小项 0 m0=┐P∧┐Q∧┐ R 1 m1=┐P∧┐Q∧R 0 m2=┐P∧Q∧┐R 1 m3=┐P∧Q∧R 0 m4=P∧┐Q∧┐R 1 m5=P∧┐Q∧R 0 m6=P∧Q∧┐R 1 极大项 M0=P∨Q∨R0 0 0 1 0 1 1 0 1 0 1 1
1 1M1=P∨Q∨┐R M2=P∨┐Q∨R M3=P∨┐Q∨┐R M4=┐P∨Q∨R M5=┐P∨Q∨┐R M6=┐P∨┐Q∨R极小项和极大项的性质m 任意两个极小项的合取必为假； i∧mj=F M 任意两个极大项的析取必为真； i∨Mj=T ┐Mi= mi 极大项的否定是极小项； Mi=┐mi 极小项的否定是极大项；所有极小项的析取为永真公式；所有极大项的合取是永假公式。2 n ?1 i ?0? mi ? 1；2n ?1 i?0? M i ? 0。2 主析取范式和主合取范式定义3.5.4（1）在给定的析取范式中，每一个短语都是 极小项，则称该范式为主析取范式 （2）在给定的合取范式中，每一个子句都是 极大项，则称该范式为主合取范式 （3）如果一个主析取范式不包含任何极小项， 则称该主析取范式为“空”；如果一个主合 取范式不包含任何极大项，则称主合取范式
为“空”。定理3.5.2任何一个公式都有与之等价的主析取范式和 主合取范式。证明（1）利用定理3.5.1先求出该公式所对应的析取 范式和合取范式； （2）在析取范式的短语和合取范式的子句中重复出 现的命题变元，将其化成只出现一次； （3）去掉析取范式中的所有永假式（ P∧┐P ）， 去掉合取范式中所有永真式（ P∨┐P ）定理3.5.2 证明（续）（4）若析取范式的某一个短语中缺少该命题 公式中所规定的命题变元，则可用公式：(Ｐ ∨Ｐ)∧Q = Q将命题变元P补进去，并利用分 配律展开，然后合并相同的短语，此时得到 的短语将是标准的极小项 若合取范式的某一个子句中缺少该命题公式 中所规定的命题变元，则可用公式：(Ｐ∧ Ｐ)∨Q = Q将命题变元P补进去，并利用分配律展开，然证明（续）（5）利用等幂律将相同的极小项和极大项合 并，同时利用交换律进行顺序调整，由此可转 换成标准的主析取范式和主合取范式。3 求主析取范式和主合取范式的 方法主范式公式转换法利用基本等价公 式进行变换（证 明见定理3.5.2)真值表技术对公式的真值结 果进行分解，分 解成等价的极小 项的析取或者极 大项的合取例3.5.2利用等价公式转换法求公式(P→Q)→(Q∧R) 的主析取范式和主合取范式 。解 （1）求主析取范式(P→Q)→(Q∧R)= ?(?P∨Q)∨(Q∧R)=(P∧?Q)∨(Q∧R) ――析取范式= (P∧?Q∧(R∨?R))∨((P∨?P)∧Q∧R)= (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R) ∨(?P∧Q∧R) ――主析取范式例3.5.2（续）（2）求主合取范式 (P→Q)→(Q∧R)= (P∧?Q)∨(Q∧R) =(P∨Q)∧(P∨R)∧(?Q∨Q)∧(?Q∨R) = (P∨Q)∧(P∨R)∧(?Q∨R)――合取范式例3.5.2（续）=(P∨Q∨(R∧?R))∧(P∨(Q∧?Q)∨R)∧ ((P∧?P)∨?Q∨R) = (P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ∧(P∨?Q∨R)∧((P∨?Q∨R) ∧(?P∨?Q∨R)= (P∨Q∨R)∧(P∨Q∨?R)∧(P∨?Q∨R)∧(?P∨?Q∨R) ――主合取 范式需要说明求任何一个公式的主析取范式和主 合取范式不仅要取决于该公式，而 且取决于该公式所包含的命题变元。如公式： G1 = (P→Q)∧Q， G2(P, Q, R) = (P→Q)∧Q。 前者是依赖于两个命题变元的，后者应依赖于三个 命题变元。如何用极小项来构成主析取范式？P Q m0 0 0 1 m1 0 m2 m3 P&Q 0 0 1备注m0必须包含在 主析取范式中m1必须包含在 主析取范式中必须且只能包含使得公式 主析取范式中 0 1真值为真的那些解释对应的极小项。 0 1 0 0 1 m2一定不能包含 在主析取范式中1 01 1000010001m3必须包含在 主析取范式中1如何用极大项来构成主合取范式？P Q M0 M1 0 0 0 1 M2 M3 P? Q 1 1 1备注M0一定不能包含 在主合取范式中M1必须包含在 主合取范式中必须且只能包含使得公式 主合取范式中 0 1 真值为假的那些解释对应的极大项。 1 0 1 1 0 M2必须包含在 主合取范式中1 011010M3一定不能包含 在主合取范式中1 111101真值表技术（1）列出公式对应的真值表，选出公式的真 值结果为真的所有的行，在这样的每一行中， 找到其每一个解释所对应的极小项，将这些 极小项进行析取即可得到相应的主析取范式。（2）列出公式对应的真值表，选出公式的真值结 果为假的所有的行，在这样的每一行中，找到其 每一个解释所对应的极大项，将这些极大项进行 合取即可得到相应的主合取范式。例3.5.4利用真值表技术求公式G = ┐(Ｐ→Ｑ)∨Ｒ的 主析取范式和主合取范式。 P Q R P→Q ┐（P→Q） ┐(P→Q)∨R 000 1 0 0 001 1 0 1 010 1 0 0 011 1 0 1 100 0 1 1 101 0 1 1 110 1 0 0
1 1 1 1 0 1例3.5.4（续）（1）求主析取范式找出真值表中其真值为真的行：2. 0 0 1； 4. 0 1 1；5. 1 0 0； 6. 1 0 1；8. 1 1 1。 这些行所对应的极小项分别为： ┐P∧┐Ｑ∧Ｒ， ┐P∧Ｑ∧Ｒ，P∧┐Ｑ∧┐ Ｒ，例3.5.4（续）将这些极小项进行析取即为该公式G的主析取 范式。 G = ┐(Ｐ→Ｑ)∨Ｒ= (┐P∧┐Ｑ∧Ｒ)∨(┐P∧Ｑ∧Ｒ)∨(P∧┐Ｑ∧┐Ｒ)∨(P∧┐Ｑ∧Ｒ)∨(P∧Ｑ∧Ｒ)例3.5.4（续）（2）求主合取范式 找出真值表中其真值为假的行： 1．0 0 0； 3．0 1 0； 7．1 1 0。 这些行所对应的极大项分别为： P∨Ｑ∨Ｒ、P∨ ┐Ｑ∨Ｒ、 ┐Ｐ∨ ┐Ｑ∨Ｒ 将这些极大项进行合取即为该公式G的主合取范 式：G = (Ｐ→Ｑ)∨Ｒ（1）已知公式G的主析取范式，求公式G的主 （a）求?G的主析取范式，即G的主析取范式中没有 合取范式出现过的极小项的析取，若G ?4 主析取范式和主合取范式之间 的转换?mi ?1kli为Ｇ的主析取范式，则? G ? ? m jii ?1 2n ?k为?Ｇ的主析取范式。其中，mji(i=1,2,…,2n-k)是 mi(i=0,１,２,…,2n-1)中去掉mli(i=１,２,…,k) 后剩下的极小项。主析取范式?主合取范式（b）G=?(?G)即是G的主合取范式。即，2n ? k 2n ? k 2n ? k G ? ??G ? ?( ? m ) ? ? ?m ? ? M j j j i ?1 i ?1 i ?1 i i i──为G 的主合取范式。主合取范式?主析取范式（1）已知公式G的主合取范式，求公式G的主 （a）求?G的主合取范式，即G的主合取范式中没有 析取范式出现过的极大项的合取，若 G ? ?Mk i ?1 li为Ｇ的主合取范式，则?G ? 2n?i ?1?kM li为?Ｇ的主合取范式。其中，Mji(i=1,2,…,2n-k)是 Mi(i=0,１,２,…,2n-1)中去掉Mli(i=１,２,…,k)后 剩下的极大项。主合取范式?主析取范式（2）已知公式G的主合取范式，求公式G的主析 取范式 （a）求?G的主合取范式，即G的主合取范式 k G ? ? Ml 中没有出现过的极大项的合取，若 i ?1i? M 为Ｇ的主合取范式，则?G ?i ?12n?kli为?Ｇ的主合取范式。nn主合取范式?主析取范式（b）G=?(?G)即是G的主析取范式。即，G ? ??G ? ?( 2n?Mi ?1?kji)?(2n? ?Mi ?1?kji)?(2 ?ki ?1n?mji)──为G 的主析取范式。例3.5.5设Ｇ=(Ｐ∧Ｑ)∨(?Ｐ∧Ｒ)∨(?Ｑ∧?Ｒ)，求 其对应的主析取范式和主合取范式。 解 Ｇ= (Ｐ∧Ｑ)∨(?Ｐ∧Ｒ)∨(?Ｑ∧ ?Ｒ)=(Ｐ∧Ｑ∧(Ｒ∨?Ｒ))∨(?Ｐ∧(Ｑ∨?Ｑ)∧Ｒ) ∨((Ｐ∨?Ｐ)∧?Ｑ∧?Ｒ) = (Ｐ∧Ｑ∧Ｒ)∨(Ｐ∧Ｑ∧?Ｒ)∨(?Ｐ∧Ｑ∧Ｒ) ∨(?Ｐ∧?Ｑ∧Ｒ)∨(Ｐ∧?Ｑ∧?Ｒ)∨(?Ｐ∧?Ｑ∧?Ｒ) = (?Ｐ∧?Ｑ∧?Ｒ)∨(?Ｐ∧?Ｑ∧Ｒ)∨(?Ｐ∧Ｑ∧Ｒ) ∨(Ｐ∧?Ｑ∧?Ｒ)∨(Ｐ∧Ｑ∧?Ｒ)∨(Ｐ∧Ｑ∧Ｒ) = m0∨m1∨m3∨m4∨m6∨m7 ───主析取范式例3.5.5（续）?Ｇ= m2∨m5Ｇ= ? ?Ｇ＝ ?(m2∨m5)＝? m2∧? m5= M2∧M5 =(Ｐ∨?Ｑ∨Ｒ)∧(?Ｐ∨Ｑ∨?Ｒ)─主合取范式3.5.3 范式中的难点1、如何正确的理解范式定义中的“有限个 文字”、“有限个短语”、“有限个子句” 的概念是很关键的，“有限个”∈N={0, 1, 2, ?, n, ?}； 2、使用真值表技术求主范式时注意正确地 建立真值表，正确地掌握真值解释还原成 子句和短语的方法；3.5.3 范式中的难点3、使用公式转换法求主范式时，需要增加 某一个命题变元，此时注意关于该变元的 永真公式和永假公式的正确加入，同时注 意公式的正确化简； 4、利用主析取求主合取或者利用主合取求 主析取时，注意是“Ｇ”的主析取范式的 否定或“Ｇ”的主合取范式的否定，而非 直接是G的否定。3.5.4 范式的应用定理3.5.3 （1）公式G为永真式G的合取范式中每个简 单的析取式至少包含一个命题变元及其否定； （2）公式G为永假式G的析取范式中每个简 单的合取式至少包含一个命题变元及其否定；3.5.4 范式的应用例3.5.6 判断下面公式为何种类型的公式。（1）(P∧? Q)??(? P∨Q)（2）(P→Q)?R（3） ?(P→?Q)∧(Q→P)例3.5.6 解（1）(P∧? Q)??(? P∨Q) ＝((P∧?Q)→?(?P∨Q))∧(?(? P∨Q)→(P∧?Q))＝(?(P∧?Q)∨?(?P∨Q))∧((?P∨Q)∨(P∧? Q))＝(? P∨Q∨(P∧?Q))∧((?P∨Q)∨(P∧? Q)) ＝(? P∨Q∨P)∧(P∨Q∨?Q))∧(?P∨Q∨P)∧(P∨Q∨?Q) 由于该合取范式中每个简单析取式至少包含一 ――合取范式 个命题变元及其否定，由定理3.5.3知，该公式为永 真公式。例3.5.6（续）（2）(P→Q)?R ＝ ((?P∨Q)→R)∧(R→(?P∨Q)) ＝ (?(?P∨Q)∨R)∧(?R∨(?P∨Q))＝ ((P∧?Q)∨R)∧(?R∨?P∨Q)＝ (P∨R)∧(?Q∨R)∧(?R∨?P∨Q)―合取范 式例3.5.6（续）＝ (P∧?Q∧?R)∨(P∧?Q∧?P) ∨(P∧?Q∧Q)∨(P∧?R∧R)∨(P∧R∧?P) ∨(P∧R∧Q)∨(R∧?Q∧?R)∨(R∧?Q∧?P)∨ 由于该公式所对应的合取范式及析取范式都不满 (R∧?Q∧Q)∨(R∧?R∧R)∨(R∧R∧?P)∨( 足定理3.5.3中的条件，所以它既不是永真公式， R∧R∧Q) 也不是永假公式，而是一个可满足公式。＝例3.5.6（续）（3） (P→Q)∧(P∧?Q)＝(?P∨Q)∧(P∧?Q)＝(?P∧P∧?Q)∨(Q∧P∧?Q)――析取范 式由于该公式所对应的析取范式中的每一个简 单的合取式至少包含一个命题变元及其否定，根 据定理3.5.3知，该公式是一个永假公式。定理3.5.4（1）如果命题公式是永真公式它的主析取范 式包含所有的极小项，此时无主合取范式或 者说主合取范式为“空”。（2）如果命题公式是永假公式它的主合取范 式包含所有的极大项，此时无主析取范式或 者说主析取范式为“空”。（3）两个命题公式是相等的它们对应的主析 取范式之间相等，或者(可兼或)它们对应的主
合取范式之间相等。例3.5.7求证(P→Q)∧(P→R)＝P→(Q∧R)证明 左式=(P→Q)∧(P→R)＝(?P∨Q)∧(?P∨R) =(?P∨Q∨(R∧?R))∧(?P∨(Q∧?Q)∨R)= (?P∨Q∨R)∧(?P∨Q∨?R)∧ (?P∨Q∨R)∧(?P∨?Q∨R) =(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)= M4∧M5∧M6例3.5.7 解（续）右式= P→(Q∧R)=?P∨(Q∧R)= (?P∨Q)∧(?P∨R)＝M4∧M5∧M6 两个公式具有相同的主合取范式，故两公式等价。http://202.115.21.136:8080/lssx/离散数学电子科 技大学计算机科学与 工程学院示 范 性 软 日星期五第4章 谓词逻辑命题逻辑能够解决的问题 是有局限性的。只能进行命题 间关系的推理，无法解决与命 题的结构和成分有关的推理问 题。 例如(著名的苏格拉底三段论) （1）所有的人都是要死的； （2）苏格拉底是人。 （3）苏格拉底是要死的。?????苏格拉底三段论P：所有的人都是要死的； ? Q：苏格拉底是人。 ? R：所以，苏格拉底是要死的。 ? 可见，P，Q，R为不同的命题，无法体 现三者相互之间的联系。?? 问题在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现 在构成原子命题的内部成分之间。对此， 命题逻辑将无能为力。本章内容1 2 3谓词逻辑中的基本概念 谓词的翻译原理 谓词的合式公式 谓词的标准型-范式44.1 本章学习要求重点掌握 1 1 谓词逻辑符 号化及真值 2 谓词公式的 有效性和基本 等价公式 一般掌握 了解 3 前束范式与 SKOLEM范式2 1 谓词公式的 解释和真值 2 自由变元和 约束变元4.2 谓词逻辑中的基本概念与表 示? 命题是具有真假意义的陈述句，从语法上分析，一个陈述句由主语和谓语两部分组 成。 ? 例如，“计算机是现代科学技术必不可少的 工具”? 例如 若Ｐ：是电子科技大学的学生? ?? --P(陈 “陈华是电子科技大学的学生”； 华) “张强是电子科技大学的学生”。 ? --P(张 强)谓词? 更一般地，?P(x)：x是电子科技大学的学生。x：个体词P(x)P：谓词 P(x):命题函数个体词与谓词? 定义4.2.1 在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为 个体词(Individual)。而用以刻划客体的性 质或客体之间的关系即是谓词(Predicate)。? 例1 成都、北京、赵明、班、计 ? 单纯的谓词或单纯的个体词都无法构成一个完整的逻辑含义，只有将它们结合起来时才 算机科学等等仅仅是简单的个体常量；“是 能构成一个独立的逻辑断言。 中国的首都”、“是计算机的基础课程”等 仅仅是简单的谓词，它们都不能构成完整的 句子。个体词的分类? （1）表示具体的或特定的个体词称为个体常量(Individual Constant)，一般个体词 常量用带或不带下标的小写英文字母a, b, c，…，a1, b1, c1,…等表示； ? （2）表示抽象的或泛指的个体词称为个 体变量(Individual Variable)，一般用带或 不带下标的小写英文字母x, y, z, …, x1, y1, z1, …等表示。例子? 例2 考察下列句子：（1）北京是中国的首都； ? （2）离散数学是计算机的基础课程； ? （3）刘翔是一个跨栏世界冠军； ? （4）中国人是很聪明的。?个体域? 定义4.2.2? （1）个体词的取值范围称为个体域(或论域)(Individual Field)，常用D表示；? （2）而宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域(Universal Individual Field)。n元谓词? 定义4.2.3 设D为非空的个体域，定义在Dn(表示n个个体都在个体域D上取值)上取 值于{0,1}上的n元函数，称为n元命题函数 或n元谓词(Propositional Function)，记为 P(x1, x2, …, xn)。此时，个体变量x1, x2, …, xn的定义域都为D，P(x1, x2, …, xn)的值域 为{0, 1｝。例4.2.1? 设有如下命题，并用n元谓词进行表示。??? ?P：王童是一个三好学生； Q：李新华是李兰的父亲； R：张强与谢莉是好朋友； S：武汉位于北京和广州之间。例4.2.1（续）? 解 定义命题函数： ? S(x)： x是一个三好学? 用符号表示个体词：? a：王童；b：李?? ? ? ? ?生； 新华； F(x, y)： x是y的父亲； ? c：李兰；d：张强； T(x, y)： x与y是好朋友； e：谢莉；f：武汉； ? B(x,y,z)：x位于y和z之 ? g：北京；h：广 则命题可表示为： 间； 州。 P：S(a)；Q：F(b, c)； R：T(d, e)；S：B(f, g, h)。结论? （1）谓词中个体词的顺序是十分重要的，不能随意变更。如命题F(b, c)为“真”，但 命题F(c, b)为“假”；? （2）一元谓词用以描述某一个个体的某种特性，而n元谓词则用以描述n个个体之间的 关系。? （3）0元谓词(不含个体词的)实际上就是一般的命题；结论（续）? （4）具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而 后者不是命题，它的真值是不确定的。如上 例中S(a)是有真值的，但S(x)却没有真值； ? （5）一个n元谓词不是一个命题，但将n元谓 词中的个体变元都用个体域中具体的个体取 代后，就成为一个命题。而且，个体变元在 不同的个体域中取不同的值对是否成为命题 及命题的真值有很大的影响。4.2.2 量词? 例4.2.2 符号化下述命题：? （1）所有的老虎都要吃人；? （2）每一个大学生都会说英语；? （3）所有的人都长着黑头发；? （4）有一些人登上过月球； ? （5）有一些自然数是素数。例4.2.2(续)? 解 设立如下谓词：?? ? ? ? ???P(x)：x会吃人；Q(x)：x会说英语； R(x)：x长着黑头发；S(x)：x登上过月 球； T(x)：x是素数。 则有：（1）所有的x，P(x) x∈ {老虎｝； （2）每一个x，Q(x) x∈{大学生}； （3）所有的x，R(x) x∈{人}； （4）有一些x，S(x) x∈{人}； （5）有一些x，T(x) x∈{自然数}。量词含义(?x)? 所有的x； ? 任意的x；(?x)? 有些x； ? 至少有一个x；? 一切的x；? 每一个x；等? 某一些x；? 存在x；等等。等。全称量词与存在量词? 定 义 4.2.4称 (?x) 为 全 称 量 词 （ Universal Quantifier ） ， (?x) 为 存 在 量 词 （ Existential Quantifier ） ， 其 中 的 x 称 为 作 用 变 量 （Function Variable）。一般将其量词加在 其谓词之前，记为(?x)F(x)，(?x)F(x)。此时， F(x)称为全称量词和存在量词的辖域(Scope)。例4.2.2(续)? （1）(?x)P(x) ? （2）(?x)Q(x)? （3）(?x)R(x)? （4）(?x)S(x) ? （5）(?x)T(x)x∈ {老虎} ； x∈{大学生}； x∈{人}； x∈{人}； x∈{自然数}。不便之处? （1）从书写上十分不便，总要特别注明个体域； ? （2）在同一个比较复杂的句子中，对于不 同命题函数中的个体可能属于不同的个体域， 此时无法清晰表达； ? 如例 (1)和(4)的合取 ? (?x)P(x)∧(?x)R(x) ? x∈{老 ? x∈{ 虎} 人}不便之处(续)? （3）若个体域的注明不清楚，将造成无法确定其真值。即对于同一个n元谓词， 不同的个体域有可能带来不同的真值。? 例如 对于语句“(?x)(x+6 = 5)‖可表示为：“有一些x，使得x+6 = 5‖。该语句在下面 两种个体域下有不同的真值：? ?（a）在实数范围内时，确有x=-1使得 x+6 = 5，因此，(?x)(x+6 = 5)为“真”； （b）在正整数范围内时，则找不到任何 x，使得x+6=5为“真”，所以，不便之处的根源? 对了，都是因为需要特别标注每个谓词的个体域所致！全总个体域特性谓词? U(x)：x是老 ? x∈｛老虎虎｝? 新的问题出现了，U(x)如何与(?x)P(x)结合才符合逻辑呢？谓词逻辑符号化的两条规则?统一个体域为全总个体域，而对每一个 句子中个体变量的变化范围用一元特性谓 词刻划之。这种特性谓词在加入到命题函 数中时必定遵循如下原则：体域的特性谓词作为蕴涵式之前件加入。? （1）对于全称量词(?x)，刻划其对应个? （2）对于存在量词(?x)，刻划其对应个体域的特性谓词作为合取式之合取项加 入。特性谓词的例子? 想想，为什么要这样规定特性谓词加入的原则呢？若不遵循会出现什 么样的问题？ ? 例如，符号化“所有的老虎都要吃人”这 ? 个命题 若P(x)：x会吃人 U(x)：x是老虎? 则符号化的正确形式应该是 ? 若符号化为 (?x)(U(x)∧P(x)) ? (?x)(U(x)→P(x)) ? 它的含义是：“对于任意的x,x是老虎， ? 并且x会吃人”，与原命题“所有的老虎都 它的含义是：“对于任意的x,如果x是老虎，则x会吃人”，符合原命题的逻辑含义。 要吃人”的逻辑含义不符。例4.2.3? 用谓词逻辑符号化下述语句： ? (1) 天下乌鸦一般黑；? (2) 没有人登上过木星；? (3) 在美国留学的学生未必都是亚洲人；? (4) 每个实数都存在比它大的另外的实数；? (5) 尽管有人很聪明，但未必一切人都聪明； ? (6) 对于任意给定的?&0，必存在着?&0，使得对任意的x，只要|x-a|&?，就有|f(x)-f(a)|&?成 立。例4.2.3(续)? （1）天下乌鸦一般黑? 设 F(x)：x是乌鸦；G(x, y)：x与y一般黑，则：? ? ? ? ??(?x)(?y)(F(x)∧F(y)→G(x, y)) 或者┐(?x)(?y)(F(x)∧F(y)∧┐G(x, y))； （2）没有人登上过木星 设H(x)：x是人；M(x)：x登上过木星，则： ┐(?x)(H(x)∧M(y)) 或者 (?x)(H(x)→┐M(y))；例4.2.3(续)? （3）在美国留学的学生未必都是亚洲人? 设A(x)：x是亚洲人；??? ? ?H(x)：x是在美国留学的学生，则： ┐(?x)(H(x)→A(x)) 或者 (?x)(H(x)∧┐A(x))； （4）每个实数都存在比它大的另外的实数 设R(x)：x是实数；L(x, y)：x小于y，则： (?x)(R(x)→(?y)(R(y)∧L(x, y))；例4.2.3(续)（5）尽管有人很聪明，但未必一切人都聪明设M(x)：x是人；C(x)：x很聪明，则：(?x)(M(x)∧C(x))∧ ┐(?x)(M(x)→C(x))；（6）对于任意给定的?&0，必存在着?&0，使得对任意 的x，只要|x-a|&?，就有|f(x)-f(a)|&?成立。 设个体域为实数集合，则原命题可符号化为：(??)((?&0)→(??)((?&0)∧(?x)((|x-a|&?)→(|f(x)-f(a)|&?))))。4.2.3 谓词的语言翻译?1, ?x ? D, G( x) ? 1 (?x)G( x) ? ? ?0, ?x0 ? D, G( x0 ) ? 0?1, (?x)G( x) ? ? ?0, ?x0 ? D, G( x0 ) ? 1 ?x ? D, G( x) ? 0? 特殊的，当个体域D＝{x0, x1, …}是可数集合时，上述(?x)G(x)、(?x)G(x)的真值可表 示为： ? (?x)G(x)=G(x0)∧G(x1)∧... ? (?x)G(x)=G(x0)∨G(x1)∨...个体域可数或有限? 更特别的，当个体域D＝{x0, x1, … xn}是有限集合时，上述(?x)G(x)、(?x)G(x)的真值 可以用与之等价的命题公式来进行表