离散数学笔记(特级教师精心整理)

第一章，0命题逻辑素数 = 质数，合数有因子和或假必真同为真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而→r，（p→(r→q)等不是合式公式。

若公式A是单个的命题变项，则称A为0层合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。

(┐p∧q)→┐r公式(1)的成假赋值为011，其余7个赋值都是成真赋值第二章，命题逻辑等值演算（1）双重否定律⌝⌝⇔（2）等幂律 A∧⇔； A∨⇔（3）交换律 A∧⇔∧A ； A∨⇔∨A（4）结合律（A∧B）∧⇔∧（B∧C）；（A∨B）∨⇔∨（B∨C）（5）分配律（A∧B）∨C⇔（A∨C）∧（B∨C）；（A∨B）∧C⇔（A∧C）∨（B∧C）（6）德·摩根律⌝（A∨B）⌝⇔A∧⌝B ；⌝（A∧B）⇔⌝A∨⌝B（7）吸收律 A∨（A∧B）⇔A；A∧（A∨B）⇔A（8）零一律 A∨1⇔1 ； A∧0⇔0（9）同一律 A∨0⇔A ； A∧1⇔A（10）排中律 A∨⌝A⇔1（11）矛盾律 A∧⌝A⇔0（12）蕴涵等值式 A→⇔⌝∨B（13）假言易位 A→⇔⌝→⌝A（14）等价等值式↔⇔（A→B）∧（B→A）（15）等价否定等值式↔⇔⌝↔⌝⇔⌝↔⌝（16）归缪式（A→B）∧（A→⌝B）⇔⌝A(1,2,…)为简单合取式，则1∨A2∨…∨为析取范式 (p∧┐q)∨(┐q∧┐r)∨p 1∧A2∧…∧为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式主范式【∧小真，∨大假】∧成真小写【例】(p→q)→(┐q→┐p)= ┐(┐p∨q)∨(q∨┐p) (消去→)= (p∧┐q)∨┐p∨q (┐内移) (已为析取范式)= (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*）= m2∨m0∨m1∨m1∨m3= m0∨m1∨m2∨m3 (幂等律、排序)(*)由┐p及q派生的极小项的过程如下：┐p = ┐p∧(┐q∨q)= (┐p∧┐q)∨(┐p∧q)q = (┐p∨p)∧q= (┐p∧q)∨(p∧q)熟练之后，以上过程可不写在演算过程中。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、数理逻辑等领域都有着广泛的应用。

下面我们来对离散数学中的一些重要知识点进行整理。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象所组成的整体。

比如，｛1, 2, 3}就是一个集合。

集合的运算包括并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所得到的集合；补集是在给定的全集范围内，某个集合的补集就是全集中不属于该集合的元素组成的集合。

集合的关系有包含、相等、真包含等。

二、数理逻辑数理逻辑是用数学方法来研究逻辑问题。

命题是具有真假值的陈述句。

比如，“今天是晴天”就是一个命题。

命题逻辑中的连接词有“非”“与”“或”“蕴含”“等价”等。

通过这些连接词，可以将简单命题组合成复合命题，并研究其真假性。

谓词逻辑则是对命题逻辑的扩展，它引入了量词“存在”和“任意”，能够更精确地表达命题。

三、关系关系是集合中元素之间的某种联系。

比如，在整数集合中，“大于”就是一种关系。

关系可以用矩阵和关系图来表示。

关系的性质包括自反性、反自反性、对称性、反对称性和传递性。

等价关系是一种特殊的关系，满足自反性、对称性和传递性。

比如，在整数集合中，“模 n 同余”就是一种等价关系。

偏序关系则是满足自反性、反对称性和传递性的关系。

四、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射、满射和双射。

单射是指不同的自变量对应不同的函数值；满射是指函数的值域等于整个目标集合；双射则是既单射又满射。

五、图论图由顶点和边组成。

可以分为无向图和有向图。

图的遍历算法有深度优先搜索和广度优先搜索。

最短路径问题是图论中的一个重要问题，比如迪杰斯特拉算法可以用来求解单源最短路径。

六、树树是一种特殊的图，没有回路且连通。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等领域都有着广泛的应用。

以下是对离散数学中一些重要知识点的整理。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象组成的整体。

集合的表示方法有列举法、描述法等。

列举法就是将集合中的元素一一列举出来，比如{1, 2, 3}；描述法是通过描述元素所具有的性质来表示集合，例如{x ｜ x 是大于 0 小于 5 的整数}。

集合之间的关系包括子集、真子集、相等。

如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集；如果两个集合的元素完全相同，那么它们相等。

集合的运算有并集、交集、差集等。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所得到的集合。

二、关系关系是集合中元素之间的某种联系。

比如在一个班级中，同学之间的“同桌关系”就是一种关系。

关系可以用矩阵和图来表示。

矩阵表示中，若元素之间存在关系则对应的位置为1，否则为0；图表示中，用点表示元素，用线表示关系。

