离散数学测验题——谓词逻辑答案.doc

离散数学测验题(谓词逻辑部分)一、符号化下列命题。（20分，每题10分）1. 任何两个不同的人都性格不相同。解：设F(x):x是人, H(x,y), x与y相同, L(x,y): x与y性格相同 则原命题对应的谓词公式为：x(F(x)y(F(y)H(x,y)L(x,y) 或xy(F(x)F(y)H(x,y)L(x,y) 2. 尽管有些人爱吃西瓜，但并不是所有人都爱吃西瓜。解：设M(x): x是人，C(x): x爱吃西瓜，则原命题可以表示为前后两个原子命题之间的合取,“有些人爱吃西瓜”可以表示为：；“不是所有人都爱吃西瓜”可以表示为，或者则原命题对应的谓词公式为：，或者 二、说明下列推理的有效性。（45分，每题15分）1. 乌鸦是黑色的，天鹅不是黑色的；所以，天鹅不是乌鸦。解：设B(x): x是乌鸦，M(x): x是天鹅，F(x): x黑色的。则此推理可以表示为：证明：(1) x ( M ( x ) F ( x ) P规则(2)M ( y ) F ( y ) US(1)(3) x ( B( x ) F ( x ) P 规则(4)B( y ) F ( y ) US(3)(5) F ( y ) B ( y ) (4)假言易位(6)M ( y ) B ( y ) (2)(5)假言三段论(7) x( M( x ) B ( x ) UG(6)，证毕。利用反证法证明： 2. 音乐家都教育自己的孩子成为音乐家，如果教育孩子成为科学家，则不会教育孩子成为音乐家。有一个人教育他的孩子去做科学家，所以这个人一定不是音乐家。解:设 M ( x )： x 是音乐家， F ( x )： x 教育自己的孩子成为音乐家， G ( x )： x 教育他的孩子去做科学家。前提：x ( M ( x ) F ( x )， x ( G ( x ) F ( x )， $xG ( x )结论： $x M ( x ) (1) $x G ( x )P 规则(2)G ( c ) ES (3) x ( G ( x ) F ( x ) P 规则(4)G ( c ) F ( c ) US(3)(5) F ( c ) (2)(4)假言推理(6) x ( M ( x ) F ( x ) P 规则(7) M ( c ) F ( c ) US(6) (8) M ( c )(5)(7)拒取式(9) $x M ( x ) UG(8)，证毕。3. 学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是青年博士。 解：令 A(x):x是学术委员会成员，B(x):x是博士，J(x):x是教授，H(x):x是青年人。 前提: x(A(x)B(x)J(x) , $x(A(x)H(x) 结论: $x(A(x)H(x)B(x) 证明 ：(1) $x (A(x)H(x)P (2) A(c)H(c)(1)ES (3) x (A(x)B(x) J(x)P (4) A(c)B(c)J(c)(3)US (5) A(c)(2) 化简 (6) H(c)(2) 化简 (7) B(c)J(c)(4)(5) 假言推理 (8) B(c)(7) 化简 (9) A(c)H(c)B(c)(5)(6)(8) 合取 (10) $x(A(x)H(x)B(x)(9)EG 三、（35分）令：R(x): x是兔子；T(x)：x是乌龟；D(x, y)：x比y跑得快。试用谓词公式符号化以下命题：1. 兔子比乌龟跑得快xy(R(x)T(y)D(x,y)2. 有的兔子比所有的乌龟跑得快$x (R(x) y (T(y) D(x,y)3. 并不是所有的兔子都比乌龟跑得快对第3题，要求符号化的谓词公