冯伟森,Email：fws365scu.edu.cn 2019年8月3日星期六,离散 数学,计算机学院,2019/8/3,计算机学院,2,习题课二,2019/8/3,计算机学院,3,一、基本概念 全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式(重言式) 、永假公式(矛盾式，不可满足公式）、,第二章,2019/8/3,计算机学院,4,可满足公式、前束范式、母式、前束合取(或析取)范式、Skolem范式、US(全称指定规则)、ES(存在指定规则)、UG(全称推广规则)、EG(存在推广规则),2019/8/3,计算机学院,5,二、基本要求 能准确地将给定命题符号化 深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念 能准确理解约束变元(量)和自由变元的概念 掌握约束变元的改名规则和自由变元的代入规则,2019/8/3,计算机学院,6,掌握与量词相关的基本等价式和基本蕴涵式 能熟练地运用US、ES、UG、EG规则进行推理,2019/8/3,计算机学院,7,语句的符号化,1、将下列命题翻译成谓词公式 每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数。 A(x):x是实数 B(x):x是有理数 (x)(B(x)A(x)(x)(A(x)B(x) (x)(A(x)B(x) 直线a和b平行当且仅当a和b不相交。 A(x):x是直线 F(x，y):x与y平行 G（x,y):与相交 ()()（A()A() (F(，)G（,)）),2019/8/3,计算机学院,8,除非所有会员都参加，这个活动才有意义。 A(x):是会员 B(x):x有意义 ：这个活动 F(x，y):参加 B（）(x)（A(x)F(x，)） 或 (x)（A(x)F(x，)）B（） 任何正整数不是合数就是素数。 A(x):是正整数 (x)：是合数 (x)：是质数 (x)（A(x)(x)(x)）,2019/8/3,计算机学院,9,凡是存钱的人都想有利息，如果没有利息，人们就不会存钱。 A(x):是存钱的人 F(x，y):想有 P：存钱没有利息 Q: 人们不存钱 a: 利息 (x)（A(x)F(x，a)）（PQ）,2019/8/3,计算机学院,10,2、把下列语句符号化，并确定相应谓词公式是永真式、可满足式，还是矛盾式。 如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和数x+1的积也不等于0。 A(x):，（，） xA(（x，)）（A(x)A()） A(x） A(（x，)） 可满足式(Why?),2019/8/3,计算机学院,11,诚实的人都讲实话。小林不是诚实的，因而小林不讲实话。 A(x):是诚实的人 B(x):x讲实话 :小林 (x)（ A(x) B(x) ） A() B() F 好货不便宜。小王买的衣服很贵，所以小王买的是优质衣服。 A(x):不便宜 B(x):x是好货 ：小王买的衣服 (x)（ B(x) A(x)）（）（） F,2019/8/3,计算机学院,12,每个懂得人性本质的作家都很高明。不能刻划人们内心世界的诗人都不是真正的诗人。莎士比亚创作了哈姆雷特。没有一个不懂得人性本质的作家能够刻划人们的内心世界。只有真正的诗人才能创作哈姆雷特。因此，莎士比亚是一个高明的作家。 A(x):是懂得人性本质的作家 B(x):x是真正的诗人 C(x):x能刻划人们内心世界 D(x)：很高明 (x,y)：创作了 ：莎士比亚 ：哈姆雷特,T,2019/8/3,计算机学院,13,例1,将下列三条自然公理翻译成谓词公式： 每个自然数有且仅有一个直接后继； 没有任何自然数以0为其直接后继； 对0以外的任何自然数，有且仅有一个直接先行。 解：设个体域D为自然数 令p(x):x的直接先行; s(x):x的直接后继; EQUAL(x,y):x=y (x)(y)EQUAL(y,s(x) (z)EQUAL(z,s(x)EQUAL(y,z),有,且仅有,2019/8/3,计算机学院,14,(x)EQUAL(0,s(x) (x)EQUAL(x,0) (y)EQUAL(y,p(x)(z)EQUAL(z,p(x) EQUAL(y,z),0以外的任何自然数,2019/8/3,计算机学院,15,例2,证明下述论断的正确性： 每个报考研究生的大学毕业生要么参加研究生的入学考试，要么被推荐为免试生； 每个报考研究生的大学毕业生当且仅当学习成绩优秀才被推荐为免试生； 有些报考研究生的大学毕业生学习成绩优秀，但并非所有报考研究生的大学毕业生学习成绩都优秀。 因此，有些报考研究生的大学毕业生要参加研究生的入学考试。,2019/8/3,计算机学院,16,例2(续1),解：设P(x)：x是报考研究生的大学毕业生； Q(x)：x参加研究生入学考试； R(x)：x被推荐为免试生； S(x)：x学习成绩优秀。 则原论断可符号化为： (x)(P(x)(Q(x)R(x)， (x)(P(x)(R(x)S(x)， (x)(P(x)S(x), (x)(P(x)S(x) (x)(P(x)Q(x),2019/8/3,计算机学院,17,例2(续2),证明：(1) (x)(P(x)S(x) P (2) (x)(P(x)S(x) T,(1),E (3) P(c)S(c) ES,(2) (4) P(c) T,(3),I (5) (x)(P(x)(Q(x)R(x) P (6) P(c)（Q(c)R(c)） US,(5) (7) Q(c)R(c) T,(4),(6),I (8)(x)(P(x)(R(x)S(x) P (9) P(c)(R(c)S(c) US，（8） (10) R(c)S(c) T,(4),(9),I,2019/8/3,计算机学院,18,例2(续3),(11)(R(c)S(c)(S(c)R(c) T,(10),E (12) R(c)S(c) T,(12),I (13) S(c) T,(3),I (14) R(c) T,(12),(13),I (15) Q(c) T,(7),(14),I (16) P(c)Q(c) T,(4),(15),I (17) (x)(P(x)Q(x) ES,(16),2019/8/3,计算机学院,19,例3,证明下列论断的正确性： 有些学生相信所有的教师；任何一个学生都不相信骗子；所以，教师都不是骗子。,解：设谓词如下： S(x)：x是学生 T(x)：x是教师 P(x)：x是骗子 L(x,y)：x相信y 则可符号化为： 前提：(x)(S(x)(y)(T(y)L(x,y)， (x)(y)(S(x)P(y)L(x,y)。 结论：(x)(T(x)P(x) 即证明：(x)(S(x)(y)(T(y)L(x,y)， (x)(y)(S(x)P(y)L(x,y) (x)(T(x)P(x),2019/8/3,计算机学院,20,证明：,(x)(S(x)(y)(T(y)L(x,y) P S(c)(y)(T(y)L(c,y) ES,1) S(c) T,2),I (y)(T(y)L(c,y) T,2),I T(x)L(c,x) US,4) (x)(y)(S(x)P(y)L(x,y) P (y)(S(c)P(y)L(c,y) US,6) (S(c)P(x)L(c,x) US,7) S(c)(P(x)L(c,x) T,8),E P(x)L(c,x) T,3),8),E L(c,x)P(x) T,10),E T(x)P(x) T,5),11),E (x)(T(x)P(x) US,12),说明：该结论明显是一个错误的结论，原因在于有一个错误的假设，但推理是正确的。,2019/8/3,计算机学院,21,例4,1.采用反证法： (x)(y)(P(y)R(x,y) (y)(Q(y)R(x,y) P(附加) (x)(y)(P(y)R(x,y) (y)(Q(y)R(x,y) T,1),E (y)(P(y)R(c,y) (y)(Q(y)R(c,y) ES,2) (y)(P(y)R(c,y) (y)(Q(y)R(c,y) T,3),E (y)(P(y)R(c,y) T,4),I,证明：(x)(P(x)Q(x) (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y)。,2019/8/3,计算机学院,22,例4(续1),P(b)R(c,b) ES,5) P(b) T,6),I (x)(P(x)Q(x) P P(b)Q(b) US,8) Q(b) T,7),9),I R(c,b) T,6),I (Q(b)R(c,b) T,10),11)I (y)(Q(y)R(c,y) T,4),E (y)(Q(y)R(c,y) T,13),E (Q(b)R(c,b) US,14) (Q(b)R(c,b)(Q(b)R(c,b) US,14) ,2019/8/3,计算机学院,23,例4(续2),2.采用CP规则的直接证明法：,(y)(P(y)R(x,y) P(附加前题) P(f(x)R(x,f(x) ES，1) P(f(x) T,2) (x)(P(x)Q(x) P P(f(x)Q(f(x) US,4) Q(f(x) T,3),5),I R(x,f(x) T,2) Q(f(x)R(x,f(x) T,6),7),I (y)(Q(y)R(x,y) EG,8) (y)(P(y)R(x,y)(y)(Q(y)R(x,y) CP,1),9) (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y) EG,10),x是自由变元,2019/8/3,计算机学院,24,例5,所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数也不是无理数。 解：设Q(x)：x是有理数；R(x)：x是实数； N(x)：x是无理数； C(x)：x是虚数； (x)(Q(x)R(x), (x)(N(x)R(x) (x)(C(x) R(x) (x)(C(x)(Q(x)N(x),2019/8/3,计算机学院,25,(x)(Q(x)R(x) P Q(x)R(x) US(1) (x)(N(x)R(x) P N(x)R(x) US(3) (x)(C(x)R(x) P C(x)R(x) US(5) R(x)C(x) T(6)E,2019/8/3,计算机学院,26,Q(x)C(x) T(