关系的性质包括自反性、对称性、反对称性和传递性。

自反性是指每个元素都与自身有关系；对称性是指如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是指如果 a 与 b 有关系且 b 与 a 有关系，那么 a ＝b；传递性是指如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

关系的运算有复合关系和逆关系。

复合关系是将两个关系组合起来得到新的关系；逆关系是将原关系中的元素顺序颠倒得到的关系。

三、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射、满射和双射。

单射是指不同的定义域元素对应不同的值域元素；满射是指值域中的每个元素都有定义域中的元素与之对应；双射是既是单射又是满射。

以下是MIT离散数学的一些主要内容和笔记要点：
集合论：
集合论是离散数学的基础，它研究集合及其性质和运算。

集合是由元素组成的，元素之间通过集合运算进行组合。

常见的集合运算包括并集、交集、差集等。

命题逻辑：
命题逻辑是研究命题及其推理的逻辑系统。

命题是一个陈述句，它要么为真，要么为假。

命题逻辑中的基本概念包括原子命题、合取、析取、否定等。

图论：
图论是研究图的结构和性质的数学分支。

图是由顶点和边组成的，顶点表示对象，边表示对象之间的关系。

图论中的基本概念包括路径、回路、连通性等。

组合数学：
组合数学是研究计数问题的数学分支。

计数问题包括排列、组合、分割等问题。

组合数学中的基本概念包括加法原理、乘法原理等。

离散概率论：
离散概率论是研究离散随机事件的概率的数学分支。

离散随机事件是指可以列举出来的事件，如掷骰子、抽扑克牌等。

离散概率论中的基本概念包括概率空间、随机变量、期望等。

抽象代数：
抽象代数是研究代数结构的数学分支。

代数结构包括群、环、域等。

抽象代数中的基本概念包括群的定义、群的性质、环的运算等。

离散数学的其他分支：
离散数学还包括其他分支，如数理逻辑、集合论与泛函分析的交叉学科等。

数理逻辑是研究推理规则和推理系统的数学分支。

集合论与泛函分析的交叉学科是研究集合论和泛函分析之间的联系和应用的数学分支。

以上是MIT离散数学的主要内容和笔记要点，希望能对你有所帮助。

