离散数学练习题第一章一•填空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: y在x =0可导，q: y在x=0连续。

P为假命题，q为真命题，推理符号化为：(p q) q p，由p, q得真值可知，推理的真值为0,所以推理不正确。

五、判断公式的类型1，( (q p) ((p q) ( p q))) r2. (p (q p)) (r q)3. (p r) (q r)•填空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)的成真赋值为5•矛盾式的主析取范式为6•设公式A 为含命题变项p, q, r 又已知A 的主合取范式为M 0 M 2 M 3 M 5则A 的p,q,r(p q) r0000011010 0 011 1100 11010 110 0 1111r 的主析取范式。

三、用其表达式求公式 (p 解：真值表 解：p (qr) p (q r) p ( q r) (p qr)五、用主析取范式判断(pq)与(pq)( (p q))是否等值。

解：(p q) ((p q) (q p))(( p q) ( q p)) (p q) (q p) (p q) (q p) (p (qp))( q (q p)) (pq)((q p))所以他们等值。

四、将公式p (q r)化成与之等值且仅含 中连接词的公式第二章练习题1.求公式 (p q)) ( qp)的主合取范式。

解："(p q)) p) (p q) (p q) p q2•求公式 ((p q) (p q)) (qp)的主析取范式，再由主析取范式求出主合取范式。

q)) p) (q((p q) (P q (q (p q ) 0m 3(q (qp) M((p q) ( p q)) (q p) p)) ((q p) q) (p q) qM 1M2q)由上表可知成真赋值为001 ; 011 ; 100; 111第四章习题一，填空题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三.给定解释1如下：(a)个体域为实数集合R;(b)特疋兀素a 0 ；(c)特定函数f (x, y) x y,x R, y R(d)特定谓词F (x, y): x y,G(x, y):x y, x R, y R给出下列公式在1的解释, 并指出他们的真值：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 y 0,则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如下:⑻个体域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 ；其真值为03. x y zF( f (x, y),z)解：x y z(x y z)，即对任意的自然数x, y，都存在z，使得x y z ;真值为14. xF(f (x, x),g(x, x))打 2 2x )，即存在自然数x使得2x x，其真值为1解：x(2x第六章习题一，填空1•设A 2,a, 3,4，B ,4, a ,3，则A B ________________ 2,a, 3,{a},3, ____ 2.设A 1 , 1,2 ，则P(A) —{ ,{{1}}, {{{ 1,2}}}, {{1}, {{1,2}}} ______________ 3•设A 1 1,2，则P(A) ____{ ，{{1}}，{{1,2}}，{{1}，{1，,2}}} _________ 4•设A 1,2，则P(A) ____{ ，{1}，{2}，{1,2}} _________5•设[a,b], (c,d)代表实数区间，那么([0,4] [2,6]) (1,3) ____[3,4] ________6•设XY为任意集合，且X Y 1,2,3 ，X Z 2,3,4，若Z Y,则一定有—2 Z;3 Z ______(1 Z; 2 Z; 3 Z; 4 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}三、设A 1,2,3,4,5,6 ， B 2,4,6 ，C 3 x|x n,n N,x15，求: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为会打排球的人数。

A=12,B=10~（A B）=5A B=25-5=20A B-A=8A B=10-8=2第七章习题设x,y 5 y 1,2x ，求x,y解：由有序相等的充要条件：y 1解得：5 2x2.已知A 0,1解：(1) A B 0,1 1,2 ，试确定下列集合(1) A B, (2) A 1 B0,2 , 1,1 1,2(3) A A BA(2)0,1,1 ,0,1 , 1,10,1,2 , 1,1,11,2, 1,1,2A (3) AB0,0,1 ,0,00,1,10,1, 1,1,1, 1,1 ,, 1,0,11,0 1,2, 0,0,2 , 0,1,2 , 1,1,2 1,0,2P143 页13题1,2 , 2,4 3,3 1,3 , 2,4 , 4,2求：B, B, domA, , domB, dom(A B), ranA解：1,2 , 1,3 , 2,4 3,3 , 4,22,4domA 1,2,3domB 1,2,4ranA 2,3,4。