离散数学( 第10讲习题课2)

1、冯伟森冯伟森EmailEmail：20222022年年1 1月月1515日星期六日星期六2022-1-152022-1-15计算机学院计算机学院2 22022-1-152022-1-15计算机学院计算机学院3 3一、基本概念一、基本概念 全总个体域（全论域）、全称量词、存全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、量符号、变量符号、函数符号、

2、谓词符号、谓词公式、公式的解释、永真公式谓词公式、公式的解释、永真公式( (重言式重言式) ) 、永假公式永假公式( (矛盾式，不可满足公式）、矛盾式，不可满足公式）、第二章第二章2022-1-152022-1-15计算机学院计算机学院4 4 可满足公式、前束范式、母式、前束合取可满足公式、前束范式、母式、前束合取( (或或析取析取) )范式、范式、SkolemSkolem范式、范式、US(US(全称指定规则全称指定规则) )、ES(ES(存在指定规则存在指定规则) )、UG(UG(全称推广规则全称推广规则) )、EG(EG(存在推广规则存在推广规则) )2022-1-152022-1-15计

3、算机学院计算机学院5 5二、基本要求二、基本要求 能准确地将给定命题符号化能准确地将给定命题符号化 深刻理解全称量词、存在量词及量词的辖域、深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念全总个体域的概念 能准确理解约束变元能准确理解约束变元( (量量) )和自由变元的概念和自由变元的概念 掌握约束变元的改名规则和自由变元的代入掌握约束变元的改名规则和自由变元的代入规则规则2022-1-152022-1-15计算机学院计算机学院6 6 掌握与量词相关的基本等价式和基本蕴涵式掌握与量词相关的基本等价式和基本蕴涵式 能熟练地运用能熟练地运用USUS、ESES、UGUG、EGEG规则进行推理

4、规则进行推理2022-1-152022-1-15计算机学院计算机学院7 7语句的符号化语句的符号化1 1、将下列命题翻译成谓词公式、将下列命题翻译成谓词公式 每个每个有理数有理数都是都是实数实数，但是并非每个实数都是有理数，但是并非每个实数都是有理数，有些实数是有理数。有些实数是有理数。 A(x):xA(x):x是实数是实数 B(x):xB(x):x是有理数是有理数 (x)(B(x)A(x)(x)(B(x)A(x)(x)(A(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x) 直线直线a a和和b b平行当且仅当平行当且仅当a a和和b b不相交。不相交

5、。 A(x):xA(x):x是直线是直线 F(xF(x，y):xy):x与与y y平行平行G G（x,y):x,y):与相交与相交 ( () ) ( () )（A(A()A()A() ) (F(F(，) )G G（, ,) )）) )2022-1-152022-1-15计算机学院计算机学院8 8 除非所有会员都参加，这个活动才有意义。除非所有会员都参加，这个活动才有意义。A(x):A(x):是会员是会员B(x):xB(x):x有意义：这个活动有意义：这个活动F(xF(x，y):y):参加参加B B（）（） (x)(x)（A(x)A(x)F(xF(x，) )）或或(x)(x)（A(x)A(x)F

6、(xF(x，) )） B B（）（） 任何正整数不是合数就是素数。任何正整数不是合数就是素数。A(x):A(x):是正整数是正整数(x)(x)：是合数：是合数(x)(x)：是质数：是质数 (x)(x)（A(x)A(x)(x)(x) (x)(x)）2022-1-152022-1-15计算机学院计算机学院9 9 凡是存钱的人都想有利息，如果没有利息，凡是存钱的人都想有利息，如果没有利息，人们就不会存钱。人们就不会存钱。A(x):A(x):是存钱的人是存钱的人F(xF(x，y):y):想有想有P P：存钱没有利息：存钱没有利息Q:Q: 人们不存钱人们不存钱a: a: 利息利息 (x)(x)（A(x)

