离散数学概念题解与自测pdf

命题演算

? 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

原始命题/原子命题 复合命题 逻辑连接词 否定/┐ 合取/∧ 析取/∨

条件/→（┐P∨Q）

双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)） 真值表 命题公式/公式 命题变元 命题演算

等价（自反性、对称性、传递性，等价变换法俗称“少林派”） 结合律 交换律 分配律

德·摩根律/反演律 双重否定率 代换

蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”） 对偶法则 对偶

不可兼析取（析取符上加一横，异或） 逆条件（条件符上加字母c） 与非/↑ 或非/↓

? ? ? ? ? ? ? ? ? ?

结合力（ ⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件 ） 析取范式 合取范式

主析取范式（∑=m∨…） 主合取范式（∏=M∧…） 直接推演 P规则 T规则

CP规则（俗称“北冥神功”） 间接推演/间接证明/反

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

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

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

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

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看

第十一章 群、环、域

11.1 半群

内容提要

11.1.1 半群及独异点

定义 11.1 称代数结构为半群（semigroups），如果 ? 运算满足结合律．当半群含有关于 ? 运算的么元，则称它为独异点（monoid），或含么半群．

定理11.1 设为一半群,那么

（1）的任一子代数都是半群，称为的子半群．

（2）若独异点的子代数含有么元e,那么它必为一独异点,称为的子独异点．

定理11.2 设,是半群,h为S到S’的同态,这时称h为半群同态．对半群同态有

（1）同态象为一半群．

（2）当为独异点时，则为一独异点.

定理11.3 设为一半群,那麽

SS

（1）为一半群，这里S为S上所有一元函数的集合，○ 为函数的合成运算．

S

（2）存在S到S的半群同态．

11.1.2 自由独异点

定义 11.2 称独异点为自由独异点（free monoid）,如果有A?S使得 （1）e?A．

（2）对任意u?S，x?A,u?x ? e . 自由独异点（free monoid）,如果有A?S使得 （3）对任意u,v?S，x,y?A,若u?x = v?y,那么u = v,x = y．

（4） S由A

习题 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) 小王既聪明又用功，但身体不

第九章 特 殊 图

9.1 二分图

内容提要

9.1.1 二分图的基本概念

定义9.1 无向图G = 称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = ?，且对每一e?E，?(e) = (x, y)，x?X，y?Y。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边e?E，使?(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当?X? = m，?Y? = n时，完全二分图G记为Km,n。

定理9.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

9.1.2 匹配

定义9.2 设G = 为二分图，M?E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 定

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

离散数学标准化作业纸 专业班级 学号 姓名 第一章 命题逻辑的基本概念

一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！”

（4）刘红和魏新是同学。 （5）a+b

（6）你去图书馆吗？

（7）如果买不到飞机票，我哪儿也不去。

（8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！

二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3?2。 （3）只有2<1，才有3?2。 （4）除非2<1，才有3?2。 （5）除非2<1，否则3?2。 （6）2<1仅当3<2。 三、将下列命题符号化

(1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。

- 1 -

离散数学标准化作业纸 专业班级 学号 姓名 四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r) （2）（p?r）

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

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

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

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

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

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

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

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

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看

第一讲 引言

一、课程内容

·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。

二、数理逻辑发展史

1. 目的

·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。 ·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

2. 数理