离散数学及其应用第4章-谓词演算与推理(上)课件.ppt

1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第4 4章谓词演算与推理章谓词演算与推理 （上）（上）2022-8-52022-8-5 谓词公式与等值演算谓词公式与等值演算2 2 谓词公式的范式谓词公式的范式3 3个体词、谓词与量词个体词、谓词与量词1 1&本章学习内容本章学习内容(上上)2022-8-5计算机应用技术研究所计算机应用技术研究所4个体词、谓词与量词个体词、谓词与量词&个体词、

2、谓词与量词个体词、谓词与量词J 逻辑与谓词逻辑逻辑与谓词逻辑4 命题函数与谓词命题函数与谓词4 量词与特性谓词量词与特性谓词62022-8-5&命题逻辑的局限性命题逻辑的局限性 命题是一个具有确切真假含义的陈述句，一般由主语和谓语这两个基本部分组成。【例】对于如下命题：小张是合肥工业大学学生；小李是合肥工业大学学生。命题逻辑无法表达这种概念层次上的共同特性。72022-8-5&命题逻辑的局限性命题逻辑的局限性82022-8-5&命题逻辑的局限性命题逻辑的局限性&个体词、谓词与量词个体词、谓词与量词4 逻辑与谓词逻辑逻辑与谓词逻辑J 命题函数与谓词命题函数与谓词4 量词与特性谓词量词与特性谓词1

3、02022-8-5&含变量的语句含变量的语句对于“小张是大学生”这个原子命题，可将其主语“小张”进行抽象，得到如下语句：“某某是大学生”。可将该语句看成是一种含变量含变量的语句。令x表示“某某”，则可将上述含变量的语句表示为：“x是大学生”。若再令P表示谓语部分“是大学生”，则可将其表示为P(x)，即：P(x)：x是大学生是大学生。112022-8-5&个体变量与命题函数个体变量与命题函数【定义】【定义】客观世界中可以独立存在的具体或抽象对象称为个体个体，表示个体的词称为个体词个体词。若个体词以常量的方式表示特定个体，则称之为个体常量个体常量；若个体词以变量的方式泛指不确定的个体，则称之为个体

4、变量个体变量。122022-8-5&个体变量与命题函数个体变量与命题函数132022-8-5&个体变量与命题函数个体变量与命题函数 个体变量的取值应有一个明确范围，故有如下个体域的概念：【定定义义】个体变量的取值范围称为个体域个体域或论域论域。宇宙间所有的个体域聚集在一起构成的个体域，称为全总个体域全总个体域。注意：个体变量的个体域可根据问题的实际状况或需要来确定。且个体变量的个体域的不同，其相应含变量语句的含义也会有所不同。142022-8-5&个体变量与命题函数个体变量与命题函数152022-8-5&个体变量与命题函数个体变量与命题函数【例题】将下列原子命题抽象成简单命题函数：（1）小红是

5、个好学生；（2）王华喜欢离散数学；（3）刘明和王玲考试成绩很好。162022-8-5&个体变量与命题函数个体变量与命题函数172022-8-5&谓词与谓词填式谓词与谓词填式注意：注意：单纯的个体词或单纯的谓词都无法完成一个完整的逻辑含义，只有将它们结合起来才能构成完整独立的逻辑断言。182022-8-5&谓词与谓词填式谓词与谓词填式192022-8-5&谓词与谓词填式谓词与谓词填式202022-8-5&谓词与谓词填式谓词与谓词填式 命题其实就是一种特殊的零元谓词，谓词逻辑是命题逻辑的一种自然推广212022-8-5&谓词与谓词填式谓词与谓词填式【例题】试给出如下命题的谓词式：P：王彤是个三好学

6、生；Q：李琳是王玲的老师；R：今天气温在18度到25度之间。222022-8-5&谓词与谓词填式谓词与谓词填式232022-8-5&谓词与谓词填式谓词与谓词填式&个体词、谓词与量词个体词、谓词与量词4 逻辑与谓词逻辑逻辑与谓词逻辑4 命题函数与谓词命题函数与谓词J 量词与特性谓词量词与特性谓词252022-8-5&量词与特性谓词量词与特性谓词262022-8-5&量词与特性谓词量词与特性谓词【例题】使用全称量词表示下列原子命题：（1）所有的老虎都要吃人；（2）每个大学生都会说英语；（3）所有人都长着黑头发。272022-8-5&量词与特性谓词量词与特性谓词282022-8-5&量词与特性谓词量

