离散数学复习总结+试题

离散数学

第一章：命题逻辑

目标语言：表达判断的一些语言的汇集。

判断：对事物有肯定或否定的一种思维模式。

命题：能表达判断语言的陈述句。

原子命题：不能分解为更简单陈述句的语句

复合命题：由联结词，标点符号和原子命题复合构成的命题，称作复合命题。

命题标识符：表示命题的符号。

命题变元：只表示命题位置标志的命题标识符。

原子变元：当命题变元表示原子命题的时候。

否定：

合式公式：命题推演的合式公式规定为：

(1) 单个命题边缘本省是一个合式公式。

(2) 如果A是合式公式，那么A是合式公式

(3) 如果A和B都是合式公式，那么AB，AB，AB和AB都是合式公式。

(4) 当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题的变元，联结词和括号的符号串是合式公式。

翻译：把自然语言中有些语句翻译成数理逻辑中的形式符号。

优先次序：联结词运算的优先次序为：，，，，。

真值表：在命题公式中，根据分量指派真值的各种可能组合，旧确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题的真值表。

逻辑相等：给定两个命题公式A和B，设12,,,nPPP为任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等，记作：AB

子公式：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。

定理：设X是合式公式A的子公式，若XY，则将A中的X用Y来置换，所得公式B与公式A等价，即AB。

重言式：给定一个命题公式，若无论对分量进行怎样的指派，其对应的真值永为真，则称命题公式为重言式或永真公式。

矛盾式：给定一个命题公式，若无论对分量进行怎样的指派，其对应的真值永为假，则称命题公式为矛盾式或永假公式。

蕴涵式：当且仅当PQ是一个重言式时，称P蕴涵Q，并记作PQ。

逆转式：对PQ来说，PQ称为其逆转式。

反换式：对PQ来说，PQ称为其反换式。

逆反式：对PQ来说，QP称为其逆反式。

定理：任何两个重言式的合取或析取时一个重言式。

定理：一个重言式，对同一分量都用任何合取公式置换，其结果仍为一重言式。

定理：设,AB是两个命题公式，AB当且仅当AB为一个重言式。

定理：设,PQ是两个命题公式，PQ的充要条件是PQ，且QP

最小联结词组：对于任何一个命题公式，都能由仅含这些连接词的命题公式等价代换，而比这些联结词再少的命题公式不能对给定的公式作等价代换，这样的连接词组就是最小联结词。

对偶式：在给定的命题公式A中，使联结词变为

第二章：谓词公式

谓词：在反应判断的句子中，用以刻画客体的性质或关系。

谓词填式：把谓词字母后填以客体所得的式子称为谓词填式。

n元谓词： 由n个客体插入到固定位置上的谓词填式称为n元谓词。

命题函数：由一个谓词，一些客体变元组成的表达式称为简单命题函数。命题函数不是一个命题，只有当客体变元取特定一个名称时才成为命题。

复合命题函数：由一个或n个简单命题函数以及括号、逻辑连接词组成的表达式成为复合命题函数。

个体域：在命题函数中，命题变元的论述称为个体域。

全总个体域：把各种个体域综合在一起，作为论述范围的域，成为全总个体域。

全称量词：符号“”称为全称量词，表示“对于所有的”，“每一个”，“至少有一个”，“对任意一个”，“凡”，“一切”等词。

存在量词：符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。

存在唯一量词：符号“!”称为存在唯一量词，用以表达“恰有一个”，“存在唯一一个”等词。

特性谓词：使用全总个体域，限定客体变元变化范围的量词，称为特性谓词。

原子公式：把形如12,,,nAxxx称为谓词演算的原子公式，其中，12,,,nxxx是客体变元。

合式公式：谓词演算的合式公式由如下各条组成：

(1) 原子谓词公式是合式公式

(2) 若A是合式公式，则A是一个合适公式

(3) 若A和B都是合适公式，则AB，AB，AB和AB是合适公式

(4) 如果A是合适公式，x是中出现的任何变元，则xA，xA和!xA都是合式公式。

(5) 只有经过有限次的应用（1）、（2）、（3）、（4）所得到的公式才是合式公式。

指导变元：给a定为一个谓词公式，其中有一部分公式形式为xPx，或xPx，或!xPx。这里，，!的后面跟x的称为相应量词的指导变元

辖域：给定谓词公式中，xPx，xPx和!xPx中的Px称为相应量词的辖域。