《离散数学》课时一 命题逻辑的基本概念1. 命题判定给定句子是否为命题，应该分两步：① 首先判定它是否为陈述句. ② 其次判断它是否有唯一真值.题1.下列语句中，下面哪一个选项是命题？（ ）你今天有空吗？ 请勿随地吐痰！ 我正在说谎.是偶数.答案：考点重要程度 分值题型 1.命题 ★★★ 选择、填空2.命题联结词 ★★★★★ 填空3.命题公式及其赋值★★★★解答1) 命题：能判断其真值的陈述句. 2) 真值：真、假. （1、0） 3) 真命题：真值为真的命题. 4) 假命题：真值为假的命题.5) 原子命题（简单命题）：不能再被分解成更简单的命题. 6) 复合命题：由简单命题通过联结词联结而成的命题.2.命题联结词联结词符号化真值表否定0 11 0合取0 0 00 1 01 0 01 1 1析取0 0 00 1 11 0 11 1 1蕴涵0 0 10 1 11 0 01 1 1等价0 0 10 1 01 0 01 1 1 优先顺序：题1.将下列命题符号化. 1.4不是素数. 2.小智和小红是学生. 3.小智和小红是同学. 4.小智是江苏人或者江西人. 5.小红喜欢唱歌或跳舞.6.①只要能被4整除，则一定能被2整除. ②只有能被4整除，则才能被2整除. ③能被4整除，仅当能被2整除.7.的充要条件是是无理数.答案：1.是素数.符号化为2.小智是学生.小红是学生.符号化为3.小智和小红是同学.符号化为4.小智是江苏人. 小智是江西人.符号化为5.小红喜欢唱歌. 小红喜欢跳舞.符号化为6.能被整除. 能被整除. 符号化为符号化为7.是无理数. 符号化为：自然语言中的“既……，又……”“不但……，而且……”“虽然……，但是……” “一面……，一面……”等.：“只要，就”，“因为，所以”，“仅当”，“只有才”，“除非才”，“除非，否则非”等等，符号化为.：“当且仅当”，“……充要条件”等.3. 命题公式及其赋值题1.写出下列公式的真值表，并求它们的成真赋值和成假赋值.的真值表1) 命题变元：取值1（真）或0（假）的变元.2) 合式公式：将命题变元用联结词或圆括号按一定逻辑关系联结起来的符号串. 3) 设是出现在公式中的全部命题变元，给各指定一个真值，称为对的一个赋值，若指定的一组值使为1，则称这组值为的成真赋值；若使为0，则称这组值的成假赋值.设为任一命题公式1) 若在它的各种赋值下取值均为真，则称为重言式或永真式. 2) 若在它的各种赋值下取值均为假，则称为矛盾式或永假式. 3) 若不是矛盾式，则称为可满足式.课时一练习题1.指出下列语句哪些是命题，哪些不是.如果是命题，指出它的真值.(1)计算机有视觉吗？(2)明天我去看球赛.(3)请勿大声喧哗！(4)不存在最大的质数.2.下列语句是命题的有（）.明天下午开会吗？2014年元旦是星期六.. 请保持安静！3.下列句子中有（）个命题.(1)我是老师. (2)禁止吸烟！ (3)蚊子是鸟类动物.(4)我正在说谎. (5)月亮比地球大.4.将下列命题符号化.(1)王强身体很好，成绩也很好.(2)小静只能挑选或房间.(3)如果和是偶数，则是偶数.5.（判断题）记：小李今天18岁，：小李今年19岁，则“小李今年18岁或19岁”可以翻译成. （）6.设：我听课，：我做课堂笔记.命题“我一边听课，一边做课堂笔记”符号化为____.7.设表示“天下大雨”，表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）.8.个命题变元组成的命题公式共有__________种不同真值指派情况.9.命题公式中成真赋值的个数为（）.10.下列命题公式中，哪个是永真式（）.11.求命题公式的真值表.课时二命题逻辑等值演算考点重要程度分值常见题型1.等值式★★★★★证明、解答2.析取范式与合取范式★★★★解答3.主析取范式与主合取范式必考填空、解答4.联结词的完备集★★判断、选择1.等值式设是两个命题公式，若构成的等价式为重言式，则称与是等值的，记作.常见等值式：1)双重否定律2)幂等律3)交换律4)结合律5)分配律（对的分配律）（对的分配律）6)德摩根律7)吸收律8)零律9)同一律10)排中律题1.推断公式类型.因此，该公式是一个重言式或者永真式.题2.用等值演算法证明. 得证.11) 矛盾律12)蕴涵等值式13)等价等值式14)假言易位15)等价否定等值式16)归谬论证明：证明：2.析取范式与合取范式题1：用等值演算法求取求下列公式：的合取范式和析取范式.解：(1)先求合取范式(2)再求析取范式1)文字：命题变元及其否定.2)简单析取式：仅由有限个文字构成的析取式.3)简单合取式：仅由有限个文字构成的合取式.4)析取范式：由有限个简单合取式的析取构成的命题式.，其中是简单合取式.5)合取范式：由有限个简单析取式的合取构成的命题式.，其中是简单析取式.3.主析取范式与主合取范式设与是命题变元含的极小项和极大项，则所有简单合取式都是极小项的析取范式称为主析取范式.所有简单析取式都是极大项的合取范式称为主合取范式.在含有个命题变元的简单合取式（简单析取式）中，若每个命题变元和它的否定式恰好出现一个且仅出现一次，而且命题变元或它的否定式按照下标从小到大顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）.表1 含的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称表2 含的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称题1.利用真值表法，按顺序求命题公式：的主析取范式. 解：因此，该命题公式的主析取范式是.题2.含个命题变项的命题公式的主合取范式为，则它的主析取范式为___________（表示成的形式）.答案：题3.求命题公式的主析取范式和主合取范式.因此，该命题公式的主析取范式是，解：主合取范式是.4. 联结词的完备集题1.(判断)命题联结词集是联结词完备集. （ ） 答案：正确.设是一个联结词集合，如果一个命题公式都可以由仅含中的联结词构成的公式表示，则称是一个联结词完备集. 设是两个命题，复合命题“与的否定式”称作的与非式，记作.即，“”称作与非联结词.复合命题“或的否定式”称作的或非式，记作.即，“”称作或非联结词.以下都是联结词完备集课时二练习题1.下列哪个公式是永假式（）.2.下列是重言式的为（）.3.求解的公式类型？（永真、永假、可满足）4.给定命题公式：，与之逻辑等价的是（）.5.用等值演算法证明等值式.6.任意两个不同大项的析取为________式，全体大项的合取式为________式.7.合式公式的主合取范式为（）.8.含个命题变项的命题公式的主析取范式为，则它的主合取范式________.9.构造命题公式的真值表，并由此写出它的主析取范式和主合取范式.10.已知命题公式，求主析取范式（要求通过等值演算推出）.11.某电路中有个灯泡和个开关、、.已知在且仅在下述种情况下灯亮：1)的扳键向上，、的扳键向下；2)的扳键向上，、的扳键向下；3)、的扳键向上，的扳键向下；4)、的扳键向上，的扳键向下.设表示灯亮，分别表示、、扳键向上，求的主析取和主合取范式.12.下面的联结词集合不是完备集的是________.（表示与非）13.联结词组中，下面哪一个选项是命题公式的最小联结词组（）.课时三 命题逻辑的推理理论考点重要程度 分值常见题型 1.推理的相关公式 ★★★★★选择、填空2.自然推理系统必考证明1. 推理的相关公式1) 设和是两个命题公式，当且仅当是重言式时，称从可推出或是前提的有效结论，记为.2) 命题公式推出的推理正确当且仅当为重言式.3) 推理的形式结构：前提： 结论：① 附加律②化简律③ 假言推理④拒取式 ⑤ 析取三段论⑥ 假言三段论 ⑦等价三段论⑧ 构造性二难构造性二难（特殊形式）⑨破坏性二难题1.求函数命题公式推的推理正确当且仅当__________为重言式. 答案：题2.下面不正确的是________.答案：2.自然推理系统题1：构造下面推理的证明.前提：结论：证明：①前提引入②前提引入③①②拒取式④前提引入⑤③④假言推理⑥前提引入⑦⑤⑥拒取式⑧前提引入⑨⑦⑧析取三段论得证是有效结论.题2.在自然推理系统中，构造并证明下列推理.（命题逻辑推理证明）如果小王是理科生，则他的数学成绩一定很好.如果小王不是文科生，则他一定是理科生.小王的数学成绩不好.所以，小王是文科生.解：设简单命题：小王是理科生.：小王的数学成绩很好.：小王是文科生.前提：结论：证明：①前提引入②前提引入③①②拒取式④前提引入⑤③④拒取式得证是有效结论.题3.用推理的形式结构证明：前提：结论：证明：①附加前提引入②①附加律③前提引入④②③假言推理⑤④化简律⑥⑤附加律⑦前提引入⑧⑥⑦假言推理得证是有效结论.题4.在自然推理系统中构造下面推理的证明.如果小张守第一垒并且小李向队投球，则队取胜；或者队未取胜，或者队成为联赛第一名；队没有成为联赛的第一名；小张守第一垒.因此，小李没向队投球.解：设简单命题：小张守第一垒.：小李向队投球.：队取胜.：队成为联赛第一名.前提：结论：证明：用归谬法①结论的否定引入②前提引入③前提引入④前提引入⑤④⑤拒取式⑥⑥置换⑦前提引入⑧⑦⑧析取三段论⑨①⑨合取由于最后一步，即，所以推理正确.课时三练习题1.若推理正确，则推理的结论一定是正确的.（）判断2.判断以下结论是否有效：前提是：：，结论是：.________（填“是”或“否”）3.下列个推理中，不正确的是（）.4.在自然推理系统中，用构造法证明下面推理.前提：结论：5.如果小张去看电影，则当小王去看电影时，小李也去.小赵不去看电影或小张去看电影.小王去看电影.所以当小赵去看电影时，小李也去.6.使用命题逻辑中的推理理论构造下面推理的证明：前提：结论：7.构造下面推理的证明：前提：，结论：.8.公安机关正在调查一宗盗窃案，现获得事实如下：(1)或盗窃了文物；(2)若盗窃了文物，则作案时间不可能在午夜前；(3)若证词正确，则在午夜前屋里灯光未灭；(4)若证词不正确，则作案时间发生在午夜前；(5)午夜时屋里灯光灭了.试问谁是盗窃犯？试写出推导过程.设:“盗窃了文物”，：“盗窃了文物”，：“作案时间发生在午夜前”，：“午夜前屋里灯光灭了”，：“证词正确”.课时四 谓词逻辑基本概念考点重要程度 分值常见题型 1.谓词逻辑命题符号化 ★★★★ 选择、填空2.谓词逻辑公式及其解释 ★★★选择1. 谓词逻辑命题符号化题1.将下列命题在谓词逻辑中用谓词符号化，并讨论它们的真值. (1) 只有是素数，才是素数. (2) 如果大于，则大于. 解：(1)设元谓词：是素数，命题可符号化为由于此蕴涵式的前件为假，所以命题为真. (2)设元谓词：，命题可符号化为由于为真，而为假，所以命题为假.个体词、谓词和量词是谓词逻辑命题符号化的个基本要素. 1) 个体词个体词是指所研究对象中可以独立存在的具体的或抽象的客体.将表示具体或特定的客体的个体词称作个体常项.而将表示抽象或泛指的个体词称作个体变项.并称个体变项的取值范围为个体域（或称作论域）.全总个体域：由宇宙间一切事物组成的个体域. 2) 谓词：刻画个体词性质及个体词之间相互关系的词.题2：命题“所有的人都长着黑头发”，令：是人；：长着黑头发.则该命题符号化为（）.答案：.题3.令：是人；：登上过月球.则命题“有的人登上过月球.”符号化（）.答案：题4.设有命题：是火车，：是汽车，：跑得比快，那么命题“有的汽车比一些火车跑得快”的逻辑表达式是__________.答案：.题5.设：是运动员，：是大学生，命题“不是所有的运动员都是大学生.”谓词符号化为__________.答案：或注：当多个量词出现时，它们的顺序一般不能随意调换.3)量词：表示个体之间数量关系的词全称量词：符号，表示个体域中“所有的”.“一切的”“所有的”“每一个”“任意的”“凡”“都”等.存在量词：符号，表示个体域中有一个个体.“存在”“有一个”“有的”“至少有一个”等.2.谓词逻辑公式及其解释题 1.指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项.解：是指导变元，量词的辖域.在中，是约束出现，而且约束出现两次，和均为自由出现，各自由出现一次.公式中含个量词，前件上的量词的指导变元为，的辖域，其中是约束出现，是自由出现.后件中的量词的指导变元为，的辖域为，其中是约束出现，均为自由出现.在整个公式中，约束出现一次，自由出现两次，自由出现一次，约束出现一次，自由出现一次.题2.设论域，与公式等价的命题公式是（）.答案：在公式和中，称为指导变元，为量词的辖域.在和的辖域中，的所有出现都称作约束出现，中不是约束出现的其他变项均称作自由出现.设为一公式，若在任何情况下的任何赋值下均为真，则称为永真式或逻辑有效式；若在任何情况下的任何赋值下均为假，则称为矛盾式或永假式.若至少存在一个情况下的一个赋值使为真，则称是可满足式.课时四练习题1.命题的意义是（）.对任何均存在使得；对任何均存在使得；存在对任何均使得；存在对任何均使得；2.设：是学生；：喜欢英语.则命题“有些学生喜欢英语”的符号化为_____.3.设：是人，：犯错误，命题“没有不犯错误的人”符号化为（）.4.令：是人，：是花，：喜欢，则命题“有些人喜欢所有的花”可符号化为_________.5.令：是火车，：是汽车，：比快，则命题“每列火车都比某些汽车快”在谓词逻辑中命题符号化为_________.6.试把下列语句翻译为谓词演算公式.(1)某些人喜欢所有明星； (2)并非“所有人均喜欢某些某些电脑游戏”.7.设个体域，消去公式中的量词为：___________.8.谓词公式中量词的辖域为（），量词的辖域为（）.课时五 谓词逻辑等值演算与推理考点重要程度 分值常见题型 1.谓词逻辑等值式与置换规则 ★★★选择、填空 2.谓词逻辑前束范式 ★★★★ 选择、解答3.谓词逻辑推理理论 必考证明1. 谓词逻辑等值式与置换规则设是谓词逻辑中任意两个公式，若是永真式，则称与等值，记作，称是等值式.下面给出谓词逻辑中的基本等值式. 1) 量词否定等值式 设公式含自由出现的个体变项，则2) 量词辖域收缩与扩张等值式 设公式含自由出现的个体变项，不含的自由出现，则题1.设个体域，将下列公式的量词消去.解：消去量词，得先缩小量词辖域，再消去量词，得3)量词分配等值式设公式含自由出现的个体变项，则4)命题逻辑中的重言式的代换实例都是谓词逻辑中的永真式.例如：先消去，得再消去，得题2.设是不含变元的公式，谓词公式等价于（）.答案：.题3.谓词公式的真值为，其中，：，定义域：. 答案：先消去，得再消去，得因此，的真值为1.2.谓词逻辑前束范式（前束范式存在定理）谓词逻辑中的任何公式都存在等值的前束范式.具有如下形式的谓词逻辑公式称作前束范式，其中为或，为不含量词的公式. 例，是前束范式不是前束范式题1：下列哪项为前束范式（）.答案：题2.求下列各式的前束范式.解：转化方法：1)把条件或双条件联结词转化；2)利用量词否定公式，把否定深入到命题变元和谓词公式的前面；3)换名；4)利用量词作用域的扩张和收缩等价式，把量词提到前面.3.谓词逻辑的推理理论在谓词逻辑中，从前提出发推出结论的推理的形式结构，依然采用如下的蕴涵式形式若上式为永真式，则推理正确，否则称推理不正确.①命题逻辑推理定律的代换实例.例如：②由基本等值式生成的推理实例.例如：由双重否定律可生成由量词否定等值式可以生成③一些常用的重要推理定律.④4条消去量词和引入量词的规则.全称量词消去规则：，不在中约束出现或，为任意个体常量.存在量词消去规则：，为使得为真的特定的个体常量.全称量词引入规则：，中无变元.前提：结论：证明：①前提引入②①③②化简律④②化简律⑤前提引入⑥⑤⑦③⑥假言推理⑧④⑦合取⑨⑧得证是有效结论.前提：结论：证明：①附加前提引入②置换③②④前提引入⑤④⑥③⑤析取三段论⑦⑥得证是有效结论.题3.证明下列各式.（简明注明使用等值式名称或推理定理名称）所有北极熊都是白色的，没有棕熊是白色的，所以北极熊不是棕熊.解：命题符号化：是北极熊. ：是白色的. ：是棕熊.前提：结论：证明：用归谬法①结论的否定引入②①置换③②④③化简律⑤③化简律⑥前提引入⑦⑥⑧④⑦假言推理⑨⑤⑧合取⑩⑨由于最后一步与前提中矛盾，所以推理正确.课时五练习题1.下列四个公式正确的有（）.2.在个体域中，若，，谓词有，，，，求的真值.3.下列等价关系正确的是（）.4.设个体域，消去公式中的量词.①②5.下列谓词公式中是前束范式的是（）.6.的前束范式为_________.7.求合式公式的前束范式____________.8.求谓词公式的前束范式.9.设个体域为，并对设定为，，，，其真值为的公式为__________.10.证明题前提：；结论：11.在自然推理系统中构造下面推理再证明.前提：，结论：12.先将下列推理符号化，再利用推理规则证明推理的正确性.所有的大一学生都要学习英语；并非所有的大一学生都要学习离散数学；故有些学习英语的不学习离散数学.假设谓词如下：：是大一学生；：要学习英语；：要学习离散数学.课时六 集合代数考点重要程度 分值常见题型 1.集合的基本概念 ★★ 选择、填空2.集合的运算 ★★★ 选择、填空3.有穷集的计数 ★★★ 解答4.集合恒等式 ★★★证明1. 集合的基本概念题1.，将的子集分类.元子集，也就是空集：； 元子集：； 元子集：； 元子集：；1) 把一些事物汇集到一起组成一个整体就称作集合，而这些事物就是这个集合的元素或成员.元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作.例：，2) 设为集合，如果中的每个元素都是中的元素，则称是的子集，记作,如果不被包含，记作.3) 设为集合，如果且，则称与相等，记作.4) 设为集合，如果且,则称是的真子集，记作.5) 不含任何元素的集合称作空集，记作.空集是一切集合的子集.6) 含有个元素的集合简称为元集，它的含有个元素的子集称作它的元子集.题2.设，则下列正确的是（）.答案：.题3.已知集合，则的幂集合___________.元子集：元子集：元子集：元子集：答案：.2.集合的运算8)若是元集，则有个元素.9)在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作.7)设为集合，把的全体子集构成的集合称作的幂集，记作.1)并运算：2)交运算：3)差运算：4)对称差：5)的绝对补集定义如下：题1：设，，则差集 ，而对称差.答案：.题2.设全集的子集为，，，. 答案：,.3. 有穷集的计数题1.对名会外语的科技人员进行掌握外语情况的调查.其统计结果如下：会英、日、德和法语的人分别是和人，其中同时会英语和日语的有人，会英、德、和法语中任两种语言的都是人.已知会日语的人既不懂法语也不懂德语，分别求只会一种语言（英、德、法、日）的人数和会种语言的人数. 解：令分别表示会英、法、德、日语的人的集合，根据题意画出文氏图如下图所示.设同时会种语言的有人，只会英、法或德语一种语言的分别为和人.将和填入图中相应的区域，然后依次填入其他区域的人数.根据已知条件列出方程组解，得.因此，只会英语、德语、法语、日语的人数 为，会种语言的人数为.包含排斥原理：题2.请用集合计数的包含排斥原理，计算之间既不能被和，也不能被整除的数的个数.解：设可被整除可被整除可被整除用表示有穷集的元素数，表示小于等于的最大整数，则有4. 集合恒等式下面的恒等式给出了集合运算的主要算律，其中代表任意的集合.幂等律结合律交换律分配律同一律零律排中律矛盾律吸收律德摩根律题1.证明.证：除了以上算律以外，还有一些关于集合运算性质的重要结果.例如：课时六练习题1.下面是真命题的是（）.2.若集合的元素个数，则其幂集的元素个数___________.3.设集合，则__________.4.设是集合，若，则（）.5.设集合被整除，,被整除，，则__________，___________.6.，求__________.7.计算机班的名学生中，有人在第一次考试中得，人在第次考试中得，已知有人两次考试均未得，则两次考试都得的学生人数为__________人.8.某班有个学生，会语言的人，会语言的人，会语言的人，以上三门都会的人，都不会的没有，请问仅会两门的有几人？（要求写出求解过程）9.某大学计算机专业名学生中，语言课有人优秀，数据结构课有人优秀，离散数学课有人优秀.并且语言和数据结构两门课都优秀的有人；语言和离散数学两门课都优秀的有人；数据结构和离散数学两门课都优秀的有人.此外，还有人一门优秀都没得到.如果获得门优秀者可得奖学金元，获得门优秀者可得奖学金元，仅获得一门优秀者可得奖学金元，问为该专业学生发奖学金需多少元？10.设是三集合，已知，则一定有.（）11.集合的运算满足结合律，吸收律.（）12.证明.13.设是任意集合，证明等式.课时七 二元关系（1）考点重要程度 分值常见题型 1.有序对与笛卡尔积 ★★★ 填空、解答2.二元关系 ★★★★★ 选择、填空3.关系的运算 ★★★★填空、解答1. 有序对与笛卡尔积题1.设，求.若，则.由两个元素和按照一定顺序排列而成的二元组称作一个有序对或序偶，记作，其中是它的第一元素，是它的第二元素.设为集合，用中元素为第一元素，中元素为第二元素构成有序对，所有这样的有序对组成的集合称作和的笛卡尔积，记作，符号化表示为笛卡尔积运算具有以下性质：1) 对任意集合，根据定义有.2) 一般地说，笛卡尔积运算不满足交换律，即（当时）3) 笛卡尔积运算不满足结合律，即 （当时）4)笛卡尔积运算对并和交运算满足分配律，即2.二元关系1)如果一个集合满足以下条件之一：a)集合非空，且它的元素都是有序对；b)集合是空集.则称该集合为一个二元关系，记作，二元关系也可简称为关系.对于二元关系，如果，则记作.2)设为集合，的任何子集所定义的二元关系称作从到的二元关系，特别当时称作上的二元关系.3)若，那么，的子集就有个，每一个子集代表一个上的二元关系，因此上有个不同的二元关系.题1.设集合，设关系为上的小于关系，则 .答案：.题2.设为集合，且，则上最多可定义个不同的二元关系.答案：.题1.，则的关系矩阵是 .答案：.题5.已知集合上的二元关系的关系矩阵，那么 .答案：.上的特殊关系：空关系，全域关系，恒等关系.空关系：空集全域关系：恒等关系：给出一个关系的方法有种：集合表达式、关系矩阵和关系图.设，是上的关系，的关系图记作，有个顶点，若，在中就有一条从到的有向边.3.关系的运算设是二元关系1)中所有有序对的第一元素构成的集合称作的定义域，记作，形式化表示为2)中所有有序对的第二元素构成的集合称作的值域，记作，形式化表示为3)的定义域和值域的并集称作的域，记作，形式化表示为题1.，求.4)设是二元关系，的逆关系，简称为的逆，记作，其中5)设为二元关系，对的右复合记作，其中题2.设，，求.。

