#代数结构与数理逻辑学习笔记6
参考书：
离散数学及其应用（第 2 版）（屈婉玲等）
符号逻辑讲义（徐明）
定义 16.1 命题与联结词
命题是能判断真假的陈述句。真命题真值为 \(1\)，假命题真值为 \(0\)
不能再分解的命题称为简单命题或原子命题，常用 \[ p,q,r,p_1,q_1,\dots \] 表示
由简单命题和联结词构成的命题称为复合命题
常用联结词如下：
| 联结词 | 符号 | 复合命题 | 真值条件 |
|---|---|---|---|
| 否定 | \(\neg\) | \(\neg p\) | \(p\) 真时 \(\neg p\) 假，\(p\) 假时 \(\neg p\) 真 |
| 合取 | \(\wedge\) | \(p\wedge q\) | \(p,q\) 同真时为真 |
| 析取 | \(\vee\) | \(p\vee q\) | \(p,q\) 至少一个真时为真 |
| 蕴含 | \(\to\) | \(p\to q\) | 仅当前件真、后件假时为假 |
| 等价 | \(\leftrightarrow\) | \(p\leftrightarrow q\) | \(p,q\) 真值相同时为真 |
真值表为：
| \(p\) | \(q\) | \(\neg p\) | \(p\wedge q\) | \(p\vee q\) | \(p\to q\) | \(p\leftrightarrow q\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
蕴含式 \(p\to q\)：不表示两个命题之间一定有因果关系，只表示一种真值函数，只要 \(p\) 为假，\(p\to q\) 就为真
定义 16.2 命题公式及其赋值
命题公式递归定义如下：
- 单个命题变项是命题公式
- 若 \(A\) 是命题公式，则 \(\neg A\) 是命题公式
- 若 \(A,B\) 是命题公式，则 \((A\wedge B),(A\vee B),(A\to B),(A\leftrightarrow B)\) 是命题公式
- 有限次使用以上规则得到的符号串才是命题公式
命题公式也称为合式公式
为减少括号，通常约定联结词优先级为： \[ \neg,\quad \wedge,\quad \vee,\quad \to,\quad \leftrightarrow \] 其中 \(\neg\) 优先级最高，\(\leftrightarrow\) 优先级最低
给命题公式中所有命题变项指定真值，称为该公式的一个赋值或解释
若公式 \(A\) 中有 \(n\) 个不同命题变项，则共有 \(2^n\) 种赋值
在每个赋值下，公式 \(A\) 都有唯一确定的真值
若 \(A\) 在所有赋值下均为真，则称 \(A\) 为重言式或永真式，记为 \(\models A\)
若 \(A\) 在所有赋值下均为假，则称 \(A\) 为矛盾式或永假式
若 \(A\) 至少在一个赋值下为真，则称 \(A\) 为可满足式
既不是重言式也不是矛盾式的公式称为偶然式
定理 16.2.1 重言式、矛盾式和可满足式
设 \(A\) 是命题公式，则：
- \(A\) 是重言式当且仅当 \(\neg A\) 是矛盾式
- \(A\) 是矛盾式当且仅当 \(\neg A\) 是重言式
- \(A\) 可满足当且仅当 \(A\) 不是矛盾式
证明： 点击查看证明
由否定联结词真值表： \[ v(\neg A)=1-v(A) \]
若 \(A\) 在所有赋值下都为真，则 \(\neg A\) 在所有赋值下都为假，所以 \(\neg A\) 是矛盾式
反过来，若 \(\neg A\) 是矛盾式，则 \(\neg A\) 在所有赋值下都为假，故 \(A\) 在所有赋值下都为真，即 \(A\) 是重言式
第二条同理
第三条只是“存在赋值使 \(A\) 为真”和“并非所有赋值都使 \(A\) 为假”的等价
定义 16.3 等值式
设 \(A,B\) 是命题公式。若在任意赋值下 \(A\) 与 \(B\) 的真值都相同，则称 \(A\) 与 \(B\) 等值，记为 \[ A\Leftrightarrow B \] 或 \[ A\equiv B \]
等值式也可以用重言式刻画： \[ A\equiv B \iff A\leftrightarrow B\text{ 是重言式} \]
常用基本等值式如下：
| 名称 | 等值式 |
|---|---|
| 双重否定律 | \(\neg\neg A\equiv A\) |
| 幂等律 | \(A\vee A\equiv A,\quad A\wedge A\equiv A\) |
| 交换律 | \(A\vee B\equiv B\vee A,\quad A\wedge B\equiv B\wedge A\) |
| 结合律 | \((A\vee B)\vee C\equiv A\vee(B\vee C)\)；\((A\wedge B)\wedge C\equiv A\wedge(B\wedge C)\) |
| 分配律 | \(A\vee(B\wedge C)\equiv(A\vee B)\wedge(A\vee C)\)；\(A\wedge(B\vee C)\equiv(A\wedge B)\vee(A\wedge C)\) |
| De Morgan 律 | \(\neg(A\vee B)\equiv\neg A\wedge\neg B\)；\(\neg(A\wedge B)\equiv\neg A\vee\neg B\) |
| 吸收律 | \(A\vee(A\wedge B)\equiv A,\quad A\wedge(A\vee B)\equiv A\) |
| 零律 | \(A\vee 1\equiv 1,\quad A\wedge 0\equiv 0\) |
| 同一律 | \(A\vee 0\equiv A,\quad A\wedge 1\equiv A\) |
| 排中律 | \(A\vee\neg A\equiv 1\) |
| 矛盾律 | \(A\wedge\neg A\equiv 0\) |
| 蕴含等值式 | \(A\to B\equiv\neg A\vee B\) |
| 等价等值式 | \(A\leftrightarrow B\equiv(A\to B)\wedge(B\to A)\) |
| 假言易位 | \(A\to B\equiv\neg B\to\neg A\) |
等值演算就是不断用已知等值式替换公式中的子公式，从而把一个公式化成更方便的形式。
定理 16.3.1 等值代换
若 \(A\equiv B\)
则在任意命题公式中，把某处出现的 \(A\) 替换为 \(B\)，所得公式与原公式等值
例 16.3.2 等值演算
化简： \[ \neg(p\to q)\vee(p\wedge q) \]
有 \[ \neg(p\to q)\vee(p\wedge q) \equiv \neg(\neg p\vee q)\vee(p\wedge q) \]
\[ \equiv (p\wedge\neg q)\vee(p\wedge q) \]
\[ \equiv p\wedge(\neg q\vee q) \]
\[ \equiv p\wedge 1 \]
\[ \equiv p \]
定义 16.4 析取范式与合取范式
命题变项及其否定统称为文字
有限个文字的合取称为简单合取式： \[ l_1\wedge l_2\wedge\cdots\wedge l_k \]
有限个文字的析取称为简单析取式： \[ l_1\vee l_2\vee\cdots\vee l_k \]
有限个简单合取式的析取称为析取范式
有限个简单析取式的合取称为合取范式
也就是说： \[ D_1\vee D_2\vee\cdots\vee D_m \] 是析取范式，其中每个 \(D_i\) 是简单合取式；
\[ C_1\wedge C_2\wedge\cdots\wedge C_m \] 是合取范式，其中每个 \(C_i\) 是简单析取式。
定理 16.4.1 范式存在
任意命题公式都可以化为与之等值的析取范式，也可以化为与之等值的合取范式
证明： 点击查看证明
按等值演算步骤处理
第一步，消去蕴含和等价： \[ A\to B\equiv \neg A\vee B \] \[ A\leftrightarrow B\equiv(A\wedge B)\vee(\neg A\wedge\neg B) \]
第二步，把否定号内移到命题变项前： \[ \neg\neg A\equiv A \] \[ \neg(A\vee B)\equiv\neg A\wedge\neg B \] \[ \neg(A\wedge B)\equiv\neg A\vee\neg B \]
第三步，使用分配律： \[ A\wedge(B\vee C)\equiv(A\wedge B)\vee(A\wedge C) \] 可得到析取范式；
使用 \[ A\vee(B\wedge C)\equiv(A\vee B)\wedge(A\vee C) \] 可得到合取范式
每一步都是等值变形，所以最终公式与原公式等值
定义 16.4.2 主析取范式与主合取范式
设公式含命题变项 \[ p_1,p_2,\dots,p_n \]
含全部 \(n\) 个命题变项的简单合取式称为极小项，其中每个命题变项恰出现一次，形式为 \(p_i\) 或 \(\neg p_i\)
极小项只在一个赋值下为真
含全部 \(n\) 个命题变项的简单析取式称为极大项，其中每个命题变项恰出现一次，形式为 \(p_i\) 或 \(\neg p_i\)
极大项只在一个赋值下为假
由极小项组成的析取范式称为主析取范式
由极大项组成的合取范式称为主合取范式
求主析取范式的方法：
- 列出公式真值表
- 找出使公式为真的赋值行
- 每一行写出对应极小项
- 把这些极小项析取起来
求主合取范式的方法：
- 列出公式真值表
- 找出使公式为假的赋值行
- 每一行写出对应极大项
- 把这些极大项合取起来
定义 16.5 联结词完备集
若任意命题公式都可以用某个联结词集合中的联结词表示，则称这个联结词集合是功能完备集
教材中常用的功能完备集有： \[ \{\neg,\wedge,\vee\} \]
\[ \{\neg,\wedge\} \]
\[ \{\neg,\vee\} \]
\[ \{\neg,\to\} \]
定理 16.5.1 常用联结词完备集
集合 \[ \{\neg,\wedge\},\quad \{\neg,\vee\},\quad \{\neg,\to\} \] 都是功能完备集
证明： 点击查看证明
由范式存在定理，任意命题公式都可化为只含 \(\neg,\wedge,\vee\)
的公式
对 \(\{\neg,\wedge\}\)： \[ A\vee B\equiv\neg(\neg A\wedge\neg B) \] 所以可用 \(\neg,\wedge\) 表示 \(\vee\)
对 \(\{\neg,\vee\}\)： \[ A\wedge B\equiv\neg(\neg A\vee\neg B) \] 所以可用 \(\neg,\vee\) 表示 \(\wedge\)
对 \(\{\neg,\to\}\)： \[ A\vee B\equiv\neg A\to B \] 且 \[ A\wedge B\equiv\neg(A\to\neg B) \] 所以可用 \(\neg,\to\) 表示 \(\vee\) 与 \(\wedge\)
因此这三组联结词都是功能完备集
定义 16.6 推理的形式结构
设 \(A_1,A_2,\dots,A_k,B\) 是命题公式。若对任意赋值，只要 \(A_1,A_2,\dots,A_k\)都为真，\(B\) 也为真，则称从前提 \(A_1,\dots,A_k\) 推出结论 \(B\) 的推理是有效的，记为 \[ A_1,A_2,\dots,A_k\Rightarrow B \] 或 \[ A_1,A_2,\dots,A_k\models B \]
推理有效性的真值表判定： \[ A_1,\dots,A_k\models B \] 当且仅当 \[ (A_1\wedge A_2\wedge\cdots\wedge A_k)\to B \] 是重言式
也等价于 \[ A_1\wedge A_2\wedge\cdots\wedge A_k\wedge\neg B \] 是矛盾式
定理 16.6.1 推理有效性的等价条件
设 \(A_1,\dots,A_k,B\) 是命题公式，则以下三者等价：
- \(A_1,\dots,A_k\models B\)
- \((A_1\wedge\cdots\wedge A_k)\to B\) 是重言式
- \(A_1\wedge\cdots\wedge A_k\wedge\neg B\) 是矛盾式
证明： 点击查看证明
第一条等价于第二条：
对任意赋值，若所有前提为真则结论为真，正是 \[ (A_1\wedge\cdots\wedge A_k)\to B \] 在任意赋值下为真。
第二条等价于第三条：
蕴含式 \[ (A_1\wedge\cdots\wedge A_k)\to B \] 等值于 \[ \neg(A_1\wedge\cdots\wedge A_k)\vee B \]
它不是重言式，当且仅当存在赋值使 \[ A_1\wedge\cdots\wedge A_k \] 为真且 \(B\) 为假，也就是 \[ A_1\wedge\cdots\wedge A_k\wedge\neg B \] 可满足
所以蕴含式是重言式，当且仅当前提合取再合取 \(\neg B\) 是矛盾式
定义 16.7 自然推理系统 P
自然推理系统 \(P\) 由三部分组成：
- 字母表：命题变项符号、联结词符号和括号
- 合式公式：即命题公式
- 推理规则
系统 \(P\) 的基本推理规则包括：
- 前提引入规则：证明的任意步骤都可以引入前提
- 结论引入规则：证明中已经得到的结论可以作为后续证明的前提
- 置换规则：证明中任一公式的子公式可以用与它等值的公式替换
常用推理规则如下：
| 名称 | 推理形式 |
|---|---|
| 假言推理 | \(\dfrac{A\to B,\ A}{B}\) |
| 附加规则 | \(\dfrac{A}{A\vee B}\) |
| 化简规则 | \(\dfrac{A\wedge B}{A}\) |
| 拒取式规则 | \(\dfrac{A\to B,\ \neg B}{\neg A}\) |
| 假言三段论 | \(\dfrac{A\to B,\ B\to C}{A\to C}\) |
| 析取三段论 | \(\dfrac{A\vee B,\ \neg B}{A}\) |
| 构造性二难 | \(\dfrac{A\to B,\ C\to D,\ A\vee C}{B\vee D}\) |
| 破坏性二难 | \(\dfrac{A\to B,\ C\to D,\ \neg B\vee\neg D}{\neg A\vee\neg C}\) |
| 合取引入 | \(\dfrac{A,\ B}{A\wedge B}\) |
定理 16.7.1 假言推理有效
\[ A\to B,\ A\models B \]
证明： 点击查看证明
只需证明 \[ ((A\to B)\wedge A)\to B \] 是重言式
若前件为真，则 \(A\to B\) 为真且 \(A\) 为真
由蕴含联结词真值表，\(A\) 真且 \(A\to B\) 真时，\(B\) 必真
所以不可能出现前件真而后件假的赋值，该蕴含式为重言式
定理 16.7.2 拒取式有效
\[ A\to B,\ \neg B\models \neg A \]
证明： 点击查看证明
由假言易位：\(A\to B\equiv \neg B\to\neg A\)
于是前提 \(A\to B\) 可置换为 \(\neg B\to\neg A\)
再由假言推理，从 \[ \neg B\to\neg A,\quad \neg B \] 推出 \[ \neg A \]
故拒取式有效
例 16.7.3 自然推理系统 P 中的证明
证明： \[ p\vee q,\ q\to r,\ p\to s,\ \neg s\models r\vee q \]
证明序列可写为：
| 步骤 | 公式 | 理由 |
|---|---|---|
| 1 | \(p\vee q\) | 前提引入 |
| 2 | \(q\to r\) | 前提引入 |
| 3 | \(p\to s\) | 前提引入 |
| 4 | \(\neg s\) | 前提引入 |
| 5 | \(\neg p\) | 3,4 拒取式 |
| 6 | \(q\) | 1,5 析取三段论 |
| 7 | \(r\) | 2,6 假言推理 |
| 8 | \(r\vee q\) | 7 附加规则 |
所以推理有效
定义 16.8 一阶逻辑命题符号化
命题逻辑把简单命题看作整体，不能分析命题内部的个体、性质和关系。
一阶逻辑引入：
- 个体词：表示具体对象或变量，如 \(a,b,x,y\)
- 谓词：表示对象的性质或对象之间的关系，如 \(F(x),G(x,y)\)
- 量词：表示对象范围
两个基本量词：
| 量词 | 符号 | 读法 |
|---|---|---|
| 全称量词 | \(\forall\) | 对任意、所有 |
| 存在量词 | \(\exists\) | 存在、至少有一个 |
例如在论域为全体人的情况下：
- “所有人都会死”可符号化为 \(\forall x(H(x)\to M(x))\)
- “有些学生喜欢离散数学”可符号化为 \(\exists x(S(x)\wedge L(x))\)
- “没有人既是学生又是老师”可符号化为 \(\neg\exists x(S(x)\wedge T(x))\)
注记 16.8.1 符号化中的常见形式
全称命题常写成蕴含式： \[ \forall x(P(x)\to Q(x)) \] 表示“所有 \(P\) 都是 \(Q\)”
存在命题常写成合取式： \[ \exists x(P(x)\wedge Q(x)) \] 表示“存在某个对象既是 \(P\) 又是 \(Q\)”
“没有 \(P\) 是 \(Q\)”常写为： \[ \neg\exists x(P(x)\wedge Q(x)) \] 或等值地写为： \[ \forall x(P(x)\to\neg Q(x)) \]
定义 16.9 一阶逻辑公式及解释
一阶逻辑中常见符号包括：
- 个体常项：\(a,b,c,\dots\)
- 个体变项：\(x,y,z,\dots\)
- 函数符号：\(f,g,\dots\)
- 谓词符号：\(F,G,R,\dots\)
- 量词：\(\forall,\exists\)
- 命题联结词：\(\neg,\wedge,\vee,\to,\leftrightarrow\)
项表示个体：
- 个体常项和个体变项是项
- 若 \(f\) 是 \(n\) 元函数符号，\(t_1,\dots,t_n\) 是项，则 \(f(t_1,\dots,t_n)\) 是项
原子公式包括：
- \(n\) 元谓词 \(F\) 作用在 \(n\) 个项上：\(F(t_1,\dots,t_n)\)
- 等式：\(t_1=t_2\)
一阶公式由原子公式经过命题联结词和量词构成。
在 \(\forall xA\) 或 \(\exists xA\) 中，\(A\) 称为量词的辖域
若 \(x\) 的一次出现受到 \(\forall x\) 或 \(\exists x\) 约束，则称为约束出现；否则称为自由出现
没有自由变项的公式称为闭式
给出一阶公式的解释时，需要指定：
- 个体域 \(D\)
- 个体常项在 \(D\) 中对应的元素
- 函数符号在 \(D\) 上对应的函数
- 谓词符号在 \(D\) 上对应的性质或关系
在解释确定以后，一阶公式才有真值
例 16.9.1 公式解释
设个体域为整数集 \(\mathbb{Z}\)，谓词 \(P(x)\) 表示“\(x\) 是偶数”，谓词 \(Q(x)\) 表示“\(x>0\)”。
则 \[ \exists x(P(x)\wedge Q(x)) \] 表示“存在正偶数”，为真
而 \[ \forall x(P(x)\to Q(x)) \] 表示“所有偶数都是正数”，为假。
定义 16.10 一阶逻辑等值式与置换规则
若一阶公式 \(A,B\) 在任意解释下真值都相同，则称 \(A\) 与 \(B\) 等值，记为 \[ A\equiv B \]
命题逻辑中的等值式在一阶逻辑中仍可使用
一阶逻辑特有的基本等值式主要是量词等值式：
\[ \neg\forall xA(x)\equiv \exists x\neg A(x) \]
\[ \neg\exists xA(x)\equiv \forall x\neg A(x) \]
\[ \forall x(A(x)\wedge B(x))\equiv \forall xA(x)\wedge\forall xB(x) \]
\[ \exists x(A(x)\vee B(x))\equiv \exists xA(x)\vee\exists xB(x) \]
若 \(x\) 不在 \(B\) 中自由出现，则有：
\[ \forall x(A(x)\wedge B)\equiv \forall xA(x)\wedge B \]
\[ \exists x(A(x)\wedge B)\equiv \exists xA(x)\wedge B \]
\[ \forall x(A(x)\vee B)\equiv \forall xA(x)\vee B \]
\[ \exists x(A(x)\vee B)\equiv \exists xA(x)\vee B \]
相同量词可以交换： \[ \forall x\forall yA(x,y)\equiv\forall y\forall xA(x,y) \]
\[ \exists x\exists yA(x,y)\equiv\exists y\exists xA(x,y) \]
但不同量词一般不能随意交换： \[ \forall x\exists yA(x,y)\not\equiv\exists y\forall xA(x,y) \]
一阶逻辑的置换规则：若 \[ A\equiv B \] 则在公式中可以用 \(B\) 置换某处出现的 \(A\)，所得公式与原公式等值
定理 16.10.1 量词否定等值式
\[ \neg\forall xA(x)\equiv \exists x\neg A(x) \]
\[ \neg\exists xA(x)\equiv \forall x\neg A(x) \]
证明： 点击查看证明
第一式：
\(\neg\forall xA(x)\) 表示“并非所有 \(x\) 都满足 \(A(x)\)”。
这等价于“存在某个 \(x\) 不满足 \(A(x)\)”，即 \[ \exists x\neg A(x) \]
第二式：
\(\neg\exists xA(x)\) 表示“不存在 \(x\) 满足 \(A(x)\)”。
这等价于“所有 \(x\) 都不满足 \(A(x)\)”，即 \[ \forall x\neg A(x) \]
定理 16.10.2 量词对合取与析取的分配
\[ \forall x(A(x)\wedge B(x))\equiv \forall xA(x)\wedge\forall xB(x) \]
\[ \exists x(A(x)\vee B(x))\equiv \exists xA(x)\vee\exists xB(x) \]
证明： 点击查看证明
第一式：
\(\forall x(A(x)\wedge B(x))\) 表示对每个对象 \(x\)，\(A(x)\) 和 \(B(x)\) 都成立。
这等价于：
- 对每个对象 \(x\)，\(A(x)\) 成立
- 对每个对象 \(x\)，\(B(x)\) 成立
即 \[ \forall xA(x)\wedge\forall xB(x) \]
第二式：
\(\exists x(A(x)\vee B(x))\) 表示存在某个对象 \(x\)，使 \(A(x)\) 或 \(B(x)\) 成立。
这等价于“存在对象使 \(A(x)\) 成立，或者存在对象使 \(B(x)\) 成立”，即 \[ \exists xA(x)\vee\exists xB(x) \]
注记 16.10.3 两个常见错误
一般没有： \[ \forall x(A(x)\vee B(x))\equiv \forall xA(x)\vee\forall xB(x) \]
也一般没有： \[ \exists x(A(x)\wedge B(x))\equiv \exists xA(x)\wedge\exists xB(x) \]
例如在个体域 \(\{1,2\}\) 上，令 \(A(x)\) 表示 \(x=1\)，\(B(x)\) 表示 \(x=2\)
则 \[ \forall x(A(x)\vee B(x)) \] 为真，但 \[ \forall xA(x)\vee\forall xB(x) \] 为假
同时 \[ \exists xA(x)\wedge\exists xB(x) \] 为真，但 \[ \exists x(A(x)\wedge B(x)) \] 为假
定义 16.11 一阶逻辑前束范式
若一阶公式写成 \[ Q_1x_1Q_2x_2\cdots Q_nx_nB \] 其中每个 \(Q_i\) 是 \(\forall\) 或 \(\exists\)，而 \(B\) 中不再含量词，则称该公式为前束范式
前面的 \[ Q_1x_1Q_2x_2\cdots Q_nx_n \] 称为量词前缀，\(B\) 称为母式
例如： \[ \forall x\exists y(P(x)\to R(x,y)) \] 是前束范式
化前束范式的一般步骤：
- 消去 \(\to\) 与 \(\leftrightarrow\)
- 用 De Morgan 律和量词否定律把否定号移到原子公式前
- 必要时改名约束变项，避免不同量词使用同名变项
- 使用量词辖域扩张与收缩等值式，把量词逐步移到公式最前面
定理 16.11.1 前束范式存在
任意一阶逻辑公式都可以化为与之等值的前束范式
证明： 点击查看证明
按前束范式的化法逐步变形
第一步，利用 \(A\to B\equiv \neg A\vee B\) 和 \(A\leftrightarrow B\equiv(A\wedge B)\vee(\neg A\wedge\neg B)\) 消去 \(\to,\leftrightarrow\)
第二步，利用命题逻辑的否定等值式和量词否定等值式： \[ \neg\forall xA\equiv\exists x\neg A \] \[ \neg\exists xA\equiv\forall x\neg A \] 把否定号移到原子公式前
第三步，如果两个量词使用同一个变项，或量词变项与自由变项冲突，则先改名约束变项
第四步，利用量词辖域扩张与收缩公式，把量词逐步提出到公式最前面
经过有限步等值变形后，得到形如 \[ Q_1x_1Q_2x_2\cdots Q_nx_nB \] 的公式，其中 \(B\) 不含量词
每一步都保持等值，因此所得前束范式与原公式等值
例 16.11.2 化为前束范式
将 \[ \forall xP(x)\to \exists yQ(y) \] 化为前束范式。
先消去蕴含： \[ \forall xP(x)\to \exists yQ(y) \equiv \neg\forall xP(x)\vee \exists yQ(y) \]
用量词否定律： \[ \equiv \exists x\neg P(x)\vee \exists yQ(y) \]
提出量词： \[ \equiv \exists x\exists y(\neg P(x)\vee Q(y)) \]
所以其一个前束范式为 \[ \exists x\exists y(\neg P(x)\vee Q(y)) \]