第一章习题
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+36； （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+36； （7） 2+24，当且仅当3+3=6； （8） 2+24，当且仅当3+36；
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(qr);
令狐文艳创作
（令狐文艳创作
（2） (pr)(ps);
（3）（p(qr)((pq)(rs); (4)(p(qrp)))(rs); 1.6设p：2+3=5。
q：大熊猫产在中国。 r：复旦大学在广州。 求下列复合命题的真值： （1）(p
q)→r
┐p
（2）(r→(p∧q))
（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)
1. 8
(rs)
用等值演算法证明下列等值式。
(1) (pq)(pq)p;
令狐文艳创作
令狐文艳创作
(2) ((pq)(pr))(p(qr)); (3) (pq)(qp)(pq))
1.
9设 A,B,C 为任意的命题公式。
(1) 已知(2) 已知
ACBC,问AB吗？ ACBC,问AB吗？
AB吗？
(3) 已知AB, 问
1.10求下列命题公式的主析取范式，主合取范式，成真赋值，成假赋值。
1.11通过求主析取范式判断下列各组命题公式是不是等值。 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构造下面的推理的证明。
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给定下列三组前提。
上述前提中，（1）的逻辑结论（有效结论）为A，（2）的逻辑结论为B，（3）的逻辑结论C。 供选择的答案
A,B,C:① r ② q ③p④ s ⑤pq⑥ps⑦pq 1.19设计一个符合下列要求的室类照明控制的线路，在房间的门外、门类及其床头分别装一个可以控制同一个电灯F的3
令狐文艳创作
令狐文艳创作
个开关A,B,C, 当且仅当一个开关的搬键向上或3 个开关的搬键都向上时候电灯亮，则F的逻辑关系式可以化简为A 供选择的答案
A:①ABC②ABC(ABC)
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，其输出分别为FA,FB,FC。本线路中，在同一时间内只能有一个信号通过，若同时有两个和两个以上信号申请输出时，则按A,B,C的顺序输出。写出FA,FB,FC在联结词完备集{┐,∨}中的表达式。
第二章习题
2.1在一阶逻辑中将下列命题符号化.
令狐文艳创作
令狐文艳创作
（1）鸟都会飞翔.
（2）并不是所有人都爱吃糖. （3）有人爱看小说.
（4）没有不爱看电影的人.
2.2 在一阶逻辑中将下列命题符号化，并
指出个命题的真值.个体域分别为
（a）自然数集合N（N中含O）. （b）整数集合Z. （c）实数集合R.
（1）对于任意的x，均由x12x22x1 (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=(x+
（2）存在x，使得x+5=9。
2
)(x-)。
其中(a)个体域为自然数集合，(b)个体域为实数集合。 2.5将下列各式翻译成自然语言，然后再不同领域中却定它们的真值. 个体域分别为 （a）实数集合 (b)整数集合 (c)正整数集合 (d)（非0 实数集合）
2.6设个体域D={a,b,c}，消去下列各式的量词： (1) xy(F(x)∧G(y)) (2) xy(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y))
2.7．设个体域D={1,2}，请给出两种不同的解释I1和I2，使
令狐文艳创作
令狐文艳创作
得下面公式在I1下都是真命题，而在I2下都是假命题。 (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) xyF(x,y) (2) xyF(x,y)
(3) xy(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) 试给出解释，使得 在下具有不同的真值 （2）试给出解释，使得 在下具有不同的真值
2.12给出解释，使下面的两个公式在解释下面为假，从而说明这两个公式都不是逻辑有效式（用真式） 2.13设个体域，在D=｛a,b,c｝ 下D验证量词否定等值式
2.15设个体域，在D=｛a,b,c｝,消去下列公式中的量词。
（1）xF(x)yG(y)(2)x(F(x)yG(y))(3)yxH(x,y)
2.16求下列各式的前束范式，要求使用自由变换换名规则。 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取个体域为整数集，给定下列各公式 在上面的公式中，真命题为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个推理 2.20在一阶逻辑中构造下面的推理证明
每个喜欢步行的人都不喜欢坐汽车， 每个人或者喜欢坐汽车或自行车，有的人不喜欢自行车，所以有的人不喜欢步行。 命题符号化： F(x): x 喜欢步行,G(x):x 喜欢坐汽车,H(x):x 喜欢自行车.
令狐文艳创作
令狐文艳创作
在上述推理中，（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)S1＝{x|x是十进制的数字}
(2)S2＝{x|x＝2∨x＝5}
令狐文艳创作
令狐文艳创作
(3)S3＝{x|x＝x∈Z∧3 (5)S5＝{ 3.2.设F表示一年级大学生的集合，S表示二年级大学生的集合，M表示数学专业学生的集合，R表示计算机专业学生的集合，T表示听离散数学课学生的集合，G表示星期一晚上参加音乐会的学生的集合，H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。 (1)所有计算机专业二年级的学生在学离散数学课。 (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。 (3)听离散数学课的学生都没参加星期一晚上的音乐会。 (4)这个音乐会只有大学一、二年级的学生参加。 令狐文艳创作 2 令狐文艳创作 (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。 备选答案： ①TG∪H ②G∪HT ③S∩RT ④H＝G∪T ⑤T∩G＝⑥F∪SG ⑦GF∪S ⑧S-(R∪M)G ⑨GS-(R∩M) 3.3.确定下列命题是否为真： (1) (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}}} 令狐文艳创作 (2)∈(3){} 令狐文艳创作 3.4已知A={,{}},求A×P(A)。 3.5对于任意集合A,B,C，若A×BA×C,是否一定有BC成立？为什么？ 3.6．设A,B,C,D是任意集合， (1)求证(A∩B)×(C∩D)=(A×C)∩(B×D)。 (2)下列等式中哪个成立？那些不成立?对于成立的给出证明，对于不成立的举一反例。 (A∪B)×(C∪D)=(A×C)∪(B×D) (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}上的恒等关系IA，全域关系EA，小 令狐文艳创作 令狐文艳创作 于或等于关系LA，整除关系DA。 3.10.列出集合A={，{}，{，{}}，{，{}，{，{}}}}上的包含关系。 3.11.设A={1，2，4，6}，列出下列关系R: (1)R={ (2) R={ (3) R={ (4) R={ 3.12.Ri是X上的二元关系，对于x∈X定义集合 Ri(x)={y|xRiy}。 显然Ri(x)X。如果X={-4，-3，-2，-1，0，1，且令 R1={ 2，3，4}，令狐文艳创作 R2={ 求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),ranA,ranB,ran(A∩B),fld(A-B)3.15．设 令狐文艳创作 2 令狐文艳创作 R={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R R,R ,R{0,1},R[{1,2}]。 3.16 设 A={<,{,{}}>,<{},>} 求A,A,A,A{},A[],A 3.17 设A={a,b,c,d}，R1,R2为A上的关系，其中 R1={ R2={ 求R1R2, R2R1,R1,R2。 3.18．设A={a,b,c}，试给出A上两个不同的关系R1和R2,使得 R1=R1, R2=R23.19．证明定理7.4的(1)，(2)，(4)。 3.20．证明定理7.5的(2)，(3)。 3.21设R1和R2为A上的关系，证明： 令狐文艳创作 2 3 2 3 -1 2 3 -1 ,A{{}},A[{{}}]。 令狐文艳创作 （1）(R1∪R2)=R1∪R2第四章习题代数系统 4.1、列出以下运算的运算表： (1) A={1,2,}，x∈A，x是x的倒数，即x=. (2) A={1,2,3,4},x,y∈A有xy=max(x,y),max(x,y)是x和y之中较大的数。 4.2、判断下列集合对所给的二元运算是否封闭： (1) 整数集合Z和普通的减法运算 (2) 非零整数集合Z和普通的除法运算 (3) 全体n×n实矩阵集合Mn(R)和矩阵加法及乘法运算，其中n≥2 (4) 全体n×n实可逆矩阵集合关于矩阵加法和乘法运算，其中n≥2 (5) 正实数集合R和运算，其中运算定义为： ａ,ｂ∈R,ab=ab-a-b (6) n∈Z,nZ={nz|z∈Z}.nZ关于普通的加法和乘法运算。 (7) A={a1,a2,...,an},n≥2.运算定义如下：ai,aj∈A,aiaj=ai. (8) S={2x-1|x∈Z}关于普通的加法和乘法运算。 (9) S={0,1},S关于普通的加法和乘法运算。 令狐文艳创作 + + + + * -1 -1 -1 （2）(R1∩R2)=R1∩R2 -1-1-1 令狐文艳创作 (10)S={x|x=2,n∈Z}，S关于普通的加法和乘法运算 4.3、对于上题中封闭的二元运算判断是否适合交换律、结合律和分配律。 4.4、对习题2中封闭的二元运算找出它的单位元，零元和所有可逆元素的逆元。 4.5、S=Q×Q,Q为有理数集，*为S上的二元运算， 是否可交换，可结合？是否为幂等的？ (2)*运算是否有单位元，零元？如果有，请指出，并求S中所有可逆元素的逆元。 4.6、R为实数集，定义以下六个函数f1,...,f6.x,y∈R有 f1( f2( (1)*运算在S上 n+ (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= 4.11、设V1=<{1,2,3},,1>,其中xy表示取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为虚数单位,即i=-1.验证G关于复数加法构成群。 5.3.设Z为整数集合,在Z上定义二元运算如下： x,y∈Z,xy=x+y-2 问Z关于运算能否构成群？为什么？ 令狐文艳创作 2 A 令狐文艳创作 5.4.设A={x|x∈R∧x≠0,1}.在A上定义六个函数如下： f1(x)=x,f4(x)=(1-x), f6(x)=x(x-1) 令F为这六个函数构成的集合,运算为函数的复合运算。 (1) 给出运算的运算表。 (2) 验证 5.5.设G为群,且存在a∈G,使得 G={a|k∈Z}, 证明G是交换群。 5.6.证明群中运算满足消去律. 5.7.设G为群,若x∈G有x=e,证明G为交换群。 5.8.设G为群,证明e为G中唯一的幂等元。 5.9.证明4阶群必含2阶元。 5.10设A={a+bi|a,b∈Z,i=-1},证明A关于复数的加法和乘法构成环,称为高斯整数环。 令狐文艳创作 2 2 k -1 -1 f2(x)=x,f5(x)=(x-1)x, -1 -1 f3(x)=1-x, 令狐文艳创作 5.12.(1) 设R1,R2是环,证明R1与R2的直积R1×R2也是环。 (2) 若R1和R2为交换环和含幺环,证明R1×R2也是交换环和含幺环。 5.13. 判断下列集合和给定运算是否构成环、整环和域,如果不能构成,说明理由。 (1) A={a+bi|a,b∈Z},其中i=-1,运算为复数的加法和乘法。 (2) A={-1,0,1},运算为普通加法和乘法。 (3) A=M2(Z),2阶整数矩阵的集合，运算为矩阵加法和乘法。 (4) A是非零有理数集合Q,运算为普通加法和乘法。5.14.设G是非阿贝尔群,证明G中存在元素a和b,a≠b,且ab=ba. 5.15.设H是群G的子群,x∈G,令 xHx={xhx|h∈H}, 证明xHx是G的子群,称为H的共轭子群。 5.16.设 算为矩阵乘法,给出G的运算表 (2) 试找出G的所有子群 令狐文艳创作 -1 -1 -1* 2 (1) 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.对以下各小题给定的群G1和G2以及f:G1→G2,说明f是否为群G1到G2的同态。如果是,说明G是否为单同态,满同态和同构,并求同态像f(G1)和同态核kerf. (1) G1= f:Z→R,f(x)= * * * (2) G1= A={x|x∈C∧|x|=1},其中C为复数集合。 f:Z→A,f(x)=cosx+i sinx (3) G1= f:R→A,f(x)=cosx+i sinx 5.20.设f是群G1到G2的同构,证明f是G2到G1的同构。 5.21.图中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 令狐文艳创作 -1 令狐文艳创作 5.22.下列各集合对于整除 关系都构成偏序集,判断哪些偏序集是格。 (1)L={1,2,3,4,5},3,4,6,9,12,18,36}Z (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 令狐文艳创作 + (2)L={1,2,3,6,12} 2 n (3)L={1,2 (4)L={1,2,2,...,2},n∈ 5.23.(1)画出Klein四元群的子群格。 令狐文艳创作 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,且abc,证明 a∨b=b∧c 5.26.针对图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,...,an},ai,aj∈S2,ai*aj=ai.这里的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是 (1)化简f. (2)求f的对偶式f。