离散数学笔记目录1.1 什么是集合 (2)1.2 集合内部 (2)1.3 集合运算 (3)1.3 运算定律及证明 (4)1.5 可数集合与不可数集合 (5)2.1 什么是命题 (5)2.2 命题联结词 (6)2.3 命题符号化及应用 (7)2.4 命题公式和真值表 (7)2.5 公式的分类和逻辑等价 (8)2.6 基本等价关系及其应用 (8)集合论1.1 什么是集合一、什么是集合1.定义：集合是由指定范围内的满足给定条件的所有对象聚集在一起构成，每一个对象称为这个集合的元素。

二、集合的符号表示1.表示字母：用大写英文字母表示集合: A, B, C, · · · , A1, B2, C3, · · ·用小写英文字母表示元素: a, b, c, · · · , a1, b2, c3, · · ·2.表示方法：（1）枚举法：列出集合中的全部元素或者仅列出一部分元素，其余用省略号(· · · ) 表示。

B = {2, 4, 6, 8, 10, · · · }（2）叙述法：通过刻画集合中元素所具备的某2.种性质或特性来表示一个集合。

P = {x|P(x)}（3）文氏图：一般使用平面上的方形或圆形表示一个集合，而使用平面上的一个小圆点来表示集合的元素。

3.关系：（1）属于关系若 a 是集合 A 中的元素，则称a属于A，记为a∈A若 a 不是集合 A 中的元素，则称a不属于A，记为a∉A4.基数（1）集合A 中的元素个数称为集合的基数，记为|A|（2）集合的基数有限，称为有限集（3）集合的基数无限，称为无限集1.2 集合内部一、空集1.定义：不含任何元素的集合叫做空集，记作∅. 空集可以符号化为∅= {x|x ≠ x}.【NB】空集是绝对唯一的。

