离散数学第一章

练习题

一．填空

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: ｙ在ｘ=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??