7、词与特性谓词292022-8-5&量词与特性谓词量词与特性谓词【例题】使用存在量词表示下列原子命题：（1）有一些人登上过月球；（2）有一些自然数是素数。302022-8-5&量词与特性谓词量词与特性谓词312022-8-5&量词与特性谓词量词与特性谓词【例题】使用量词表示下列原子命题：（1）每列火车都比某些汽车快；（2）某些汽车比所有的火车慢。322022-8-5&量词与特性谓词量词与特性谓词332022-8-5&量词与特性谓词量词与特性谓词342022-8-5&量词与特性谓词量词与特性谓词352022-8-5&量词与特性谓词量词与特性谓词362022-8-5&量词与特性谓词量词与特性谓词37

8、2022-8-5&量词与特性谓词量词与特性谓词382022-8-5&量词与特性谓词量词与特性谓词392022-8-5&量词与特性谓词量词与特性谓词402022-8-5&量词与特性谓词量词与特性谓词有时需要对量词含义进行否定。例如：“每个老虎都吃人”的否定，就是：“不是每个老虎都吃人”或“至少存在一个老虎不吃人”412022-8-5&量词与特性谓词量词与特性谓词量词德摩根律的具体逻辑含义由如表所示：422022-8-5&量词与特性谓词量词与特性谓词【例题】求下列命题谓词式的否定式：（1）有一些学生喜欢离散数学；（2）三班的男生跑步都很快。432022-8-5&量词与特性谓词量词与特性谓词4420

9、22-8-5&量词与特性谓词量词与特性谓词452022-8-5&量词与特性谓词量词与特性谓词 有多个类似的命题谓词式进行复杂的逻辑运算，那么对运算结果个体域的确定会十分麻烦。462022-8-5&量词与特性谓词量词与特性谓词u 其次，对于一个命题的谓词表达式，其个体域的确定又是非常重要的。u 个体域的差异往往会导致其真值取值的不同。例：命题“所有人都是大学生”，l 如果个体域是某大学的某个班，则该命题为真；l 如果个体域是某中学的某个班，则该命题为假；l 如果个体域为某电影院某场电影的全体观众，则命题的真值就比较难以确定。472022-8-5&量词与特性谓词量词与特性谓词u 命题的谓词表达式命

10、题的谓词表达式不能采用不能采用对每个表达式分别对每个表达式分别指定个体域的方式。指定个体域的方式。u 将将所有的谓词和命题函数所有的谓词和命题函数共用全总个体域共用全总个体域作为作为一种统一的个体域，不同的个体变量可以通过一种统一的个体域，不同的个体变量可以通过设立与其含义设立与其含义相对应相对应的特性谓词来确定其个体的特性谓词来确定其个体域。域。482022-8-5&量词与特性谓词量词与特性谓词492022-8-5&量词与特性谓词量词与特性谓词502022-8-5&量词与特性谓词量词与特性谓词512022-8-5&量词与特性谓词量词与特性谓词【例题】使用特性谓词符号化下列命题：（1）所有人都

11、会犯错误；（2）金子都会闪光，但闪光的不一定是金子；（3）有人很聪明，但不是一切人都聪明；（4）天下乌鸦一般黑。522022-8-5&量词与特性谓词量词与特性谓词532022-8-5&量词与特性谓词量词与特性谓词542022-8-5&量词与特性谓词量词与特性谓词【例题】用谓词式符号化下列命题：如果一个人只说谎话，那么他说的每一句话都是不可信的。552022-8-5&量词与特性谓词量词与特性谓词【例题】符号化下面一组语句：（1）海关人员检查每一个入境的不重要人物；（2）某些走私者入境时仅仅被走私者所检查；（3）没有一个走私者是重要人物；（4）有些海关人员是走私者。562022-8-5&量词与特性

12、谓词量词与特性谓词2022-8-5计算机应用技术研究所计算机应用技术研究所57本节内容到此结束本节内容到此结束2022-8-52022-8-5 谓词公式与等值演算谓词公式与等值演算2 2 谓词公式的范式谓词公式的范式3 3个体词、谓词与量词个体词、谓词与量词1 1&本章学习内容本章学习内容(上上)2022-8-5计算机应用技术研究所计算机应用技术研究所59谓词公式与等值演算谓词公式与等值演算&谓词公式与等值演算谓词公式与等值演算J 谓词公式的概念谓词公式的概念4 变量的自由与约束变量的自由与约束4 谓词公式的解释与分类谓词公式的解释与分类4 谓词公式的等价与蕴含谓词公式的等价与蕴含612022

13、-8-5&谓词公式的概念谓词公式的概念（1）个体常量符号个体常量符号：用带或不带下标的小写英文字母a,b,c,表示个体常量。（2）个体变量符号个体变量符号：用带或不带下标的小写英文字母x,y,z,表示个体变量。（3）个体函数符号个体函数符号：用带或不带下标的小写英文字母f,g,h,表示个体函数。所谓个体函数，就是个体与个体之间的映射关系。（4）谓词符号谓词符号：用带或不带下标的大写英文字母P,Q,R,表示谓词。622022-8-5&谓词公式的概念谓词公式的概念632022-8-5&谓词公式的概念谓词公式的概念642022-8-5&谓词公式的概念谓词公式的概念652022-8-5&谓词公式的概念

