离散数学(第8讲)

1、冯伟森Email：07 八月 2022离散数学计算机学院2022/8/7计算机学院2主要内容 量词化逻辑 1、谓词 2、量词 3、全总个体域 4、自由变元与约束变元 2022/8/7计算机学院3 命题逻辑是数理逻辑的基础，主要研究命题和命题间的演算。原子命题是命题演算的基本单位，并把它看作是不可再分解。这就带来了命题逻辑的局限性。命题逻辑研究的范围限制在命题及其外部关系上，无法研究命题内部的成份、结构以及命题之间所具有的逻辑特征（共同性和差异性） 例2-11 设基本命题，P：李明是大学生 Q：王芳是大学生 R：松树是植物 很明显，P与Q在内部关系上，应该比R密切得多。然而，命题逻辑无法反映这种

2、区别，也无法反映P、Q间的共同性。序2022/8/7计算机学院4 例2-1.2 (著名的苏格拉底三段论) 设自然语言中的三个命题：1）所有的人都是要死的；2）苏格拉底是人；3）所以，苏格拉底是要死的。解：假设 P：所有的人都是要死的；Q：苏格拉底是人。R：苏格拉底是要死的。显然，无论用什么方法也无法推论出 P，Q R。 但是，这样简单的，凭直觉就知苏格拉底的论证是正确的推理，命题逻辑却无能为力。这是由命题逻辑的局限性造成的，因此，需要对命题的内部关系进行研究。2022/8/7计算机学院52.1 量词化逻辑谓词和量词一、谓词 Predlicate 在对命题的内部逻辑关系进行研究时，把基本命题分成

3、客体(个体）和谓词。客体独立存在的具体事物或抽象概念（即命题中所描述的对象。如主语，客观实体等）。谓词刻划客体的性质（特征）或描述客体间的关系。谓词一般用大写字母（串）表示;个体用小写字母表示。2022/8/7计算机学院6例2-1.3如有句子：张红是一个四川大学的学生；王南是一个四川大学的学生；李华是一个四川大学的学生。则在命题逻辑中必须要用三个命题P，Q，R来表示。但是，它们都具有一个共同的特征： “是一个四川大学的学生”因此，若将句子分解成：“主语谓语”用P表示“是一个四川大学的学生”，P后紧跟“某某人”。则上述句子可写为：P(张红)；P(王南)；P(李华)。一般地，P(x)：x是一个四川

4、大学的学生。P：谓词x：客体词P(x)：命题函数2022/8/7计算机学院7与谓词相联系的个体的数目，就是谓词的元数。描述一个个体的性质的谓词叫“一元谓词”。描述两个个体间的关系的谓词叫“二元谓词”。如A：比大命题4比3大表示成A（4，3）描述三个个体间的关系的谓词叫“三元谓词”。如B：在和之间 B（n,c,z）：内江在成都与重庆之间。定义2.1 设D是由客体构成的称为个体域的非空集合，以D中元素为值的变元称为客体变元。由形如 谓词标识符（客体变元1，客体变元2，客体变元n） 构成的、其值为“真”或“假”的表达式，称为n元谓词。即n元谓词是描述n个个体间的关系。2022/8/7计算机学院8命题

5、函数 设D为非空的个体域，定义在Dn(表示n个客体都在个体域(论域) D上取值)上取值于0,1上的n元函数，称为n元命题函数,记为P(x1,x2,xn)。此时，客体变元x1,x2,xn的定义域都为D， P(x1,x2,xn)的值域为0，1。 因此，n元谓词也可称为n元命题函数。 注意：n元谓词中的客体或客体变元是有一定次序的。 如A（4，3）为T，A（3，4）为F。2022/8/7计算机学院9 n元谓词和命题的关系： P(x,y,z):x+y=z 3元谓词 x=3,P(3,y,z):3+y=z 2元谓词 x=3,y=4,P(3,4,z):3+4=z 1元谓词x=3,y=4,z=5,P(3,4,

6、5):3+4=5 0元谓词(命题)F 可见，0元谓词就是命题；命题是谓词的特殊情况，谓词是命题的扩充。 每个谓词一般都有各自的个体域，把各种个体域综合在一起作为论述范围的域叫全总个体域（全论域）用E表示。2022/8/7计算机学院10几个结论1) 谓词中个体词的顺序是十分重要的，不能随意变更。2) 一元谓词用以描述某一个客体的某种特性或性质，而n元谓词（二个以上）则用以描述n个客体之间的关系。3) 0元谓词(不含客体词的)实际上就是一般的命题。具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。一个n元谓词不是一个命题，但将n元谓词中的