7、F(xA(x)F(x，a)a)）（PQPQ）2022-1-152022-1-15计算机学院计算机学院10102 2、把下列语句符号化，并确定相应谓词公式、把下列语句符号化，并确定相应谓词公式是永真式、可满足式，还是矛盾式。是永真式、可满足式，还是矛盾式。 如果两个数的积等于如果两个数的积等于0 0，那么至少其中一个数，那么至少其中一个数为为0 0，数，数x-x-1 1不等于不等于0 0，所以数，所以数x-x-1 1和数和数x x+1+1的积的积也不等于也不等于0 0。A(x):A(x):，（，），（，） x x A(A(（x x，) )）（A(x)A(A(x)A() )） A(xA(x） A(

8、A(（x x，) )） 可满足式可满足式( (Why?Why?) ) 2022-1-152022-1-15计算机学院计算机学院1111 诚实的人都讲实话。小林不是诚实的，因而诚实的人都讲实话。小林不是诚实的，因而小林不讲实话。小林不讲实话。A(x):A(x):是诚实的人是诚实的人B(x):xB(x):x讲实话讲实话: :小林小林 (x)(x)（ A(x) B(x) A(x) B(x) ） A(A() B(B() ) F F 好货不便宜。小王买的衣服很贵，所以小王好货不便宜。小王买的衣服很贵，所以小王买的是优质衣服。买的是优质衣服。A(x):A(x):不便宜不便宜B(x):xB(x):x是好货是

9、好货：小王买的衣服：小王买的衣服 (x)(x)（ B(x) A(x) B(x) A(x)）（）（）（）（） F F2022-1-152022-1-15计算机学院计算机学院1212每个懂得人性本质的作家都很高明。不能刻划人们内心世界的每个懂得人性本质的作家都很高明。不能刻划人们内心世界的诗人都不是真正的诗人。莎士比亚创作了哈姆雷特。没有一个诗人都不是真正的诗人。莎士比亚创作了哈姆雷特。没有一个不懂得人性本质的作家能够刻划人们的内心世界。只有真正的不懂得人性本质的作家能够刻划人们的内心世界。只有真正的诗人才能创作哈姆雷特。因此，莎士比亚是一个高明的作家。诗人才能创作哈姆雷特。因此，莎士比亚是一个高

10、明的作家。 A(x):A(x):是是懂得人性本质的作家懂得人性本质的作家 B(x):xB(x):x是是真正的诗人真正的诗人 C(x):xC(x):x能刻划人们内心世界能刻划人们内心世界 D(x)D(x)：很高明：很高明 (x,y)(x,y)：创作了：创作了 ：莎士比亚：哈姆雷特：莎士比亚：哈姆雷特 T T2022-1-152022-1-15计算机学院计算机学院1313例例1 1将下列三条自然公理翻译成谓词公式：将下列三条自然公理翻译成谓词公式： 每个自然数有且仅有一个直接后继；每个自然数有且仅有一个直接后继； 没有任何自然数以没有任何自然数以0 0为其直接后继；为其直接后继； 对对0 0以外的

11、任何自然数，有且仅有一个直接先行。以外的任何自然数，有且仅有一个直接先行。解：设个体域解：设个体域D D为自然数为自然数 令令p(x):xp(x):x的直接先行的直接先行; ; s(x):x s(x):x的直接后继的直接后继; ; EQUAL(x,y):x=y EQUAL(x,y):x=y ( ( x)x)( ( y y) ) EQUAL(y,s(x)EQUAL(y,s(x) ( ( z)EQUAL(z,s(x)EQUAL(y,z)z)EQUAL(z,s(x)EQUAL(y,z) 有有且仅有且仅有2022-1-152022-1-15计算机学院计算机学院1414 ( ( x x) ) EQUAL

12、(0,s(x)EQUAL(0,s(x) ( ( x)x)EQUAL(x,0)EQUAL(x,0)( ( y y) ) EQUAL(y,p(x)(EQUAL(y,p(x)( z)EQUAL(z,p(x)z)EQUAL(z,p(x) EQUAL(y,z) EQUAL(y,z)0 0以外的任何以外的任何自然数自然数2022-1-152022-1-15计算机学院计算机学院1515例例2 2 证明下述论断的正确性：证明下述论断的正确性：每个报考研究生的大学毕业生要么参加研究生每个报考研究生的大学毕业生要么参加研究生的入学考试，要么被推荐为免试生；的入学考试，要么被推荐为免试生；每个报考研究生的大学毕业生

13、当且仅当学习成每个报考研究生的大学毕业生当且仅当学习成绩优秀才被推荐为免试生；绩优秀才被推荐为免试生；有些报考研究生的大学毕业生学习成绩优秀，有些报考研究生的大学毕业生学习成绩优秀，但并非所有报考研究生的大学毕业生学习成但并非所有报考研究生的大学毕业生学习成绩都优秀。绩都优秀。因此，有些报考研究生的大学毕业生要参加研因此，有些报考研究生的大学毕业生要参加研究生的入学考试。究生的入学考试。2022-1-152022-1-15计算机学院计算机学院1616例例2(2(续续1)1)解：解：设设P(x)P(x)：x x是报考研究生的大学毕业生；是报考研究生的大学毕业生；Q(x)Q(x)：x x参加研究生

14、入学考试；参加研究生入学考试；R(x)R(x)：x x被推荐为免试生；被推荐为免试生；S(x)S(x)：x x学习成绩优秀。学习成绩优秀。则原论断可符号化为：则原论断可符号化为：( ( x)x)(P(x)(Q(x)(P(x)(Q(x) R(x)R(x)，( ( x)x)(P(x)(R(x)(P(x)(R(x)S(x)S(x)， ( ( x)x)(P(x)S(x),(P(x)S(x), ( ( x)x)(P(x)S(x)(P(x)S(x) ( ( x)x)(P(x)Q(x)(P(x)Q(x)2022-1-152022-1-15计算机学院计算机学院1717例例2(2(续续2)2)证明：证明：(1)

15、 (1) ( ( x)x)(P(x)S(x) P(P(x)S(x) P(2) (2) ( ( x)x)(P(x)(P(x)S(x) T,(1),ES(x) T,(1),E(3) P(c)(3) P(c)S(c) ES,(2)S(c) ES,(2)(4) P(c) T,(3),I(4) P(c) T,(3),I(5) (5) ( x)x)(P(x)(Q(x)(P(x)(Q(x) R(x) PR(x) P(6) P(c)(6) P(c)（Q(c)Q(c) R(c)R(c)） US,(5)US,(5)(7) Q(c)(7) Q(c) R(c) T,(4),(6),IR(c) T,(4),(6),I(

16、8)(8)( x)x)(P(x)(R(x)(P(x)(R(x)S(x) PS(x) P(9) P(c)(R(c)(9) P(c)(R(c)S(c) USS(c) US，（，（8 8）(10) R(c)(10) R(c)S(c) T,(4),(9),IS(c) T,(4),(9),I2022-1-152022-1-15计算机学院计算机学院1818例例2(2(续续3)3)(11)(R(c)S(c)(S(c)R(c) T,(10),E(11)(R(c)S(c)(S(c)R(c) T,(10),E(12) R(c)S(c) T,(12),I(12) R(c)S(c) T,(12),I(13)(13)

17、S(c) T,(3),IS(c) T,(3),I(14) (14) R(c) R(c) T,(12),(13),IT,(12),(13),I(15) Q(c) T,(7),(14),I(15) Q(c) T,(7),(14),I(16) P(c)Q(c) T,(4),(15),I(16) P(c)Q(c) T,(4),(15),I(17) (17) ( ( x)x)(P(x)Q(x) ES,(16)(P(x)Q(x) ES,(16)2022-1-152022-1-15计算机学院计算机学院1919例例3 3 证明下列论断的正确性：证明下列论断的正确性：有些有些学生学生相信相信所有的所有的教师教师

18、；任何一个学生都不相信；任何一个学生都不相信骗子骗子；所以，教师都不是骗子。所以，教师都不是骗子。解：解：设谓词如下：设谓词如下：S(x)S(x)：x x是学生是学生T(x)T(x)：x x是教师是教师P(x)P(x)：x x是骗子是骗子L(x,y)L(x,y)：x x相信相信y y则可符号化为：则可符号化为：前提：前提：( ( x)x)(S(x)(S(x)( ( y)(T(y)y)(T(y)L(x,y)L(x,y)，( ( x)(x)( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y)。结论：结论：( ( x)(T(x)x)(T(x)P(x)P(x)即证明：即证明：( (

19、 x)x)(S(x)(S(x)( ( y)(T(y)y)(T(y)L(x,y)L(x,y)，( ( x)(x)( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y) ( ( x)(T(x)x)(T(x)P(x)P(x)2022-1-152022-1-15计算机学院计算机学院2020证明：证明：1)1) ( ( x)x)(S(x)(S(x)( ( y)(T(y)y)(T(y)L(x,y)L(x,y)P P2)2) S(c)S(c)( ( y)(T(y)y)(T(y)L(c,y)L(c,y)ES,1)ES,1)3)3) S(c)S(c)T,2),IT,2),I4)4) ( ( y

20、)(T(y)y)(T(y)L(c,y)L(c,y)T,2),IT,2),I5)5) T(x)T(x)L(c,x)L(c,x)US,4)US,4)6)6) ( ( x)x)( ( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y)P P7)7) ( ( y)(S(c)y)(S(c)P(y)P(y)L(c,y)L(c,y)US,6)US,6)8)8) ( (S(c)S(c)P(x)P(x)L(c,x)L(c,x)US,7)US,7)9)9) S(c)S(c)( (P(x)P(x)L(c,x)L(c,x)T,8),ET,8),E10)10)P(x)P(x)L(c,x)L(c,x)T

21、,3),8),ET,3),8),E11)11)L(c,x)L(c,x)P(x)P(x)T,10),ET,10),E12)12)T(T(x)x)P(x)P(x)T,5),11),ET,5),11),E13)13)( ( x)(x)(T(T(x)x)P(x)P(x)US,12)US,12)说明：该结论明显说明：该结论明显是一个错误的结论，是一个错误的结论，原因在于有一个错原因在于有一个错误的假设，但推理误的假设，但推理是正确的。是正确的。2022-1-152022-1-15计算机学院计算机学院2121例例4 41.1.采用反证法：采用反证法：1)1) ( ( x)(x)( ( y)y)(P(y)(

22、P(y)R(x,y)R(x,y)( ( y)y)(Q(y)(Q(y)R(x,y)R(x,y)P(P(附加附加) )2)2) ( ( x)x)( ( ( y)y)(P(y)(P(y)R(x,y)R(x,y)( ( y)y)(Q(y)(Q(y)R(x,y)R(x,y)T,1),ET,1),E3)3) ( ( ( y)y)(P(y)(P(y)R(c,y)R(c,y)( ( y)y)(Q(y)(Q(y)R(c,y)R(c,y)ES,2)ES,2)4)4) ( ( y)y)(P(y)(P(y)R(c,y)R(c,y) ( ( y)y)(Q(y)(Q(y)R(c,y)R(c,y)T,3),ET,3),E5

23、)5) ( ( y)y)(P(y)(P(y)R(c,y)R(c,y)T,4),IT,4),I证明：证明：( ( x)(P(x)x)(P(x)Q(x) Q(x) ( ( x)(x)( ( y)y)(P(y)(P(y)R(x,y)R(x,y)( ( y)y)(Q(y)(Q(y)R(x,y)R(x,y)。2022-1-152022-1-15计算机学院计算机学院2222例例4(4(续续1)1)6)6) P(b)P(b)R(c,b)R(c,b)ES,5)ES,5)7)7) P(b)P(b)T,6),IT,6),I8)8) ( ( x)(P(x)x)(P(x)Q(x) Q(x) P P9)9) P(b)P

24、(b)Q(b)Q(b)US,8)US,8)10)10) Q(b)Q(b)T,7),9),IT,7),9),I11)11) R(c,b)R(c,b)T,6),IT,6),I12)12) (Q(b)(Q(b)R(c,b) R(c,b) T,10),11)IT,10),11)I13)13) ( ( y)y)(Q(y)(Q(y)R(c,y)R(c,y)T,4),ET,4),E14)14) ( ( y)y)(Q(y)(Q(y)R(c,y)R(c,y)T,13),ET,13),E15)15) (Q(b)(Q(b)R(c,b)R(c,b)US,14)US,14)16)16) (Q(b)(Q(b)R(c,b)

25、R(c,b)(Q(b)(Q(b)R(c,b)R(c,b)US,14)US,14)17)17) 2022-1-152022-1-15计算机学院计算机学院2323例例4(4(续续2)2)2.2.采用采用CPCP规则的直接证明法：规则的直接证明法：1)1) ( ( y)y)(P(y)(P(y)R(x,y) P(R(x,y) P(附加前题附加前题) ) 2)2) P(f(x)P(f(x)R(x,f(x)R(x,f(x)ESES，1) 1) 3)3) P(f(x)P(f(x)T,2)T,2)4)4) ( ( x)(P(x)x)(P(x)Q(x)Q(x)P P5)5) P(f(x)P(f(x)Q(f(x)

26、Q(f(x)US,4)US,4)6)6) Q(f(x)Q(f(x)T,3),5),IT,3),5),I7)7) R(x,f(x)R(x,f(x)T,2)T,2)8)8) Q(f(x)Q(f(x)R(x,f(x)R(x,f(x)T,6),7),IT,6),7),I9)9) ( ( y)y)(Q(y)(Q(y)R(x,y)R(x,y)EG,8)EG,8)10)10)( ( y)y)(P(y)(P(y)R(x,y)R(x,y)( ( y)y)(Q(y)(Q(y)R(x,y) R(x,y) CP,1),9)CP,1),9)11)11)( ( x)(x)( ( y)y)(P(y)(P(y)R(x,y)R

27、(x,y)( ( y)y)(Q(y)(Q(y)R(x,y)R(x,y)EG,10)EG,10)x x是自由变元是自由变元2022-1-152022-1-15计算机学院计算机学院2424例例5 5 所有的有理数都是实数；所有的无理数也是所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理实数；虚数不是实数。因此，虚数既不是有理数也不是无理数。数也不是无理数。解：设解：设Q(x)Q(x)：x x是有理数；是有理数；R(x)R(x)：x x是实数；是实数； N(x)N(x)：x x是无理数；是无理数； C(x)C(x)：x x是虚数；是虚数；( ( x)(Q(x)x)(Q(

28、x)R(x), (R(x), ( x)(N(x)x)(N(x)R(x)R(x)( ( x)(C(x)x)(C(x) R(x)R(x) ( ( x)(C(x)x)(C(x)( (Q(x)Q(x) N N(x)(x)2022-1-152022-1-15计算机学院计算机学院2525(1)(1)( ( x)(Q(x)x)(Q(x)R(x)R(x) P P(2)(2) Q(x) Q(x)R(x)R(x) US(1)US(1)(3)(3)( ( x)(N(x)x)(N(x)R(x)R(x) P P(4)(4) N(x) N(x)R(x)R(x) US(3)US(3)(5)(5)( ( x)(C(x)x)(

29、C(x)R(x)R(x) P P(6)(6) C(x)C(x)R(x)R(x) US(5)US(5)(7)(7) R(x)R(x)C C(x)(x) T(6)ET(6)E2022-1-152022-1-15计算机学院计算机学院2626(8)(8) Q(x) Q(x)C(x)C(x) T(2)(7)IT(2)(7)I(9)(9) N(x) N(x)C(x)C(x) T(4)(7)IT(4)(7)I(10)(10)(Q(x)(Q(x)C(x)C(x) ( (N(x)N(x)C(x)C(x) T(8)(9)T(8)(9)E E(11)(11) C(x)C(x)( (Q Q( (x)x) N N(x)

30、(x) T(10)EIT(10)EI(12)(12) ( ( x)(C(x)x)(C(x)( (Q(x)Q(x) N(x)N(x) ) UG(11)UG(11)2022-1-152022-1-15计算机学院计算机学院2727例例6 6 每个旅客或者坐头等舱或者坐二等舱，每个每个旅客或者坐头等舱或者坐二等舱，每个旅客当且仅当富裕时坐头等舱，有些旅客富裕并旅客当且仅当富裕时坐头等舱，有些旅客富裕并非每个旅客都富裕。因此，有些旅客坐二等舱。非每个旅客都富裕。因此，有些旅客坐二等舱。解：设解：设P(x)P(x)：x x是旅客；是旅客；Q(x)Q(x)：x x坐头等舱；坐头等舱； R(x)R(x)：x

31、x坐二等舱；坐二等舱； S(x)S(x)：x x是富裕的；是富裕的；( ( x)(P(x)x)(P(x)（Q(x)Q(x) R(x),R(x),( ( x)(P(x)x)(P(x)(S(x)(S(x)Q(xQ(x)( ( x)(P(x)x)(P(x) S(x)S(x) ( ( x)(P(x)x)(P(x)S(x)S(x) ( ( x)(P(x)x)(P(x) R(x)R(x) )2022-1-152022-1-15计算机学院计算机学院2828 ( ( x)(P(x)x)(P(x) S(x)S(x) ( ( x)(P(x)x)(P(x)S(x)S(x) P P ( ( x)(P(x)x)(P(x)S(x)S(x) T TE E ( ( x)(P(x)x)(P(x) S(x)S(x) T TE E P(c)P(c) S(c)S(c) ESES P(c) P(c) T TE E S(c) S(c) T TE E ( ( x)(P(x)x)(P(x)（Q(x)Q(x) R(x)R(x) P P P(c)P(c)（Q(c)Q(c) R(c)R(c) USUS2022-1-152022-1-15计算机学院计算机学院2929 Q(c)Q(c) R(c) R(c) T TI I ( ( x)(P(x)x)(P(x)(S(x)(S(x)Q(x)Q(x) P P