离散数学第一单元练习题

离散数学第一章测验一、下列那些是命题?是命题的指出其真值。

1.√5是无理数。

2.3是素数或4是素数。

3.2x+3<5。

4.你去图书馆吗?5.刘红与魏新是同学。

6.吸烟请到吸烟室去!7.2015年元旦下大雪。

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

9.8是偶数的充分必要条件是8能被3整除。

10.圆的面积等于半径的平方乘以π。

二、将下列命题符号化。

1.只要你学习了，你考试就能及格。

P : 你学习Q : 你考试及格2.只有天下雨了，我才不去上街。

P : 天下雨Q : 我不去上街3.实函数f(x)可微当且仅当f(x)连续。

P : 实函数f(x)可微Q : f(x)连续4.除非你努力，否则你就会失败。

P : 你努力Q : 你失败5.若不是他生病或出差了，我是不会同意他不参加学习的。

P : 他生病Q : 他出差R : 我同意他不参加学习三、下列那些是重言式，哪些是矛盾是，哪些是偶然式，哪些是可满足式。

1.P∨(¬P∧Q)2.¬(P∨Q)↔(¬P∧¬Q)3.¬P∨Q→Q4.(P∧¬(Q→P))∧(Q∧R)5.(P∧Q↔P)↔(P↔Q)6.(P∧(P→Q))→Q7.¬(P→Q)∧Q8.P∧(Q∨¬R)四、不用真值表证明下列等价式并写出对偶式。

1.(P∧Q)∨¬(¬P∨Q)⇔P2.(P→Q)∧(Q→P)⇔(P∧Q)∨(¬P∧¬Q)3.P→(Q→R)⇔Q→(P→R)五、不用真值表证明下列蕴含式。

1.P→Q⇒P→(P∧Q)2.((P∨¬P)→Q)→((P∨¬P)→R)⇒Q→R3.(Q→(P∧¬P))→(R→(P∧¬P))⇒R→Q六、求下列式子的主析取范式和主合取范式。

1.(P∨Q)∧R2.P→(P∨Q∨R)3.¬(Q→¬P)∧¬P七、某单位要从张、王、马三名同志中选派一部分人外出培训，但是由于部门工作需要，必须满足以下条件：(1) 若张去，马也去。

第一章习题1．下列哪些语句是命题？(1) 黄山是在安徽省。

(2) 你会做这道题目吗？(3) 月球比地球大。

(4) 请关上窗户！(5) 如果1+2=5，我就去游泳。

(6) 只有6是偶数，3才能被2整除。

解：(1)，(3) ，(5) ，(6) 是命题，(2)，(4)分别是疑问句和命令句，它们不是命题。

2．给出下面命题的否定命题。

(1) 上海是一座城市。

解：该句的否定命题为：上海不是一座城市。

(2) 1+2=5并且2×3=6。

解：该句的否定命题为：1+2≠5或2×3≠6。

(3) 2是素数或3是偶数。

解：该句的否定命题为：2不是素数并且3不是偶数。

3．将下列命题符号化。

(1) 灯泡有故障或开关有故障。

解：P表示：灯泡有故障，Q表示：开关有故障，命题符号化为：P∨Q(2) 今天下大雨和3+3=6。

解：P表示：今天下大雨，Q表示：3+3=6，命题符号化为：P∧Q(3) 虽然天气炎热，老师坚持给我们上课。

解：P表示：天气炎热，Q表示：老师坚持给我们上课，命题符号化为：P∧Q(4) 他一边走路，一边看书。

解：P表示：他走路，Q表示：他看书，命题符号化为：P∧Q(5) 如果天下大雨，他就乘公共汽车上班。

解：P表示：天下大雨，Q表示：他乘公共汽车上班，命题符号化为：P→Q(6) 只有天下大雨，他才乘公共汽车上班。

解：P表示：天下大雨，Q表示：他乘公共汽车上班，命题符号化为：Q→P(7) 2＋2＝4当且仅当雪是白色的。

