离散数学习题
第一章习题
1.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．用真值表判断下列公式的类型：方法不限。 （1）p →(p ∨q ∨r) （2）(p →┐q)→┐q （3）┐(q →r)∧r
（4）(p →q)→(┐q →┐p) （5）(p ∧r)(┐p ∧┐q)
（6）((p →q)∧(q →r))→(p →r) （7）(p →q)(r s)
1. 8用等值演算法证明下列等值式。
(1) (p ∧q)∧(p ∧?q)?p;
(2) ((p →q)∧(p →r))?(p →(q ∧r)); (3) ?(p ?q)?(q ∨p)∧?(p ∧q)) 1. 9设 A,B,C 为任意的命题公式。
(1) 已知A ∨C ?B ∨C,问A ?B 吗？ (2) 已知A ∧C ?B ∧C,问A ?B 吗？ (3) 已知?A ??B, 问A ?B 吗？
1.10求下列命题公式的主析取范式，主合取范式，成真赋值，成假赋值。
1(()();2()();3();
p q v p q r p q q p p q q r ∨∧→∧∧?→→?∨?→∧∧（）（）（） 1.11通过求主析取范式判断下列各组命题公式是不是等值。
();2();2;2;
p q r q p r p q p q →→→→↑↓（1）1，，（）1，，
1.12有一探测队有3名队员，有一天取得一块矿样，3人的判断如下： 甲说：这不是铁，也不是铜； 已说：这不是铁，是锡； 丙说：这不是锡，是铁；
经实验鉴定后发现，其中一人两个判断是正确的，一个人判断对一半，一个人的判断全错了，根据以上的情况判断矿样的种类。
1.13判断下列的推理是不是正确，先将命题符号化，在写出前提和结论，然后在进行判断。
（1）如果今天是1号，则明天是5号，今天是1号，所以明天是5号。 （1）如果今天是1号，则明天是5号，明天是5号，所以今天是1号。 （1）如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。 （1）如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。 1.14构造下面的推理的证明。
(),,..
(2)34p p q q r r p ?∧??∨??→→∨?→→→∧→??∧∧∧∧（1）前提：结论：前提：p (q s),q,p r;结论：r s.（）前提：p q.结论：p (p q)
（）前提：q p,q s,s t,t r.结论：p q r s.
1.15如果他是理科学生，他必学好数学，如果他不是文科学生，他必是理科学生，他没有学好数学，所以他不是文科学生。 判断上面的推理是不是正确，并且证明你的结论。 1.16给定命题公式如下；
上述公式的成真赋值A ，成假赋值为B ，公式的类型为C 。
供选择的答案
:① 无 ② 全体赋值 ③ 010，100，101，111 ④010，100，101，110，111 B: ① 无 ② 全体赋值 ③000，001，011， ④000，010，110 C: ①重言式 ②矛盾式 ③ 可满足式 1.17给定命题公式如下；
上述公式的主析取范式中含的极小项的个数为A ，主合取范式含的极大项的个数为B ，成真值的赋值为C 供选择的答案
A ① 2 ② 3 ③ 5 ④ 0 ⑤ 8
B ① 0 ② 8 ③ 5 ④ 3
C ① 000,001,110; ②001,011,101,110,111; ③全体赋值 ④ 无 1.18给定下列三组前提。
(),,(2)(),,(3),,p q q r r p q r r s s
p q q r r s
?∧??∨?∧→?∨??∨?∨→(1)
上述前提中，（1）的逻辑结论（有效结论）为A ，（2）的逻辑结论为B ，（3）的逻辑结论C 。 供选择的答案
A,B,C:① r ② q ③p ? ④ s ⑤p q ?∨? ⑥p s → ⑦p q ∧
1.19设计一个符合下列要求的室类照明控制的线路，在房间的门外、门类及其床头分别装一个可以控制同一个电灯F 的3个开关A,B,C, 当且仅当一个开关的搬键向上或3 个开关的搬键都向上时候电灯亮，则F 的逻辑关系式可以化简为A
供选择的答案
A:① A B C ∨∨ ②()A B C A B C ∨∨∨∧∧
1.20．某电路中有一个灯泡和三个开关A,B,C 。已知在且仅在下述四种情况下灯亮：
（1）C 的扳键向上，A,B 的扳键向下。 （2）A 的扳键向上，B,C 的扳键向下。 （3）B,C 的扳键向上，A 的扳键向下。 （4）A,B 的扳键向上，C 的扳键向下。
设F 为1表示灯亮，p,q,r 分别表示A,B,C 的扳键向上。 （a ）求F 的主析取范式。
（b ）在联结词完备集{┐,∧}上构造F. （c ）在联结词完备集{┐,→,}上构造F.
1.21．一个排队线路，输入为A,B,C ，其输出分别为F A ,F B ,F C 。本线路中，在同一时间内只能有一个信号通过，若同时有两个和两个以上信号申请输出时，则按A,B,C 的顺序输出。写出F A ,F B ,F C 在联结词完备集{┐,∨}中的表达式。
第二章习题
2.1在一阶逻辑中将下列命题符号化.
（1）鸟都会飞翔.
（2）并不是所有人都爱吃糖. （3）有人爱看小说.
（4）没有不爱看电影的人.
2.2 在一阶逻辑中将下列命题符号化，并指出个命题的真值.个体域分别为 （a ）自然数集合N （N 中含O ）. （b ）整数集合Z. （c ）实数集合R.
（1）对于任意的x ，均由()2
2
121x x x +=++
(2 )存在x ，使得x+2=0. (3 ) 存在x ，使得5x=1.
2.3 在一阶逻辑中将下列命题符号化.
（1）每个大学生不是文科生就是理科生. （2）有些人喜欢所有的花. （3）没有不犯错误的人.
（4）在北京工作的人未必就是北京人. （5）任何金属都可以溶解在某种液体中. （6）凡对顶角都相等.
2.4在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为(a),(b)时命题的真值：
（1）对于任意的x ，均有x 2-2=(x+
)(x-)。
（2）存在x ，使得x+5=9。
其中(a)个体域为自然数集合，(b)个体域为实数集合。
2.5将下列各式翻译成自然语言，然后再不同领域中却定它们的真值.
(1)(.0)(2)(.0)(3)(.1)(4)(.1)(5)(.)(6)(.)(7)()
x y x y x y x y x y x y x y x y x y x y x x y x y x x y z x y z ??=??=??=??=??=??=???-= 个体域分别为 （a ）实数集合 (b)整数集合 (c)正整数集合 (d)（非0 实数集合）
2.6设个体域D={a,b,c}，消去下列各式的量词：
(1) x y(F(x)∧G(y))
(2)
x
y(F(x)∨G(y))
(3) xF(x)→yG(y)
(4) x(F(x,y)→yG(y))
2.7．设个体域D={1,2}，请给出两种不同的解释I 1和I 2，使得下面公式在I 1下都是真命题，而在I 2下都是假命题。
(1) x(F(x)→G(x))
(2)
x(F(x)∧G(x)
2.8．给定解释I 如下： (a) 个体域D={3,4}。
(b) (x)为(3)=4，(4)=3。
(c)
(x,y)为
(3,3)=
(4,4)=0，
(3,4)=
(4,3)=1。
试求下列公式在I 下的真值：
(1) x yF(x,y)
(2) x yF(x,y)
(3) x y(F(x,y)→F(f(x),f(y))
2.9．在自然推理系统F 中构造下面推理的证明： (1) 前提：x(F(x)→(G(a)∧R(x)))，xF(x)
结论：x(F(x)∧R(x)) (2) 前提：x(F(x)∨G(x))，┐xG(x)
结论：xF(x)
(3) 前提：x(F(x)∨G(x))，x(┐G(x)∨┐R(x))，
xR(x)
结论：
xF(x)
2.10．在自然推理系统F 中，证明下面推理：
(1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。 (2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。 (3) 不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不是无理数。 2.11(1) 试给出解释，使得
(()())(()())x F x G x x F x G x ?→?∧与
在下具有不同的真值 （2）试给出解释，使得
(()())(()())x F x G x x F x G x ?∧?→与
在下具有不同的真值
2.12给出解释，使下面的两个公式在解释下面为假，从而说明这两个公式都不是逻辑有效式（用真式）
(1)(()())(()())
(2)(()())(()())x F x G x xF x xG x xF x xG x x F x G x ?∨→?∨??∧?→?∧
2.13设个体域，在D=｛a,b,c ｝
下D 验证量词否定等值式
(1)()()
(2)()()
xA x x A x xA x x A x ??????????
2.14在一阶逻辑中将下面的命符号化，并且要求只能使用全称量词（1）没有人长绿色的头发（2）有的北京人没有去过香山
2.15设个体域，在D=｛a,b,c ｝,消去下列公式中的量词。
?→??∧???（1）xF(x)yG(y)(2)x(F(x)yG(y))(3)y xH(x,y)
2.16求下列各式的前束范式，要求使用自由变换换名规则。
?∨??∧?→?(1)xF(x)yG(x,y)
(2)x(F(x)yG(x,y,z)zH(x,y,z)
2.17 构造下面推理的证明
（1）前提；()((()())())xF x y F y G y R y ?→?∨→
结论：()xF x ?
（3） 前提：(()(()())),(x F x G y R x xF x ?→∧?）
结论：(()())x F x R x ?∧
2.18取个体域为整数集，给定下列各公式
(1)(.0)(2)(.1)(3)(.2)(4)()
x y x y x y x y y x x y x y z x y z ??=??=??=???-=
?????(5)x-y=-y+x (6)x y(x.y=y)(7)x(x.y=x)
(8)x y(x+y=2y)
在上面的公式中，真命题为A, 假命题为B 供选择的答案
A:① (1),(3),(4),(6)② (3),(4),(5)③ (1),(3),(4),(5)④(3),(4),(6),(7)
B:① (2),(3),(6)② (2),(6),(8)③(1),(2),(6),(7)④(2),(6),(8),(7) 2.19在一阶逻辑中给出下面4个推理
y ?→???∧????∧?→???(1)前提：x(F(x)G(x)),yF(y) 结论：yG(y)(2)前提：x(F(x)G(x)) 结论：yF(y)(3)前提：xF(x),xG(x) 结论：(F(y)G(y))(4)前提：x(F(x)H(x)),H(y) 结论：x(F(x)_)
2.20在一阶逻辑中构造下面的推理证明
每个喜欢步行的人都不喜欢坐汽车， 每个人或者喜欢坐汽车或自行车，有的人不喜欢自行车，所以有的人不喜欢步行。
命题符号化： F(x): x 喜欢步行,G(x):x 喜欢坐汽车,H(x):x 喜欢自行车.
F ?→??∨????前提：x(F(x)G(x)),x(G(x)H(x)x(H(x))结论：x((x))
(1)(())(2)()
(3)(()())(4)()()(5)()x H x H c x G x H x G c H c G c ????∨∨前提引入前提引入F(x))
?→?→????(6)x(F(x)G(x)) 前提引入(7)F(c)G(c) （6）UI (8)F(c)
(9)x(F(x)) (8) EG
在上述推理中，（2）后用的推理规则为A ，（4）后面用的推理规则为B ，（5）用的推理规则是（2）（4）所得到的推理规则C,（8）用的推理规则是（5）和（7）得到的推理规则D 供选择的答案
A,B,C,D ① UI,② EI,③ UG,④ EG,⑤拒取式⑥假言推理⑦析取三段论
第三章习题集合与二元关系
3.1.选择适当的谓词表示下列集合： (1)小于5的非负整数 (2)奇整数集合
(3)10的整倍数的集合
2.用列元素法表示下列集合：
(1)S 1＝{x|x 是十进制的数字}
(2)S 2＝{x|x ＝2∨x ＝5}
(3)S 3＝{x|x ＝x ∈Z ∧3 (4)S 4＝{x|x ∈R ∧x 2 －1＝0∧x>3} (5)S 5＝{ 3.2.设F 表示一年级大学生的集合，S 表示二年级大学生的集合，M 表示数学专业学生的集合，R 表示计算机专业学生的集合，T 表示听离散数学课学生的集合，G 表示星期 一晚上参加音乐会的学生的集合，H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。 (1)所有计算机专业二年级的学生在学离散数学课。 (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。 (3)听离散数学课的学生都没参加星期一晚上的音乐会。 (4)这个音乐会只有大学一、二年级的学生参加。 (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。 备选答案： ①T G∪H ②G∪H T ③S∩R T ④H＝G∪T ⑤T∩G＝⑥F∪S G ⑦G F∪S ⑧S-(R∪M)G ⑨G S-(R∩M) 3.3.确定下列命题是否为真： (1) (2)∈ (3){} (4)∈{} (5){a，b}{a，b，c，{a，b，c}} (6){a，b}∈{a，b，c，{a，b }} (7){a，b}{a，b，{{a，b}}} (8){a，b}∈{a，b，{{a，b}}} 3.4已知A={,{}},求A×P(A)。 3.5对于任意集合A,B,C，若A×B A×C,是否一定有B C成立？为什么？ 3.6．设A,B,C,D是任意集合， (1) 求证(A∩B)×(C∩D)=(A×C)∩(B×D)。 (2) 下列等式中哪个成立？那些不成立?对于成立的给出证明，对于不成立的举一反例。 ∪B)×(C∪D)=(A×C)∪(B×D) (A (A-B)×(C-D)=(A×C)-(B×D) 3.7．设A,B为任意集合，证明 若A×A=B×B，则A=B。 3.8列出从集合A={1，2}到B={1}的所有的二元关系。 3.9列出集合A={2，3，4}上的恒等关系I A，全域关系E A，小于或等于关系L A，整除关系D A。 3.10.列出集合A={，{}，{，{}}，{，{}，{，{}}}}上的包含关系。 3.11.设A={1，2，4，6}，列出下列关系R: (1) R={ (2) R={ (3) R={ (4) R={ 3.12.R i是X上的二元关系，对于x∈X定义集合 R i(x)={y|xR i y}。 显然Ri(x)X。如果X={-4，-3，-2，-1，0，1，2，3，4}，且令 R1={ R2={ R3={ 求R1(0)，R1(1)，R2(0)，R2(-1)，R3(3)。 3.13.设A={0，1，2，3}，R是A上的关系，且 R={<0，0>，<0，3>，<2，0>，<2，1>，<2，3>，<3，2>} 给出R的关系矩阵和关系图。 3.14．设 Ａ={<1,2>,<2,4>,<3,3>} Ｂ={<1,3>,<2,4>,<4,2>} 求A∪B,A∩B,domA,dom(A∪B),r anA,ranB,ran(A∩B),fld(A-B) 3.15．设 R={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求R R,R-1 ,R{0,1},R[{1,2}]。 3.16 设 A={<,{,{}}>,<{},>} 求A-1,A2,A3,A{},A[],A,A{{}},A[{{}}]。 3.17 设A={a,b,c,d}，R1,R2为A上的关系，其中 R1={ R2={ 求R1R2, R2R1,R12,R23。 3.18．设A={a,b,c}，试给出A上两个不同的关系R1和R2,使得R12=R1, R23=R2 3.19．证明定理7.4的(1)，(2)，(4)。 3.20．证明定理7.5的(2)，(3)。 3.21设R1和R2为A上的关系，证明： （1）(R1∪R2)-1=R1-1∪R2-1 （2）(R1∩R2)-1=R1-1∩R2-1 第四章习题代数系统 4.1、列出以下运算的运算表： (1) A={1,2,}，x∈A，x是x的倒数，即x=. (2) A={1,2,3,4},x,y∈A有x y=max(x,y),max(x,y)是x和y之中较大的数。 4.2、判断下列集合对所给的二元运算是否封闭： (1) 整数集合Z和普通的减法运算 (2) 非零整数集合Z*和普通的除法运算 (3) 全体n×n实矩阵集合M n(R)和矩阵加法及乘法运算，其中n≥2 (4) 全体n×n实可逆矩阵集合关于矩阵加法和乘法运算，其中n≥2 (5) 正实数集合R+和运算，其中运算定义为： ａ,ｂ∈R+,a b=ab-a-b (6) n∈Z+,nZ={nz|z∈Z}.nZ关于普通的加法和乘法运算。 (7) A={a1,a2,...,a n},n≥2.运算定义如下：a i,a j∈A,a i a j=a i. (8) S={2x-1|x∈Z+}关于普通的加法和乘法运算。 (9) S={0,1},S关于普通的加法和乘法运算。 (10)S={x|x=2n,n∈Z+}，S关于普通的加法和乘法运算 4.3、对于上题中封闭的二元运算判断是否适合交换律、结合律和分配律。 4.4、对习题2中封闭的二元运算找出它的单位元，零元和所有可逆元素的逆元。 4.5、S=Q×Q,Q为有理数集，*为S上的二元运算， (1) *运算在S上是否可交换，可结合？是否为幂等的？ (2) *运算是否有单位元，零元？如果有，请指出，并求S中所有可逆元素的逆元。 4.6、R为实数集，定义以下六个函数f1,...,f6.x,y∈R有 f1( f3( f5( (1) 指出哪些函数是R上的二元运算。 (2) 对所有R上的二元运算说明是否为可交换、可结合、幂等的。 (3) 求所有R上二元运算的单位元、零元以及每一个可逆元素的逆元。 4.7、令S={a,b},上有四个二元运算：*,,·和,分别由表10.8确定。 表10.8 (1) 这四个运算中哪些运算满足交换律、结合律、幂等律 (2) 求每个运算的单位元、零元及所有可逆元素的逆元。 4.8、设S={1,2,...,10},问下面定义的运算能否与S构成代数系统 (1) x*y=gcd(x,y),gcd(x,y)是x与y的最大公约数。 (2) x*y=lcm(x,y),lcm(x,y)是x与y的最小公倍数。 (3) x*y=大于等于x和y的最小整数。 (4) x*y=质数p的个数，其中x≤p≤y. 4.9、下面各集合都是N的子集，它们能否构成代数系统V= (1) {x|x∈N∧x可以被16整除} (2) {x|x∈N∧x与8互质} (3) {x|x∈N∧x是40的因子} (4) {x|x∈N∧x是30的倍数} 4.10、设V= (1) S1={2n|n∈Z} (2) S2={2n＋1|n∈Z} (3) S3={－1，0，1} 4.11、设V1=<{1,2,3},,1>,其中x y表示取x和y之中较大的数。V2=<{5,6},*,6>,其 中x*y表示取x和y之中较小的数。求出V1和V2的所有子代数。指出哪些是平凡子代数，哪些是真子代数。 第五章几个典型的代数系统 5.1.设A={0,1},试给出半群的运算表,其中为函数的复合运算。 5.2.设G={a+bi|a,b∈Z},i为虚数单位,即i2=-1.验证G关于复数加法构成群。 5.3.设Z为整数集合,在Z上定义二元运算如下： x,y∈Z,x y=x+y-2 问Z关于运算能否构成群？为什么？ 5.4.设A={x|x∈R∧x≠0,1}.在A上定义六个函数如下： f 1(x)=x, f 2 (x)=x-1, f 3 (x)=1-x, f 4(x)=(1-x)-1, f 5 (x)=(x-1)x-1, f 6 (x)=x(x-1)-1 令F为这六个函数构成的集合,运算为函数的复合运算。 (1) 给出运算的运算表。 (2) 验证 5.5.设G为群,且存在a∈G,使得 G={a k|k∈Z}, 证明G是交换群。 5.6.证明群中运算满足消去律. 5.7.设G为群,若x∈G有x2=e,证明G为交换群。 5.8.设G为群,证明e为G中唯一的幂等元。 5.9.证明4阶群必含2阶元。 5.10设A={a+bi|a,b∈Z,i2=-1},证明A关于复数的加法和乘法构成环,称为高斯整数环。 5.12. (1) 设R 1,R 2 是环,证明R 1 与R 2 的直积R 1 ×R 2 也是环。 (2) 若R 1和R 2 为交换环和含幺环,证明R 1 ×R 2 也是交换环和含幺环。 5.13. 判断下列集合和给定运算是否构成环、整环和域,如果不能构成,说明理由。 (1) A={a+bi|a,b∈Z},其中i2=-1,运算为复数的加法和乘法。 (2) A={-1,0,1},运算为普通加法和乘法。 (3) A=M 2 (Z),2阶整数矩阵的集合，运算为矩阵加法和乘法。 (4) A是非零有理数集合Q*,运算为普通加法和乘法。 5.14.设G是非阿贝尔群,证明G中存在元素a和b,a≠b,且ab=ba. 5.15.设H是群G的子群,x∈G,令 xHx-1={xhx-1|h∈H}, 证明xHx-1是G的子群,称为H的共轭子群。 5.1 6.设 (1) G上的二元运算为矩阵乘法,给出G的运算表 (2) 试找出G的所有子群 (3) 证明G的所有子群都是正规子群。 5.17.设G是有限群，K是G的子群，H是K的子群,证明[G:H]=[G:K][K:H]. 5.18.令G={Z,+}是整数加群。求商群Z/4Z,Z/12Z和4Z/12Z. 5.19.对以下各小题给定的群G 1和G 2 以及f:G 1 →G 2 ,说明f是否为群G 1 到G 2 的同 态。如果是,说明G是否为单同态,满同态和同构,并求同态像f(G 1 )和同态核kerf. (1) G 1= 2 = 加法和乘法。 f:Z→R*,f(x)= (2) G 1= 2 = A={x|x∈C∧|x|=1},其中C为复数集合。 f:Z→A,f(x)=cosx+i sinx (3) G 1= 2 = f:R→A,f(x)=cosx+i sinx 5.20.设f是群G 1到G 2 的同构,证明f-1是G 2 到G 1 的同构。 5.21.图中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 5.22.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 5.23. (1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 5.24.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 5.25.设L是格,a,b,c∈L,且a b c,证明 a ∨b=b∧c 5.2 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.10 5.27.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。 5.28.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。 5.29.对以下各小题给定的集合和运算判断它们是哪一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。 (1) S1={0，1,-1}，运算为普通加法和乘法。 (2) S2={a1,a2,...,a n},a i,a j∈S2,a i*a j=a i.这里的n是给定的正整数,且n≥2. (3) S3={0,1},*为普通乘法。 (4) S4={1,2,5,7,10,14,35,70},和*分别表示求最小公倍数和最大公约数运算。 (5) S5={0,1,2},*为模3加法,为模3乘法。 5.30.设B是布尔代数,B中的表达式f是 (a ∧b)∨(a∧b∧c)∨(b∧c) (1)化简f. (2)求f的对偶式f* 。 5.31.设 （1）(a∧b)∨(a∧b＇)∨(a＇∨b) （2）(a∧b)∨(a∧（b∧c)＇)∨c 5.32.对于n=1,...,5,给出所有不同构的n元格,并说明哪些是分配格、有补格和布尔格。 5.33.设 x y=(x∧y＇)∨(x＇∧y) 问 5.34.设G 1为循环群,f是群G 1 到G 2 的同态,证明f(G 1 )也是循环群。 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 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. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 第一章习题 1.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); 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨?? ②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。 离散数学（本）复习题 1.请给出公式G=（P→（Q→P））→（?P→（P→Q））的真值表。 2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系R C。 3.R，S是集合A上的两个关系。试证明下列等式： （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R （3）(R∪S)-1= R-1∪S-1 （4）(R∩S)-1= R-1∩S-1 4.设R是集合A上的关系，令 R+={(x, y)|x∈A，y∈A，并且存在n>0，使得xR n y}， 则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。 5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。 6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，R）的Hasse图。 7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？ 9.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。 10.若R是等价关系，试证明R-1也是等价关系。 11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值： a) (P∧(Q∧R))∨?((P∨Q)∧(R∨S)) b) (?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S) c) (?(P∧Q)∨?R)∨((Q??P)→(R∨?S)) d) (P∨(Q→(R∧?P)))?(Q∨?S) 12.试将下列公式化成等价的前束范式： (1)?x(P(x)→?yQ(x，y))； (2)?x((??yP(x，y))→(?zQ(z)→R(x)))； (3)?x?y(?zP(x，y，z)∧(?uQ(x，u)→?vQ(y，v)))。 13.设S={G1，…，G n}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。 14.证明下面的等价式： (1) (?P∧(?Q∧R))∨(Q∧R)∨(P∧R)=R (2) P→(Q→P)=?P→(P→Q) (3) P→(Q∨R)=(P→Q)∨(P→R) (4) (P→Q)∧(R→Q)=(P∨R)→Q 15．找出下面公式的Skolem范式： (1)?(?xP(x)→?y?zQ(y，z))； (2)?x(?E(x，0)→(?y(E(y，g(x))∧?z(E(z，g(x))→E(y，z)))))。 16．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n≤2 C，其中2m C表示 m m中取2的组合数。 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ ７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =， 1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p 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 ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群} 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (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） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (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）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P离散数学屈婉玲版第一章部分习题汇总
离散数学习题解答
离散数学习题
离散数学试题及答案精选版
离散数学习题三 含答案
离散数学(本)复习题
离散数学题库
离散数学试题与答案
离散数学题目大汇总
离散数学题库及答案
离散数学复习题及标准答案
离散数学课后答案
离散数学深刻复知识题(全)
离散数学复习题及答案
最新离散数学习题答案
离散数学练习题及答案
山东大学离散数学题库及答案