如何用一个命题公式的真值表求出它的主析取范式和主合取范式?二者有何关系?
命题:能判断真假的陈述句,真值取 1(真)或 0(假)。n 个命题变元共有 2ⁿ 种赋值。
真值表:枚举所有 2ⁿ 种赋值及其公式真值,是判定等值/重言/矛盾的基础工具。
极小项(minterm):n 个变元的合取,每个变元或其否定恰好出现一次。对某一行赋值为真时,对应一个极小项(变元取真写本身,取假写否定)。
极大项(maxterm):n 个变元的析取,每个变元或其否定恰好出现一次。
关系:同一公式的 PDNF 与 PCNF 覆盖互补的行;若公式有 k 行取真,则 PDNF 含 k 个极小项,PCNF 含 2ⁿ−k 个极大项。任何命题公式都有唯一的 PDNF 与唯一 PCNF。
用途:标准化后可判公式等价(范式相同即等价)、判可满足性,是逻辑推理与电路化简的基础。
题目与答案就在本页;收藏、批注和错题重练在应用内