← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 2273.v.8.a

合取范式与析取范式

理解等级:初级

AND 与 OR 都可结合,所以可定义 n 元形式 AND{p1,…,pn} 与 OR{p1,…,pn}。若一个 AND{…} 中各 p 本身不再含 AND,整个表达式叫合取范式(CNF);若一个 OR{…} 中各 p 不再含 OR,叫析取范式(DNF)。规范形式便于比较和变换布尔表达式,例如把 WHERE 条件化成合取范式,就能逐项判断哪些条件可以推到连接之前提前过滤。参见[[真值功能完备性]]、[[前束范式未必最自然]]。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 练习答案 附录F 练习答案 · 查看原书依据

      进一步,因为AND和OR是可互换的和可组合的,并且它们都具备恒等值,所以我们可以定义n-元版本如下: ·定义AND{p1,p2,...,pn}等价于 ( p1 ) AND ( p2 ) AND ... AND ( pn ) AND TRUE 如果没有p包含任何AND,那么该表达式整体被称为“合取范式”(conjunctive normal form,CNF)。 ·定义OR{p1,p2,...,pn}等价于 ( p1 ) OR ( p2 ) OR ... OR ( pn ) OR FALSE 如果没有p包含任何OR,那么该表达式整体被称为“析取范式”(disjunctive normal form,DNF) 10.11 (a)不合法(假设x覆盖空集且q为TRUE;则EXISTS x(q)为FALSE)。

    参考来源

    - 位置:《SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)》附录F《练习答案》F.10 第10章 练习10.10(源文件:`_epub-src/OEBPS/text00148.html`) - 结论依据:答案在证明 AND、OR 可结合后,定义 n 元 AND/OR,并据此给出合取范式与析取范式的定义。 - 原始内容:如果没有p包含任何AND,那么该表达式整体被称为“合取范式”(conjunctive normal form,CNF)。