约束变元：在作用域中，x的一切出现，称为x在公式a中的约束出现，所有约束出现的变元。

自由变元：在谓词公式a中，除去约束变元以外所出现的变元。

换名：对公式a中的约束变元，遵照一定的规则跟该名称符号。

代入：是对自由变元代以式子，代入后的结果式是原式的特例。

赋值：在谓词公式中常包含命令变元和课题变元，当客体变元由确定的课题所取代，命题变元用确定的命题所取代时，就称为对谓词公式赋值。一个谓词公式经过赋值以后，就称为具有确定真值的命题。

等价：给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E，若对A和B的任一组变元进行赋值所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记为AB。

有效：给定任意谓词公式wffA，对于其个体域E，对于A的所有赋值，wffA为真，则称wffA在E上是有效的（或永真的）。

不可满足的：一个谓词公式wffA，如果在所有赋值下都为假，则称该wffA为不可满足的（或、永假的）。

可满足的：一个wffA，如果至少在一种赋值下为真，则称该wffA为可满足的。

谓词演算中的等价公式和蕴涵公式：命题演算中的等加工时表和蕴涵公式表都可推广到谓词演算中的使用，此外还有如下一些谓词公式的等价公式和蕴涵公式。

（1） 蕴涵公式：

xAxxBxxAxBx xxBxxAxxBx

（2） 等价公式：

xAxBxxAxxBx，

xAxBxxAxxBx，

xAxxAx，

xAxxAx，

xABxAxBx，

xABxAxBx， xAxBxxAxxBx，

xAxBxAxB，

xAxBxAxB，

AxBxxABx，

AxBxxABx。

前束范式：一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式，其形式为12nvvvA，其中是量词，或，1,2,3,,ivin是客体变元，A是没有量词的谓词公式。

前束合取范式：一个wffA如果具有如下形式，则称为前束合取范式：

12121112121222nllvvvAAAAAA

12mmmmlAAA

其中是量词，或，1,2,3,,ivin是客体变元，ijA是原子公式或其否定。

前束析取范式：一个wffA如果具有如下形式，则称为前束合取范式：

12121112121222nllvvvAAAAAA

12mmmmlAAA

其中是量词，或，1,2,3,,ivin是客体变元，ijA是原子公式或其否定。

定理：任意一个谓词公式均和一个前束范式等价。

定理：每一个wffA都可以转化为与其等价的前束合取范式。

定理：每一个wffA都可以转化为与其等价的前束析取范式。

全称指定规则：如果对论域中所指的客体x，Px成立，则对论域中某个任意客体c，有Pc成立。这个规则可表示为xPxPc，简称US。 全程推广规则：如果能够证明对论域中每一个客体c断言Pc都成立，则可得到结论对论域xPx。这个规则可表示为PxxPx，简称UG。

存在指定规则：如果对论域中某些客体Px成立，则对论域中某个制定客体c，使得Pc成立。这个规则可表示为xPxPc，简称ES。

存在推广规则：如果能够证明对论域中每一个客体c，有Pc成立，则在论域中必存在x，使得Px成立。这个规则可表示为PcxPx，简称EG。

带有量词蕴含公式和等价公式

xAxVxBxxAxBx xAxBxxAxVxBx

xAxxBxxAxBx xAxBxxAxxBx

xAxBxxAxxBx xAxxAx

xAxxAx xABxAxBx

xABxAxBx xAxBxxAxxBx

xAxBxAxB xAxBxAxB

AxBxxABx AxBxxABx

图论：

图：三元有序组,,GVGEG称为图，其中VG是非空结点集，EG是连接结点的边集，G是边集到节点无序偶（有序偶）集合上的函数。因每条边总是关联连个节点，故图常记为,GVE。

无向边：边是两个点的无序偶对。

有向边：边是两个点的序偶。

有向图：每一条边都是有向边的图。

无向图：每一条边都是无向边的图。

混合图：图既有有向边又有无向边的图。在此暂不讨论。

邻接点：若两个点有边（有向或无向）相连，则称这两个点邻接。

邻接边：若两条边有公共点，则称这两条边邻接。

环：只与一个结点关联的边（可以作为有向边，也可以作为无向边）

结点的度：与结点v关联的边数（约定：对于环，度加2）。记为deg(v)

图G的最大度：maxdeg|GvvVG。

图G的最小度：mindeg|GvvVG