自考离散数学命题演算笔记一、命题演算的基本概念1. 命题：可以明确判断真假的陈述句称为命题。

2. 命题符号：用字母（如p、q、r等）表示的命题称为命题符号。

3. 命题演算：研究命题符号之间关系的数学分支。

二、命题演算的基本运算1. 否定（¬）：表示对命题的否定，如¬p表示对p的否定。

2. 合取（∧）：表示两个命题的合取，如p∧q表示p和q同时为真。

3. 析取（∨）：表示两个命题的析取，如p∨q表示p和q至少有一个为真。

4. 蕴含（→）：表示两个命题的蕴含关系，如p→q表示如果p为真，则q必为真。

5. 双条件（↔）：表示两个命题的双条件关系，如p↔q表示p和q同时为真或同时为假。

三、命题演算的基本法则1. 双重否定律：¬¬p = p2. 假言三段论：p→q, ¬q→¬p3. 假言换位：p→q ↔ ¬q→¬p4. 交换律：p∧q ↔ q∧p, p∨q ↔ q∨p5. 结合律：p∧(q∧r) ↔ (p∧q)∧r, p∨(q∨r) ↔ (p∨q)∨r6. 分配律：p∧(q∨r) ↔ (p∧q)∨(p∧r), p∨(q∧r) ↔(p∨q)∧(p∨r)7. 吸收律：p∧(p∨q) ↔ p, p∨(p∧q) ↔ p8. 德摩根律：¬(p∧q) ↔ ¬p∨¬q, ¬(p∨q) ↔ ¬p∧¬q9. 互补律：p∨¬p ↔ 1, p∧¬p ↔ 010. 等幂律：p∧p ↔ p, p∨p ↔ p自考离散数学命题演算笔记四、命题逻辑函数命题逻辑函数是指对命题进行运算的函数，它将命题作为输入，输出也是一个命题。

