主题对照

谓词逻辑与量词

比较谓词、命题、联结词与量词的逻辑语义,以及它们在查询与约束表述中的陷阱。

18 张卡片 · 1 本书

本层 18 张卡片 · 含下级覆盖 18 张卡片

本主题的卡片

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

谓词、命题与闭合世界

理解关系变量还有一个远比”它只是个抽象文件”更深刻的视角:每个关系变量都关联 一个谓词(predicate),这个谓词是对现实世界某一部分的通用(参数化)陈述, 叫做这个关系变量的”内涵”(intension)——比如供应商关系变量S的谓词是”供应商 SNO签订了合同,其名称为SNAME,其状态为STATUS,其所在城市为CITY”,参数就是 关系变量的各个属性。谓词本质上是一个真值函数:用具体实参(如S1、Smith、20、 London)替换参数(逻辑学称为”实例化谓词”),得到的是一个命题(proposition) ——一个逻辑上非真即假的陈述句(注意:”命题总是真的”是常见误区,命题也 可以是假的,例子是”莎士比亚写了The Monkey Wrench Gang”这个命题为假)。关键 的建模约定是:关系变量在某一时刻实际出现的每一个元组,都被当作”用这个元组 的属性值实例化关系变量谓词后得到的命题在此刻为真”;而没有出现在关系变量里、 但看起来符合标题结构的元组,则被当作对应命题此刻为假——这个”未出现即为假” 的约定就是所谓的闭合世界假设(closed world assumption)。这个视角带来一条 精炼的总结:在任何时刻,一个关系变量恰好且只包含当时代表真命题的全部元组。 另外要注意术语上的”术语强占”提醒:SQL大量把”谓词”(predicate)这个词借用来 指代WHERE子句里的布尔表达式(”比较谓词”“IN谓词”),这和本节讨论的、更宽泛 的逻辑学意义上的”谓词”(关系变量的整体语义陈述)是两个不同层次的概念,容易 混淆。

结构图:

flowchart LR
    A["关系变量谓词<br/>(参数化陈述, 如S的内涵)"] -->|用具体实参实例化| B[命题<br/>非真即假的陈述句]
    B -->|元组实际出现在关系变量中| C[命题为真<br/>元组被收录]
    B -->|元组未出现/闭合世界假设| D[命题为假<br/>元组不被收录]
查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

数据库是一个逻辑系统

类型是可以谈论的事物的集合,关系是关于这些事物的真陈述:类型提供词汇,关系提供陈述能力,二者缺一不可,合起来又足以表示现实在某一时刻的状态。于是数据库就是真命题的集合,连同运算构成逻辑系统——基关系变量中的元组是公理,关系运算是推理规则,回答查询就是从已知真理推出新真理。设计、约束与优化问题由此都能用形式逻辑来回答。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

表达式的谓词可推导

任何关系表达式都有对应的谓词,且总能由其中关系变量的谓词加上运算语义推导出来。例如投影 S{SNO,SNAME,STATUS} 的谓词是“存在某个城市 CITY,使供应商 SNO……位于 CITY”:CITY 从参数变成了被存在量词约束的变元,所以结果少了一个属性,但信息并没有被随意丢弃。每个关系运算都对应一次对逻辑谓词的改写。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

蕴涵只看真值

逻辑联结词只由运算元的真值定义,与含义无关,所以 p AND q 与 q AND p 永远等价,而自然语言里交换两句话的顺序可能改变意思。蕴涵最容易误解:前件为假时整个蕴涵为真,两个毫不相干的真命题组成的蕴涵也为真。这对约束恰恰必要——IF COLOR=‘Red’ THEN CITY=‘London’ 不应被非红色零件违反。由定义可得 p IMPLIES q 等价于 (NOT p) OR q。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

谓词是真值函数

含占位符的语句,如“x 是恒星”,在代入实参前无法判定真假,它不是命题,而是谓词:一个接收实参、返回真值的函数。谓词按形参个数分为 n 元谓词,命题就是 0 元谓词,所以所有命题都是谓词,大部分谓词却不是命题。联结词也能组合谓词,复合谓词的元数取决于其中形参的个数,而不是它由几个简单谓词构成。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

量词把谓词变成命题

除了代入实参,量词化也能从谓词得到命题:EXISTS x(p(x)) 表示至少有一个 x 使 p 为真,一个正例即可证实;FORALL x(p(x)) 表示所有 x 都使 p 为真,一个反例即可推翻。联结词组合谓词后仍是同一形参的谓词,量词化却会“用掉”形参。n 元谓词只量化 m 个形参,得到 n−m 元谓词。同类量词可以交换次序,不同类量词的次序则会改变含义。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

量词次序改变含义

