离散结构习题(完整版)
- 格式：pdf
- 大小：474.10 KB
- 文档页数：16
离散结构习题
第一章 命题逻辑
1、将以下命题进行命题符号化。 (1)李平不但聪明又用功。 (2)李平虽然聪明，但不用功。 (3)李平不但聪明，而且用功。 (4)李平不是不聪明，而是不用功。 2、 命题公式 (p∨ ¬q)的成真赋值为 _______________________。
3、 命题公式 ( p∧ ¬q) ∨ (¬p∧ ¬q) 的成真赋值为 ___________________。 4、 将命题 “没有一个运动员不是强壮的 ”谓词符号化为 ___________________。 5、 下列句子中有（ ）个是命题。 (1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。 A. 1 B . 2 C. 3 D. 4 6、 下列公式中，哪个是永真式（ ） A. q → ( p∧q) B. ( p∧q) →p C. p → ( p∧ q) D. ( p ∨q) → q 、 求命题公式 7 ( p →q) ∧ ( p→ r ) 的主析取范式，主合取范式及其成真成假赋值。 8、 求命题公式 (( p ∨q) →r ) → p 的主析取范式，主合取范式及其成真成假赋值。 9、 求命题公式 p →(q →r) 主析取范式，主合取范式及其成真成假赋值。 10、推理及证明 。 （1）如果我上街 , 我一定去新华书店 . 我没上街 , 所以我没去新华书店 . （2）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物 理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。 （3）如果今天是星期一 , 则要进行英语或离散数学的考试 . 如果英语老师有会 , 则不考 英语. 今天是星期一 , 英语老师有会 , 所以进行离散数学的考试 . 11、某课题组要从 a, b, c, d, e 5 人中派 3 人分别到上海、广州、香港去开会，每个地方只 能去一人 . 已知 a 只想去上海， b 只想去广州， c, d, e 都表示想去广州或香港 . 问该课 题组在满足个人要求的条件下，给出一种派遣方案？
(2) D1 中特定元素 a=2； (3) 函数 f(x) 为 f(2)=3,f(3)=2 ； (4) 谓词 F(x) 为 F(2)=0;F(3)=1;G(x,y) 为 G(i,j)=1,i,j=2,3; L(x,y) 为 L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0; 在解释 I 下，求下列各式的真值。 1) ∀x (F ( x) ∧ G(x,a)) 2) ∃x(F ( f ( x)) ∧G( x, f (x))); 3)∀x∃yL(x, y)
第六章 树
1、下图中 , （ ）是欧拉图。
13、设有向图 D 如图 G3 所示,回答下列问题：
（1）求图 D 的邻接矩阵； （2）求图 D 中长度为 2 的通路数； （3）求图 D 中长度为 2 的回路数； （4）求图 D 的可达矩阵 13、有 7 个人, A 会讲英语 , B 会讲英语和汉语 , C 会讲英语、意大利语和俄语 , D 会讲 日语和汉语 , E 会讲德语和意大利语 , F 会讲法语、日语和俄语 , G 会讲法语和德语 . 问 能否将他们沿圆桌安排就坐成一圈 , 使得每个人都能与两旁的人交谈? 14、证明：若无向图 G 中只有两个奇数度结点，则这两个结点一定是连通的。 15、 设 G 是一个 n 阶无向简单图， n 是大于等于 2 的奇数． 证明图 G 与它的补图 G’ 中 的奇数度顶点个数相等。 16、 证明 K5 和 K3,3 不是平面图 .
第三章 集合
1、 在 1 和 1000 之间 （包括 1 和 1000 在内） 不能被 4 和 5 整除的数有个________________。 2、设 F ( x) : x是有理数， G( x)： x能表示成分数。在一阶逻辑中，命题“没有不能表示成 分数的有理数”可符号化为( ) 。 A. ¬∀x (F (x) ∧ ¬ G( x)) B. ¬∀x (F (x) → ¬G( x)) C. ¬∃x (F ( x) ∧ ¬G(x)) D. ¬∃x ( F( x) → ¬G( x)) 4、设个体域是整数集，则下列命题的真值为真的是( ) 。 A．∃y ∀x ( x .y =1) B．∀x∃y (x. y≠0) C． ∀x ∃y(x. y =y 2) D．∃y ∀x (x .y= x2 ) 5、下列命题中为假命题的是( )。 A．{∅}∈P(∅) B．{∅}⊆P({∅}) C. P(∅)⊆ ∅ D. P(∅)∈P({∅}) 6、求 1 到 1000 之间不能被 5、6、8 整除的数的个数。 7、已知 A，B，C 是三个集合，证明： A-(B∪C)=(A-B)-C.
第四章 二元关系和函数
1、若集合 A＝{a,b},B ＝{0,1,2}, 则 A×B 为_______________；B×A 为______________。 2、设集合A = {1, 2} ，则P(A)为_____________； P(A) ×A为_________________。 3、 设集合A={0, 1}, B={1, 2}, C={0, 1, 2} ， 则A, B 和C的笛卡尔积A×B×C为： _______________。 4、设 R 是定义在集合 A {1, 2, 3, 4} 上的二元关系 R { <1,1> ,< 1, 2> , <2, 3> , <1, 4 >} ，则 R 的对称闭包 s(R) _______________。 5、设 ，则从 到 有 种不同的关系，有 种不同的函数． ）。 6、集合 A {1, 2, , 10}上的关系 R={<x, y>| x +y=10, ∀x, y∈A}，则 R 的性质为（ A、自反的 B 、传递的、对称的 C、对称的 D 、反自反的、传递的 7、设 R, Z, N 分别表示实数、整数和自然数集，设函数 f1: N 1→{0,1,2}，f(x) =x mod3， F2: R→R ,f(x)=2x ，f3: Z→N, f (x)=| x|, f4:N→N×N，f (x)=< x ,x+1> 则上述函数中满射的个数为（ ）。 A. 1 B. 2 C. 3 D. 4 8、设 R 和 S 定义在 P 上，P 是所有人的集合。 R={< x, y> | x, y ∈P, x 是 y 的父亲}， ）。 S={< x, y> | x, y∈ P , x 是 y 的母亲 ，则对于<x, y>∈ S-1 ∘R 表示（ A. x 是 y 的丈夫 B. x 是 y 的妻子
C. x 是 y 的孙子 9、设 A、 C、 10、设 为自然数集 A、为单射而非满 C、为双射 11、设 A、 12、设函数
D. x 是 y 的祖母
分别为实数集、整数集，自然数集，则下列关系中能构成函数的是（ B ） B、 D、 上的函数，且 B、为满射而非单射 D、既非单射又非满射 到 ，则 （ D ）
4、设无向图G＝<V, E>是哈密尔顿图，则V 的任意非空子集V1，都有_______________。 5、设有向图D 为欧拉图，则图D 中每个结点的入度_______________。 6、设完全图 Kn 有 n 个结点(n≥2) ，m 条边，当_______________时，Kn 中存在欧拉回路。 7、设图 G 的邻接矩阵为
1
22、设 f 是 A 上的满射，且 f f f ，证明： f I A ． 则 g f I A, f g IB ． g , f g 1 ，
1
24、 设函数 f ：A B ，g ：B A ， 证明： 若 g f I A, f g IB ， 则f 为 A 的幂集，证明：如果 f 是 A 到 B 的满射，则 g 是 ቤተ መጻሕፍቲ ባይዱ 到 ( A) 的单射．
则 G 的边数为（ ）。 A．5 B．6 C．3 D．4 8、图 G 如图所示，以下说法正确的是（
）．
A．{( a, d)} 是割边 B．{( a, d)} 是边割集 C．{( d, e)} 是边割集 D．{( a, d) ,(a, c)} 是边割集 9、无向图 G 存在欧拉通路，当且仅当（ ）． A．G 中所有结点的度数全为偶数 B．G 中仅有有两个奇数度结点 C．G 连通且所有结点的度数全为偶数 D．G 连通且仅有两个奇数度结点 10、 设图 G=< V， E> ， 其中 V={ a1, a2, a3, a4, a5} ,E ={<a1, a2>， <a2, a4>， <a3, a1>， <a4, a5>， <a5, a2>（1）试给出 G 的图形表示；（2）求 G 的邻接矩阵，关联矩阵（3）判断图 G 是强连通 图、单侧连通图还是弱连通? 11、设有向图 D 如右图所示，求图 D 中长度为 3 的通路数，并指出其中的回路数。
g , f g 1 ．
25、 设函数 f ：A B ，g ：B ( A) ， 对于 b B ，g (b) {x x A f ( x ) b} ， ( A)
第五章 图和特殊图
1、无向连通图是欧拉图的充分必要条件是____________________。
2、已知图 G 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 G 的边数是____________。 3、设给定图 G(如下图所示)，则图 G 的点割集是___________________。
第二章 一阶谓词逻辑
1、将命题 “没有一个运动员不是强壮的 ”谓词符号化为 ___________________。 2、 将下列命题符号化： ________________。 (1)偶数均能被 2 整除 . (2)存在着偶素数 . (3)没有不吃饭的人 . (4)素数不全是奇数 . 3、 公式 ∀xP( x) → ∀xQ(x)的前束范式为 _____________________________。 4、 给定解释 I 如下： (1) D1={2,3} ；
第一章 命题逻辑
1、将以下命题进行命题符号化。 (1)李平不但聪明又用功。 (2)李平虽然聪明，但不用功。 (3)李平不但聪明，而且用功。 (4)李平不是不聪明，而是不用功。 2、 命题公式 (p∨ ¬q)的成真赋值为 _______________________。
3、 命题公式 ( p∧ ¬q) ∨ (¬p∧ ¬q) 的成真赋值为 ___________________。 4、 将命题 “没有一个运动员不是强壮的 ”谓词符号化为 ___________________。 5、 下列句子中有（ ）个是命题。 (1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。 A. 1 B . 2 C. 3 D. 4 6、 下列公式中，哪个是永真式（ ） A. q → ( p∧q) B. ( p∧q) →p C. p → ( p∧ q) D. ( p ∨q) → q 、 求命题公式 7 ( p →q) ∧ ( p→ r ) 的主析取范式，主合取范式及其成真成假赋值。 8、 求命题公式 (( p ∨q) →r ) → p 的主析取范式，主合取范式及其成真成假赋值。 9、 求命题公式 p →(q →r) 主析取范式，主合取范式及其成真成假赋值。 10、推理及证明 。 （1）如果我上街 , 我一定去新华书店 . 我没上街 , 所以我没去新华书店 . （2）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物 理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。 （3）如果今天是星期一 , 则要进行英语或离散数学的考试 . 如果英语老师有会 , 则不考 英语. 今天是星期一 , 英语老师有会 , 所以进行离散数学的考试 . 11、某课题组要从 a, b, c, d, e 5 人中派 3 人分别到上海、广州、香港去开会，每个地方只 能去一人 . 已知 a 只想去上海， b 只想去广州， c, d, e 都表示想去广州或香港 . 问该课 题组在满足个人要求的条件下，给出一种派遣方案？
(2) D1 中特定元素 a=2； (3) 函数 f(x) 为 f(2)=3,f(3)=2 ； (4) 谓词 F(x) 为 F(2)=0;F(3)=1;G(x,y) 为 G(i,j)=1,i,j=2,3; L(x,y) 为 L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0; 在解释 I 下，求下列各式的真值。 1) ∀x (F ( x) ∧ G(x,a)) 2) ∃x(F ( f ( x)) ∧G( x, f (x))); 3)∀x∃yL(x, y)
第六章 树
1、下图中 , （ ）是欧拉图。
13、设有向图 D 如图 G3 所示,回答下列问题：
（1）求图 D 的邻接矩阵； （2）求图 D 中长度为 2 的通路数； （3）求图 D 中长度为 2 的回路数； （4）求图 D 的可达矩阵 13、有 7 个人, A 会讲英语 , B 会讲英语和汉语 , C 会讲英语、意大利语和俄语 , D 会讲 日语和汉语 , E 会讲德语和意大利语 , F 会讲法语、日语和俄语 , G 会讲法语和德语 . 问 能否将他们沿圆桌安排就坐成一圈 , 使得每个人都能与两旁的人交谈? 14、证明：若无向图 G 中只有两个奇数度结点，则这两个结点一定是连通的。 15、 设 G 是一个 n 阶无向简单图， n 是大于等于 2 的奇数． 证明图 G 与它的补图 G’ 中 的奇数度顶点个数相等。 16、 证明 K5 和 K3,3 不是平面图 .
第三章 集合
1、 在 1 和 1000 之间 （包括 1 和 1000 在内） 不能被 4 和 5 整除的数有个________________。 2、设 F ( x) : x是有理数， G( x)： x能表示成分数。在一阶逻辑中，命题“没有不能表示成 分数的有理数”可符号化为( ) 。 A. ¬∀x (F (x) ∧ ¬ G( x)) B. ¬∀x (F (x) → ¬G( x)) C. ¬∃x (F ( x) ∧ ¬G(x)) D. ¬∃x ( F( x) → ¬G( x)) 4、设个体域是整数集，则下列命题的真值为真的是( ) 。 A．∃y ∀x ( x .y =1) B．∀x∃y (x. y≠0) C． ∀x ∃y(x. y =y 2) D．∃y ∀x (x .y= x2 ) 5、下列命题中为假命题的是( )。 A．{∅}∈P(∅) B．{∅}⊆P({∅}) C. P(∅)⊆ ∅ D. P(∅)∈P({∅}) 6、求 1 到 1000 之间不能被 5、6、8 整除的数的个数。 7、已知 A，B，C 是三个集合，证明： A-(B∪C)=(A-B)-C.
第四章 二元关系和函数
1、若集合 A＝{a,b},B ＝{0,1,2}, 则 A×B 为_______________；B×A 为______________。 2、设集合A = {1, 2} ，则P(A)为_____________； P(A) ×A为_________________。 3、 设集合A={0, 1}, B={1, 2}, C={0, 1, 2} ， 则A, B 和C的笛卡尔积A×B×C为： _______________。 4、设 R 是定义在集合 A {1, 2, 3, 4} 上的二元关系 R { <1,1> ,< 1, 2> , <2, 3> , <1, 4 >} ，则 R 的对称闭包 s(R) _______________。 5、设 ，则从 到 有 种不同的关系，有 种不同的函数． ）。 6、集合 A {1, 2, , 10}上的关系 R={<x, y>| x +y=10, ∀x, y∈A}，则 R 的性质为（ A、自反的 B 、传递的、对称的 C、对称的 D 、反自反的、传递的 7、设 R, Z, N 分别表示实数、整数和自然数集，设函数 f1: N 1→{0,1,2}，f(x) =x mod3， F2: R→R ,f(x)=2x ，f3: Z→N, f (x)=| x|, f4:N→N×N，f (x)=< x ,x+1> 则上述函数中满射的个数为（ ）。 A. 1 B. 2 C. 3 D. 4 8、设 R 和 S 定义在 P 上，P 是所有人的集合。 R={< x, y> | x, y ∈P, x 是 y 的父亲}， ）。 S={< x, y> | x, y∈ P , x 是 y 的母亲 ，则对于<x, y>∈ S-1 ∘R 表示（ A. x 是 y 的丈夫 B. x 是 y 的妻子
C. x 是 y 的孙子 9、设 A、 C、 10、设 为自然数集 A、为单射而非满 C、为双射 11、设 A、 12、设函数
D. x 是 y 的祖母
分别为实数集、整数集，自然数集，则下列关系中能构成函数的是（ B ） B、 D、 上的函数，且 B、为满射而非单射 D、既非单射又非满射 到 ，则 （ D ）
4、设无向图G＝<V, E>是哈密尔顿图，则V 的任意非空子集V1，都有_______________。 5、设有向图D 为欧拉图，则图D 中每个结点的入度_______________。 6、设完全图 Kn 有 n 个结点(n≥2) ，m 条边，当_______________时，Kn 中存在欧拉回路。 7、设图 G 的邻接矩阵为
1
22、设 f 是 A 上的满射，且 f f f ，证明： f I A ． 则 g f I A, f g IB ． g , f g 1 ，
1
24、 设函数 f ：A B ，g ：B A ， 证明： 若 g f I A, f g IB ， 则f 为 A 的幂集，证明：如果 f 是 A 到 B 的满射，则 g 是 ቤተ መጻሕፍቲ ባይዱ 到 ( A) 的单射．
则 G 的边数为（ ）。 A．5 B．6 C．3 D．4 8、图 G 如图所示，以下说法正确的是（
）．
A．{( a, d)} 是割边 B．{( a, d)} 是边割集 C．{( d, e)} 是边割集 D．{( a, d) ,(a, c)} 是边割集 9、无向图 G 存在欧拉通路，当且仅当（ ）． A．G 中所有结点的度数全为偶数 B．G 中仅有有两个奇数度结点 C．G 连通且所有结点的度数全为偶数 D．G 连通且仅有两个奇数度结点 10、 设图 G=< V， E> ， 其中 V={ a1, a2, a3, a4, a5} ,E ={<a1, a2>， <a2, a4>， <a3, a1>， <a4, a5>， <a5, a2>（1）试给出 G 的图形表示；（2）求 G 的邻接矩阵，关联矩阵（3）判断图 G 是强连通 图、单侧连通图还是弱连通? 11、设有向图 D 如右图所示，求图 D 中长度为 3 的通路数，并指出其中的回路数。
g , f g 1 ．
25、 设函数 f ：A B ，g ：B ( A) ， 对于 b B ，g (b) {x x A f ( x ) b} ， ( A)
第五章 图和特殊图
1、无向连通图是欧拉图的充分必要条件是____________________。
2、已知图 G 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 G 的边数是____________。 3、设给定图 G(如下图所示)，则图 G 的点割集是___________________。
第二章 一阶谓词逻辑
1、将命题 “没有一个运动员不是强壮的 ”谓词符号化为 ___________________。 2、 将下列命题符号化： ________________。 (1)偶数均能被 2 整除 . (2)存在着偶素数 . (3)没有不吃饭的人 . (4)素数不全是奇数 . 3、 公式 ∀xP( x) → ∀xQ(x)的前束范式为 _____________________________。 4、 给定解释 I 如下： (1) D1={2,3} ；
