本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动,欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外,在本系列学习文章中,为了透彻理解离散数学,本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录,在后续学习中还会逐渐补充:
(国外经典教材)离散数学及其应用 第七版
Discrete Mathematics and Its Applications 7th
,作者是Kenneth H.Rosen
,袁崇义译,机械工业出版社离散数学 第二版,武波等编著,西安电子科技大学出版社,离散数学 第三版,方世昌等编著,西安电子科技大学出版社,(经典参考书及其题解)离散数学/离散数学——理论•分析•题解,左孝凌、李为鉴、刘永才编著,上海科学技术文献出版社离散数学习题集:数理逻辑与集合论分册,耿素云;图论分册,耿素云;抽象代数分册, 张立昂。北京大学出版社
文章目录
3. 逻辑等价与蕴含、谓词演算的永真公式3.1 谓词逻辑的逻辑等价与蕴含3.2 谓词演算的永真公式3.2.1 命题逻辑的等价式和蕴含式在谓词逻辑中的推广应用3.2.2 量词的否定律3.2.3 量词辖域的扩张与收缩律3.2.4 量词的分配律3.2.5 多重量词律3.2.6 常用等价公式和蕴含公式3.3 前束范式3. 逻辑等价与蕴含、谓词演算的永真公式
3.1 谓词逻辑的逻辑等价与蕴含
定义3.1.1 给定任意两个谓词公式 AAA 和 BBB ,若对于任何赋值,AAA 和 BBB 的真值均相同,则称谓词公式 AAA 和 BBB 等价,记为 A⇔BA\Leftrightarrow BA⇔B 。
定义3.1.2 给定任意两个谓词公式 AAA 和 BBB ,若 A→BA\to BA→B 是永真式,则称 AAA 蕴含 BBB ,记为 A⇒BA \Rightarrow BA⇒B 。
类似于命题逻辑的逻辑等价与蕴含,对于谓词公式 A,B,CA, B, CA,B,C ,有如下结论:
A⇔BA \Leftrightarrow BA⇔B 当且仅当 A↔BA \leftrightarrow BA↔B 是重言式。A⇔BA \Leftrightarrow BA⇔B 当且仅当 A⇒BA \Rightarrow BA⇒B 且 B⇒AB \Rightarrow AB⇒A 。A⇔BA \Leftrightarrow BA⇔B 且 B⇔CB \Leftrightarrow CB⇔C ,则 A⇔CA \Leftrightarrow CA⇔C(谓词逻辑等价关系的传递规则)。A⇒BA \Rightarrow BA⇒B 且 B⇒CB \Rightarrow CB⇒C ,则 A⇒CA \Rightarrow CA⇒C(谓词逻辑蕴含关系的传递规则)。
命题逻辑中的代入规则、替换规则,在谓词逻辑中同样适用。
3.2 谓词演算的永真公式
3.2.1 命题逻辑的等价式和蕴含式在谓词逻辑中的推广应用
对于命题逻辑中的任一等价/蕴含公式,对其应用代入规则,即用谓词逻辑的任意公式代入命题逻辑等价/蕴含公式中的某个命题变元,所得结果是谓词逻辑的一个等价/蕴含公式。例如,对 E10E_{10}E10 德摩根律 ¬(A∧B)⇔¬A∨¬B\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B¬(A∧B)⇔¬A∨¬B ,用 ∀xP(x)\forall xP(x)∀xP(x) 代入 AAA 、∃xQ(x)\exist xQ(x)∃xQ(x) 代入 BBB ,则有 ¬(∀xP(x)∧∃xQ(x))⇔¬∀xP(x)∨¬∃xQ(x)\lnot (\forall xP(x) \land \exist xQ(x)) \Leftrightarrow \lnot \forall xP(x) \lor \lnot \exist xQ(x)¬(∀xP(x)∧∃xQ(x))⇔¬∀xP(x)∨¬∃xQ(x)
3.2.2 量词的否定律
量词的否定律(2个公式),说明全称量词和存在量词可以相互表达。
¬∀xP(x)⇔∃x¬P(x)¬∃xP(x)⇔∀x¬P(x)\begin{aligned} &\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)\\ &\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x) \end{aligned} ¬∀xP(x)⇔∃x¬P(x)¬∃xP(x)⇔∀x¬P(x)
证明:
(1)设论域为 DDD ,ttt 是任一赋值。
如果 ttt 使得 ¬∀xP(x)\lnot \forall xP(x)¬∀xP(x) 为真,则 ttt 使得 ∀xP(x)\forall xP(x)∀xP(x) 为假,即存在个体 a∈Da \in Da∈D 使得 P(a)P(a)P(a) 为假,从而有 ¬P(a)\lnot P(a)¬P(a) 为真,故有 ∃x¬P(x)\exist x\lnot P(x)∃x¬P(x) 为真。如果 ttt 使得 ¬∀xP(x)\lnot \forall xP(x)¬∀xP(x) 为假,则 ttt 使得 ∀xP(x)\forall xP(x)∀xP(x) 为真,即对于任一个体 a∈Da \in Da∈D ,均有 P(a)P(a)P(a) 为真,从而有 ¬P(a)\lnot P(a)¬P(a) 为假,故有 ∃x¬P(x)\exist x\lnot P(x)∃x¬P(x) 为假。综上所述,¬∀xP(x)⇔∃x¬P(x)\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)¬∀xP(x)⇔∃x¬P(x) 成立。再给出等价公式 ¬∀xP(x)⇔∃x¬P(x)\lnot \forall xP(x) \Leftrightarrow \exist x\lnot P(x)¬∀xP(x)⇔∃x¬P(x) 在一个有限论域上的证明。设有限论域为 D={a1,a2,…,an}D = \{ a_1, a_2, \dots, a_n\}D={a1,a2,…,an} ,则对某个个体变元 xxx 的量化可以用命题形式表示,于是有:
¬∀xP(x)⇔¬(P(a1)∧P(a2)∧⋯∧P(an))⇔¬P(a1)∨¬P(a2)∨⋯∨¬P(an)⇔∃x¬P(x)\begin{aligned} \lnot \forall xP(x) &\Leftrightarrow \lnot (P(a_1) \land P(a_2) \land \dots \land P(a_n)) \\ &\Leftrightarrow \lnot P(a_1) \lor \lnot P(a_2) \lor \dots \lor \lnot P(a_n) \\ &\Leftrightarrow \exist x\lnot P(x) \end{aligned}¬∀xP(x)⇔¬(P(a1)∧P(a2)∧⋯∧P(an))⇔¬P(a1)∨¬P(a2)∨⋯∨¬P(an)⇔∃x¬P(x)
(2)设论域为 DDD ,ttt 是任一赋值。
如果 ttt 使得 ¬∃xP(x)\lnot \exist xP(x)¬∃xP(x) 为真,则 ttt 使得 ∃xP(x)\exist xP(x)∃xP(x) 为假,即对于任一个体 a∈Da \in Da∈D ,均有 P(a)P(a)P(a) 为假,从而有 ¬P(a)\lnot P(a)¬P(a) 为真,故有 ∀x¬P(x)\forall x\lnot P(x)∀x¬P(x) 为真。如果 ttt 使得 ¬∃xP(x)\lnot \exist xP(x)¬∃xP(x) 为假,则 ttt 使得 ∃xP(x)\exist xP(x)∃xP(x) 为真,即存在个体 a∈Da \in Da∈D 使得 P(a)P(a)P(a) 为真,从而 ¬P(a)\lnot P(a)¬P(a) 为假,故有 ∀x¬P(x)\forall x\lnot P(x)∀x¬P(x) 为假。综上所述,¬∃xP(x)⇔∀x¬P(x)\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x)¬∃xP(x)⇔∀x¬P(x) 成立。再给出等价公式 ¬∃xP(x)⇔∀x¬P(x)\lnot \exist xP(x) \Leftrightarrow \forall x\lnot P(x)¬∃xP(x)⇔∀x¬P(x) 在一个有限论域上的证明。设有限论域为 D={a1,a2,…,an}D = \{ a_1, a_2, \dots, a_n\}D={a1,a2,…,an} ,则对某个个体变元 xxx 的量化可以用命题形式表示,于是有:
¬∃xP(x)⇔¬(P(a1)∨P(a2)∨⋯∨P(an))⇔¬P(a1)∧¬P(a2)∧⋯∧¬P(an)⇔∀x¬P(x)\begin{aligned} \lnot \exist xP(x)&\Leftrightarrow \lnot (P(a_1) \lor P(a_2) \lor \dots \lor P(a_n)) \\ &\Leftrightarrow \lnot P(a_1) \land \lnot P(a_2) \land \dots \land \lnot P(a_n) \\ &\Leftrightarrow \forall x\lnot P(x) \end{aligned}¬∃xP(x)⇔¬(P(a1)∨P(a2)∨⋯∨P(an))⇔¬P(a1)∧¬P(a2)∧⋯∧¬P(an)⇔∀x¬P(x)
3.2.3 量词辖域的扩张与收缩律
设 P(x)P(x)P(x) 是谓词公式,QQQ 是不含自由变元 xxx 的谓词公式。于是有:
(1)∀x(P(x)∧Q))⇔∀xP(x)∧Q\forall x(P(x) \land Q)) \Leftrightarrow \forall xP(x) \land Q∀x(P(x)∧Q))⇔∀xP(x)∧Q
(2)∀x(P(x)∨Q))⇔∀xP(x)∨Q\forall x(P(x) \lor Q)) \Leftrightarrow \forall xP(x) \lor Q∀x(P(x)∨Q))⇔∀xP(x)∨Q
(3)∃x(P(x)∧Q)⇔∃xP(x)∧Q\exist x(P(x) \land Q) \Leftrightarrow \exist xP(x) \land Q∃x(P(x)∧Q)⇔∃xP(x)∧Q
(4)∃x(P(x)∨Q)⇔∃xP(x)∨Q\exist x(P(x) \lor Q) \Leftrightarrow \exist xP(x) \lor Q∃x(P(x)∨Q)⇔∃xP(x)∨Q
上面一组比较简单,下面一组比较复杂:
(5)∃xP(x)→Q⇔∀x(P(x)→Q)\exist xP(x) \to Q \Leftrightarrow \forall x(P(x) \to Q)∃xP(x)→Q⇔∀x(P(x)→Q)
(6)∀xP(x)→Q⇔∃x(P(x)→Q)\forall xP(x) \to Q \Leftrightarrow \exist x(P(x) \to Q)∀xP(x)→Q⇔∃x(P(x)→Q)
(7)Q→∃xP(x)⇔∃x(Q→P(x))Q\to \exist xP(x) \Leftrightarrow \exist x(Q \to P(x))Q→∃xP(x)⇔∃x(Q→P(x))
(8)Q→∀xP(x)⇔∀x(Q→P(x))Q \to \forall xP(x) \Leftrightarrow \forall x(Q \to P(x))Q→∀xP(x)⇔∀x(Q→P(x))
证明(5)∃xP(x)→Q⇔¬∃xP(x)∨Q⇔∀x¬P(x)∨Q⇔∀x(¬P(x)∨Q)⇔∀x(P(x)→Q)\begin{aligned} \exist xP(x) \to Q &\Leftrightarrow \lnot \exist xP(x) \lor Q \\ &\Leftrightarrow \forall x \lnot P(x) \lor Q \\ &\Leftrightarrow \forall x(\lnot P(x) \lor Q) \\ &\Leftrightarrow \forall x(P(x) \to Q)\end{aligned}∃xP(x)→Q⇔¬∃xP(x)∨Q⇔∀x¬P(x)∨Q⇔∀x(¬P(x)∨Q)⇔∀x(P(x)→Q)
证明(6)∀xP(x)→Q⇔¬∀xP(x)∨Q⇔∃x¬P(x)∨Q⇔∃x(¬P(x)∨Q)⇔∃x(P(x)→Q)\begin{aligned} \forall xP(x) \to Q &\Leftrightarrow \lnot \forall xP(x) \lor Q \\ &\Leftrightarrow \exist x \lnot P(x) \lor Q \\ &\Leftrightarrow \exist x(\lnot P(x) \lor Q) \\ &\Leftrightarrow \exist x(P(x) \to Q)\end{aligned}∀xP(x)→Q⇔¬∀xP(x)∨Q⇔∃x¬P(x)∨Q⇔∃x(¬P(x)∨Q)⇔∃x(P(x)→Q)
证明(7)Q→∃xP(x)⇔¬Q∨∃xP(x)⇔∃x(P(x)∨¬Q)⇔∃x(Q→P(x))\begin{aligned} Q\to \exist xP(x) &\Leftrightarrow \lnot Q\lor \exist xP(x) \\ &\Leftrightarrow \exist x(P(x) \lor \lnot Q) \\ &\Leftrightarrow \exist x(Q \to P(x)) \end{aligned}Q→∃xP(x)⇔¬Q∨∃xP(x)⇔∃x(P(x)∨¬Q)⇔∃x(Q→P(x))
证明(8) Q→∀xP(x)⇔¬Q∨∀xP(x)⇔∀x(P(x)∨¬Q)⇔∀x(Q→P(x))\begin{aligned} Q\to \forall xP(x) &\Leftrightarrow \lnot Q \lor \forall xP(x) \\ &\Leftrightarrow \forall x(P(x) \lor \lnot Q) \\ &\Leftrightarrow \forall x(Q \to P(x)) \end{aligned}Q→∀xP(x)⇔¬Q∨∀xP(x)⇔∀x(P(x)∨¬Q)⇔∀x(Q→P(x))
3.2.4 量词的分配律
有限论域中易证(1)和(2):
(1)∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)\forall x(P(x) \land Q(x)) \Leftrightarrow \forall xP(x) \land \forall xQ(x)∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)
(2)∃x(P(x)∨Q(x))⇔∃xP(x)∨∃xQ(x)\exist x(P(x) \lor Q(x)) \Leftrightarrow \exist xP(x) \lor \exist xQ(x)∃x(P(x)∨Q(x))⇔∃xP(x)∨∃xQ(x)
(3)∀xP(x)∨∀xQ(x)⇒∀x(P(x)∨Q(x))\forall xP(x) \lor \forall xQ(x) \Rightarrow \forall x(P(x) \lor Q(x))∀xP(x)∨∀xQ(x)⇒∀x(P(x)∨Q(x))
(4)∃x(P(x)∧Q(x))⇒∃xP(x)∧∃xQ(x)\exist x(P(x) \land Q(x)) \Rightarrow \exist xP(x) \land \exist x Q(x)∃x(P(x)∧Q(x))⇒∃xP(x)∧∃xQ(x)
上面一组比较简单,下面一组比较复杂:
(5)∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)\forall x(P(x) \to Q(x)) \Rightarrow \forall xP(x) \to \forall xQ(x)∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)
(6)∃x(P(x)→Q(x))⇔∀xP(x)→∃xQ(x)\exist x(P(x) \to Q(x)) \Leftrightarrow \forall xP(x) \to \exist xQ(x)∃x(P(x)→Q(x))⇔∀xP(x)→∃xQ(x)
(7)∀x(P(x)↔Q(x))⇒∀xP(x)↔∀xQ(x)\forall x(P(x) \leftrightarrow Q(x)) \Rightarrow \forall xP(x) \leftrightarrow \forall xQ(x)∀x(P(x)↔Q(x))⇒∀xP(x)↔∀xQ(x)
(8)∃xP(x)→∀xQ(x)⇒∀x(P(x)→Q(x))\exist xP(x) \to \forall xQ(x) \Rightarrow \forall x(P(x) \to Q(x))∃xP(x)→∀xQ(x)⇒∀x(P(x)→Q(x))
证明(1)设 ttt 是谓词公式 ∀x(P(x)∧Q(x))\forall x(P(x) \land Q(x))∀x(P(x)∧Q(x)) 的任一赋值,其论域为 DDD 。
如果 ttt 使得 ∀x(P(x)∧Q(x))\forall x(P(x) \land Q(x))∀x(P(x)∧Q(x)) 为真,则对于任一个体 a∈Da \in Da∈D ,使得 P(a)∧Q(a)P(a) \land Q(a)P(a)∧Q(a) 为真,即 P(a)P(a)P(a) 和 Q(a)Q(a)Q(a) 的真值均为真,从而有 ∀xP(x)\forall xP(x)∀xP(x) 和 ∀xQ(x)\forall xQ(x)∀xQ(x) 均为真,即 ∀xP(x)∧∀xQ(x)\forall xP(x) \land \forall xQ(x)∀xP(x)∧∀xQ(x) 为真;如果 ttt 使得 ∀xP(x)∧Q(x))\forall xP(x) \land Q(x))∀xP(x)∧Q(x)) 为假,则存在个体 a∈Da \in Da∈D ,使得 P(a)∧Q(a)P(a) \land Q(a)P(a)∧Q(a) 为假,即 P(a)P(a)P(a) 或 Q(a)Q(a)Q(a) 的真值为假,从而有 ∀xP(x)\forall xP(x)∀xP(x) 或 ∀xQ(x)\forall xQ(x)∀xQ(x) 为假,即 ∀xP(x)∧∀xQ(x)\forall xP(x) \land \forall xQ(x)∀xP(x)∧∀xQ(x) 为假综上所述,∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)\forall x(P(x) \land Q(x)) \Leftrightarrow \forall xP(x) \land \forall xQ(x)∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x) 成立
证明(5)任给一个赋值 ttt ,其论域为 DDD 。假设在 ttt 下,∀xP(x)→∀xQ(x)\forall xP(x) \to \forall xQ(x)∀xP(x)→∀xQ(x) 的真值为 FFF ,则 ∀xP(x)\forall xP(x)∀xP(x) 为 TTT ,∀xQ(x)\forall xQ(x)∀xQ(x) 为 FFF 。由 ∀xQ(x)\forall xQ(x)∀xQ(x) 为 FFF ,得到存在 a∈Da\in Da∈D ,使得 Q(a)Q(a)Q(a) 为 FFF ,又因为 ∀xP(x)\forall xP(x)∀xP(x) 为 TTT ,有 P(a)P(a)P(a) 为 TTT ,从而推出 P(a)→Q(a)P(a) \to Q(a)P(a)→Q(a) 为 FFF ,即 ∀x(P(x)→Q(x))\forall x(P(x) \to Q(x))∀x(P(x)→Q(x)) 为 FFF 。由否定后件法得到,∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x)\forall x(P(x) \to Q(x)) \Rightarrow \forall xP(x) \to \forall xQ(x)∀x(P(x)→Q(x))⇒∀xP(x)→∀xQ(x) 。
证明(8)∃xP(x)→∀xQ(x)⇔¬∃xP(x)∨∀xQ(x)⇔∀x¬P(x)∨∀xQ(x)⇒∀x(¬P(x)∨Q(x))⇔∀x(P(x)→Q(x))\begin{aligned} \exist xP(x) \to \forall xQ(x) &\Leftrightarrow \lnot \exist xP(x) \lor \forall xQ(x) \\ &\Leftrightarrow \forall x\lnot P(x) \lor \forall xQ(x) \\ &\Rightarrow \forall x(\lnot P(x) \lor Q(x)) \\ &\Leftrightarrow \forall x(P(x) \to Q(x)) \end{aligned} ∃xP(x)→∀xQ(x)⇔¬∃xP(x)∨∀xQ(x)⇔∀x¬P(x)∨∀xQ(x)⇒∀x(¬P(x)∨Q(x))⇔∀x(P(x)→Q(x))
3.2.5 多重量词律
对于多个量词的情况,量词出现的先后次序不能随意调换。为了便于说明,这里只讨论两个量词的情况,更多量词的使用方法与此类似。若设 P(x,y)P(x, y)P(x,y) 表示 x,yx, yx,y 是同乡,xxx 的论域为一班学生,yyy 的论域为二班学生,则:
∀x∀yP(x,y)\forall x\forall yP(x, y)∀x∀yP(x,y) 表示“一班每个学生和二班每个学生都是同乡”,∀y∀xP(x,y)\forall y\forall xP(x, y)∀y∀xP(x,y) 表示“二班每个学生和一班每个学生都是同乡”,二者都表示“一班和二班所有的学生都是同乡”,含义相同,所以 ∀x∀yP(x,y)⇔∀y∀xP(x,y)\forall x\forall yP(x, y) \Leftrightarrow \forall y\forall xP(x, y)∀x∀yP(x,y)⇔∀y∀xP(x,y) 。∃x∃yP(x,y)\exist x\exist yP(x, y)∃x∃yP(x,y) 表示“一班的某些学生和二班的某些学生是同乡”,例如一班的小明和二班的小李是同乡,也可以说“二班的某些学生和一班的某些学生是同乡”,即 ∃y∃xP(x,y)\exist y\exist xP(x, y)∃y∃xP(x,y) ,所以 ∃x∃yP(x,y)⇔∃y∃xP(x,y)\exist x\exist yP(x, y) \Leftrightarrow \exist y\exist xP(x, y)∃x∃yP(x,y)⇔∃y∃xP(x,y) 。∀x∃yP(x,y)\forall x \exist yP(x, y)∀x∃yP(x,y) 表示“对于一班任意学生,二班至少有一个学生和他是同乡”,∃y∀xP(x,y)\exist y\forall xP(x, y)∃y∀xP(x,y) 表示“二班存在某个学生,和一班所有学生是同乡”。显然,二者的含义是不同的,如果后者为真,则前者也为真,即 ∃y∀xP(x,y)⇒∀x∃yP(x,y)\exist y\forall xP(x, y) \Rightarrow \forall x\exist yP(x, y)∃y∀xP(x,y)⇒∀x∃yP(x,y) 。但是如果前者为真,后者不一定为真,即 ∀x∃yP(x,y)⇏∃y∀xP(x,y)\forall x\exist yP(x, y) \nRightarrow \exist y\forall xP(x, y)∀x∃yP(x,y)⇏∃y∀xP(x,y) ,所以二者不等价。
对于二元谓词前置量词,有以下8个等价公式和蕴含公式,可见,全称量词和存在量词在谓词公式中出现的次序不能随意改变:
(1)∀x∀yP(x,y)⇔∀y∀xP(x,y)\forall x\forall yP(x, y) \Leftrightarrow \forall y\forall xP(x, y)∀x∀yP(x,y)⇔∀y∀xP(x,y)
(2)∀x∀yP(x,y)⇒∃y∀xP(x,y)\forall x\forall yP(x, y) \Rightarrow \exist y\forall xP(x, y)∀x∀yP(x,y)⇒∃y∀xP(x,y)
(3)∀y∀xP(x,y)⇒∃x∀yP(x,y)\forall y\forall xP(x, y) \Rightarrow \exist x\forall yP(x, y)∀y∀xP(x,y)⇒∃x∀yP(x,y)
(4)∃x∀yP(x,y)⇒∀y∃xP(x,y)\exist x\forall yP(x, y) \Rightarrow \forall y \exist xP(x, y)∃x∀yP(x,y)⇒∀y∃xP(x,y)
(5)∃y∀xP(x,y)⇒∀x∃yP(x,y)\exist y\forall xP(x, y) \Rightarrow \forall x\exist yP(x, y)∃y∀xP(x,y)⇒∀x∃yP(x,y)
(6)∀x∃yP(x,y)⇒∃y∃xP(x,y)\forall x\exist yP(x, y) \Rightarrow \exist y\exist xP(x, y)∀x∃yP(x,y)⇒∃y∃xP(x,y)
(7)∀y∃xP(x,y)⇒∃x∃yP(x,y)\forall y\exist xP(x, y) \Rightarrow \exist x\exist yP(x, y)∀y∃xP(x,y)⇒∃x∃yP(x,y)
(8)∃x∃yP(x,y)⇔∃y∃xP(x,y)\exist x\exist yP(x, y) \Leftrightarrow \exist y\exist xP(x, y)∃x∃yP(x,y)⇔∃y∃xP(x,y)
其关系图如下所示:
3.2.6 常用等价公式和蕴含公式
谓词逻辑中常用的等价公式和蕴含公式如下所示。结合替换规则和传递规则,可以比较方便地推导证明谓词逻辑中的一些等价公式和蕴含公式:
3.3 前束范式
对于一个谓词公式,如果所有量词都非否定地集中出现在整个公式的最前端,它们的辖域为整个公式,则称该公式为前束范式,如 ∀x∀y∃z(Q(x,y)→R(z))\forall x\forall y\exist z(Q(x, y) \to R(z))∀x∀y∃z(Q(x,y)→R(z)) 。应用量词的否定律和量词辖域的扩张公式,结合换名规则,任何一个谓词公式都可以变换为前束范式。
【离散数学】数理逻辑 第二章 谓词逻辑(3) 谓词公式的逻辑等价与蕴含 谓词演算的永真公式