下载文档原格式
离散数学笔记总结一、命题逻辑。
1. 基本概念。
- 命题：能够判断真假的陈述句。
例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。
- 命题变元：用字母表示命题，如p,q,r等。
2. 逻辑联结词。
- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。
- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。
- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。
- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。
- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。
3. 命题公式。
- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。
- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。
- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。
4. 逻辑等价与范式。
- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。
例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。
- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。
- 合取范式：由有限个简单析取式的合取组成的命题公式。
- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。
- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。
二、谓词逻辑。
1. 基本概念。
- 个体：可以独立存在的事物，如人、数等。
- 谓词：用来刻画个体性质或个体之间关系的词。
例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。
- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。
- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。
离散数学中的二元关系1 什么是二元关系二元关系是离散数学里面一个重要的概念，指的是两个可以分别属于两个集合A和B的元素之间的关系。
它是一种特殊的集合论概念，意味着在某一个函数f上，两个元素之间存在着一种单一的关系，这种关系被称之为二元关系。
这种二元关系可以用写成集合的形式也可以是表的形式。
2 二元关系表的一般形式一般的二元关系表的形式为：$f=\left\{\left(x,y\right)\inA\times B \mid P(x,y)\right\}$其中，A和B都是集合，P(x,y)是关于它们的关系式，学习中会有各种关系式，比如等于、不等于、大于及小于等。
3 二元关系的类型由于不同的二元关系关系式不同，所以，二元关系也可以分为多种类型。
常见的有：（1）等价关系：表示两个可以互换的元素之间的关系，一般以“=”表示，也可以一一对应；（2）全序关系：表示两个元素之间的一种“前大于后”的关系，一般以“>”或“<”表示，可以用来描述一种有序的类型；（3）传递关系：这种关系意味着“当关系式成立时，如果保持原有的条件不变，则关系式仍然成立”，这种关系一般以“++”表示；（4）偏序关系：和全序关系类似，也是一种前大于后的一种关系，但不代表完全的大小，只是一种大体的参照，一般以“>+”及“<+”表示；（5）子集关系：子集关系是一个集合是某个集合的子集，一般以“⊆”表示；（6）关联关系：此关系也称为满足关系，是指满足一定的关系式，两个或多个元素有直接或间接的关系，一般以“→”表示。
4 二元关系的应用二元关系是离散数学中很重要的概念，与它特殊的表达方式有着密切的联系。
在数学运算中，二元关系常常被用来表示集合之间的关系、排列组合以及概率等，还应用于计算机科学中的图论。
此外，在社会学、心理学等学科中，二元关系也被广泛应用，它有助于理解彼此之间的关系、区分概念及表达媒体变化等。
