离散数学(第4讲PPT学习教案.pptx

离散数学是计算机科学中的基础学科，主要研究离散而非连续的数据结构和逻辑关系。第四讲的主题聚焦在命题公式的范式表示上，这在理解布尔逻辑和算法设计中至关重要。范式是一种将复杂的逻辑表达式转化为标准形式的方法，便于分析和简化。 我们介绍几个关键术语：析取范式（Disjunctive Normal Form, DNF）和合取范式（Conjunctive Normal Form, CNF）。析取范式是若干子句通过逻辑“或”（∨）连接的形式，而合取范式则是若干短语通过逻辑“与”（∧）连接。子句是有限个命题变元或它们的否定的析取，而短语是有限个命题变元或它们的否定的合取。例如，P、～P是句节，同时也是子句、短语、析取范式和合取范式。P∨Q∨～R是子句、析取范式和合取范式，但P∨（Q∨～R）不是析取范式，可以通过去括号规则转换为P∨Q∨～R成为析取范式。 范式的使用在于它们提供了公式等价性的简便验证方式。例如，通过定理1.6我们知道任何命题公式都可以转换为等价的合取范式和析取范式。这一过程通常涉及等价公式、德摩根定律以及布尔代数的各种定律，如结合律、分配律、吸收律、幂等律和交换律。 在实际应用中，为了进一步简化，我们引入了主析取范式和主合取范式。主析取范式是由若干极小项组成的析取式，极小项是包含所有命题变元的析取，且每个变元仅出现一次，要么是原形，要么是否定形式。例如，P∧P∧～P是一个极小项，因为它包含了P和它的否定，并且没有其他变量。每个极小项对应着布尔函数的一种特定赋值，使得该函数为真。对于两个命题变元，有四个极小项，即P∧Q，P∧～Q，～P∧Q，和～P∧～Q。对于n个变元，将有2^n个极小项。 求主析取范式和主合取范式的方法主要有真值表法和公式转换法。真值表法是列出所有可能的输入组合并检查哪些导致真值，然后将这些组合构造为析取或合取的形式。公式转换法则依赖于逻辑推理和布尔代数定律，将原始公式逐步转换为标准形式。 离散数学中的范式理论是理解和处理复杂逻辑表达式的关键工具，它在算法设计、证明、逻辑推理和计算机科学的许多领域都有着广泛的应用。掌握如何构造和转换各种范式，对于深入理解离散数学以及相关领域的知识至关重要。