计算机专业的离散作业资源
需积分: 3
51 浏览量 2009-12-23 19:50:16 上传 评论 收藏 181KB DOC 举报
身份认证 购VIP最低享 7 折!
30元优惠券将在59:57:9后过期 去使用
离散数学是计算机科学中的基础课程，主要研究不连续或离散对象的数学结构和性质。这份离散作业涵盖了逻辑推理、谓词逻辑、集合论和关系理论等多个核心主题。 一、逻辑公式类型的判断与主析取范式 在第一部分试题中，涉及的是逻辑公式类型的识别以及主析取范式（Minterm Canonical Form）的求解。通过真值表，我们可以确定一个逻辑公式的类型：永真式（Tautology）、永假式（Contradiction）或可满足式（Satisfiable）。例如，公式（1）和（2）分别对应永真式和永假式，而（3）是可满足式。主析取范式是指一个逻辑公式可以表示为若干个最小项的析取（“∨”运算），其中（3）的主析取范式是m0∨m2∨m6。 二、谓词逻辑的类型判断 第二部分涉及到的是量词（Universal Quantifier “∀”和Existential Quantifier “∃”）与逻辑联接词的结合。通过代换实例和逻辑等价法则，我们可以判断逻辑公式的类型。例如，（1）通过等价替换被证明为永真式，（2）是矛盾式，而（3）为可满足式，因为它在不同的解释下可以是真也可以是假。 三、推理证明 第三部分是基于逻辑推理的题目。这里运用了蕴含（Implication）、量词和逻辑等价关系来推导结论。例如，通过假设和逻辑规则，我们能证明如果考试准时进行，那么天气一定是好的。 四、集合论的运算 第四部分涉及到集合的运算，特别是笛卡尔积（Cartesian Product）和集合的差集（Set Difference）。这里证明了A×（B-C）等于（A×B）减去（A×C），这是集合论中的基本定理之一。 五、关系的传递闭包 第五部分讨论了关系的传递闭包。证明了传递闭包t(R)实际上就是迭代R的运算结果Ri，这涉及到关系的性质分析。 六、双射函数的复合 最后一部分证明了如果两个函数g:A→B和f:B→C都是双射（既满射又单射），那么它们的复合函数fog:A→C也是双射。这证明了双射的封闭性，即双射函数的复合仍然保持双射性。 这些题目涵盖的离散数学知识包括逻辑推理、谓词逻辑、集合论、关系理论和函数性质。这些知识点对于理解计算机科学的基础概念，特别是在算法设计、数据结构、编译原理等领域，都有着至关重要的作用。
离散数学考试试题（A卷及答案）
一、（15分）用真值表方法判断下列公式的类型，并求（3）的主析取范式。
（1）（PQ）（P∨Q）。
（2）（PQ）∧Q。
（3）（PQ）∧R。
解 （1）、（2）和（3）的真值表如表 1、表 2 和表 3 所示：
表 1
P Q PQ P∨Q
（PQ）（P∨
Q）
0 0
0 1
1 0
1 1
1
1
0
1
1
1
0
1
1
1
1
1
表 2
P Q PQ
（PQ） （PQ）∧Q
0 0
0 1
1 0
1 1
1
1
0
1
0
0
1
0
0
0
0
0
表 3
P Q R PQ R
（PQ）∧R
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
0
由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。
（3）的主析取范式为：m
0
∨m
2
∨m
6
。
二、（15 分）判断下列公式的类型：
（1）xF（x）（xyG（x，y）xF（x））。
（2）（F（x，y）R（x，y））∧R（x，y）。
（3）xyF（x，y）xyF（x，y）。
解 （1）因为 P（QP）P∨（Q∨P）（P∨P）∨QT，而
xF（x）（xyG（x，y）xF（x））是 P（QP）的代换实例，所以
xF（x）（xyG（x，y）xF（x））为永真式。
1
本内容试读结束，登录后可阅读更多
下载后可阅读完整内容，剩余5页未读，立即下载
相关知识
计算机专业的离散作业资源
作业治疗（OT）
sin90度=1的证明
远程医疗会成为2011年的发展趋势吗？
python 测试题1
IO(2) 缓冲字节输入输出流
杂记
尤未尽意
8.8暑假训练
【每日一题
网址: 计算机专业的离散作业资源 https://m.mcbbbk.com/newsview543630.html
| 上一篇: 综合实践活动课程标准：研究性学习 |
下一篇: 「图」成都崇州训狗宠物训练指导 |
