为什么带量词的规格不只需要真值表
“每个顶点都有一个出邻点”是一句话,但它的真假取决于所讨论的图:有向圈满足它,删去一条边后却可能不再满足。命题逻辑可以用一个布尔(Boole)变量代表整句话,却不能说明它为什么对某些顶点成立、对另一些顶点不成立。谓词逻辑提供了这种内部结构:关系表示边,变量表示顶点,量词说明哪些选择必须成功。
把规格变成证明或程序时,这些结构尤其重要。先看到顶点,再为它选择邻点,邻点可以依赖于顶点;若要求同一个邻点服务所有顶点,就必须在不知道具体顶点时把它选定。混淆这两种要求,会把正确的逐输入算法变成一个根本不可能兑现的固定输出承诺。
本节讨论初等的关系型一阶逻辑。我们建立可靠的推理规则和精确的有限求值算法;并不声称给出了完整的一阶证明系统。
结构、赋值与变量作用域
定义 12.2.1
(关系结构与项)
固定一个非空论域 。关系语言列出谓词符号及其元数,例如一元符号 和二元符号 。一个结构把 解释成 的子集,把 解释成 的子集。等号表示论域元素真正相等。我们允许常量符号,每个常量命名一个指定的论域元素;本节不需要函数符号。一个项就是变量或常量。
定义 12.2.2
(赋值与量化公式的真假)
一个赋值 为每个变量指定论域中的值。原子式 在 下为真,当且仅当 属于所解释的关系。常量使用结构中固定的解释。联结词像命题逻辑那样组合真假值。对于量词,用 表示只把 改为 的赋值:
定义 12.2.3
(约束变量、自由变量与句子)
变量的一次出现,若处在量化该变量的量词作用域内,就是约束出现;否则是自由出现。若有多个这样的量词,以最内层的量词为准。因此,在 中,第一个 自由,第二个 受约束,而 自由。没有自由变量的公式称为句子。句子的真假取决于结构,却不取决于赋值:对公式作结构归纳可知,只有自由变量的值才可能影响真假。
常见错误
(用嵌套量词遮蔽变量)
不同的角色最好使用不同的变量名。句子 在语法上没有问题,但内层量词遮蔽了外层变量。由于 非空,它只表示某个元素有自环,并不表示每个顶点都有自环。只把内层约束变量改名,就得到 ,原先失去的依赖关系便清楚了。
定义 12.2.4
(在结构中为真、有效与蕴含)
讨论一个公式在某结构中为真时,论域与关系已经固定。若一个句子在其语言的每个结构中都为真,就称它有效;这里始终采用非空论域约定。若每个使前提集合 全部为真的结构与赋值也使结论 为真,就说 蕴含 。检验一幅图,只能确定该图中的真假,不能证明关于所有图的有效性。
代入必须保留变量原来的意义
定义 12.2.5
(避免捕获的代入)
用 表示把 的自由出现替换成项 ; 的约束出现不动。代入前,若某个约束变量会捕获 中的变量,就先给它换一个新名字。改名必须在其作用域内一致进行,并采用未使用的名字,所以不改变意义。有限公式只用有限多个变量名,总能找到新名字。
例题 12.2.6
(一次意外改变问题的代入)
设 ,要用变量 替换自由的 。直接按文字替换得到 ,它问的是有没有自环。应先把约束变量改为 ,得到 ,再代入为 ;正确结果问的是当前自由变量 所指的顶点有没有出邻点。取只有一条边 的双顶点图,并令 ,则正确结果为真,被捕获的版本却为假。
定理 12.2.7
(避免捕获的代入究竟表示什么)
设 为变量或常量,并按上述方法避免变量捕获。公式 在赋值 下为真,当且仅当 在 下为真;其中 是项 在原赋值下的值。
证明
(对公式结构归纳)
对原子式,替换只改变原先由自由 占据的参数位置,两边因而检验同一个元组。联结词情形由归纳假设组合而得。遇到约束 的量词时,代入停止,而且这个量化公式的真假与进入时 的值无关。遇到约束另一个变量 的量词时,必要时先改名,使 不出现在 中。这样,改变 不会改变 的值;对不同变量 的赋值更新也可以交换次序。对每个 使用归纳假设,再使用相同的全称或存在条件,就完成了公式结构归纳。
这个引理解释了代入规则为什么需要附带条件:语法上的替换必须对应某个精确的赋值变化。变量捕获破坏了这种对应,属于数学错误,而不是书写风格上的偏好。
四条量词规则及其条件
全称消去:从 推出 ,其中代入必须避免捕获。全称命题在项 所指的值上成立,而代入引理说明所得公式正是这个实例。
存在引入:从 推出 。项 的值就是所需见证。以上两条规则都要求 确实指向论域中的元素;没有定义的表达式不是合法实例。
全称引入:引入一个新参数 ,不依赖任何专门限制 的额外假设,证明 ,然后推出 。准确地说, 不能出现在尚未解除的前提或原公式中。参数是一个新常量,其解释可以任意选择。
存在消去:假设前提蕴含 。用新参数 暂时假设 ,并推出结论 。若 没有出现在 、其他尚未解除的前提或原公式 中,就可以解除这个临时假设,推出 。
命题 12.2.8
(四条量词规则的可靠性)
四条规则在所述附带条件下都是可靠的:凡满足前提的结构与赋值,也满足结论。
证明
(为什么新参数条件给出可靠性)
全称消去:全称命题在项 所指的值上成立,而代入引理说明所得公式正是这个实例。存在引入:项 的值提供所需见证。
全称引入:固定满足前提的结构及任意 ,把 解释成 。前提没有提到 ,所以仍然成立, 的证明因而说明 在 上成立。 是任意的,所以 在每个元素上成立。
存在消去:固定满足原前提的结构。前提蕴含 ,选一个见证并把 解释成它,于是 成立。临时推导证明 ;而 不提到 ,所以这仍是关于原结构的结论。
证明透视
任意元素与未知见证各有不同的任务
全称引入要求证明对新名字的每一种解释都成立。存在消去只需使用一种满足见证性质的解释,但最终结论不能依赖这个名字。新参数的限制使这两个语义论证成立。如果已有假设限制了 ,补写一句“令 任意”并不能取消那个限制。
例题 12.2.9
(把存在命题通过一个全称蕴含传递)
假设 和 ,要证 。暂时命名一个见证 ,使 成立。全称消去给出 ,于是得到 。存在引入给出 。这个结论不含 ,所以存在消去允许解除临时的见证假设。我们没有找出某个预先命名的元素满足 ,而是证明了某个元素满足它。
反例模式
见证不会自动变成某个指定常量
令 , 只在 上成立,而已有常量 表示 。此时 为真, 却为假。从存在命题跳到某个事先指定元素的命题,是无效推理。同样,若临时假设 尚未解除,就不能从它全称引入 :所谓任意参数实际上已经受到限制。
否定、受限论域与见证依赖
命题 12.2.10
(量词否定)
对任何公式 ,
证明
(借语义条款否定量词)
第一个等价式不要求每个值都失败:只要一个值使公式体为假,全称命题就失败。第二个等价式说明,没有见证正是每个值都失败。
每次处理一个量词,可得
常见错误
(否定全称—存在句子需要顶点,而不是一条边)
右侧要求找到一个没有任何出边的顶点,而不只是找到一条缺失的边。一个缺失的有向点对只能反驳更强的命题 。
定义 12.2.11
(受限量词)
对于子集 ,受限量词是下面的缩写:
其中 表示属于 。
常见错误
(用合取限制全称量词)
若 为空,受限全称式为真,受限存在式为假,即使背景论域 非空也是如此。若改用合取来写全称式,就是错误: 要求每个论域元素既属于 又满足 ,所以只要 为空它就为假。全称限制中必须使用蕴含。
命题 12.2.12
(交换全称量词与存在量词)
对任何公式 ,句子 蕴含 。反方向的蕴含一般不成立。
证明
(同一个见证适用于每个 x)
在 中, 的见证可以依赖 ;在 中,同一个见证必须适用于每个 。若第二句以 为见证成立,则无论选了哪个 ,同一个 都是第一句的见证。
反例模式
在 x 之后选取的见证未必适用于每个 x
取论域 ,令 表示 。则 为真:取 。但 为假: 在 处失败, 在 处失败。没有一个值能同时等于两个元素,所以反方向的蕴含不成立。
若句子由一串量词和一个不含量词的公式体构成,每次存在选择可以依赖此前的选择,却不能依赖稍后的全称选择。这是嵌套语义条件的直接含义,不是允许提前猜中未来的信息。
概念视角结构
把见证看作此前选择的函数
在有限论域上, 恰好表示存在函数 ,使对每个 都有 ;而 表示这个函数可以取为常数函数。一般而言,每个存在变量的见证是排在它之前的全称变量的函数,而不依赖排在它之后的任何变量。这个读法解释了为什么常数函数给出上面的蕴含,也解释了为什么按此前选择索引的见证表可能比公式本身大得多。
给定有限结构上的精确算法
假设可以明确枚举 的全部 个元素。给定公式及其自由变量的值,在输入关系中求原子式的真假,递归计算联结词,并用有限循环实现量词。对于全称量词,依次把 赋成每个论域值并计算公式体;遇到假就立即返回假,循环全部完成才返回真。对于存在量词,遇到真就返回真,全部失败才返回假。进入作用域时保存 的旧赋值,离开时恢复;当同一个变量名还有外层意义时,这一步不可省略。
定理 12.2.13
(有限求值的正确性与终止性)
上述递归求值器对每个公式、每个这样的有限结构以及每个自由变量赋值,都返回语义规定的真假值。设公式语法树大小为 ,最大嵌套量词深度为 ,项求值和关系成员查询都为单位成本,则最坏时间为 。若一个论域索引可放入一个机器字,则除已存储的模型和只读公式外,深度优先实现只需 个工作机器字。
证明
(归纳证明正确性与成本计数)
按公式结构归纳证明正确性。原子式直接使用结构中的解释。每个联结词对递归得到的正确结果应用相应真值函数。对于全称量词,循环恰好在语义规定的赋值下访问每个 ;一次失败就反驳全称命题,全部完成则证明每种情形。存在量词同理,或者提前找到见证,或者所有选择都失败。恢复赋值保证一个递归调用不会改变兄弟分支的意义。递归只进入严格较小的公式结点,每个循环又都是有限的,因此必然终止。
对于时间界,一条路径上的每个量词至多带来 倍的重复。所以一个特定语法树结点至多被求值 次,而结点总数为 。局部布尔运算与循环管理的总工作量也满足同一界。深度优先遍历最多保存 层调用、变量值和循环位置,不必把整棵选择树留在内存中。关系表、输入编码以及查询元组的实际成本,需要与这里的单位成本模型分开计算。
若公式固定, 就固定,因此在所述模型下,这是关于论域大小的多项式界。若公式也作为可变输入, 可以随输入增长,所示界并不是统一的多项式时间保证。正确的有限求值器也不因此能判定所有有限及无限结构上的有效性;它回答的是一个给定公式在一个给定结构和赋值中的真假。
例题 12.2.14
(有向圈、见证表与失败证据)
设 ,边恰为 、、。检验 时,可以为 分别记录见证 ,所以句子为真。但 为假:候选 可用 反驳, 可用 反驳, 可用 反驳,因为这些对角边都不存在。再删去 ,第一句也变为假;反例是 ,并附上所有 都失败的事实。
真的全称命题通常没有一个像存在命题那样的单独见证。在这里,全称—存在句子需要给每个顶点提供一个见证。反过来,反驳存在—全称句子,可能需要为每个存在候选分别给出一个失败的全称实例。即使程序只返回布尔值,明确这种依赖仍有助于理解它证明了什么。
练习
快速检查
(找出 的自由变量。给约束变量改名,使自由角色与约束角色不再混淆。)
解答 · 答案
自由变量是 :自由 出现在左边的析取支,自由 出现在右边。清楚的改名结果是 。右边量词只约束自己作用域中的 ,不会越过析取符去约束左边的 。
快速检查
(设 、,且 只在 上成立。比较 与 。如果 为空,又会怎样?)
解答 · 答案
使用蕴含的句子为真:在 处后件为真,在 处前件为假。使用合取的句子为假,因为公式体在 处已经失败。若 为空,每个蕴含都为真,每个合取都为假。因此受限全称式为真,但使用合取的句子在这个非空论域中仍为假。
快速检查
(证明 。若把两边的合取都换成析取,是否仍然等价?)
解答 · 答案
若每个元素同时满足两个谓词,那么每个谓词都在全部元素上成立。反之,若两个独立的全称命题成立,任取一个元素,它就同时满足二者,从而得到合取的全称命题。对析取,从 到 的方向成立,反方向却失败。取 ,让 只在 为真, 只在 为真;每个元素都满足其中一个谓词,但两个谓词都不普遍成立。
快速检查
(某证明写道:“假设 ,把一个见证叫作 ,所以 ,所以 。”指出无效的一步,给出双元素反模型。如果另有前提 ,可以有效地推出什么含 的结论?)
解答 · 答案
无效的是全称引入: 是关于存在见证的临时假设, 并非不受限制。取 、,则存在为真而全称为假。若另有全称蕴含,可用临时见证推出 ,再引入 ,最后解除见证假设。所得结论不含 ,满足存在消去的要求。
快速检查
(在 上令 表示 。判断 和 ,分别给出见证或反驳数据,并给出简单嵌套循环求值器检验任一句子时所需原子成员查询次数的上界。)
解答 · 答案
第一句为真: 时选 , 时选 。第二句为假:无论预先选哪个 ,全称选择都可取 ,使原子式为假。两句都有至多两种外层选择、每种至多两种内层选择,所以任一句都至多需要四次成员查询;提前停止可能减少次数。第二句不容许先看到 再选 ,因为存在选择在全称选择的外层。