19.2 一阶逻辑前束范式

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义19.2.1 前束范式】形式Q₁x₁…QₖxₖB称为前束范式,Qᵢ为∀或∃,B不含量词,称母式。k可为0,故无量词公式也是前束范式。前缀允许混合量词,但所有量词须集中于最前;¬∃xA虽然可化为前束式,自身还不是前束式。前束式可含自由变量,不能把它们一并量化而改变原命题。

【定理19.2.1】经典一阶逻辑在非空域约定下,每个公式均有等值前束范式。它通常不唯一,也不要求母式已经是合取范式。前束化保留等值;消去存在量词的斯科伦化通常仅保留可满足性,不能混称同一过程。

【构造步骤与证明思路】先消去↔与→,将¬推到原子式前(跨量词要交换∀∃);各绑定变量换成互异新名字,并避开全部自由变量;由内向外用辖域伸缩将量词移到前面。变量不在另一分支自由出现保证移出合法,结构归纳便证明存在性。也可保留→,但量词从前件移出必须交换种类;以下保留原书的后一种写法。

【例19.2.1】(1)(∀xF(x))∧¬∃xG(x)⇔(∀xF(x))∧∀y¬G(y)⇔∀x∀y(F(x)∧¬G(y))。又可用∀对∧分配律得到∀x(F(x)∧¬G(x))。两个前束式都对。

(2)(∀xF(x))∨¬∃xG(x)⇔(∀xF(x))∨∀y¬G(y)⇔∀x∀y(F(x)∨¬G(y))。不能直接变成∀x(F(x)∨¬G(x));D={0,1}且F=G={0}时后式真、原式假。(例完)

【注19.2.1】只有∧项的全称量词可以按有效分配律合并;一般不把两组独立的全称析取强行共享同一变量。换名使分支间不意外捕获变量,是前束化必要的预处理;前缀长短不同并不说明其中一式错误。

【例19.2.2】(1)(∃xF(x))∧∀xG(x)⇔(∃yF(y))∧∀xG(x)⇔∃y∀x(F(y)∧G(x)),先换名,再移出∃、∀。

(2)(∀xF(x))→∃xG(x)⇔(∀yF(y))→∃xG(x)⇔∃y∃x(F(y)→G(x)),前件∀移出成为∃。

(3)(∃xF(x))→∀xG(x)⇔(∃yF(y))→∀xG(x)⇔∀y∀x(F(y)→G(x)),前件∃移出成为∀。在(1)中独立的∀x与∃y也可对换得到另一个等值前束式,因为母式分离;不能由此推广为一般混合量词可交换。(例完)

【例19.2.3】(1)(∀xF(x,y))→∃yG(x,y)⇔(∀tF(t,y))→∃wG(x,w)⇔∃t∃w(F(t,y)→G(x,w)),自由变量仍{x,y}。

(2)((∀x₁F(x₁,x₂))→∃x₂G(x₂))→∀x₁H(x₁,x₂,x₃)。先换为((∀x₄F(x₄,x₂))→∃x₅G(x₅))→∀x₁H(x₁,x₂,x₃)。内层蕴涵先化为∃x₄∃x₅(F(x₄,x₂)→G(x₅));它整体又在外层前件,移出时两次∃变∀,结果∀x₄∀x₅∀x₁((F(x₄,x₂)→G(x₅))→H(x₁,x₂,x₃))。括号必须保留,母式是(A→B)→C而不是A→(B→C);自由变量始终{x₂,x₃}。(例完)