离散数学章练习题及答案 下载本文

离散数学第一章

练习题

一.填空

1.公式(p??q)?(?p?q)的成真赋值为 01;10

2.设p, r为真命题,q, s 为假命题,则复合命题(p?q)?(?r?s)的真值为 0 3.公式?(p?q)与(p??q)?(p?q)共同的成真赋值为 01;10

4.设A为任意的公式,B为重言式,则A?B的类型为 重言式

5.设p, q均为命题,在 不能同时为真 条件下,p与q的排斥也可以写成p与q的相容或。

二.将下列命题符合化 1. 7不是无理数是不对的。

解:?(?p),其中p: 7是无理数; 或p,其中p: 7是无理数。 2.小刘既不怕吃苦,又很爱钻研。

解:?p?q,其中p: 小刘怕吃苦,q:小刘很爱钻研 3.只有不怕困难,才能战胜困难。

解:q??p,其中p: 怕困难,q: 战胜困难

或p??q,其中p: 怕困难, q: 战胜困难 4.只要别人有困难,老王就帮助别人,除非困难解决了。

解:?r?(p?q),其中p: 别人有困难,q:老王帮助别人 ,r: 困难解决了 或:(?r?p)?q,其中p:别人有困难,q: 老王帮助别人,r: 困难解决了 5.整数n是整数当且仅当n能被2整除。

解:p?q,其中p: 整数n是偶数,q: 整数n能被2整除 三、求复合命题的真值