常见的命题逻辑函数包括：1. 常函数：常函数的输出是一个固定的命题，无论输入是什么。

例如，常真函数T的输出始终为真，常假函数F的输出始终为假。

2. 投影函数：投影函数的输出是其输入之一。

离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：A、V、一、f「。

记住“p仅当q”意思是“如果p,则q"，即p-。

记住“q除非p”意思是“」p-q”。

会考察条件语句翻译成汉语。

构造真1.2语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过p推导出q,证永真式是通过p推导出T。

(p—r)A(q-r) = (pVq)-r(p—q)V(p-r) = p—(qVr)(p—r)V(q-r) = (pAq)-r双条件命题等价式pf = (pfq) A (qfp)pf = -pfqpf Q (pAq) V(-pA-q)「(pf) = pfq1.4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如V x>0P(x)。

当论域中的元素可以一一列举，那么V xP(x)就等价于P(x1)AP(x2)...A P(xn)。

同理，3 xP(x)就等价于 P(x1)VP(x2)...VP(xn)。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如V x(P(x)AQ(x))和(V xP(x)) A (V xQ(x))。

量词表达式的否定：「V xP(x) Q 3 x-P(x),「3 xP(x) Q V x-P(x)。

1.5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证不代命题和量化命题的组合使用。

二、集合、函数、序列、与矩阵2.1集合£说的是元素与集合的关系，^说的是集合与集合的关系。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等众多领域都有着广泛的应用。