用二元谓词”x比y高”完全量化两个形参,理论上能构造8个命题,但因为 [[量词把谓词变成命题]]里”同类量词顺序不影响含义”这条 规则,8个实际归并成6个逻辑上不同的命题:EXISTS x(EXISTS y(...))(某人比 另一人高,通常为真);EXISTS x(FORALL y(...))(某人比所有人都高,包括 自己,恒假);FORALL x(EXISTS y(...))(所有人都比某人高,恒假); EXISTS y(FORALL x(...))(某人比所有人都矮,恒假);FORALL y(EXISTS x(...))(所有人都比某人矮,恒假);FORALL x(FORALL y(...))(所有人都比 所有人高,恒假)。这个例子的关键教训是:即便6个命题里有5个的真值都恰好是 FALSE,也绝不能因此认为它们含义相同——事实上没有任何两个命题的含义是一样 的,真值巧合相同和逻辑含义相同是完全不同的两件事,这也说明只看命题最终的 真值判断,无法反推出量词组合的具体结构。这个例子还引出一条量化时容易被 忽视的隐含前提:以上判断全部假设了论域(这里是”人”)至少存在一个元素—— 如果这个前提不成立(论域为空),结论会完全不同(详见[[空论域上FORALL恒真]])。

结构图:

flowchart TD
    A["二元谓词: x比y高"] --> B["EXISTS x(EXISTS y(...))<br/>某人比另一人高: 真"]
    A --> C["EXISTS x(FORALL y(...))<br/>某人比所有人高: 假"]
    A --> D["FORALL x(EXISTS y(...))<br/>所有人都比某人高: 假"]
    A --> E["EXISTS y(FORALL x(...))<br/>某人比所有人矮: 假"]
    A --> F["FORALL y(EXISTS x(...))<br/>所有人都比某人矮: 假"]
    A --> G["FORALL x(FORALL y(...))<br/>所有人都比所有人高: 假"]
    C -.真值相同但含义各不相同.-> D
    D -.-> E
    E -.-> F
    F -.-> G
查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

自由与约束指的是出现

谓词的形参叫自由变元,被量词化后成为约束变元。约束变元可以安全改名,EXISTS x(x>3) 与 EXISTS y(y>3) 等价;自由变元则不能随意改。严格说,“自由”与“约束”描述的是变元的每一次出现而非变元本身:在 EXISTS x(x>3) AND x 中,前两个 x 受约束,最后一个是自由的,把三个 x 全改成 y 就改变了含义。命题可以重新定义为不含自由出现的谓词。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

前束范式未必最自然

前束范式要求所有量词集中在最前面,里面是不含量词的矩阵,如 Q1 x1(Q2 x2(q))。它与其他写法同样正确,是有用的分析与规范化工具,却不一定最好懂:“未供应 P2 的供应商”写成 NOT EXISTS SPX(…) 一目了然,改写成前束范式 FORALL SPX(SPX.SNO≠SX.SNO OR SPX.PNO≠’P2’) 反而难读。规范形式服务于分析,书写时应优先考虑可读性。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

UNIQUE量词

UNIQUE x(p(x)) 表示恰有一个 x 使 p 为真。键约束可写成 FORALL SX (UNIQUE SY (SX.SNO = SY.SNO)):对每个供应商,恰好只有一个供应商与它编号相同,也就是它自己。外键写成 FORALL SPX (UNIQUE SX (SX.SNO = SPX.SNO)) 更贴切:每笔出货在 S 里恰好对应一个供应商。写成 EXISTS 也能过,只是因为 {SNO} 已经是 S 的键。

SQL 的 UNIQUE(子查询) 在结果没有重复行时为 TRUE,空表或只有一行时也为 TRUE,更像“至多一个”。样例里 UNIQUE (SELECT 0 FROM S WHERE CITY = 'Athens') 为真,因为只有 S5;换成 Paris 为假,因为 S2 和 S3 都在 Paris。这里绝不能写 DISTINCT:两行 Paris 会先合成一行 0,UNIQUE 反而变成真。检查键时同样不能写,UNIQUE (SELECT SNO FROM S) 靠的就是保留重复的编号。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

SQL缺FORALL的双重否定

EXISTS x(p) 等价于 NOT FORALL x(NOT p),理论上一个量词就够,但不同问题用哪个量词自然程度差异很大。SQL 只有 EXISTS,也无法提供 FORALL(子查询) 运算符:子查询结果已是被限制后的行,如“Paris 的供应商”,对它求“全部”并不表示“所有供应商都在 Paris”。

“供应了所有零件的供应商”用关系演算是 {SX} WHERE FORALL PX (EXISTS SPX (SPX.SNO = SX.SNO AND SPX.PNO = PX.PNO))。SQL 没有 FORALL,只能读成“不存在零件 PX,使得不存在出货把供应商 SX 和这个 PX 连起来”,外层和内层都是 NOT EXISTS。双重否定最难写对,也最难读懂。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

空论域上FORALL恒真

论域为空时,EXISTS x(p) 必为假,于是 FORALL x(…) 无论括号里写什么都为真:“所有身高超过 50 英尺的人都在 IBM 工作”是真命题。落到查询里,当零件表为空时,“供应了所有零件的供应商”会返回全部供应商;反过来,EXISTS SX(TRUE) 恰好可以表达“S 非空”。逻辑是数据库的必要基础,但并不充分——逻辑上正确的答案未必是用户需要的,系统必要时应解释结果。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

