离散12习题

离散12习题(总22页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第1章习题答案1. 说明下列语句哪些是命题及命题的真值（1）(2)(5)(7)(8)(9)(10)(11)是命题，其中（1）（5）（8）（10）是真命题，（9）的真值现在不知道。

2. 将下列命题符号化。

（1） ,p q ∧其中:p 小王聪明，:q 小王用功。

（2） ,p q ∧⌝其中:p 天气很冷，:q 下雪。

（3） ,p q ∨其中:p 晚上有英语课，:q 晚上有数学课。

（4）(),r p q →∨其中:p 你年满14岁，:q 你身高超过米，:r 你坐过山车。

（5） p q →，其中 :p 产量上升，:q 工资提高。

（6） ()p q ⌝∧，其中:p 销量下降，:q 价格上涨。

（7） p q →，其中:p 你给我发个电子邮件，:q 我有你的邮件地址。

（8） p q ↔，其中 :p 两个三角形全等，:q 它们的三条对应边相等。

（9）(),r p q s →∧∧⌝其中:p 阳光充足，:q 在夏天，:s 下雨，:r 我去游泳。

（10）p q ↔，其中:p 热带风暴来临，:q 下大雨。

3.（1）小王至少会讲汉语或英语的一种。

（2） 小王会讲汉语和英语 (3) 小王会讲汉语但不会英语1（4）小王不会讲汉语或不会讲英语。

（5）小王会讲汉语。

（6）小王既不会讲汉语也不会讲英语是不可能的。

4. 设命题p :天下雨，q ：我去打球，r :我有空。

用自然语言写出下列命题。

（1）如果我去打球，那么一定是我有空且天没下雨；我有空且天没下雨我就一定去打球。

(2) 若天下雨或我有空我就去打球。

(3) (qr )˄(rq )(4) 天下雨或我有空那是不可能的。

5. 设命题p :这个材料很有趣；q :这些习题很难；r :学生喜欢这门课。

（1）p q ∧ （2）()p q r ∧⌝→ （3）p r ↔ （4）p q r ⌝∧⌝∧⌝ （5）p q ∀6. 构造下列各题的真值表，写出成真赋值和成假赋值。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散数学练习题(含答案)题目1. 对于集合 $A={1,2,3,...,10}$ 和 $B={n|n是偶数，2<n<8}$，求 $A \cap B$ 的元素。

2. 存在三个可识别的状态A,B,C。

置换群 $S_3$ 作用在状态集上。

定义四个动作：$α: A → C, β: A → B, γ: C→ A, δ: B→ C$。

确定式子，描述 $\{α,β,γ,δ\}$ 的乘法表。

3. 证明 $\forall n \in \mathbb{N}$，合数的个数不小于$n$。

4. 给定一个无向带权图，图中每个节点编号分别是$1,2,...,n$，证明下列结论：a. 如果从节点$i$到$j$只有一条权值最小的路径，则这条路径的任意子路径都是最短路径。

b. 如果从节点$i$到$j$有两条或两条以上权值相等的路径，则从$i$到$j$的最短路径可能不唯一。

答案1. $A \cap B = \{2,4,6\}$。

2. 乘法表：3. 对于任意$n$，我们可以选择$n+1$个连续的自然数$k+1,k+2,...,k+n,k+n+1$中的$n$个数，其中$k \in \mathbb{Z}$。

这$n$个数构成的$n$个正整数均为合数，因为它们都至少有一个小于它自身的因子，所以不是质数。

所以合数的个数不小于任意$n$。

4.a. 根据题意，从$i$到$j$只有一条权值最小的路径，即这条最短路径已被确定。

如果从这条路径中任意取出一段子路径，假设这段子路径不是这个节点到$j$的最短路径，那么存在其他从$i$到$j$的路径比这段子路径更优，又因为这条路径是最短路径，所以这段子路径也一定不优于最短路径，矛盾。

所以从这条路径中任意取出的子路径都是最短路径。

b. 如果从节点$i$到$j$有多条权值相等的路径，则这些路径权值都是最短路径的权值。

因为所有最短路径的权值相等，所以这些路径的权值就是最短路径的权值。

所以从$i$到$j$的最短路径可能不唯一。

离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合1、（）已知集合A的元素个数为10，则集合A的幂集的基=102。

2、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

2、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

3、( ) 已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B={Ф}。

4、（）已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B=Ф。

5、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

6、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

7、（）已知集合A的元素个数为n，则A×A的幂集的元素个数为n2。

8、（）已知两个集合A、B，则A-B是由属于B但不属于A的元素构成的集合。

⼆、第⼆章—⼆元关系1、（）若R是A上的⼆元关系，I A是A上的恒等关系，则当且仅当I A∈R时，R是A上的⾃反关系。

2、（√）若R是集合A上的⼆元关系，且当（a，b）∈R且（a，c）∈R时，就有（b，c）∈R，则R是A 上的可传递关系。

3、（）设A是集合，A1、A2、．．．A n都是A的⾮空⼦集，令S={A1，A2，．．．,A n}，则如果S是集合A的⼀个划分，那么S⼀定是集合A的⼀个完全覆盖；反之亦然。

5、（）R是⾮空集合A上的等价⼆元关系，则A关于R的商集A/R是集合A的⼀个划分，但不是A的⼀个完全覆盖。

6、（）已知集合A有4元素，易知集合A共有24个互不相同的⼦集合，所以在集合A上⼀共可定义24个互不相同的⼆元关系。

7、（）若R1和R2都是集合A上的可传递⼆元关系，则R1∪R2也是A上的传递关系。

8、（）设R是有限的⾮空集合A上的偏序关系，则A必有极⼤（⼩）元和最⼤（⼩）元。

9、（）若R1和R2都是集合A上的相容关系，则R1∩R2也是A上的相容关系。

10、（）若R1和R2都是集合A的可传递⼆元关系，则R1∩R2也是A上的传递关系。

第二部分:.集合1.若集合A 上的关系R 是对称的，则1R -也是对称的。

( )2.数集合上的不等关系()≠可确定A 的一个划分。

( )3.设A ，B ，C 为任意集合，若A B A C ⨯=⨯，则 B C =。

( )4.函数的复合运算“。

”满足结合律。

( )5.A ，B ，C 为任意集合，若 A B A C ⋃=⋃ 则B C =。

( )6.设R 是实数集，R 上的关系R (){},2,,x y x y x y R =-<∈，则R 是相容关系。

() 7.设,A ≤是偏序集，B A ⊆，则B 的极大元b B ∈且唯一。

( )8.设{}1,2A =，{}B a =，则()222A B A B ⋃⋃=。

（注 其中 2A 为()A ϕ） ( )9.设 {}0,1A =，{}1,2B =， 则{}20,1,1,0,1,2,1,0,1,1,0,2A B ⨯=。

( )10.集合A 上的恒等关系是一个双射函数。

( )11.设A ，B 为任意集合，不能A B ⊂ 且A B ∈。

( )12.设R 是集合A 上的关系，若12,R R 是对称的， 则 12R R 也是对称的。

( )1. 设A ＝{}∅，B ＝(())P P A ，下列各式中哪个是错的 ( )A. B ∅⊆B. {}B ∅⊆C. {{}}B ∅∈D. {,{}}()P A ∅∅⊆2. 设Z 为整数集，下面哪个序偶不构成偏序集 ( )A. Z,<〈〉 (<：小于关系)B. Z,〈≤〉 (≤：小于等于)C. Z,=〈〉 (＝：等于关系)D. Z,|〈〉 (|：整除关系)3. 设集合{}4,3,2,1=A ，A 上的二元关系{},4,3,4,2,3,2,1,1=R则R 具有 ( )A.自反性B.对称性C.传递性D. 以上答案都不对4. 设{}d c b a A ,,,=，下面哪一个是A 的划分 （ ）A.{}{}{}d c b a ,,,,ΦB. {}{}d c b a ,,,C. {}{}{}{}d a c b a ,,,,D. {}{}{}c b a ,,5. 设A ＝∅，B={∅,{∅}}，则B A -是 ( )A. {{∅}}B. {∅}C. {∅,{∅}}D. ∅6. 下图描述的偏序集中，子集{b,e,f}的上界为 ( )A. b,cB. a,bC. bD. a,b,c7. 设集合{}{}ΦΦ=,A , 则A 的幂集为： ( )A. {}{}ΦΦ, B. {}{}{}{}{}{}ΦΦΦΦΦ,,,, C. {}{}{}{}ΦΦΦ,, D. {}{}{}{}{}{}{}ΦΦΦΦΦ,,,, 8. 若Q P Q P ⋃=⋂, 则P, Q 要满足的条件为 （ ）A. Q P ⊆B. P Q ⊆C. Q 为空集D. P=Q``````````````````````````````9. 在０ ∅之间应填入的符号为 ( )A. ＝B. ⊂C. ∈D. ∉10. 设,A 〈≤〉是偏序集，B A ⊆，下面结论正确的是 ( )A. B 的极大元b B ∈且唯一B. B 的极大元b A ∈且不唯一C. B 的上界b B ∈且不唯一D. B 的上确界b A ∈且唯一11. 集合{}4,3,2,1=I , I 上的关系 R={4,43,44,1,3,3,3,2,23,1,1,1，则R 是 （ ）A. 反对称的B. 传递的C.反自反的D. 自反的12. 设S A B ⊆⨯，下列各式中哪个是正确的 ( )A. domS B ⊆B. domS A ⊆C. ranS A ⊆D. domS ranS S ⋃=13. 设A ＝｛1,2,3,4,5｝，下面哪个集合等于A ( )A. ｛1,2,3,4,5,6｝B. {x |x 是整数且225x ≤}C. {x |x 是正整数且5x ≤}D. {x |x 是正有理数且5x ≤}14. 设A ＝｛｛1,2,3｝,{4,5},{6,7,8}｝，下列各式中哪个是错的 ( )A. A ∅⊆B. {6,7,8}A ∈C. {{4,5}}A ⊂D. {1,2,3}A ⊂15. 设集合X ≠∅，则空关系X ∅不具备的性质是 ( )A. 自反性B. 反自反性C. 对称性D. 传递性``````````````````````````````````````````````16. 集合A 的一个划分，确定A 的元素间的关系为 ( )A. 全序关系B. 等价关系C. 偏序关系D. 拟序关系17. 设{}d c b a A ,,,=，下面哪一个是A 的划分 ( )(A) {}{}{}d c b a ,,,,Φ (B){}{}d c b a ,,, (C) {}{}{}{}d a c b a ,,,, (D) {}{}{}c b a ,,18. 设集合A ＝{0, b }, B ={1, b , 3}, 则A ⋃B 上的恒等关系是 ( )(A) {<0, 0>, <1, 1>, <3, 3>} (B){<0, 0>, <1, 1>, <b , b >,<3, 3>}(C) {<1, 1>, <b , b >, <3, 3>} (D) {<0, 1>,<1, b > , <b , 3>, <3, 0>}19. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ⋂C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >}(C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}20. 设A , B , C 都是集合，如果A ⋂C ＝B ⋂C ，则有 ( )(A) A ＝B (B) A ≠B(C) 当A －C ＝B －C 时,有A =B (D) 当C =E 时, 有A ≠B21. 设集合A ＝{∅，a }，则幂集P (A )＝ ( )(A){,{},{,}}a a ∅∅ (B){{},{},{,}}a a ∅∅(C){,{},{},{,{}}},}a a A ∅∅∅ (D){,{},{},{,}}a a ∅∅∅22. 集合A 上的等价关系R ，决定了A 的一个划分，该划分就是 ( )A. 并集A RB. 交集A RC. 差集A R -D. 商集/A R23. 设1R 和2R 是集合A 上的任意关系，则下列命题为真的是 ( )A. 若1R 和2R 是自反的，则12R R 也是自反的B. 若1R 和2R 是反自反的，则12R R 也是反自反的C. 若1R 和2R 是对称的，则12R R 也是对称的D. 若1R 和2R 是传递的，则12R R 真也是传递的24. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ⋂C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >}(C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}25. 设A , B , C 都是集合，如果A ⋂C ＝B ⋂C ，则有 ( )(A) A ＝B (B) A ≠B(C) 当A －C ＝B －C 时,有A =B (D) 当C =E 时, 有A ≠B26. 设集合A ＝{∅，a }，则幂集P (A )＝ ( )(A){,{},{,}}a a ∅∅ (B){{},{},{,}}a a ∅∅(C){,{},{},{,{}}},}a a A ∅∅∅ (D){,{},{},{,}}a a ∅∅∅27. 集合A 上的关系R 是相容关系的必要条件是 ( )A. 自反的，反对称的B. 反自反的，对称的C. 传递的，自反的D. 自反的，对称的28. 集合{1,2,,10}A = 上的关系R={x,y |x+y=10 x,y }A ∈且则R 的性质为 ( )A. 自反的B. 对称的C. 传递的，对称的D. 反自反的，传递的29. 下面关于集合的表示中，正确的是 ( )A. 0φ=B. {}φφ∈C. φφ∈D. {,}a b φ∈30. 设{}c b a A ,,=，{}2,1=B ，则从A 到B 的所有函数集合中有 个函数。

