19.1 一阶逻辑等值式与置换规则

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【19.1 等值关系】A⇔B表示A↔B在所有非空域、解释和赋值下都真;↔是公式中的联结词,⇔是说明两公式等值的元语言记号。例如“没有不犯错误的人”:¬∃x(M(x)∧¬E(x))⇔∀x(M(x)→E(x))。不能仅凭某一个解释下真值相同就证明等值。

【第一组基本等值式】第16章命题等值式的一致代换实例仍成立,如A⇔¬¬A,A→B⇔¬A∨B。原书示例F(x)→G(x)右边写成¬F(x)∨G(y),自由变量改变,应改为¬F(x)∨G(x)。其他交换、结合、分配、吸收、德摩根、蕴涵与等价消去等也可直接使用。

【式19.1.1 有限域消量词】若D={a₁,…,aₙ},n≥1,这些名称穷尽域中对象,则∀xA(x)⇔A(a₁)∧…∧A(aₙ),∃xA(x)⇔A(a₁)∨…∨A(aₙ)。这是在指定有限域中的等值展开;若常项没有穷尽任意解释的域,不能把它当成对所有域有效的公式。代入仅替换自由的x,须防变量捕获。

【式19.1.2 量词否定】¬∀xA(x)⇔∃x¬A(x),¬∃xA(x)⇔∀x¬A(x)。把否定穿过量词时,∀与∃互换,辖域内部仍须保留¬;多重量词从外向内依次处理。

【式19.1.3 全称辖域伸缩】前提x不在B中自由出现:

(1)∀x(A(x)∨B)⇔(∀xA(x))∨B。

(2)∀x(A(x)∧B)⇔(∀xA(x))∧B。

(3)∀x(A(x)→B)⇔(∃xA(x))→B。

(4)∀x(B→A(x))⇔B→∀xA(x)。

【式19.1.4 存在辖域伸缩】仍要求x∉FV(B):

(1)∃x(A(x)∨B)⇔(∃xA(x))∨B。

(2)∃x(A(x)∧B)⇔(∃xA(x))∧B。

(3)∃x(A(x)→B)⇔(∀xA(x))→B。

(4)∃x(B→A(x))⇔B→∃xA(x)。

上述某些等值需要非空域;B中可以有受约束的同名字母,但不能有自由x。量词跨过蕴涵前件时发生∀/∃互换,跨后件时不互换。可先以A→B⇔¬A∨B消去蕴涵,再从量词否定和∧∨的伸缩逐步推出,而不死记方向。

【式19.1.5 量词分配】∀x(A(x)∧B(x))⇔(∀xA(x))∧∀xB(x);∃x(A(x)∨B(x))⇔(∃xA(x))∨∃xB(x)。相反方向的两种“分配”一般不是等值。

【置换与换名】已知A⇔B,可以在公式的同一子公式位置以B替换A。换名只改变某量词绑定的那些出现和指导变元,不能改动内部被另一个同名量词遮蔽的出现;新名字应避开辖域内已有变量及全式自由变量。α换名不改变真假,随便把自由变量改名则会改变赋值含义。

【例19.1.1】(1)(∀xF(x,y,z))→∃yG(x,y,z)⇔(∀tF(t,y,z))→∃wG(x,w,z)。原来x在右侧自由,y在左侧自由,换名后这些自由出现都保留。(2)∀x(F(x,y)→∃yG(x,y,z))⇔∀x(F(x,y)→∃tG(x,t,z)),只换内层约束的y,不动F中的自由y。(例完)

【例19.1.2 反例】取D={0,1},A={0}、B={1}。∀x(A(x)∨B(x))真,而(∀xA(x))∨∀xB(x)假;∃x(A(x)∧B(x))假,而(∃xA(x))∧∃xB(x)真。这分别否定∀对∨、∃对∧的无条件分配。一般只有右侧全称析取蕴涵左侧,以及左侧存在合取蕴涵右侧。原书用奇偶数也可给出同样反例。(例完)

【例19.1.3】在D={a,b,c}中:(1)∀x(F(x)→G(x))⇔(F(a)→G(a))∧(F(b)→G(b))∧(F(c)→G(c))。

(2)∀x(F(x)∨∃yG(y))⇔(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c))。关键是∃yG(y)不含自由x,先缩小∀x辖域,再展开;此处并未使用不成立的“∀对∨分配”。

(3)∃x∀yF(x,y)⇔(F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,b)∧F(c,c))。先展开内层∀得到每行合取,再展开外层∃得到三行析取。(例完)

【例19.1.4】D={2,3},a=2,f交换2与3;F(2)=0、F(3)=1;G除G(3,3)=0外均为1;L为相等关系。

(1)∀x(F(x)∧G(x,a))=(0∧1)∧(1∧1)=0。

(2)∃x(F(f(x))∧G(x,f(x)))=(1∧1)∨(0∧1)=1,见证2。

(3)∀x∃yL(x,y)=(1∨0)∧(0∨1)=1。

(4)∃y∀xL(x,y)=(1∧0)∨(0∧1)=0。后两式逐行选择见证与寻找一列全真不同,量词不能交换。(例完)

【例19.1.5】(1)¬∃x(M(x)∧F(x))⇔∀x¬(M(x)∧F(x))⇔∀x(M(x)→¬F(x))。

(2)¬∀x(M(x)→F(x))⇔∃x¬(¬M(x)∨F(x))⇔∃x(M(x)∧¬F(x))。

(3)¬∀x∀y((F(x)∧G(y))→H(x,y))⇔∃x∃y(F(x)∧G(y)∧¬H(x,y))。

(4)¬∃x∃y(F(x)∧G(y)∧L(x,y))⇔∀x∀y((F(x)∧G(y))→¬L(x,y))。每步先交换量词并保留否定,再用命题等值化简;不能只翻量词而丢失内部否定。(例完)