下面就为大家整理一下离散数学的主要知识点。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象组成的整体。

集合的表示方法有列举法、描述法等。

集合的运算包括并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所剩下的元素组成的集合；补集是在给定的全集内，某个集合的补集是由全集中不属于该集合的元素组成的集合。

集合之间的关系有包含、相等、真包含等。

包含关系是指一个集合中的所有元素都属于另一个集合；相等关系是指两个集合中的元素完全相同；真包含关系是指一个集合包含另一个集合，且两个集合不相等。

二、关系关系是集合中元素之间的某种联系。

关系可以用集合的形式来表示。

关系的性质包括自反性、对称性、反对称性和传递性。

自反性是指集合中的每个元素都与自身有关系；对称性是指如果元素 a 与元素 b 有关系，那么 b 与 a 也有关系；反对称性是指如果元素 a 与元素 b 有关系，且 b 与 a 也有关系，那么 a 等于 b；传递性是指如果元素 a 与元素 b 有关系，b 与元素 c 有关系，那么 a 与 c 也有关系。

关系的运算有合成运算、逆关系等。

合成运算可以得到新的关系，逆关系是将原关系中的元素顺序颠倒得到的关系。

三、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的性质包括单射、满射和双射。

单射是指定义域中的不同元素在值域中的对应元素也不同；满射是指值域中的每个元素都有定义域中的元素与之对应；双射是指函数既是单射又是满射。