离散数学试题与答案试卷一一、填空 20% （每小题2分）1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。

2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。

3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为。

6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。

7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

8．图的补图为 。

9．设A={a ，b ，c ，d} ，A 上二元运算如下：* a b c dA BCa b cda b c db c d ac d a bd a b c那么代数系统<A，*>的幺元是，有逆元的元素为，它们的逆元分别为。

10．下图所示的偏序集中，是格的为。

二、选择20% （每小题2分）1、下列是真命题的有（）A．}}{{}{aa⊆；B．}}{,{}}{{ΦΦ∈Φ；C．}},{{ΦΦ∈Φ；D．}}{{}{Φ∈Φ。

2、下列集合中相等的有（）A．{4，3}Φ⋃；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。

3、设A={1，2，3}，则A上的二元关系有（）个。

A．23 ；B．32 ；C．332⨯；D．223⨯。

4、设R，S是集合A上的关系，则下列说法正确的是（）A．若R，S 是自反的，则SR 是自反的；B．若R，S 是反自反的，则SR 是反自反的；C．若R，S 是对称的，则SR 是对称的；D．若R，S 是传递的，则SR 是传递的。

5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下|}||(|)(,|,{tsApt st sR=∧∈><=则P（A）/ R=（）A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“⊆”的哈斯图为（）7、下列函数是双射的为（）A．f : I→E , f (x) = 2x ；B．f : N→N⨯N, f (n) = <n , n+1> ；C．f : R→I , f (x) = [x] ；D．f :I→N, f (x) = | x | 。

习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）P：天下雨 Q：我去教室┐P → Q（2）P：你去教室 Q：我去图书馆 P → Q（3）P，Q同（2） Q → P（4）P：2是质数 Q：2是偶数 P∧Q3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。

（2）如果我去教室，那么明天不是晴天，我也不去图书馆。

（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。

习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(P → Q) →R，P → Q，R，P，Q（2）(┐P∨Q) ∨（R∧P），┐P ∨ Q，R∧P，┐P，Q，R，P（3）((P → Q) ∧ (Q → P)) ∨┐(P → Q))，(P → Q) ∧(Q → P)，┐(P → Q)，P → Q，(Q → P)，P → Q，P，Q，Q，P，P，Q3、（1）((P → Q) → (Q → P)) → (P → Q)（2）((P → Q) ∨ ((P → Q) → R))→ ((P → Q) ∧ ((P → Q) → R)) （3）(Q → P∧┐P) → (P∧┐P → Q)4、(P → Q) ∨ ((P∧Q) ∨ (┐P∧┐Q)) ∧ (┐P∨Q)习题1.31、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1（2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0（3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0（4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1（5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 13、（1）原式 <=> F→Q <=> T 原式为永真式（2）原式 <=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)<=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式（3）原式 <=> ┐(P∧Q) ←→┐(P∧Q) <=> T 原式为永真式（4）原式 <=> P∧(Q∨R) ←→ P∧(Q∨R) <=> T 原式为永真式（5）原式 <=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满足式（6）原式 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式（7）原式 <=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P<=> T∧┐P <=> ┐P 原式为可满足式（8）原式 <=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R)<=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R)<=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R∨R))<=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式4、（1）左 <=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P∨┐Q) <=> 右（2）左 <=> ┐(┐P∨Q) <=> 右（3）左 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右（4）左 <=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中<=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P)<=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P)<=> (P∨Q)∧┐(P∧Q) <=> 右∧(⌝R∨Q)⇔⌝(P∨Q)∨Q⇔右(5)左⇔(⌝P∨Q)5.(1)左⇒Q⇒⌝P∨Q⇒右(2)(P→(Q→R))→((P→Q)→(P→R))⇔⌝(⌝P∨⌝Q∨R)∨⌝(⌝P∨Q) ∨(⌝P∨R)⇔(P∧Q∧⌝R)∨(P∧⌝Q)∨⌝P∨R⇔(P∧Q∧⌝R)∨((P∨⌝P)∧(⌝Q∨⌝P))∨R⇔(P∧Q∧⌝R)∨(⌝Q∨⌝P∨R)⇔(P∧Q∧⌝R) ∨⌝(P∧Q∧⌝R)⇔T故P→(Q→R)⇒(P→Q)→(P→R)(3).(P→Q)→(P→P∧Q)⇔⌝(⌝P∨Q)∨⌝P∨(P∧Q)⇔⌝(⌝P∨Q)∨(⌝P∨P)∧(⌝P∨Q)⇔⌝(⌝P∨Q)∨(⌝P∨Q)⇔T故P→Q⇒P→P∧Q(4).((P→Q) →Q) →P∨Q⇔⌝(⌝(⌝P∨Q) ∨Q) ∨P∨Q⇔((⌝P∨Q)∧⌝Q)∨P∨Q⇔(⌝P∧⌝Q)∨(Q∧⌝Q) ∨P∨Q⇔⌝(P∨Q)∨(P∨Q)⇔T故(P→Q) →Q⇒P∨Q(5).((P∨⌝P)→Q)∧((P∨⌝P)→R)→(Q→R)⇔⌝((⌝T∨Q)∧(⌝T∨R)) ∨⌝Q∨R⇔⌝(Q∧R)∨⌝Q∨R⇔⌝Q∨⌝R∨⌝Q∨R⇔⌝Q∨T⇔T故((P∨⌝P) →Q)∧((P∨⌝P)→R)⇒Q→R(6)左⇔(Q→F)∧(R→F)⇔(⌝Q∨F)∧(⌝R∨F)⇔⌝Q∧⌝R⇒⌝R⇒⌝R∨Q⇔右6.(1)原式⇔(⌝P∧⌝Q∧R)(2)原式⇔⌝P∨⌝Q∨P⇔⌝(P∧Q∧⌝P)(3)原式⇔P∨(Q∨⌝R∨P)⇔P∨Q∨⌝R⇔⌝(⌝P∧⌝Q∧R)7.(1)原式⇔⌝(⌝P∨⌝Q∨P)(2)原式⇔(⌝P∨Q∨⌝R) ∧⌝P∧Q⇔⌝(⌝(⌝P∨Q∨⌝R)∨P∨⌝Q)(3)原式⇔⌝P∧⌝Q∧ (R∨P) ⇔⌝(P∨Q∨⌝(R∨P))8. (1) (P∨Q)∧((⌝P∧ (⌝P∧Q))∨R)∧⌝P(2)(P∨Q∨R)∧(⌝P∧R)(3)(P∨F)∧(Q∨T)习题1.41.(1)原式⇔⌝(⌝P∨⌝Q)∨((⌝P∨⌝Q)∧(Q∨P))⇔⌝(⌝P∨⌝Q)∨(Q∨P)⇔(P∧Q) ∨Q∨P⇔Q∨P,既是析取范式又是合取范式(2)原式⇔((⌝P∨Q)∨(⌝P∨⌝Q))∧(⌝(⌝P∨Q) ∨⌝(⌝P∨⌝Q)) ⇔(P∧Q)∨(P∧⌝Q) 析取范式⇔P∧(Q∨⌝Q)合取范式(3)原式⇔⌝P∨Q∨⌝S∨ (⌝P∧Q)析取范式⇔(⌝P∨(⌝P∧Q))∨Q∨⌝S⇔⌝P∨Q∨⌝S合取范式(4)原式⇔P∨P∨Q∨Q∨R既是析取范式又是合取范式2.(1)原式⇔P∨⌝Q∨R为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:(⌝P∧⌝Q∧⌝R)∨(⌝P∧⌝Q∧R)∨(⌝P∧Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧⌝∧QR)∨(P∧Q∧⌝R)∨(P∧Q∧R)(2)原式⇔(P∧⌝Q) ∨R⇔(P∧⌝Q∧(R∨⌝R))∨((P∨⌝P)∧R)⇔(P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧Q)∨( ⌝P∧R)⇔(P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧(Q∨⌝Q)∧R)∨(⌝P∧(Q∨⌝Q)∧R) ⇔(P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧Q∧R)∨(P∧⌝Q∧R)∨(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)⇔(P∧⌝Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧Q∧R) ∨(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)为真的解释是101，100，111，011，001(3)原式⇔(⌝P∨(Q∧R))∧(P∨(⌝Q∧⌝R))⇔((⌝P∨ (Q∧R)) ∧P)∨(( ⌝P∨ (Q∧R))∧( ⌝Q∧⌝R))⇔(⌝P∧P)∨(Q∧P∧R)∨( ⌝P∧⌝Q∧⌝R)∨(Q∧R∧⌝Q∧⌝R)⇔(P∧Q∧R)∨(⌝P∧⌝Q∧⌝R)为真的解释是：000,111(4)原式⇔P∨P∨Q∨Q∨R⇔P∨Q∨R为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：(⌝P∧⌝Q∧R)∨(⌝P∧Q∧⌝R)∨(⌝P∧Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧⌝Q∧R)∨(P∧Q∧⌝R)∨(P∧Q∧R)3.(1)原式⇔⌝P∨Q∨⌝P∨⌝Q⇔T主合取范式，无为假的解释。

