离散数学练习题第一章一．填空1. 公式(p q) ( p q )的成真赋值为01 ；102. 设p, r 为真命题，q, s 为假命题，则复合命题(p q) ( r s) 的真值为03. 公式(p q)与(p q) (p q )共同的成真赋值为01；104. 设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)) 的真值为02. (( 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)))，(p(q p)) (r q)2.3.(p r)(q r)解：设三个公式为A,B,C 则真值表如下：由上表可知A为重言式，B 为矛盾式，C为可满足式第二章练习题一．填空1. 设A为含命题变项p, q, r 的重言式，则公式A ((p q) ) 的类型为重言式2. 设B为含命题变项p, q, r 的重言式，则公式B ((p q) )的类型为矛盾式3. 设p, q 为命题变项，则( p q) 的成真赋值为01 ；104．设p,q 为真命题，r, s 为假命题，则复合函数(p r) ( q s) 的成真赋值为__0___5. 矛盾式的主析取范式为___0 _____6. 设公式A为含命题变项p, q, r 又已知A的主合取范式为M0 M 2 M 3 M 5则A的主合取范式为m1 m4 m6 m7、用等值演算法求公式的主析取范式或主合取范式1. 求公式( (p q)) ( q p) 的主合取范式。

( (p q)) ( q p) (p q) (p q) p q 解：p q M 22.求公式((p q) (p q)) (q p)的主析取范式，再由主析取范式求出主合取范式解：三、用其表达式求公式(p q) r 的主析取范式。

解：真值表由上表可知成真赋值为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 02. 有的实数是有理数，有的实数是无理数。

解：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)0；特定元素(c) 特定函数f (x, y) xy, x R, y R(d) 特定谓词F(x,y): x y, G(x, y): x y, x R, y R给出下列公式在I 的解释，并指出他们的真值：1.x y(G(x, y)F(x,y))解：x y((x y)(x y)) ，即对任意的实数，x,y ，则x y ；真值为12.x y(F(f (x, y), a)G(x,y))解：x y(x y 0(x y)) ，即对任意的实数x, y若x y0, 则x y,其真值为03. x y(G(x,y) F( f (x,y),a))解：x y((x y) (x y 0)) ，即对任意的实数x,y若x y, 则x y 0, 其真值为14.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, g(x,y) x y;(d)N 上谓词F(x,y) :x y给出下列公式在I 下的解释，并指出他们的真值：1. xF(g(x,a),x)解：x(2x x) ，即对任意的自然数x，都有2x x，真值为02. 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 x2) ，即存在自然数x使得2x x2，其真值为1 第六章习题一，填空1.设A2,a, 3,4 ，B,4, a ,3 ，则A B 2,a, 3 ,{a},3, __2.设A1, 1,2 ，则P(A) ____ { ,{{ 1}}, {{{ 1,2}}},{{1}, {{ 1,2}}}______________________3. 设A 1 1,2 ，则P(A)____ { ，{{1}} ，{{1,2}}，{{1} ，{1 ，,2}}}4. 设A1,2 ，则P(A) ____{ ，{1} ，{2} ，{1,2}}5.设[a,b], (c,d) 代表实数区间，那么([0,4] [ 2,6]) (1,3) ___________________ [3,4] __________6. 设X,Y,Z 为任意集合，且X Y 1,2,3 ，X Z 2,3,4 ，若Z Y,则一定有2 Z;3 Z ___________7.设A, 则(A A) A ________________ ___________二，简答题1.设I 1,2, 12 ，A 1,3,5,7,9,11 ，B 2,3,5,7,11 ，C 2,3,6,12 ，D 2,4,8 ，计算：A B; A C ; C (A B); A B; C D ;B D ;A B {1,2,3,5,7,9,11} A C ={3} C （A B）={6, 12} A B={1, 9}C D ={3,6,12} B D ={3,4,5,7,8,11}2. 设A a , a,b ，求：A; AA ={a,b}A={a}3三、设A 1,2,3,4,5,6 ，B 2,4,6 ，C x|x n3,n N,x 15 ，求:A C ;B A; P（B）C={1,8}A C ={1,2,3,4,5,6,8}B A=P（B）={ ,{2},{4},{6},{2,4},{2,6},{4,6},{2,4,6}}四：一个班50个学生，在一次考试中有26 人得5 分，在第二次考试中有21 人得5 分，如果两次考试中没有得5 分的有17 人，那么两次考试中都得5 分的有都少人？（提示：应用包含排斥原理）答：设A为第一次考试得5分的人，B为第二次考试得5 分的人。

A=26,B=21~（A B）=17A B=50-17=33A B-A=7A B=21-7=14五，一个班25个学生，会打篮球的有12 人，会打排球的有10人，两种球都不会打的有5 人，那么两种球都会打的有多少人？（提示：应用包含排斥原理）答：设A为会打篮球的人数，B 为会打排球的人数。