解：P表示：2＋2＝4，Q表示：雪是白色的，命题符号化为：P↔Q4．判断下列各蕴涵式是真是假。

(1) 若一周有八天，则3+2=5。

解：P表示：一周有八天，Q表示：3+2=5，命题符号化为：P→Q由于P为假，Q为真，P→Q为真，故该命题为真命题。

(2) 若一周有七天，则3+2≠5。

解：P表示：一周有七天，Q表示：3+2≠5，命题符号化为：P→Q由于P为真，Q为假，P→Q为假，故该命题为假命题。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1)设：p：派小王去开会。

q：派小李去开会.则命题：“派小王或小李中的一人去开会" 可符号化为：（p q) (p q）。

（2）设A,B都是命题公式，A B，则A B的真值是T。

（3）设:p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p q .（4）设A , B 代表任意的命题公式，则蕴涵等值式为A B A B。

（5）设，p：径一事;q：长一智。

在命题逻辑中,命题:“不径一事，不长一智。

" 可符号化为： p q 。

（6）设A , B 代表任意的命题公式，则德摩根律为（A B）Û A B）。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。

”可符号化为: （p q）（p q） .（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题:“他既聪明又用功。

" 可符号化为：P Q .（9）对于命题公式A,B,当且仅当 A B 是重言式时，称“A蕴含B”，并记为A B。

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:“我们不能既划船又跑步.”可符号化为：（P Q) 。

（11）设P，Q是命题公式,德·摩根律为：（P Q）P Q) 。

（12）设P:你努力.Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：P Q .（13）设p：小王是100米赛跑冠军。

q:小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军.”可符号化为：p q。

（14）设A，C为两个命题公式，当且仅当A C为一重言式时,称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A B A B。

（）2.命题公式p q r是析取范式。

( √ )3.陈述句“x + y > 5”是命题。

离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合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上的传递关系。

习题一 5.证明下列各等价式
(4)(P Q) (Q R) (R P) (P Q) (Q R) (R P) 证明 : (P Q) (Q R) (R P) (Q (P R) ) (R P) (分配律) (Q (R P) ) (P R (R P) ) (Q R) (P Q) (R P) (分配律、吸 收律、交换律)
P1 P4 ~ P1
~P4
~P4 ~P3
~P3
P2
P2 P3 P2 J
J
习题一 23(3) 利用消解法证明蕴含式：
P (Q R), Q (R S) P (Q S) 证明: 首先把结论否定加入前提得公式集: P (Q R), Q (R S), ~(P (Q S)) 构造子句集:{~P ~Q R, ~Q ~R S, P, Q, ~S} 消解过程如下: (1) P 引入子句 (2) ~P ~Q R 引入子句 (3) ~Q R 由(1)(2)消解 (4) Q 引入子句 (5) R 由(3)(4)消解 (6) ~Q ~R S 引入子句 (7) ~Q S 由(5)(6)消解 (8) ~S 引入子句 (9) ~Q 由(7)(8)消解 (10) 由(9)(4)消解
P (R (Q P)) 1 1 1 1 0 1
1 1 0
0
0
1
1 1 1 1 解法一 (真值表法) 由对应于公式取值为0的全部解释得主合取范式： (~P Q R) (~P ~ Q R) 由对应于公式取值为1的全部解释得主析取范式：
(~P ~ Q ~ R) (~P ~ Q R) (~P Q ~ R) (~P Q R) (P ~ Q R) (P Q R)

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100typedef int ElemType;typedef struct{ElemType data[MAX_STACK_SIZE];int top;} Stack;void InitStack(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);N=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)离散数学是计算机专业的一门必修课。

离散数学习题解答第一章命题逻辑习题1.1（P2）1 、a. 是命题b. 是命题c.是命题d .是命题e .是命题f .不是命题疑问句2 、a. A: 我是大学生。

b. B: 你是我的玫瑰花。

c. P: 明天是个艳阳天。

d. Q: 3+2>8。

e.R: 我喜欢离散数学这门课。

f.不是命题。