一、填空题1、集合的表示方法有两种： 法和 法。

请把“奇整数集合”表示出来{ }。

1、列举；描述；}12|{Z k k x x ∈+=，2、无向连通图G 含有欧拉回路的充分必要条件是不含有奇数度结点.2*、连通有向图D 含有欧拉回路的充分必要条件是D 中每个结点的入度＝出度. 3、设R 是集合A 上的等价关系，则R 所具有的关系的三个特性是 、自反性、对称性、传递性.4、有限图G 是树的一个等价定义是：连通无回路（或任一等价定义）.5、设N (x )：x 是自然数，Z (y )；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为∀x (N (x )→Z (x ))∧∃x (Z (x )∧⌝N (x ))6、在有向图的邻接矩阵中，第i 行元素之和,第j 列元素之和分别为 、结点v i 的出度和结点v j 的入度． 7、设A ，B 为任意命题公式，C 为重言式，若C B C A ∧⇔∧，那么命题B A ↔是重言式的真值是 1 ．8、命题公式)(Q P →⌝的主析取范式为P ∧⌝Q ．9、 设图G ＝<V ，E >和G '＝<V ',E '>,若 ，则G '是G 的真子图，若V '=V ,E '⊆E ，则G '是G 的生成子图. E E V V E E V V ⊆'='⊂'⊂',;或 10、在平面图>=<E V G ,中,则∑=ri ir 1)deg(＝2∣E ∣,其中r i(i =1,2,…,r )是G 的面．11、设}2,1{},,{==B b a A ，则从A 到B 的所有映射是11、σ1={（a ，1），（b ，1）}；σ2={（a ，2），（b ，2）}；σ3={（a ，1），（b ，2）}；σ4={（a ，2），（b ，1）}12、表达式∀x ∃yL （x ，y ）中谓词的定义域是{a ，b ，c }，将其中的量词消除，写成与之等价的命题公式为 12、（L （a ，a ）∨L （a ，b ）∨L （a ，c ））∧（L （b ，a ）∨L （b ，b ）∨L （b ，c ））∧（L （c ，a ）∨L （c ，b ）∨L （c ，c ）） 12*、设个体域D ＝{a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为 (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b )))13、含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 14、设R ，S 都是集合A 上的等价关系，则对称闭包s (R ⋂S )= R ⋂S15、设G 是连通平面图，v ,e ,r 分别表示G 的结点数，边数和面数，则v ,e 和r 满足的关系式是2=-+e r v16、设G 是n 个结点的简单图，若G 中每对结点的度数之和≥n ，则G 一定是哈密顿图. 17、一个有向树T 称为根树，若 ，其中 ，称为树根，称为树叶. 若有向图T 恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点.18、图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路. 通路长度；初级；简单. 19、设A 和B 为有限集，|A|=m ，|B|=n ，则有 个从A 到B 的关系，有 个从A 到B 的函数，其中当m ≤n 时有 个入射，当m=n 时，有 个双射。

离散数学复习题有答案1. 什么是集合的子集？子集是指一个集合中的所有元素都属于另一个集合。

如果集合A中的每一个元素都是集合B的元素，那么集合A就是集合B的子集。

2. 描述有限集合和无限集合的区别。

有限集合是指元素数量有限的集合，可以被一一列举。

无限集合则包含无限多个元素，无法被完全列举。

3. 什么是二元关系？二元关系是集合A和集合B之间的一种对应关系，它由有序对(a, b)组成，其中a属于集合A，b属于集合B。

4. 什么是函数？函数是一种特殊的二元关系，其中每个定义域中的元素都与值域中的一个且仅一个元素相关联。

5. 什么是等价关系？等价关系是一种自反的、对称的、传递的二元关系。

在集合A上的等价关系将A划分为若干个不相交的等价类。

6. 什么是偏序关系？偏序关系是一种自反的、反对称的、传递的二元关系。

它在集合上定义了一个部分顺序。

7. 什么是有向图和无向图？有向图是一种图，其中的边有方向，表示从一个顶点指向另一个顶点。

无向图的边没有方向，表示两个顶点之间的双向连接。

8. 什么是强连通分量？在有向图中，强连通分量是指图中的一组顶点，这些顶点中的每一个顶点都可以到达集合中的其他任何顶点。

9. 什么是二进制数？二进制数是一种基数为2的数制，只使用0和1两个数字来表示数值。

10. 什么是逻辑运算？逻辑运算是对逻辑值（真或假）进行的操作，包括与（AND）、或（OR）、非（NOT）等运算。

11. 什么是归纳法？归纳法是一种数学证明方法，通过证明一个基本情况，然后假设某个情况成立，再证明下一个情况也成立，从而证明整个命题。

12. 什么是图的遍历？图的遍历是指按照一定的规则访问图中的每个顶点，确保每个顶点都被访问一次。

常见的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

13. 什么是正规表达式？正规表达式是一种描述字符串集合的模式，用于文本搜索和文本处理。

它由一系列字符和元字符组成，定义了字符串的匹配规则。