《离散简答题集合.doc》由会员分享，可在线阅读，更多相关《离散简答题集合.doc（4页珍藏版）》请在金锄头文库上搜索。
1、 离散简答题集合1.什么是命题逻辑公式？举例说明.定义 命题公式，简称公式，定义为：（1）命题变元是公式；（2）如果P是公式，则P是公式；（3）如果P、Q是公式，则PQ、PQ、PQ、 PQ都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号 串是才是公式。例如（PQ）R2. 什么是恒假的命题逻辑公式？举例说明.定义 设G为公式：如果G在所有解释下取值均为假，则称G是永假式或矛盾式；例如 （PQ）R3. 什么是命题逻辑的解释？举例说明. 定义 设G是命题公式， P1，P2，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，Pn的一组真值
2、，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，G=（PQ）R，则I： P Q R 1 1 0是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。 4. 什么是命题逻辑的主析取范式？举例说明.设G为公式，P1，P2，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，Pn的一个极小项，则称该析取范式为G的主析取范式5. 什么是命题逻辑的主合取范式？举例说明.设G为公式，P1，P2，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，Pn的一个极大项，则称该合取范式为G的主合取范式。6. 什么是命题逻辑的析取范式？举例
3、说明.由有限个简单合取式构成的析取式称为析取范式。、例如 PQR7. 什么是命题逻辑的合取范式？举例说明.由有限个简单析取式构成的合取式称为合取范式。例如 PQR8. 什么是谓词逻辑公式, 举例说明.定义2.2.3 谓词演算的合式公式定义如下：（1）原子公式是合式公式；（2）若A是合式公式，则（A）也是合式公式；（3）若A，B是合式公式，则（AB）、（AB）、（AB）、（AB）是合式公式；（4）若A是合式公式，则x A、$x A是合式公式；（5）只有有限次地应用（1）（4）构成的符号串才是合式公式。 例如：计算机系的学生都要学离散数学。令C（x）：x是计算机系的学生，G（x）：x要学离散数学;
4、则命题（2）可符号化为：x（C（x） G（x） 9.什么是谓词逻辑公式的解释, 举例说明.谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1）对每一个常项符号指定D中一个元素。（2）对每一个n元函数符号，指定一个函数。（3）对每一个n元谓词符号，指定一个谓词。显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作TI（G）。例2.2.6 设有公式：（$x）（y）（F（x，y）G（x，y）。在如下给出的解释下，判断该公式的真值。解 （1）解释I为： D：整数集合。 F（x，y）：x+y0 G（x，y）：xy因为对任
5、意的x，任意yD，有x+y0为“假”，所以无论G（x，y）为“真”或“假”，都有F（x，y）G（x，y）为“真”所以（$x）（y）（F（x，y）G（x，y）为“真”。 10. 什么是两集合的交集? 举例说明.定义对于任意两个集合A、B，由所有既属于A又属于B的元素构成的集合，称作A与B的交集，记作AB。例如例如，Aa，b，c，Bb，c，d，e，则ABb，c11. 什么是一个集合的幂集合? 举例说明.定义 设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集例如：A1，2，3，则 (A)，1，2，3，1，2，1，3，2，3，1，2，312. 什么是关系, 举例说明.设A，B是两个集合，R
6、是笛卡儿积AB的任一子集，则称R为从A到B的一个二元关系，简称关系例 设A=a，b，c，d，e，B=1，2，3，R=，13. 什么是关系的自反性, 对称性, 传递性？设R是集合A上的二元关系，如果对于每个xA，都有R，则称二元关系R是自反的。设R是集合A上的二元关系，如果对于每个x，yA， 当R，就有R，则称二元关系R是对称的。设R是集合A上的二元关系，如果对于任意x，y，zA，当R，R，就有R，则称二元关系R在A上是传递的。例 设A=1，2，3， R=，,14. 什么是等价关系, 举例说明.设R是非空集合A上的二元关系，如果有R是自反的、对称的和传递的，则称R是集合A上的等价关系 例 设A=
7、1，2，3， R=，,15. 什么是偏序关系, 举例说明.设R是集合A上的一个关系，如果有R是自反的、反对称的和传递的，则称R是A上的一个偏序关系 例 设R是集合A=2，3，6，8上的关系，R=x整除y，验证R是偏序关系。证明 R=，容易验证R是自反的、反对称的和传递的。故它是偏序关系。 16 什么是欧拉图? 什么是哈密顿图? 通过图中所有边一次且仅一次行遍所有顶点的回路，称为欧拉回路；具有欧拉回路的图，称为欧拉图； ( a ) ( b )v1 v4v2 v3v4v1v2v3在图8.1-1中，（a）存在欧拉通路，但不存在欧拉回路，因而它不是欧拉图。而（b）中存在欧拉回路，所以（b）是欧拉图。 经过图中所有顶点一次且仅一次的回路，称为哈密尔顿回路；具有哈密尔顿回路的图，称为哈密尔顿图；在图8.2-2中，（a）、（b）中存在哈密尔顿回路，是哈密尔顿图，（c）中存在哈密尔顿通路，但不存在哈密尔顿回路，是半哈密尔顿图，（d）中既无哈密尔顿回路，也无哈密尔顿通路，不是哈密尔顿图。