3、解：三个真命题如：8是偶数;2+8>5；太阳从东边升起；三个假命题如：3+2>8；雪是黑色的；太阳从西边升起；三个非命题如：请勿抽烟！; 春天多美好; 我正在说慌；习题 1.2（P5）1、 a. 复合命题设P :李子是酸的。

Q:李子是甜的。

则命题可表示为P∧Q。

b 简单命题设P: 张一和陈一是好朋友。

2、设P: 天下雨。

Q: 我不去游泳。

R: 我有时间。

a. P→Q。

b. P∧⌝R。

c.⌝Q↔R。

3、 a. 设P: 6是偶数。

Q: 8是奇数。

否定命题表示为:⌝P∨⌝Q。

b. 设P:北京的春天会刮沙尘暴。

否定命题表示为:⌝P 。

4、 a. 设P:王燕学过英语。

Q:王燕学过法语。

命题表示为: （⌝P∧Q）∨（P∧⌝Q） QP⊕。

b. 设P:王成在教室看书。

Q:王成在图书馆看书。

命题表示为: （⌝P∧Q）∨（P∧⌝Q）。

5、（⌝P∧Q）∨（P∧⌝Q）。

习题 1.3（P9）1、 a. 不是命题公式。

b．是命题公式。

c. 不是命题公式。

d. 是命题公式。

2、 a.b.c.3、 a.由表可知命题公式P∨P的真值均为真，所以此公式为重言式。

b.由表可知命题公式P∧c.由表可知命题公式P→（P∨Q）的真值均为真，所以此公式为重言式。

d.由表可知命题公式P→P）的真值均为真，所以此公式为重言式。

e.4 、5、从上述真值表可看出合取和析取是可结合的，条件和双条件不是可结合的。

