离散数学。
第一章：命题逻辑。
目标语言：表达判断的一些语言的汇集。
判断：对事物有肯定或否定的一种思维模式。
命题：能表达判断语言的陈述句。
原子命题：不能分解为更简单陈述句的语句。
复合命题：由联结词，标点符号和原子命题复合构成的命题，称作复合命题。
命题标识符：表示命题的符号。
命题变元：只表示命题位置标志的命题标识符。
原子变元：当命题变元表示原子命题的时候。
否定：合式公式：命题推演的合式公式规定为：
1) 单个命题边缘本省是一个合式公式。
2) 如果a是合式公式，那么是合式公式。
3) 如果a和b都是合式公式，那么，，和都是合式公式。
4) 当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题的变元，联结词和括号的符号串是合式公式。
翻译：把自然语言中有些语句翻译成数理逻辑中的形式符号。
优先次序：联结词运算的优先次序为：。
真值表：在命题公式中，根据分量指派真值的各种可能组合，旧确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题的真值表。
逻辑相等：给定两个命题公式和，设为任一组真值指派，和的真值都相同，则称和是等价的或逻辑相等，记作：
子公式：如果是合式公式的一部分，且本身也是一个合式公式，则称为公式的子公式。
定理：设是合式公式的子公式，若，则将中的用来置换，所得公式b与公式a等价，即。
重言式：给定一个命题公式，若无论对分量进行怎样的指派，其对应的真值永为真，则称命题公式为重言式或永真公式。
矛盾式：给定一个命题公式，若无论对分量进行怎样的指派，其对应的真值永为假，则称命题公式为矛盾式或永假公式。
蕴涵式：当且仅当是一个重言式时，称蕴涵，并记作。
逆转式：对来说，称为其逆转式。
反换式：对来说，称为其反换式。
逆反式：对来说，称为其逆反式。
定理：任何两个重言式的合取或析取时一个重言式。
定理：一个重言式，对同一分量都用任何合取公式置换，其结果仍为一重言式。
定理：设是两个命题公式，当且仅当为一个重言式。
定理：设是两个命题公式，的充要条件是，且。
最小联结词组：对于任何一个命题公式，都能由仅含这些连接词的命题公式等价代换，而比这些联结词再少的命题公式不能对给定的公式作等价代换，这样的连接词组就是最小联结词。
对偶式：在给定的命题公式中，使联结词变为。
第二章：谓词公式。
谓词：在反应判断的句子中，用以刻画客体的性质或关系。
谓词填式：把谓词字母后填以客体所得的式子称为谓词填式。
n元谓词： 由n个客体插入到固定位置上的谓词填式称为n元谓词。
命题函数：由一个谓词，一些客体变元组成的表达式称为简单命题函数。命题函数不是一个命题，只有当客体变元取特定一个名称时才成为命题。
复合命题函数：由一个或n个简单命题函数以及括号、逻辑连接词组成的表达式成为复合命题函数。
个体域：在命题函数中，命题变元的论述称为个体域。
全总个体域：把各种个体域综合在一起，作为论述范围的域，成为全总个体域。
全称量词：符号“”称为全称量词，表示“对于所有的”，“每一个”，“至少有一个”，“对任意一个”，“凡”，“一切”等词。
存在量词：符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。
存在唯一量词：符号“”称为存在唯一量词，用以表达“恰有一个”，“存在唯一一个”等词。
特性谓词：使用全总个体域，限定客体变元变化范围的量词，称为特性谓词。
原子公式：把形如称为谓词演算的原子公式，其中，是客体变元。
合式公式：谓词演算的合式公式由如下各条组成：
1) 原子谓词公式是合式公式。
2) 若是合式公式，则是一个合适公式。
3) 若和都是合适公式，则，，和是合适公式。
4) 如果是合适公式，是**现的任何变元，则，和都是合式公式。
5) 只有经过有限次的应用（1）、（2）、（3）、（4）所得到的公式才是合式公式。
指导变元：给定为一个谓词公式，其中有一部分公式形式为，或，或。这里，，的后面跟的称为相应量词的指导变元。
辖域：给定谓词公式中，，和中的称为相应量词的辖域。
约束变元：在作用域中，的一切出现，称为在公式中的约束出现，所有约束出现的变元。
自由变元：在谓词公式中，除去约束变元以外所出现的变元。
换名：对公式中的约束变元，遵照一定的规则跟该名称符号。
代入：是对自由变元代以式子，代入后的结果式是原式的特例。
赋值：在谓词公式中常包含命令变元和课题变元，当客体变元由确定的课题所取代，命题变元用确定的命题所取代时，就称为对谓词公式赋值。一个谓词公式经过赋值以后，就称为具有确定真值的命题。
等价：给定任何两个谓词公式和，设它们有共同的个体域，若对和的任一组变元进行赋值所得命题的真值相同，则称谓词公式和在上是等价的，并记为。
有效：给定任意谓词公式，对于其个体域，对于的所有赋值，为真，则称在上是有效的（或永真的）。
不可满足的：一个谓词公式，如果在所有赋值下都为假，则称该为不可满足的（或、永假的）。
可满足的：一个，如果至少在一种赋值下为真，则称该为可满足的。
谓词演算中的等价公式和蕴涵公式：命题演算中的等加工时表和蕴涵公式表都可推广到谓词演算中的使用，此外还有如下一些谓词公式的等价公式和蕴涵公式。
1） 蕴涵公式：
2） 等价公式：
前束范式：一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式，其形式为，其中是量词，或，是客体变元，是没有量词的谓词公式。
前束合取范式：一个如果具有如下形式，则称为前束合取范式：
其中是量词，或，是客体变元，是原子公式或其否定。
前束析取范式：一个如果具有如下形式，则称为前束合取范式：
其中是量词，或，是客体变元，是原子公式或其否定。
定理：任意一个谓词公式均和一个前束范式等价。
定理：每一个都可以转化为与其等价的前束合取范式。
定理：每一个都可以转化为与其等价的前束析取范式。
全称指定规则：如果对论域中所指的客体，成立，则对论域中某个任意客体，有成立。这个规则可表示为，简称us。
全程推广规则：如果能够证明对论域中每一个客体断言都成立，则可得到结论对论域。这个规则可表示为，简称ug。
存在指定规则：如果对论域中某些客体成立，则对论域中某个制定客体，使得成立。这个规则可表示为，简称es。
存在推广规则：如果能够证明对论域中每一个客体，有成立，则在论域中必存在，使得成立。这个规则可表示为，简称eg。
带有量词蕴含公式和等价公式。
图论：图：三元有序组称为图，其中是非空结点集，是连接结点的边集，是边集到节点无序偶（有序偶）集合上的函数。因每条边总是关联连个节点，故图常记为。
无向边：边是两个点的无序偶对。
有向边：边是两个点的序偶。
有向图：每一条边都是有向边的图。
无向图：每一条边都是无向边的图。
混合图：图既有有向边又有无向边的图。在此暂不讨论。
邻接点：若两个点有边（有向或无向）相连，则称这两个点邻接。
邻接边：若两条边有公共点，则称这两条边邻接。
环：只与一个结点关联的边（可以作为有向边，也可以作为无向边）
结点的度：与结点v关联的边数（约定：对于环，度加2）。记为deg(v)
图的最大度：。
图的最小度：
出度：在有向图中，由一个结点射出的边数称为该结点的出度。
入度：在有向图中，射入一个结点的边数称为该结点的入度。
定理1： 每个无向图，结点度数的总和等于边数的两倍。即：
定理2：在任何图中，度数为奇数的结点个数必定是偶数。
定理3：在有向图中，所有结点的入度之和等于所有结点的出度之和。
关联：边连接了点，则称点和边关联，或称边和点关联。
注意：邻接是指点点或边边的关系，关联是指点边的关系。
孤立点：在图中不与任何其他结点邻接的点。
零图：仅由孤立点组成的图（可以有多个结点），即e是空集。
平凡图：只有一个孤立点组成的图，即只有一个结点的零图。
图是序偶，序偶元素是集合，第二个集合是第一个集合的元素的偶对的集合。
注意：1）图不同于**，**是在平面上用点、边表示点的集合及其点点之间的关系。
2）对于同一个图，可以画出不同形状的**，但这些**的一定是同构的。
3）对于同一个**，可以写出用不同符号表示的图（g = v, e >的形式），但这些图也是彼此同构的。
平行边：连接于同一对结点间的多条边。
多重图：含有平行边的图。
简单图：不含有平行边的图。以后只讨论简单图。
完全图：每一对结点见都有边相连的简单图。有个结点的完全图记为。
定理4：个结点的无向完全图的边数为。
相对与完全图的补图：由图中所有节点以及所有能使成为完全图的添加边组成图，称为相对于完全图的补图，简称的补图，记作。换句话说，是完全图去掉g的边形成的图。
子图：点的子集，以及相应的边的子集，叫原图的子图。
生成子图：如果的子图包含的所有结点，称该子图为的生成子图。
相对于图的补图：设是图的子图，若有图使，且中仅包含的边所关联的结点，则是子图`相对于图的补图。
图的同构：设图及，如果存在一一对应的映射，且或是的一条边，当且仅当或是的一条边，则同同构，记为。
两图的同构的判断方法：
1）结点数、边数要相同。
2）度数相同的结点数目相等。
3）有相同的特性：
a. 都有长度为的回路。
b. 度为的点正好和度为的点有边相连。
c. 有环的点（或其他特征）与最大度数的点的距离相同。
注意：同构的图本质上是同一个图，只不过结点的编号不同而已。
因此，对于同一个图，可以画出不同形状的**，但这些**的一定是同构的。对于同一个**，可以对结点进行不同的编号，得到不同的图的表示，这些图同构。
路：设是关联于结点和的边，交替序列称为连接到的路。
回路：在交替序列中，当时称此交替序列为回路。
迹：所有边均不相同的一条路。
圈：在通路中，。即：闭的通路；
通路：所有结点均不相同的一条路。
连通：在无向图中，结点和之间若存在一条路，则称结点和结点两点连通；
连通分支：结点之间的连通性是结点上的等价关系，由该等价关系可将分成非空子集，每一个非空子集确定了一个连通子图记为。称为图的连通分支。图的连通分支数记为。
连通图：无向图只有一个连通分支。换句话说，任意两点都连通的无向图叫连通图。
离散数学复习试卷
一 填空题。1 使得公式p q r 成真的赋值是使得公式p q r 成假的赋值是2 设个体域为d 1,2,3，试消去公式 x p x y q y 中量词的等价式 个元素的集合共有 个不同的划分，4 设a 1,2，求 a p a 5 无向树t有8片树叶，2个3度分枝点，其余的分枝点都是4度结点，问t有...
《离散数学》试题
试卷编号 8343座位号 浙江广播电视大学2006年秋季学期期末考试。离散数学 试题。2007年1月。1 设r 则定义域dom r 2 一棵无向树的顶点数n与边数m关系是。3 公式x a x b y，x z c y，z d x 中，自由变元是。4 pq pq 1 令p 今天下雨了，q 我上学，则命题...
离散数学试题
网络学院离散数学模拟试题1 考试时间 90 分钟考试方式 开卷。专业年级姓名学号 一 选择填空题 每个空格3分，共30分。答案写在答题纸上。1b.b.cd.2 若集合p q满足，则 必成立。c abcd 3 设，则是 d a 从x到y的双射。b 从x到y的满射，但不是单射。c 从x到y的映射，但不是...