第二章作业
评分要求：
1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分
2. 给出每小题得分(注意: 写出扣分理由)
3. 总得分在采分点1处正确设置.
一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):
说明
证
1. p ?(p ∧q)∨(p ∧?q)
解逻辑方程法
设 p ?((p ∧q)∨(p ∧?q)) =0, 分两种情况讨论:
???=?∧∨∧=0
)()(1)1(q p q p p 或者 ?
??=?∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ?(p ∧q)∨(p ∧?q)无成假赋值, 为永真式.
等值演算法
(p ∧q)∨(p ∧?q)
? p ∧(q ∨?q)
∧对∨的分配率
? p ∧1 排中律
? p 同一律
真值表法
2. (p→q)∧(p→r)?p→(q∧r)
等值演算法
(p→q)∧(p→r)
?(?p∨q)∧(?p∨r)蕴含等值式
??p∨(q∧r)析取对合取的分配律
?p→(q∧r)蕴含等值式
3. ?(p?q)?(p∨q)∧?(p∧q)
等值演算法
?(p?q)
??( (p→q)∧(q→p) )等价等值式
??( (?p∨q)∧(?q∨p) )蕴含等值式
??( (?p∧?q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律
?(p∨q)∧?(p∧q)德摩根律
4. (p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q)
等值演算法
(p∧?q)∨(?p∧q)
?(p∨q)∧?(p∧q)析取对合取分配律, 排中律, 同一律
说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.
等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.
二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):
1.
2.
3.
4.
1. (?p→q)→(?q∨p)
解
(?p→q)→(?q∨p)
?(p∨q)→(?q∨p)蕴含等值式
?(?p∧?q)∨(?q∨p)蕴含等值式, 德摩根律
?(?p∧?q)∨?q ∨p结合律
?p∨?q吸收律, 交换律
?M1
因此, 该式的主析取范式为m0∨m2∨m3
2. (?p→q)∧(q∧r)
解逻辑方程法
设(?p→q)∧(q∧r) =1, 则?p→q=1且q∧r=1,
解得q=1, r=1, p=0 或者q=1, r=1, p=1, 从而所求主析取范式为m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6
等值演算法
(?p→q)∧(q∧r)
? (p∨q)∧(q∧r) 蕴含等值式
? (p∧q∧r)∨(q∧r) ∧对∨分配律, 幂等律
? (p∧q∧r) ∨ (p∧q∧r)∨(?p∧q∧r) 同一律, 矛盾律, ∧对∨分配律
?m7∨ m3
主合取范式为M0∧M1∧M2∧M4∧M5∧M6
3. (p?q)→r
解逻辑方程法
设(p?q)→r =0, 解得p=q=1, r=0 或者p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7
等值演算法
(p?q)→r
? ((p→q)∧(q→p))→r 等价等值式
??((p→q)∧(q→p))∨r 蕴含等值式
? (p∧?q)∨(q∧?p)∨r 德摩根律, 蕴含等值式的否定(参见PPT)
? (p∨q∨r)∧(?q∨?p∨r) ∨对∧分配律, 矛盾律, 同一律
?M0∧ M6
主析取范式为m1∨m2∨m3∨m4∨m5∨m7
4. (p→q)∧(q→r)
解
等值演算法
(p→q)∧(q→r)
? (?p∨q)∧(?q∨r) 蕴含等值式
? (?p∧?q)∨(?p∧r)∨(q∧r) ∧对∨分配律, 矛盾律, 同一律
? (?p∧?q∧r)∨(?p∧?q∧?r) ∨ (?p∧q∧r)∨(?p∧?q∧r) ∨ (p∧q∧r)∨(?p∧q∧r)
?m1∨ m0∨ m3∨ m7
主合取范式为M2∧ M4∧ M5∧ M6.
解逻辑方程法
设(p → q) ∧ (q → r) = 1, 则p → q =1 且q → r =1.
前者解得: p=0, q=0; 或者p=0, q=1; 或者p=1, q=1.
后者解得: q=0, r=0; 或者q=0, r=1; 或者q=1, r=1.
综上可得成真赋值为000, 001, 011, 111, 从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.
真值表法
公式(p → q) ∧ (q
从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.
《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；
离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
第一章习题 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);
一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 2 2n. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 . 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是(P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝{4} ; A?B＝{1,2,3,4}; A－B＝{1,2} . 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0) 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1?R2 ={(1,3),(2,2),(3,1)} , R2?R1 = {(2,4),(3,3),(4,2)} _ R12 ={(2,2),(3,3). 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = . 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} , A∩B ={x | 0≤x≤1, x∈R} , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是?x(?P(x)∨Q(x)) . 15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。(完全图的边 数 2)1 (- n n ，树的边数为n-1) 16.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _. 17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则
第一章部分课后习题参考答案 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∧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?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 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 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 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∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 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)
第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。
【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，
习题 2.1 1．将下列命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)∧B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)∨B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A(a)∧A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，则2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a) 2．将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
离散数学试题一（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分）若
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
离散数学习题答案 习题二及答案：（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 p r ∨∨?∧ 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理
习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
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 ∧→??
离散数学练习题 一、填空题 1. 命题Q →P 的真值为0，当且仅当 。 2. 构造公式S R S R →∨∧)(的真值表 。 3. 仅用∧和┐写出下列表达式的等价形式 a) R Q P ?→∨?? b) P Q ∨? 4. 仅用∨和┐写出下列表达式的等价形式 a) )()(D C B A ∨→∨? 。 b) )(E D A ?→→?? 5. 公式A 有三个命题变元P 、Q 、R 组成，其主析取范式为A 6531m m m m ∨∨∨?，则其主合取 范式为： 6. 公式A 有三个命题变元P 、Q 、R 组成，其主合取范式为A ?65310M M M M M ∧∧∧∧，则 其主析取范式为： 。 7. 设解释I 如下： D={n ，m} P(n ，n) P(n ，m) P(m ，n) P(m ，m) 1 1 0 0 8. 确定下列各式的真值： ),(m x xP ? ___ ___; ),(y n yP ? __ ___; ),(y x yP x ??) __ ___。 ),(n x xP ? ___ ___; ),(y m yP ? __ ___; ),(y x yP x ??) __ ___。 9. 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。 10. 某集合有101个元素，则有 个子集的元素为奇数。 11. 某班有32个学生，其中14个人选择艺术，7个人选择生物，6个人选择音乐，三门课都选的有 2人，问这三门课都没选的至少有 人？ 12. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,3,5,6}, B={2,4,6,8,9}, 则：A ∩B= , B ⊕A= , B A ?= ; (A ∪B)-B = , (A ∪B)-(B ∩C)= 13. =Φ=)(},,a {A A ρ 。 14. B A b a B A ×==2},,{},1{= =×B A )(ρ
第二章 谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。
试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式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、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。
8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 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 ．自反性 。
离散数学试题 第一部分选择题 一、单项选择题 1．下列是两个命题变元p，q的小项是（ C ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ A ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ C ） A．┐(?x)A?(?x)┐A B．(?x)(B→A(x))?B→(?x)A(x) 02324# 离散数学试题第1 页共4页
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={