习题1.4 （P13）⌝(⌝P）⇔P→P1、 a. P→⇔⌝P∨P⇔1 因为公式与1等价，所以此公式是重言式。

b.⌝（P∧Q）↔（⌝P∨⌝Q）⇔（⌝（P∧Q）→（⌝P∨⌝Q））∧（（⌝P∨⌝Q）→⌝（P∧Q））⇔（（P∧Q）∨⌝（P∧Q））∧（（P∧Q）∨⌝（P∧Q））⇔1∧1⇔1 因为公式与1等价，所以此公式是重言式。

第一单元练习题一、单项选择题（每小题2分，共12分）1．若集合A ={a ，b }，B ={ a ，b ，{ a ，b }}，则（ ） A ．A ⊂B ，且A ∈B B ．A ∈B ，但A ⊄B C ．A ⊂B ，但A ∉B D ．A ⊄B ，且A ∉B 2. 若集合A 的元素个数为10，则其幂集的元素个数为（ ） A ．100 B ．10 C ．1024 D ．1 3. 设R 为实数集，函数f ：R →R ，f(x)= 2x ，则f 是（ ） A ．满射函数B ．单射函数C ．双射函数D ．非单射非满射4. 设A={1，2，3}，则A 上的二元关系有（ ）个。

A ．32 ； B ．23； C ． 332⨯； D ． 223⨯5.设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）．A ．{2}∈B B ．{2, {2}, 3, 4}⊂BC ．{2}⊂BD ．{2, {2}}⊂B 6. 集合}}}{,{},{,{ΦΦΦΦ=B 的幂集为（ ）。

A 、}},},{{},{{ΦΦΦΦ；B 、}}}},{,{},{{}}},{,{,{}},{,{}}},{,{{}},{{},{,{B ΦΦΦΦΦΦΦΦΦΦΦΦΦ；C 、}}}},{,{},{{}}},{,{,{}},{,{}},{,{}},{{},{,{B ΦΦΦΦΦΦΦΦΦΦΦΦΦ；D 、},}}},{,{},{{}}},{{,{}},{,}{{{B ΦΦΦΦΦΦΦΦΦΦ，二、填空题（每小题4分，共20分）7．设有集合A={a,b,c,d,e},B={d,e,f,g,h},则A/B=______________ ，A △B=________________.8.设集合A B12312，则A B= ，=={,,},{,}A B= ，A-B= ，P(A)-P(B )= ．9.设集合A ={ 1, 2 }，B={ a, b }，那么集合A到B的双射函数是．10. A，B，C表示三个集合，文氏图中阴影部分的集合表达式为。

离散数学第一部分测试题 一、 填空题1．当p,q,r 分别取1，0，1时，(p→q) (p→r)的真值为 假，或02．设P ：他富有，Q ：他幸福，“他既不富有也不幸福” 的符号化为 ┐ P ∧┐ Q3．“所有的人都长着黑头发”用谓词表达式符号化为 M(x):x 为人，F(x): x 长着黑头发， x(M(x)→F(x))4．如果6大于4，则4大于5用谓词表达式符号化为 G(x,y): x ﹥y ,G(6,4) →G(4,5)二、 选择题1.2x+3<4（ C ）A.是命题也是复合命题B.是命题但不是复合命题C.不是命题D.以上都不对2. 下列语句是命题的有（ D ）A. 什么时候开会呀？B. 请快开门！C. x+y>10。

D. 苹果树和梨树都是落叶乔木。

3.设p 表示命题“天下大雨”，q 表示命题“他乘公共汽车上班”，r 表示命题“他骑自行车上班”。

则命题“如果天不下大雨，他乘公共汽车上班或者骑自行车上班。

”符号化为（ B ）A ．(⌝p ∧q) →rB ．⌝p →(q ∨r )C ．⌝p ∧(q →r )D ．p →(q ∧r )三、 计算题1．求(p ∨q) →r 的主析取范式解 本公式含有三个命题变项，所以极小项均含有三个文字。

75310)()()()()()()()()()()())()(()()()()()(m m m m m r q p r q p r q p r q p r q p r q p r q p r q p r q p r q p r q p r q q p p r r q p rq p rq p rq p ∨∨∨∨⇔∧∧∨∧⌝∧∨∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔∧∧∨∧⌝∧∨∧∧⌝∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔∧∨⌝∧∨⌝∨∨⌝∧⌝∧⌝⇔∨⌝∧⌝⇔∨∨⌝⇔→∨2．求公式的主合取范式：()()R Q Q P ∧→∨证明：()()()()P Q Q R P Q Q R ∨→∧⇔⌝∨∨∧()()P Q Q R ⇔⌝∧⌝∨∧()()()()()P Q Q P P Q R ⇔⌝∧⌝∨∧⌝∨∧∧()()()()()()R Q P P R R Q P ∧∧∨⌝∨∨⌝∧⌝∧⌝⇔()()()()R Q P R Q P R Q P R Q P ∧∧∨∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔四、 证明题1.用等演算法证明下面等值式。

离散数学第1章答案习题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，Q 3、（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) <=> 右(5)左?(?P∨Q)∧(?R∨Q)??(P∨Q)∨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∨RQ∨?R∨?Q∨RQ∨TT故((P∨?P) →Q)∧((P∨?P)→R)?Q→R(6)左?(Q→F)∧(R→F)(Q∨F)∧(?R∨F)Q∧?RRR∨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∨PQ∨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∨?SP∨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主合取范式，⽆为假的解释。

4.求与公式((x1x2)x3)x4等价的主析取范式 或主合取范式。
((x1x2)x3)x4 (( x1 x2) x3) x4 ( ( x1 x2) x3) x4 ( x1 x2 x4) （ x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4) （x1 x2 x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4)
P P T(1)(2);I P T(3)(4);I
T(9)(10);I T(11);E
6. 将前提和结论符号化，并证明相应的结论是有效的。
前提：若我学习，则考试不会失败； 若我不踢球，那我将学习； 我考试失败了。
结论：我踢了球。
设：P: 我学习 Q:我考试失败 R:我踢球 则：PQ , RP, Q R
(1) PQ (2) Q (3) P (4) RP (5) R
P T(1);E P T(2)(3);I T(4);E P T(5)(6);I T(7);E
(PQ)R,RS,S PQ
(1) S (2) RS (3) R (4) (PQ)R (5) (PQ) (6) PQ
P P T(1)(2);I P T(3)(4);I T(5);E
P(QR),QS,(LM) S,Q P QL
(x1 x2 x3 x4) (x1 x2 x3 x4) （x1 x2 x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4)
5. 证明结论是前提的有效结论 (课后练习P46 T27)
PQ,PR,QS SR
(1) PQ (2) PQ (3) QS (4) PS (5) S P (6) PR (7) S R (8) SR
第一章离散数学练习参考答案离散数学第一章离散数学课后习题答案离散数学答案离散数学左孝凌答案离散数学及其应用答案离散数学第五版答案离散数学答案屈婉玲离散数学课后答案离散数学贾振华答案

