华东师范大学离散数学章炯民课后习题第1章答案

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100 typedef int ElemType; typedef struct{ElemType data[MAX_STACK_SIZE];int top;} Stack;void lnitStack(Stack *S){S->top=-1;}int Push(Stack *S,ElemType x){if(S->top==MAX_STACK_SIZE-1){printf("\n Stack is full!");return 0;}S->top++;S->data[S->top]=x;return 1;}int Empty(Stack *S){return (S->top==-1);}int Pop(Stack *S,ElemType *x){if(Empty(S)){printf("\n Stack is free!");return 0;}*x=S->data[S->top];S_>top__;return 1;}void conversion(int N){int e;Stack *S=(Stack*)malloc(sizeof(Stack));InitStack(S); while(N){Push(S,N%2);"}while(!Empty(S)){Pop(S, &e);printf("%d ",e);}}void main(){ int n;printf(" 请输入待转换的值n: \n");scanf ("%d",&n);conversion(n);1. 判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1) 离散数学是计算机专业的一门必修课。

第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)0∨(0∧1) 0（2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10.（3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1）? (0∧0∧0)0(4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→0 117．判断下面一段论述是否为真：“是无理数。

并且，如果3是无理数，则也是无理数。

另外6能被2整除，6才能被4整除。

”答：p: 是无理数 1q: 3是无理数0r: 是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

19．用真值表判断下列公式的类型：（4）(p→q) →(q→p)（5）(p∧r) (p∧q)（6）((p→q) ∧(q→r)) →(p→r)答：（4）p q p→q q p q→p (p→q)→(q→p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1所以公式类型为永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q)证明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p) ∧(q∨q)1∧(p∨q)∧(p∧q)∧1(p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(p→q)→(q p)(p q)(q p)(p q)(q p)(p q)(q p)(q p)(p q)(p q)(p q)(p q)(p q)∑(0,2,3)主合取范式：(p→q)→(q p)(p q)(q p)(p q)(q p)(p(q p))(q(q p))1(p q)(p q) M1∏(1)(2) 主合取范式为：(p→q)q r(p q)q r(p q)q r0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：(p(q r))→(p q r)(p(q r))→(p q r)(p(q r))(p q r)(p(p q r))((q r))(p q r))1 11所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p q,(q r),r结论：p(4)前提：q p,q s,s t,t r结论：p q证明：（2）①(q r) 前提引入②q r ①置换③q r ②蕴含等值式④r 前提引入⑤q ③④拒取式⑥p q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t r 前提引入②t ①化简律③q s 前提引入④s t 前提引入⑤q t ③④等价三段论⑥（q t）(t q) ⑤置换⑦（q t）⑥化简⑧q ②⑥假言推理⑨q p 前提引入⑩p ⑧⑨假言推理(11)p q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(q r),s p,q结论：s r证明①s 附加前提引入②s p 前提引入③p ①②假言推理④p(q r) 前提引入⑤q r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p q,r q,r s结论：p证明：①p 结论的否定引入②p﹁q 前提引入③﹁q ①②假言推理④￢r q 前提引入⑤￢r ④化简律⑥r￢s 前提引入⑦r ⑥化简律⑧r﹁r ⑤⑦合取由于最后一步r﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为，在（a）中为假命题，在(b)中为真命题。

2023学堂在线网课《离散数学》课后作业单元考核答案第一单元答案1.1题目：在集合 {1, 2, 3, 4} 上定义一个二元关系 R，其中 R = {(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}。

给出 R 的自反、对称、反对称和传递性特点。

•自反特性：对于任意元素x ∈ {1, 2, 3, 4}，都存在 (x, x) ∈ R。

所以，R 是自反的。

•对称特性：对于任意的(x, y) ∈ R，都存在(y, x) ∈ R。

所以，R 是对称的。

•反对称特性：对于任意的(x, y) ∈ R，如果存在 (y, x) ∈ R，那么 x = y。

所以，R 是反对称的。

•传递性特性：对于任意的(x, y) ∈ R 和(y, z) ∈ R，都存在(x, z) ∈ R。

所以，R 是传递的。

1.2题目：在集合 {1, 2, 3, 4} 上定义一个二元关系 R，其中 R = {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}。

给出 R 的自反、对称、反对称和传递性特点。

•自反特性：对于任意元素x ∈ {1, 2, 3, 4}，都存在 (x, x) ∈ R。

所以，R 是自反的。

•对称特性：对于任意的(x, y) ∈ R，都存在(y, x) ∈ R。

所以，R 是对称的。

•反对称特性：对于任意的(x, y) ∈ R，如果存在 (y, x) ∈ R，那么 x = y。

所以，R 是反对称的。

•传递性特性：对于任意的(x, y) ∈ R 和(y, z) ∈ R，都存在(x, z) ∈ R。

所以，R 是传递的。

第二单元答案2.1题目：证明或给出一个反例：若 R 是集合 A 上的一个等价关系，且对于任意 a, b ∈ A，有 (a, b) ∈ R 或 (b, a) ∈ R，那么 A 必然可以划分为若干等价类。

假设 R 是集合 A 上的一个等价关系，且对于任意a, b ∈ A，有(a, b) ∈ R 或(b, a) ∈ R。

第一章 第一节 P16 、P17
4、将下列命题符号化，并指出真值。

（1）、2与5都是素数；
（2）、不但π是无理数，而且自然对数的底e 也是无理数。

解：（1）、p ：2与5都是素数；其真值为1.
则符号化为p ；其真值为1.
（2）、p ：π是无理数；其真值为1.
q ：自然对数的底e 是无理数；其真值为1. 则符号化为p ∧q ；其真值为1。

5、将下列命题符号化，并指出真值。

（4）、3不是偶数或4不是偶数。

解：p ：3不是偶数；其真值为1。

q ：4不是偶数；其真值为0。

则符号化为p ∨q ；其真值为1.
11、将下列命题符号化，并给出各命题的真值：
（1）、若2+2=4，则地球是静止不动的。

解：p ：2+2=4；其真值为1.
q ：地球是静止不动的；其真值为0.
则符号化为p →q ；其真值为0.
12、将下列命题符号化，并给出各命题的真值：
（3）、2+2≠4与3+3=6互为充要条件。

解：p ：2+2≠4；其真值为0。

q ：3+3=6；其真值为1.
则符号化为p ↔q ；其真值为0.
14、将下列命题符号化:
(5)、李辛与李末是兄弟。

（9）、只有天下大雨，他才乘班车上班。

（10）、除非天下大雨，否则他不乘班车上班。

解：（5）、p ：李辛与李末是兄弟；
则符号化为p.
(9)、p ：天下大雨。

q ：他乘班车上班。

则符号化为p →q.
(10)、p ：天下大雨。

q ：他乘班车上班。

则符号化为q p ⌝
→.。

《离散数学》习题一参考答案第一节 集合的基数1.证明两个可数集的并是可数集。

证明：设A ，B 是两可数集，},,,,,{321 n a a a a A =，},,,,,{321 n b b b b B = ⎪⎩⎪⎨⎧-→j b i a N B A f j i 212: ，f 是一一对应关系，所以|A ∪B|=|N|=0ℵ。

2．证明有限可数集的并是可数集证：设k A A A A 321,,是有限个可数集，k i a a a a A in i i i i ,,3,2,1),,,,,(321 ==⎪⎩⎪⎨⎧+-→==i k j a N A A f ij k i i )1(:1，f 是一一对应关系，所以|A|=| k i i A 1=|=|N|=0ℵ。

3.证明可数个可数集的并是可数集。

证：设 k A A A A 321,,是无限个可数集， ,3,2,1),,,,,(321==i a a a a A in i i i i⎪⎪⎩⎪⎪⎨⎧+-+-+→=∞=i j i j i a N A A f ij i i )2)(1(21:1 ， 所以f 是一一对应关系，所以|A|=| ∞=1i i A |=|N|=0ℵ。

4.证明整系数多项式所构成的集合是可数集。

证明：设整系数n 次多项式的全体记为}|{1110Z a a x a x a x a A i n n n n n ∈++++=--则整系数多项式所构成的集合 ∞==1N n A A ；由于k x 的系数k a 是整数，那么所有k x 的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得n A 是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合 ∞==1N n A A 也是可数集。

5.证明不存在与自己的真子集等势的有限集合.证明：设集合A 是有限集，则|A|=n ，若B 是A 的真子集，则|B|≤|A|=n ，A-B ≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B ）∪B ，（A-B ）B=φ，所以，，就是|A|＞|B|，即得结论。

习题 1.11. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴ 中国有四大发明。

⑵ 计算机有空吗?⑶ 不存在最大素数。

⑷ 21+3 < 5。

⑸ 老王是山东人或河北人。

⑹ 2 与 3 都是偶数。

⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀!⑼ 请勿随地吐痰!⑽ 圆的面积等于半径的平方乘以p。

⑾只有 6 是偶数， 3 才能是 2 的倍数。

⑿雪是黑色的当且仅当太阳从东方升起。

⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺ ⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。

⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。

⑶ 天正在下雨或湿度很高。

⑷ 刘英与李进上山。

⑸ 王强与刘威都学过法语。

⑹ 如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

⑻ 除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵ p：天气冷；q：我穿羽绒服；⑶ p：天在下雨；q：湿度很高；⑷ p：刘英上山；q：李进上山；⑸ p：王强学过法语；q：刘威学过法语；⑹ p：你看电影；q：我看电影；⑺ p：我看电视；q：我外出；r ：我睡觉；⑻ p：天下大雨；q：他乘班车上班。

3. 将下列命题符号化。

⑴ 他一面吃饭，一面听音乐。

⑵ 3 是素数或 2 是素数。

⑶ 若地球上没有树木，则人类不能生存。

⑷ 8 是偶数的充分必要条件是 8能被 3 整除 ⑸ 停机的原因在于语法错误或程序错误。

⑹ 四边形 ABCD 是平行四边形当且仅当 它的对边平行 ⑺ 如果 a 和 b 是偶数，则 a +b 是偶数。

解：⑴ p ：他吃饭； q ：他听音乐；原命题符号化为： p ∧ q ⑵ p ：3 是素数； q ： 2是素数；原命题符号化为： p ∨q ⑶ p ：地球上有树木； q ：人类能生存；原命题符号化为： p → q⑷ p ：8 是偶数； q ：8能被 3整除；原命题符号化为： p ?q⑸ p ：停机； q ：语法错误； r ：程序错误；原命题符号化为： q ∨r →p⑹ p ：四边形 ABCD 是平行四边形； q ：四边形 ABCD 的对边平行；原命题符号化为： p ?q 。

§1.1 命题和逻辑连接词习题1.11. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？（1）中国有四大发明。

（2）你喜欢计算机吗？ （3）地球上海洋的面积比陆地的面积大。

（4）请回答这个问题！ （5）632=+。

（6）107<+x 。

（7）园的面积等于半径的平方乘以圆周率。

（8）只有6是偶数，3才能是2的倍数。

（9）若y x =，则z y z x +=+。

（10）外星人是不存在的。

（11）2020年元旦下大雪。

（12）如果311=+，则血就不是红的。

解是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。

2. 令p 、q 为如下简单命题：p ：气温在零度以下。

q ：正在下雪。

用p 、q 和逻辑联接词符号化下列复合命题。

（1）气温在零度以下且正在下雪。

（2）气温在零度以下，但不在下雪。

（3）气温不在零度以下，也不在下雪。

（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。

（5）若气温在零度以下，那一定在下雪。

（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。

（7）气温在零度以下是下雪的充分必要条件。

解 （1）q p ∧；（2）q p ⌝∧；（3）q p ⌝∧⌝；（4）q p ∨； （5）q p →；（6）)()(q p q p ⌝→⌝∧∨；（7）q p ↔。

3. 令原子命题p ：你的车速超过每小时120公里，q ：你接到一张超速罚款单，用p 、q 和逻辑联接词符号化下列复合命题。

（1）你的车速没有超过每小时120公里。

（2）你的车速超过了每小时120公里，但没接到超速罚款单。

（3）你的车速若超过了每小时120公里，将接到一张超速罚款单。

（4）你的车速不超过每小时120公里，就不会接到超速罚款单。