7、客体变元都用个体域中具体的客体取代后，就成为一个命题。而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。2022/8/7计算机学院11二、量词 Quantifier 在苏格拉底三段论的例子中，如要对句子： P：H(x)D(x)（所有的人都是要死的）求否定，则有：(H(x)D(x)H()()H()()上述式子说明：“命题P”的否定是：“所有的人都不死”。但这与人们在日常生活中对命题：“所有人都是要死的”。的否定为：“并非一切的人都是要死的”。显然相差甚远。其原因在于：命题P的确切含义是：“对任意的x，如果x是人，则x是要死的”。但H(x)D(x)并没有确切地表示出“

8、对任意x”这个意思，亦即H(x)D(x)不是一个命题2022/8/7计算机学院12例2-14符号化下述命题：所有的老虎都要吃人；每一个人都会犯错误；有一些人会摔跤；有一些人是大学生；每一个带伞的人都不怕雨；有一些自然数是素数。 上述每一个描述量词的语句下划有“下划线”。2022/8/7计算机学院13例2-14(续1)解：设立如下谓词：R(x)：x会吃人；P(x)：x会犯错误；N(x)：x会摔跤；Q(x)：x是大学生；C(x)：x不怕雨；S(x)：x是素数。则有：（1）所有的x，R(x) x老虎； （2）每一个x，P(x) x人； （3）有一些x，N(x) x人； （4）有一些x，Q(x) x人

9、； （5）每一个x，C(x) x带伞的人； （6）有一些x，S(x) x 自然数。 计算机学院14量词的定义 上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的“对每一个”，“对任意的”，“有一些”等等无法用谓词来表示，这些都是与客体词的数量有关的语句。为了把它们符号化，引进如下两个符号： (x):所有的x； (x)：有些x； 任意的x；至少有一个x； 一切的x；存在x； 每一个x；等等。 等等。2022/8/7计算机学院15定义2.2 (x)称为全称量词,其中的x称为作用变量。一般将量词加在谓词之前，记为(x)Q(x)。 (x)Q(x)取值为真的充分必要条件是对论域中的每个客体a，Q(

10、a)都取值为真。定义2.3 (x)为存在量词, 记为 (x)Q(x)。 (x)Q(x)取值为真的充分必要条件是对论域中至少存在一个客体a，使Q(a)取值为真。全称量化命题存在量化命题2022/8/7计算机学院16例2-14 (续2)在例14中，利用量词则有：(x)R(x)(x老虎)(x)P(x) (x人)(x)N(x)(x人)(x)Q(x)(x人)(x)C(x)(x带伞的人)(x)S(x)(x自然数)2022/8/7计算机学院17三、全总个体域1、从书写上十分不便，总要特别注明个体域。2、在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。3、有时，由于个

11、体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。如(x)(x65)，1）在实数范围内时，确有x-1使得x65， 因此，(x)(x65)为“真”。2）在正整数范围内时，则找不到任何x，使得x65为“真”，所以，(x)(x65)为“假”。2022/8/7计算机学院18基于上述情况，有必要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中客体变量的变化范围用一定的特性谓词刻划之。而统一成全总个体域后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：对于全称量词，刻划其对应个体域的特性谓词作为

12、条件联结词的前件加入。对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。2022/8/7计算机学院19例2-14 (续3)对于例14 中的例子运用特性谓词描述。解：U(x)：x是老虎；(x)(U(x)R(x)H(x)：x是人； (x)(H(x)P(x)H(x)：x是人； (x)(H(x)N(x)H(x)：x是人；(x)(H(x)Q(x)M(x)：x是带伞的人；(x)(M(x)C(x)T(x)：x是自然数；(x)(T(x)S(x)苏格拉底三段论可完整翻译为： (x)(H(x)D(x)，H(S)D(S) (x)(H(x)D(x)(x)(H()D()2022/8/7计算机学院20例2-

13、15符号化下述语句：天下乌鸦一般黑；那位身体强健的、用功的、肯于思考的大学生，解决了一个数学难题；张强和李平都是足球运动员；每个实数都存在比它大的另外的实数。并非所有的动物都是脊椎动物；尽管有人很聪明，但未必一切人都聪明；对于任意给定的0，必存在着0，使得对任意的x，只要|x-a|，就有： |f(x)-f(a)|0)()(0)(|x-a|)(|f(x)-f(a)|)2022/8/7计算机学院24四、自由变元与约束变元定义2.4：在表达式xA(x)或xA(x)中，x称为指导（作用）变元，A(x)称为相应量词的辖域（作用域）。在辖域中x的所有出现称为x在公式A中的约束出现， 此时的变元x称为约束变

14、元。 A中不是约束出现的其它变元称为 自由变元。2022/8/7计算机学院25 一个公式中允许一个变元既是约束出现,又是自由出现。为了避免由于变元的约束与自由同时出现,引起概念上的混乱,故可对约束变元换名,对自由变元代入,使得一个变元在一个公式中只以一种形式出现,即把变元的自由出现和约束出现分开。2022/8/7计算机学院26两个规则规则1(约束变元的换名规则)：1）将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换。2）新的变元一定要有别于改名辖域中的所有其它变量。规则2(自由变元的代入规则)：1）将公式中出现该自由变元的每一处都用新的个体变元替换。2）新变元不允许在

15、原公式中以任何约束形式出现。2022/8/7计算机学院27例2-1.6设P(x)：x是素数I(x)：x是整数Q(x,y)：x+y=0用语句描述下述句子，并判断其真假值。(x)(I(x)P(x)(x)(I(x)P(x)(x)(y)(I(x)I(y)Q(x，y)(x)(I(x)(y)(I(y)Q(x，y)(x)(y)(I(x)(I(y)Q(x，y)2022/8/7计算机学院28可描述为：“对任意的整数x，x一定是素数”,真值为“假”。可描述为：“存在一些整数x，x是素数”，真值为“真”。可描述为：“对任意的整数x，y，都有x+y=0”，真值为“假”。可描述为：“对任意的整数x，都存在着整数y，使得x+y=0”，真值为“真”。可描述为：“存在着整数x，使得对任意的整数y，都有x+y=0”，真值为“假”。2022/8/7计算机学院29说 明 从上面的例子可知，如有多个量词，则读的顺序按从左到右的顺序，即： (x)(y)G(x,y)(x)(y)(G(x，y) 另外，量词对变元的约束，