离散数学章练习题及答案离散数学练习题第⼀章⼀．填空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．下列是两个命题变元p，q的小项是（ C ）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列语句中是命题的只有（ A ）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（ C ）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．(∀x)(∀y)(A(x)→B(y))⇔(∃x)A(x)→(∀y)B(y)5．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x的辖域是（ C ）A．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B．Q(x,z)→(∀y)R(x,y,z)C．Q(x,z)→(∃x)(∀y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（ D ）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（ A ）A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ A ）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)02324# 离散数学试题第1 页共4页02324# 离散数学试题 第 2 页 共4页D ．a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( A ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系第二部分 非选择题二、填空题1．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。

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

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

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

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

”3．用真值表判断下列公式的类型：（1）(p→q) →(⌝q→⌝p)（2）(p∧r) ↔(⌝p∧⌝q)（3）((p→q) ∧(q→r)) →(p→r)4.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)5.用等值演算法证明下面等值式：(1)(p→q)∧(p→r)⇔(p→(q∧r))(2)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)6.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)7.在自然推理系统P中构造下面推理的证明：(1)前提：p→q,⌝(q∧r),r结论：⌝p(2)前提：q→p,q↔s,s↔t,t∧r结论：p∧q8.在自然推理系统P中用附加前提法证明下面推理：前提：p→(q→r),s→p,q结论：s→r9.在自然推理系统P中用归谬法证明下面各推理：前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p参考答案:1.（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0（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⇔12.p: π是无理数 1q: 3是无理数0r: 2是无理数 1s: 6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

1.
P
P P T(1, 2) I （2 分）
-4-
6. 7. 8.
(R S )
R S
T(4,5) I （1 分） T(3,4) I（1 分） T(6,7) I（1 分）
2. P (Q R ) 3.
Q R
4.
Q
P(附加前提) P
9.
(Q S )
CP （1 分）
5. Q ( R S )
(1)． x ( F ( x ) G ( x )) xF ( x ) xG ( x ) ； (3)． x ( F ( x ) G ( x )) xF ( x ) xG ( x ) ； ３．下列等价式不成立的是（ 2 ）.
(1)． x ( F ( x ) G ( x )) xF ( x ) xG ( x ) ; (2)． x ( F ( x ) G ( x )) xF ( x ) xG ( x ) (3)． x ( F ( x ) G ) xF ( x ) G (4)． x ( F ( x ) G ) xF ( x ) G ４．谓词公式 x ( P ( x ) yR ( x, y )) Q ( x ) 中量词（ x ）辖域是（ (1)． x ( P ( x ) yR ( x, y )) ； (3)． Q ( x ) ； (2)． P ( x ) ； (4)． ( P ( x) yR ( x, y )) ． ） ．(4)
Q Q P；
Q P Q ；
Q Q P ．
Q Q P ；
） 。 （2）
10．以下推理错误的是（
(1)． P, P Q Q ； (3)． Q, P Q P ；
(2)． P Q P ； (4)． P, P Q Q ．

第一章习题之答禄夫天创作1.2.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。

（1）2是无理数。

（2）5能被2整除。

（3）现在开会吗？（4）x+5>0（5）这朵花真是好看！（6）2是素数当且仅当三角形有三条边。

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

（8）2000年10月1日天气晴好。