四、图论图由顶点和边组成。

边可以是有向的或无向的。

图的类型有很多，如简单图、多重图、连通图等。

简单图是指没有自环和多重边的图；多重图允许存在自环和多重边；连通图是指图中任意两个顶点之间都存在路径。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息技术、通信工程等领域有着广泛的应用。

以下是对离散数学中一些重要知识点的整理。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象所组成的整体。

集合的表示方法有列举法和描述法。

列举法就是将集合中的元素一一列举出来，用花括号括起来；描述法是通过描述元素所具有的性质来表示集合。

集合之间的关系包括子集、真子集、相等。

如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集；如果两个集合的元素完全相同，那么它们相等。

集合的运算有并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同的元素组成的新集合；差集是从一个集合中去掉另一个集合的元素所剩下的元素组成的集合；补集是在给定的全集 U 中，去掉集合 A 的元素，剩下的元素组成的集合。

二、关系关系是集合中元素之间的某种联系。

可以用笛卡尔积来定义关系。

关系的性质包括自反性、反自反性、对称性、反对称性和传递性。

自反性是指集合中的每个元素都与自身有关系；反自反性则是集合中的任何元素都与自身没有关系；对称性是如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是如果 a 与 b 有关系且 b 与 a 有关系，那么 a 等于 b；传递性是如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

关系可以用关系矩阵和关系图来表示。

关系矩阵是一个二维矩阵，其中的元素表示对应元素之间是否有关系；关系图则是用节点表示元素，用有向边表示关系。

三、函数函数是一种特殊的关系，它对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射函数（一对一函数）、满射函数（映上函数）和双射函数（一一对应函数）。

单射函数是指不同的定义域元素对应不同的值域元素；满射函数是指值域中的每个元素都有定义域中的元素与之对应；双射函数则同时满足单射和满射的性质。