不一致时答案无对错

设 S 非空、约束要求至少有一种零件,而 P 实际为空,数据库已不一致。此时 {SX} WHERE EXISTS PX(TRUE),机械计算得到空集;若按约束把条件化简为 TRUE,则得到全部供应商。两个答案不可能都对,而在不一致的前提下,“正确”本身已无定义。SQL 中 CASE WHEN EXISTS(SELECT * FROM P) THEN x ELSE y END 同样会因此给出取决于求值方式的不同结果。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版)

自然语言查询天然模糊

“所供应零件都在同一城市的供应商”有两种读法:一是对它供应的任意两种零件都同城,这样只供应一种零件、甚至没有供应的供应商也满足;二是要求至少供应两种零件且两两同城。自然语言的这种模糊在复杂查询和业务规则中非常普遍。先把需求写成精确的逻辑表述,就能被迫在编码前发现并决定歧义,而不是把它悄悄带进代码、到生产环境才暴露。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

真值功能完备性

一个逻辑是真值功能完备的,当且仅当每个可能的联结词都能用它指定的联结词定义出来。二值逻辑有 16 个二元联结词,但全部都能只用 NOT 与 AND(或 NOT 与 OR)表达,所以 IMPLIES、IFF 等都不是基本的,例如 p IMPLIES q 就是 (NOT p) OR q。完备性极其重要:缺了它,就像算术缺了加法,许多判断无法表达。发散:设计规则引擎的布尔层时,先确认基本运算能组合出全部逻辑。参见[[蕴涵只看真值]]。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑

量词是迭代的OR与AND

x 取值于有限集合时,EXISTS x(p(x)) 就是各 p(xi) 依次 OR、末尾再 OR FALSE;FORALL 则是依次 AND、末尾 AND TRUE。末尾的恒等值解释了空集上 EXISTS 为假、FORALL 为真。这只因集合有限才成立,无限集上迭代不终止。量词虽是简写却极有用:不必知道库中有哪些元组就能写查询。参见[[空论域上FORALL恒真]]。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 练习答案

开放世界假设难处理否定

闭合世界假设说:库中阐明或蕴涵的都为真,其余为假;开放世界假设则说其余为未知。问“S6 签了合同吗”,库里没有 S6,闭合世界答“没签”,开放世界答“不知道”;反过来问“S6 没签合同为真吗”,开放世界的肯定答案仍是“不知道”,正反两问竟是一回事。所以开放世界无法正确处理否定,并把人推向三值逻辑。闭合世界的代价是否定式谓词需存海量行。参见[[谓词、命题与闭合世界]]。

查看卡片与原书出处

SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 练习答案

合取范式与析取范式

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

查看卡片与原书出处
辅助阅读:卢曼编号

按卢曼编号阅读

点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。

  • 展开或收起下级: 2273 SQL知识不等于关系理论 路径上下文 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
    • 展开或收起下级: 2273.q 更新是集合级运算 路径上下文 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第5章 基关系变量和基表 理解等级:未标注
      • 展开或收起下级: 2273.q.6 谓词、命题与闭合世界 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
        • 2273.q.6.b 开放世界假设难处理否定 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 练习答案 理解等级:高级
      • 2273.q.7 数据库是一个逻辑系统 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
    • 展开或收起下级: 2273.r SQL是高度冗余的语言 路径上下文 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第6章 SQL和关系代数I:原始运算符 理解等级:未标注
      • 2273.r.8 表达式的谓词可推导 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
    • 展开或收起下级: 2273.v 蕴涵只看真值 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
      • 2273.v.2 谓词是真值函数 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
      • 展开或收起下级: 2273.v.3 量词把谓词变成命题 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:未标注
        • 2273.v.3.a 量词是迭代的OR与AND 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:中级
      • 2273.v.4 量词次序改变含义 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
      • 2273.v.5 自由与约束指的是出现 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
      • 展开或收起下级: 2273.v.8 前束范式未必最自然 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
        • 2273.v.8.a 合取范式与析取范式 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 练习答案 理解等级:初级
      • 2273.v.9 UNIQUE量词 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:未标注
      • 2273.v.10 SQL缺FORALL的双重否定 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:未标注
      • 2273.v.11 空论域上FORALL恒真 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:未标注
      • 2273.v.13 不一致时答案无对错 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注
      • 2273.v.16 真值功能完备性 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第10章 SQL与逻辑 理解等级:中级
    • 展开或收起下级: 2273.w 表达式变换法则工具箱 路径上下文 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) · 第11章 使用逻辑表述SQL表达式 理解等级:未标注
      • 2273.w.7 自然语言查询天然模糊 主题成员 SQL与关系数据库理论——如何编写健壮的SQL代码(原书第2版) 理解等级:未标注

来源书籍