14、谓词公式的概念662022-8-5&谓词公式的概念谓词公式的概念 谓词公式是原子谓词公式、联结词、量词、谓词公式是原子谓词公式、联结词、量词、圆括号和逗号按上述规则组成的符号串，且命题圆括号和逗号按上述规则组成的符号串，且命题公式是谓词公式的一个特例。公式是谓词公式的一个特例。为方便起见，谓词公式中的括号可以像命题为方便起见，谓词公式中的括号可以像命题公式那样省略最外层括号。公式那样省略最外层括号。672022-8-5&谓词公式的概念谓词公式的概念682022-8-5&谓词公式的概念谓词公式的概念&谓词公式与等值演算谓词公式与等值演算4 谓词公式的概念谓词公式的概念J 变量的自由与约束变量的自

15、由与约束4 谓词公式的解释与分类谓词公式的解释与分类4 谓词公式的等价与蕴含谓词公式的等价与蕴含702022-8-5&变量的自由与约束变量的自由与约束712022-8-5&变量的自由与约束变量的自由与约束722022-8-5&变量的自由与约束变量的自由与约束确定一个量词的辖域就是要找出位于该量词之后与之相邻接的子公式，具体方法具体方法如下：（1）若量词后面有括弧有括弧，则括弧内的子公式括弧内的子公式就是该量词的辖域辖域；（2）若量词后面无括弧无括弧，则与该量词邻接的子与该量词邻接的子公式公式为该量词的辖域辖域。732022-8-5&变量的自由与约束变量的自由与约束742022-8-5&变量的自

16、由与约束变量的自由与约束752022-8-5&变量的自由与约束变量的自由与约束762022-8-5&变量的自由与约束变量的自由与约束772022-8-5&变量的自由与约束变量的自由与约束782022-8-5&变量的自由与约束变量的自由与约束【分析】判断公式的变元是自由变元还是约束变元，关键是看量词后面的辖域。792022-8-5&变量的自由与约束变量的自由与约束802022-8-5&变量的自由与约束变量的自由与约束【定义定义】若谓词公式G中不含自由变量，则称该公式为封闭公式封闭公式或闭式闭式。812022-8-5&变量的自由与约束变量的自由与约束822022-8-5&变量的自由与约束变量的自由

17、与约束约束变量的换名规则约束变量的换名规则：（1）将量词中出现的变量以及该量词辖域中此变量的所有约束出现所有约束出现都替换为新的变量；（2）新变量名一定要有别于有别于辖域中的所有其它变量名。832022-8-5&变量的自由与约束变量的自由与约束自由变量的代入规则自由变量的代入规则：（1）将公式中出现该自由变量的每一处都用新新的变量替换的变量替换；（2）新变量不允许不允许在原公式中以任何约束形式出现。842022-8-5&变量的自由与约束变量的自由与约束852022-8-5&变量的自由与约束变量的自由与约束862022-8-5&变量的自由与约束变量的自由与约束872022-8-5&变量的自由与约

18、束变量的自由与约束882022-8-5&变量的自由与约束变量的自由与约束&谓词公式与等值演算谓词公式与等值演算4 谓词公式的概念谓词公式的概念4变量的自由与约束变量的自由与约束J 谓词公式的解释与分类谓词公式的解释与分类4 谓词公式的等价与蕴含谓词公式的等价与蕴含902022-8-5&谓词公式的解释与分类谓词公式的解释与分类【定义】【定义】谓词公式谓词公式G的每一个解释的每一个解释I由如下四个由如下四个部分组成：部分组成：（1）确定非空的个体域集合）确定非空的个体域集合D；（2）确定公式）确定公式G中的每个常量符号的含义，即中的每个常量符号的含义，即指定指定D中的某个特定的元素；中的某个特定的

19、元素；912022-8-5&谓词公式的解释与分类谓词公式的解释与分类922022-8-5&谓词公式的解释与分类谓词公式的解释与分类932022-8-5&谓词公式的解释与分类谓词公式的解释与分类942022-8-5&谓词公式的解释与分类谓词公式的解释与分类952022-8-5&谓词公式的解释与分类谓词公式的解释与分类962022-8-5&谓词公式的解释与分类谓词公式的解释与分类972022-8-5&谓词公式的解释与分类谓词公式的解释与分类982022-8-5&谓词公式的解释与分类谓词公式的解释与分类992022-8-5&谓词公式的解释与分类谓词公式的解释与分类1002022-8-5&谓词公式的解

