离散数学习题答案(耿素云屈婉玲).doc

课程资料：离散数学科目，本科课程，计算机专业，软件专业，数学专业，离散数学期末考试复习资料，离散数学知识点总结，离散数学练习题模拟题，试题及答案，本科大学，必背知识点，必背考点，课后练习，期末考试试卷及答案。 ### 离散数学知识点解析 #### 一、离散数学概述 离散数学作为计算机科学与技术领域的重要基础课程之一，主要研究离散结构及其性质。本课程旨在培养学生掌握基本的逻辑推理能力、数学证明方法以及算法分析技巧等。 #### 二、命题逻辑与谓词逻辑 1. **命题逻辑**：研究简单命题（如“今天天气晴朗”）以及这些命题通过逻辑联结词（如“与”、“或”、“非”等）组成的复合命题的真假性。 - **主析取范式与主合取范式**： - **主析取范式**：一个命题公式的所有成真赋值所对应的极小项的析取形式。 - **主合取范式**：一个命题公式的所有成假赋值所对应的极大项的合取形式。 - **求解步骤**： - 将原命题转换为标准形式。 - 识别并列举所有可能的成真/成假赋值。 - 对于每种赋值情况，确定相应的极小项或极大项。 - 析取/合取这些极小项/极大项得到主析取范式/主合取范式。 2. **谓词逻辑**：在命题逻辑的基础上，增加了量词（全称量词“∀”、存在量词“∃”），可以更精确地描述涉及变量的命题。 - **量词规则**： - 全称量词引入与消去规则。 - 存在量词引入与消去规则。 #### 三、例题解析 ##### 题目二示例解析 1. **题目描述**：求下列公式的主析取范式，并求成真赋值：(2)()( )pqqrØ®ÙÙ - **解答**： - **解析过程**： - 原式转换为：()( )pqqrÛÚÙÙqrÛÙ - 进一步转换为：()( )ppqrÛØ ÚÙÙ - 最终结果为：37mmÛÚ - **成真赋值**：011，111 2. **题目描述**：求下列公式的主合取范式，并求成假赋值：(2)()( )pqprÙÚ Ø Ú - **解答**： - **解析过程**： - 原式转换为：()( )pprpqrÛÚ Ø ÚÙ Ø ÚÚ - 进一步转换为：4MÛ - **成假赋值**：100 3. **题目描述**：求下列公式的主析取范式，再用主析取范式求主合取范式：(1)()pqrÙÚ - **解答**： - **主析取范式**：13567mmmmmÛÚÚÚÚ - **主合取范式**：024MMMÛÙÙ 4. **题目描述**：用真值表法求下面公式的主析取范式：(1)()()pqprÚÚ ØÙ - **解答**： - **真值表**：（略） - **主析取范式**：1234567mmmmmmmÛÚÚÚÚÚÚ ##### 推理证明示例解析 1. **填充推理证明中的规则** - **题目描述**：前提：,,pqqr rs pØ ÚØ Ú®结论：s - **证明**： - ① p 前提引入 - ② pqØ Ú 前提引入 - ③ q ①②析取三段论 - ④ qrØ Ú 前提引入 - ⑤ r ③④析取三段论 - ⑥ rs® 前提引入 - ⑦ s ⑤⑥假言推理 2. **附加前提法** - **题目描述**：前提：()(),()pqrsstuÚ®ÙÚ®结论：pu® - **证明**： - ① p 附加前提引入 - ② pqÚ ①附加 - ③ ()()pqrsÚ®Ù 前提引入 - ④ rsÙ ②③假言推理 - ⑤ s ④化简 - ⑥ stÚ ⑤附加 - ⑦ ()stuÚ® 前提引入 - ⑧ u ⑥⑦假言推理 3. **归谬法** - **题目描述**：前提：pq® Ø，rqØ Ú，rsÙ Ø结论：pØ - **证明**： - ① p 结论的否定引入 - ② pq® Ø 前提引入 - ③ qØ ①②假言推理 - ④ rqØ Ú 前提引入 - ⑤ rØ ③④析取三段论 - ⑥ rsÙ Ø 前提引入 - ⑦ r ⑥化简 - ⑧ rrÙ Ø ⑤⑦合取 - 由于0rrÙ Ø Þ，所以推理正确。 4. **谓词逻辑推理** - **题目描述**：前提：( ( )( ))x F xG x"Ú，( )xG xØ$ 结论：( )xF x$ - **证明**： - ① ( )xG xØ$ 前提引入 - ② ( )x G x" Ø ①置换 - ③ ( )G cØ ②UI 规则 - ④ ( ( )( ))x F xG x"Ú 前提引入 - ⑤ ( )( )F cG cÚ ④UI 规则 - ⑥ ( )F c ③⑤析取三段论 - ⑦ ( )xF x$ 证明完成 以上解析涵盖了离散数学中的命题逻辑与谓词逻辑的基础概念、求解方法以及具体的例题解析。通过这些例题的解析，我们可以更好地理解和掌握离散数学的相关知识点。