（9）太阳系以外的星球上有生物。

（10）小李在宿舍里。

（11）全体起立。

（12）4是2的倍数或是3的倍数。

（13）4是偶数且是奇数。

（14）李明和王华是同学。

（15）蓝色和黄色可以调配成绿色。

1..2 将上题中的命题符号化，并讨论他们的真值。

1.3判断下列各命题的真值。

（1）若2+2=4，则3+3=6；（2）若2+2=4，则3+3≠6；（3）若2+2≠=4，则3+3=6；（4）若2+2≠=4，则3+3≠=6；（5）2+2=4，当且仅当3+3=6；（6）2+2=4，当且仅当3+3≠6；（7）2+2≠4，当且仅当3+3=6；（8）2+2≠4，当且仅当3+3≠6；1.4将下列命题符号化，并讨论其真值。

（1）如果今天是1号，则明天是2号；（2）如果今天是1号，则明天是3号；1.5将下列命题符号化。

（1）2是偶数不是素数；（2）小王不单聪明而且用功；（3）虽然天气冷。

老王还是来了；（4）他一边吃饭，一边看电视；（5）如果天下大雨，他就乘公交汽车来；（6）只有天下大雨，他才乘公交汽车来；（7）除非天下大雨，否则他不乘公交汽车来；（8）不经一事，不长一智；1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。

（1）p∨(q∧r);（2）(p↔r)∧(⌝p∨s);（3）（p∧(q∨r)→((p∨q)∧(r∧s);(4)⌝(p∨(q→r∧⌝p)))→(r∨⌝s);1.6设p：2+3=5。

q：大熊猫产在中国。

r：复旦大学在广州。

求下列复合命题的真值：（1）(p q)→r（2）(r→(p∧q))┐p（3）┐r→(┐p∨┐q∨r)（4）(p∧q∧┐r)((┐p∨┐q)→r)1.7．用真值表判断下列公式的类型：方法不限。

2
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，系电，力根通保据过护生管高产线中工敷资艺设料高技试中术卷资，配料不置试仅技卷可术要以是求解指，决机对吊组电顶在气层进设配行备置继进不电行规保空范护载高与中带资负料荷试下卷高问总中题体资，配料而置试且时卷可，调保需控障要试各在验类最；管大对路限设习度备题内进到来行位确调。保整在机使管组其路高在敷中正设资常过料工程试况中卷下，安与要全过加，度强并工看且作护尽下关可都于能可管地以路缩正高小常中故工资障作料高；试中对卷资于连料继接试电管卷保口破护处坏进理范行高围整中，核资或对料者定试对值卷某，弯些审扁异核度常与固高校定中对盒资图位料纸置试，.卷保编工护写况层复进防杂行腐设自跨备动接与处地装理线置，弯高尤曲中其半资要径料避标试免高卷错等调误，试高要方中求案资技，料术编试交写5、卷底重电保。要气护管设设装线备备置敷4高、调动设中电试作技资气高，术料课中并3中试、件资且包卷管中料拒含试路调试绝线验敷试卷动槽方设技作、案技术，管以术来架及避等系免多统不项启必方动要式方高，案中为；资解对料决整试高套卷中启突语动然文过停电程机气中。课高因件中此中资，管料电壁试力薄卷高、电中接气资口设料不备试严进卷等行保问调护题试装，工置合作调理并试利且技用进术管行，线过要敷关求设运电技行力术高保。中护线资装缆料置敷试做设卷到原技准则术确：指灵在导活分。。线对对盒于于处调差，试动当过保不程护同中装电高置压中高回资中路料资交试料叉卷试时技卷，术调应问试采题技用，术金作是属为指隔调发板试电进人机行员一隔，变开需压处要器理在组；事在同前发一掌生线握内槽图部内纸故，资障强料时电、，回设需路备要须制进同造行时厂外切家部断出电习具源题高高电中中源资资，料料线试试缆卷卷敷试切设验除完报从毕告而，与采要相用进关高行技中检术资查资料和料试检，卷测并主处且要理了保。解护现装场置设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。