20、释与分类谓词公式的解释与分类u 有些谓词公式在有些解释下为真，在另外有些谓词公式在有些解释下为真，在另外一些解释下为假；一些解释下为假；u 有些谓词公式则在所有解释下均为真；有些谓词公式则在所有解释下均为真；u 还有一些谓词公式在所有解释下均为假。还有一些谓词公式在所有解释下均为假。1012022-8-5&谓词公式的解释与分类谓词公式的解释与分类【定义定义】对于任意一个给定的谓词公式G，如果G在其所有的解释I下的真值取值为真，则称G称为有效公式有效公式；如果G在其所有的解释I下的真值取值都为假，则称G为矛盾公式矛盾公式；如果G不是矛盾公式，则称其为可满足公式可满足公式。&谓词公式与等值演算谓词

21、公式与等值演算4 谓词公式的概念谓词公式的概念4 变量的自由与约束变量的自由与约束4谓词公式的解释与分类谓词公式的解释与分类J 谓词公式的谓词公式的等价等价与蕴含与蕴含1032022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1042022-8-5&谓词公式等值式 第一组第一组：命题公式中永真公式的谓词公式代换实例显然是有效谓词公式。因此，按命题逻辑中24个基本等值式模式使用谓词公式代换出来的实例必定必定是谓词公式等值式。1052022-8-5&谓词公式等值式1062022-8-5&谓词公式等值式1072022-8-5&谓词公式等值式1082022-8-5&谓词公式等值式 上述基本的等值

22、关系式很多可以互相推导。特别是当个体域为有限集时，很容易理解上述等值关系的合理性。1092022-8-5&谓词公式等值式1102022-8-5&谓词公式等值式1112022-8-5&谓词公式等值式1122022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1132022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1142022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1152022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1162022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1172022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1182022-8-

23、5&谓词公式的等价与蕴含谓词公式的等价与蕴含1192022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1202022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1212022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1222022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1232022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1242022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1252022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1262022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含【解】这8个谓词公式显然是闭式，在根据题意得

24、到的解释下具有确定的含义及相应的真值，具体如下：1272022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1282022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1292022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含 使用这8个公式可构成20个等价式和蕴含式。为便于记忆，可将这20个等价式和蕴含式按下图方式进行排列。1302022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1312022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1322022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含1332022-8-5&谓词公式的等价与蕴含谓词公式的等价与蕴含2

25、022-8-5计算机应用技术研究所计算机应用技术研究所134本节内容到此结束本节内容到此结束2022-8-52022-8-5&本章学习内容本章学习内容(上上)谓词公式的范式谓词公式的范式3 31 12 2 谓词公式与等值演算谓词公式与等值演算个体词、谓词与量词个体词、谓词与量词2022-8-5计算机应用技术研究所计算机应用技术研究所136谓词公式的范式谓词公式的范式&谓词公式的范式谓词公式的范式J 等值型范式等值型范式4 非等型范式非等型范式1382022-8-5&等值型范式等值型范式1392022-8-5&等值型范式等值型范式【定理定理】任意一个含有量词的谓词公式都可以转化为与之等值的前束型

26、公式的形式，但是这种形式并不唯一。1402022-8-5&等值型范式等值型范式1412022-8-5&等值型范式等值型范式1422022-8-5&等值型范式等值型范式1432022-8-5&等值型范式等值型范式1442022-8-5&等值型范式等值型范式【定理定理】任意一个含有量词的谓词公式都分别存在与之等值的前束析取范式和前束合取范式，但范式的形式并不唯一。【证明】证明】首先将谓词公式可以转化为与之等值的前束型公式，然后将前束型公式的母式转化为析取范式或合取范式，即可得到相应的前束析取范式或者前束合取范式。1452022-8-5&等值型范式等值型范式1462022-8-5&等值型范式等值型范

27、式1472022-8-5&等值型范式等值型范式1482022-8-5&等值型范式等值型范式1492022-8-5&等值型范式等值型范式&谓词公式的范式谓词公式的范式4 等值型范式等值型范式J 非等值型范式非等值型范式1512022-8-5&非等值型范式非等值型范式1522022-8-5&非等值型范式非等值型范式1532022-8-5&非等值型范式非等值型范式1542022-8-5&非等值型范式非等值型范式1552022-8-5&非等值型范式非等值型范式1562022-8-5&非等值型范式非等值型范式1572022-8-5&非等值型范式非等值型范式1582022-8-5&非等值型范式非等值型范式1592022-8-5&非等值型范式非等值型范式1602022-8-5&非等值型范式非等值型范式1612022-8-5&非等值型范式非等值型范式1622022-8-5&非等值型范式非等值型范式1632022-8-5&非等值型范式非等值型范式2022-8-5计算机应用技术研究所计算机应用技术研究所164本节内容到此结束本节内容到此结束