P:2能整除5, q:旧金山是美国的首都, r:在中国一年分四季 1. ((p?q)?r)?(r?(p?q)) 2.((?q?p)?(r?p))?((?p??q)?r 解:p, q 为假命题,r为真命题 1.((p?q)?r)?(r?(p?q))的真值为0

2. ((?q?p)?(r?p))?((?p??q)?r的真值为1 四、判断推理是否正确 设y?2x为实数,推理如下:

若y在x=0可导,则y在x=0连续。y 在x=0连续,所以y在x=0可导。

解:y?2x,x为实数,令p: y在x=0可导,q: y在x=0连续。P为假命题,q为真命题,推理符号化为:(p?q)?q?p,由p,q得真值可知,推理的真值为0,所以推理不正确。

五、判断公式的类型

1,(?(q?p)?((p?q)?(?p?q)))?r 2. (p??(q?p))?(r?q) 3. (p??r)?(q?r)

解:设三个公式为A,B,C则真值表如下: p, q ,r A B 000 1 0 001 1 0 010 1 0 011 1 0 100 1 0 101 1 0 110 1 0 111 1 0 由上表可知A为重言式,B为矛盾式,C为可满足式。 C 1 0 1 1 1 1 0 1 第二章练习题

一.填空

1.设A为含命题变项p, q, r的重言式,则公式A?((p?q)?)的类型为 重言式 2.设B为含命题变项p, q, r的重言式,则公式B?((p?q)?)的类型为矛盾式 3.设p, q为命题变项,则(?p?q)的成真赋值为 01 ;10

4.设p,q 为真命题,r, s为假命题,则复合函数(p?r)?(?q?s)的成真赋值为__0___ 5.矛盾式的主析取范式为___0_____

6.设公式A为含命题变项p, q, r又已知A的主合取范式为M0?M2?M3?M5则A的主合取范式为 m1?m4?m6?m7

二、用等值演算法求公式的主析取范式或主合取范式 1.求公式?(?(p?q))?(?q??p)的主合取范式。 解:

?(?(p?q))?(?q??p)?(p?q)?(p?q)?p?q??p?q?M2

2.求公式((p?q)?(p?q))?(q?p)的主析取范式,再由主析取范式求出主合取范式。 解:

三、用其表达式求公式(p?q)?r的主析取范式。 解:真值表 p,q,r 000 001 010 011 100 101 110 111 0 1 0 1 1 0 0 1 由上表可知成真赋值为 001;011;100;111

四、将公式p?(q?r)化成与之等值且仅含??,??中连接词的公式 解:p?(q?r)?p?(?q?r)??p?(?q?r)??(p?q??r) 五、用主析取范式判断?(p?q)与(p?q)?(?(p?q))是否等值。 解:

?(p?q)??((p?q)?(q?p))??((?p?q)?(?q?p))??(?p?q)??(?q?p)?(p??q)?(q??p)?(p?(q??p))?(?q?(q??p))?(p?q)?(?(q?p))所

以他们等值。 第四章 习题 一,填空题 1.设F(x): x具有性质F,G(x): x具有性质G,命题“对所有x的而言,若x具有性质F,则x具有性质G”的符号化形式为 ?x(F(x)?G(x)

2.设F(x): x具有性质F,G(x): x具有性质G,命题“有的x既有性质F,又有性质G”的符号化形式为 ?x(F(x)?G(x)

3. 设F(x): x具有性质F,G(y): y具有性质G,命题“对所有x都有性质F,则所有的y都有性质G”的符号化形式为 ?xF(x)??yG(y)

4. 设F(x): x具有性质F,G(y): y具有性质G,命题“若存在x具有性质F,则所有的y都没有性质G”的符号化形式为 ?xF(x)??y?G(y)

5.设A为任意一阶逻辑公式,若A中__不含自由出现的个体项_____,则称A为封闭的公式。 6.在一阶逻辑中将命题符号化时,若没有指明个体域,则使用 全总 个体域。 二.在一阶逻辑中将下列命题符号化

1.所有的整数,不是负整数就是正整数,或是0。

解:?xF(x)?(G(x)?H(x)?R(x)),其中F(x):x是整数,G(x):x是负整数,H(x):x是正整数,R(x):x?0

2.有的实数是有理数,有的实数是无理数。

解:?x(F(x)?G(x))??y(F(y)?H(y)),其中,F(x):x是实数,G(x):x是有理数,H(y):y是无理数

3.发明家都是聪明的并且是勤劳的,王进是发明家,所以王进是聪明的并且是勤劳的。 解:(?x(F(x)?(G(x)?H(x)))?F(a))?(G(a)?H(a)),其中:F(x):x是发明家,G(x):x是聪明的,H(x):x是勤劳的,a:王前进 4.实数不都是有理数。

解:??x(F(x)?G(x)),其中F(x):x是实数,G(x):x是有理数 5.不存在能表示成分数的有理数。

解:?xF(x)??G(x),其中:F(x):x是无理数,G(x):x能表示成分数 6.若x与y都是实数且x>y,则x+y>y+z

?x?y((F(x)?F(y)?H(x,y)?H(x?z,解:

y?z)),F(x):x是实数,H(x,y):x?y 其中,

三.给定解释I如下:

(a)个体域为实数集合R; (b)特定元素a?0; (c)特定函数f(x,y)?x?y,(d)特定谓词F(x,y):x?y,x?R,y?R

x?R,y?R

G(x,y):x?y,给出下列公式在I的解释,并指出他们的真值: 1.?x?y(G(x,y)??F(x,y))

解:?x?y((x?y)?(x?y)),即对任意的实数,x,y,则x?y;真值为1 2.?x?y(F(f(x,y),a)?G(x,y))

解:?x?y(x?y?0?(x?y)),即对任意的实数x,y若x?y?0,则x?y,其真值为0

3.?x?y(G(x,y)??F(f(x,y),a))

解:?x?y((x?y)?(x?y?0)),即对任意的实数x,y若x?y,则x?y?0,其真值为1 4.?x?y(Gf(x,y),a)?F(x,y))

解:?x?y((x?y?0)?x?y)),即对任意的实数x,y若x?y?0,则x?y,其真值为0 四.给定解释I如下:

(a)个体域D=N; (b)特定元素a?2 (c)N上函数f(x,y)?x?y,(d)N上谓词F(x,y):x?y

给出下列公式在I下的解释,并指出他们的真值: 1.?xF(g(x,a),x)

解:?x(2x?x),即对任意的自然数x,都有2x?x,真值为0 2.?x?y(F(f(x,a),y)?F(f(y,a),x))

解:?x?y((x?2?y)?(y?2?x)),即对任意自然数x,y若x?2?y,则y?2?x;其真值为0

3.?x?y?zF(f(x,y),z)

解:?x?y?z(x?y?z),即对任意的自然数x,y,都存在z,使得x?y?z;真值为1 4.?xF(f(x,x),g(x,x)) 解:?x(2x?g(x,y)?x?y;

x2),即存在自然数x使得2x?x,其真值为1

2第六章 习题 一,填空

1.设A??2,a,?3?,4?, B???,4,?a?,3?,则A?B?____?2,a,?3?,{a},3,??______

1,??1,2???,则P(A)?____{?,{{1}},{{{1,2}}},{{1},{{1,2}}}_________ 2.设A????1?1,2??,则P(A)?____{?,{{1}},{{1,2}},{{1},{1,,2}}}________ 3.设A????1,2?,则P(A)?____{?,{1},{2},{1,2}}_________ 4. 设A??5.设[a,b], (c,d)代表实数区间,那么([0,4]?[2,6])?(1,3)?____[3,4]________

1,2,3?,X?Z??2,3,4?,若Z?Y,则一定有6.设X,Y,Z为任意集合,且X?Y??