离散数学26 前束范式

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法:绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(，，，，)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P规则，T规则，CP规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)，+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补,对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包r(R),对称闭包s(R), 传递闭包t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

3.群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，拉格朗日（Lagrange）定理4.阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元5.环与域：环，交换环，含幺环，整环，域6.格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限布尔代数的表示定理图论：1.图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图，握手定理，图的同构2.图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图） 3. 图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵4. 欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图5. 无向树与根树：无向树，生成树，最小生成树，Kruskal ，根树，m 叉树，最优二叉树，Huffman 算法6. 平面图:平面图，面，欧拉公式，Kuratoski 定理数理逻辑：命题：具有确定真值的陈述句。

第一章命题逻辑一、等价公式(真值表)1)常用联结词：┐否定∨析取∧合取→：条件∆：双条件当且仅当Q 取值为F 时P →Q 为F ，否则为T ★等价公式表(等值公式表)常用的其它真值表┐┐P<=>P 双重否定P ∨P<=>P P ∧P<=>P幂等律(P ∧Q)∧R<=>P ∧(Q ∧R)(P ∨Q)∨R<=>P ∨(Q ∨R)结合律P ∧Q<=>Q ∧P P ∨Q<=>Q ∨P交换律P ∧(Q ∨R)<=>(P ∧Q)∨(P ∧R)P ∨(Q ∧R)<=>(P ∨Q)∧(P ∨R)分配律P ∨(P ∧Q)<=>P P ∧(P ∨Q)<=>P 吸收┐(P ∧Q)<=>┐P ∨┐Q ┐(P ∨Q)<=>┐P ∧┐Q 德摩根P ∨F<=>P P ∧T<=>P 同一律P ∨T<=>T P ∧F<=>F 零律P ∨┐P<=>T P ∧┐P<=>F否定律常用的其它真值表P ┐P T F FTP Q P ∨Q T T T T F T F T T FFFP Q P ∧Q T T T T F F F T F F FFP Q P →Q (┐P ∨Q)T T T T F F F T T FFTP→Q<=>┐P ∨Q P ∆Q<=>(P→Q)∧(Q→P)P ∆Q<=>Q ∆PP ∆Q<=>(P ∧Q)∨(┐P ∧┐Q)┐(P ∆Q)<=>P ∆┐Q R ∨(P ∨┐P)<=>T R ∧(P ∧┐P)<=>F P→Q<=>┐Q→┐P ┐(P→Q)<=>P ∧┐Q (P→Q)∧(P→┐Q)<=>┐P P→(Q→R)<=>(P ∧Q)→R (P ∆Q)∆R<=>P ∆(Q ∆R)命题公式的类型：(1)若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

离散数学试题带答案一、选择题1、G 是一棵根树，则（ ）。

A 、G 一定是连通的B 、G 一定是强连通的C 、G 只有一个顶点的出度为0D 、G 只有一个顶点的入度为12、下面哪个语句不是命题（ ）。

A 、中国将成功举办2008年奥运会B 、一亿年前地球发生了大灾难C 、我说的不是真话D 、哈密顿图是连通的3、设R 是实数集合，在上定义二元运算*：a ，b ∈R ，a*b=a+b-ab ，则下面的论断中正确的是（ ）。

A 、0是*的零元B 、1是*的幺元C 、0是*的幺元D 、*没有等幂元4、下面说法中正确的是（ ）。

A 、所有可数集合都是等势的B 、任何集合都有与其等势的真子集C 、有些无限集合没有可数子集D 、有理数集合是不可数集合5、无向完全图K 3的不同构的生成子图有（ ）个。

A. 6B.5C. 4D. 36、下面哪一种图不一定是无向树?A 、无回路的连通图B 、有n 个顶点n-1条边的连通图C 、每对顶点间都有通路的图D 、连通但删去一条边则不连通的图7、设集合A ＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( )。

A.1∈AB.{{4,5}}⊂AC. {1,2,3}⊆AD.∅∈A8、在有界格中，若一个元素有补元，则补元( )。

A 、必惟一B 、不惟一C 、不一定惟一D 、可能惟一9、设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？（ ）A 、 x*y=max{x,y}B 、 x*y=min{x,y}C 、 x*y=GCD(x,y)，即x,y 的最大公约数D 、 x*y=LCM(x,y)，即x,y 的最小公倍数10、集合X 中的关系R ，其矩阵是⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=111011101M ，则关于R 的论述中正确的是（ ）。

A 、R 是对称的B 、R 是反对称的C 、R 是反自反的D 、R 中有7个元素11. 下列各组数中，哪个可以构成无向图的度数列（ ）。

第四章归结法原理§4.1命题逻辑的归结法§4.2前束范式与斯科伦范式§4.3谓词逻辑的归结法作业§4.2 前束范式与斯科伦范式在命题逻辑中，为了用归结法判断一个公式是否是另一些公式的逻辑推论，首先需要将公式化为标准形式—合取范式。

在谓词逻辑中，为了用归结法判断一个语句是否是另一些语句的逻辑推论，首先需要将语句化为标准形式—斯科伦范式。

定义4.5形式为Q1y1 … Q n y n B 的公式称为前束范式，其中n 为非负整数，每个Qi是∀或∃，B 是开公式，y1, …, y n 是不同变元。

称Q1y1…Q n y n 为该前束范式的前束词，称B 为它的母式。

开公式是前束范式，这时n= 0，前束词是空串。

当一个前束范式不是开公式时它的所有量词都出当一个前束范式不是开公式时，它的所有量词都出现在最前面，并且它们的辖域都一直管到底。

前束范式：∀x∃y∃z(P(x, y) →Q(u, v))，P(x, y)非前束范式：∀xP(x) ∧Q(y)，因为∀x 的辖域是P(x)，而不是P(x) ∧Q(y)。

可以通过等值演算将一个公式化为前束范式。

例通过等值演算将公式Q(x) ∧(∃xP(x)→∀xR(x))化为前束范式。

Q(x) ∧(∃xP(x)→∀xR(x))⇔Q(x) ∧∀x(P(x)→∀xR(x))因为x 是公式P(x) 中的自由变元，所以P(x)→∀xR(x) ⇔∀x(P(x)→R(x))不成立。

需要将约束变元换名。

Q(x) ∧∀x(P(x)→∀xR(x))⇔Q(x) ∧∀x(P(x)→∀yR(y))⇔Q(x) ∧∀x∀y(P(x)→R(y))因为x 是公式Q(x) 中的自由变元，所以Q(x) ∧∀x∀y(P(x)→R(y))⇔)∀x(Q(x) ∧∀y(P(x)→R(y)))不成立。

需要将约束变元换名。

Q(x) ∧∀x∀y(P(x)→R(y))⇔Q(x) ∧∀z∀y(P(z)→R(y))⇔∀z(Q(x) ∧∀y(P(z)→R(y)))⇔∀z∀y(Q(x) ∧(P(z)→R(y)))与公式A 等值的前束范式称为A 的前束范式。

离散数学定义定理1.3.1命题演算的合式公式规定为:(1)单个命题变元本身是一个合式公式.(2)如果A是合式公式,那么┐A是合式公式.(3)如果A和B是合式公式,那么(A∨B),(A∧B),(A→B),(AB),都是合式公式.(4)当且仅当有限次地应用(1)(2)(3)所得到的包含命题变元,连接词和圆括号的符号串是合式公式.1.3.2 设Ai是公式A的一部分,且Ai是一个合式公式,称Ai是A的子公式.1.3.3 设P为一命题公式,P1,P2,……,Pn为出现在P中的所有命题变元,对P1,P2,……,Pn指定一组真值称为对P的一种指派.若指定的一种指派,使P的值为真,则称这组指派为成真指派.若指定的一种指派,使P的值为假,则称这种指派为成假指派.含n个命题变元的命题公式,共有2n个指派.1.3.4 给定两个命题公式A和B,设P1,P2,……,Pn为所有出现于A和B中的原子变元,若给P1,P2,……,Pn任一组真值指派,A和B的真值都相同,称A和B是等价的,记做A B.1.3.5 设A为一命题公式,若A在它的各种指派情况下,其取值均为真,则称A为重言式或永真式.1.3.6 设A为一命题公式,若A在它的各种指派情况下,其取值均为假,则称A为矛盾式或永假式.1.3.7设A为一命题公式,若A在它的各种指派情况下至少存在一组成真指派,则称A为可满足式.1.4.1 设X式合式公式A的子公式,若有Y也是一个合式公式,且XY,如果将A中的X用Y 置换,得到公式B,则AB.1.4.2 设A,B为两个命题公式,AB,当且仅当A ←→B为一个重言式.P=>Q称做P蕴含Q或蕴含式,又称永真条件式.蕴含式有下列性质:(1)对任意公式A,又A=>A;(2)对任意公式A,B和C,若A=>B,B=>C,则A=>C;(3)对任意公式A,B和C,若A=>B,A=>C,则A=>(B∧C);(4)对任意公式A,B和C,若A=>C,B=>C,则A∨B=>C.1.4.3设P,Q为任意两个命题公式,PQ的充分必要条件式P=>Q,,Q=>P.蕴含式推理P∧Q=>P化简式P∧Q=>Q化简式P=>P∨Q附加式┐P=>P→Q变形附加式Q=>P→Q变形附加式┐(P→Q)=>P变形简化式┐(P→Q)=>┐Q变形简化式p∧(P→Q)=>Q假言推论┐Q∧(P→Q)=>┐P拒取式┐p∧(P∨Q)=>Q析取三段式(P→Q) ∧(Q→R)=>P→R条件三段式(PQ) ∧(QR)=>PR双条件三段式(P→Q)∧(R→S)∧(P∧R)=>Q→S合取构造二难(P→Q)∧(R→S)∧(P∨R)=>Q∨S析取构造二难P→Q=>(P∨R) →(Q∨R)前后附加式P→Q=>(P∧R) →(Q∧R)前后附加式1.5.1 一个命题公式称为合取范式,当且仅当它具有形式:A1∧A2∧…∧An(n≥1),其中A1,A2,…,An都是有命题变元及其否定所组成的析取式.1.5.2 一个命题公式称为析取范式,当且仅当它具有形式:A1∨A2∨…∨An(n≥1),其中A1,A2,…,An都是有命题变元及其否定所组成的合取式.1.5.3 n个命题变元的合取式,称作布尔合取或小项,其中每个变元与他的否定不能同时存在,但两者必须出现且仅出现一次.小项有如下性质:(1)每个小项具有一个相应的编码,当该编码与其真实指派相同时,该小项为T,在其余2n-1种指派情况下为F.(2)任意两个不同小项的合取是永假.(3)全体小项的析取式为永真.定义1.5.4 对于给定的命题公式,如果有一个等价公式,它仅由小项的析取组成,则该等价公式称作原公式的主析取范式.定理1.5.1 在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式主析取范式.定理1.5.2 任意含n个命题变元的非永假命题公式,其主析取范式是唯一的.定义1.5.5 n个命题变元的析取式称作布尔析取或大项.其中每个变元与它的否定不能同时出现,但两者必须出现仅出现一次.定理1.5.3 在真值表中一个公式的真值为F的指派所对应的大项的合取,称为此公式的主合取范式.定理1.5.4 任意含有n个命题变元的非永假命题公式A,其主合取范式是唯一的.设命题公式中含有n个命题变元,且A的主析取范式中含有k个小项mi1,mi2,…,mik,则A的主合取范式比含有2n-k个大项.如果命题公式A的主析取范式为∑(i1,i2,……,ik),则A的主合取范式为: ∏(0,1,2,…,i1-1,i1+1,…,ik-1,ik+1,……,2n-1).从A的主析取范式求其主合取范式的步骤为:(1)求出A的主析取范式中未包含小项的下标.(2)把(1)中求出的下标写成对应大项.(3)做(2)中县城大项合取,即为A的主合取范式.根据主范式(主析取范式,主合取范式)的定义和定理,可以判定含n个命题变元的公式:(1)若A可化为与其等价的含2n个小项的主析取范式,则A为永真式.(2)若A可化为与其等价的含2n个大项的主合取范式,则A为永假式.(3)若A的主析取范式不含2n个小项,或A的主合取范式不含2n个大项,则A为可满足的. 定义1.6.1 设H1,H2,…Hn,C是命题公式,当且仅当H1∧H2∧…∧Hn=>C,称C是一组前提H1,H2,…,Hn的有效结论.等值公式表E1┐┐pPE12R∨(P∧┐P)RE2P∧QQ∧PE13R ∧(P∨┐P)RE3P∨QQ∨PE14R∨(P∨┐P)TE4(P∧Q)∧RP∧(Q∧R)E15R∧(P∧┐P)FE5(P∨Q)∨RP∨(Q∨R)E16P→Q┐P∨QE6P∧(Q∨R)(P∧Q)∨(P∧R)E17┐(P→Q) P∧┐QE7P∨(Q∧R)(P∨Q)∧(P∨R)E18P→Q┐Q→┐PE8┐(P∧Q) ┐P∨┐QE19P→(Q→R)(P∧Q)→RE9┐(P∨Q) ┐P∧┐QE20PQ(P→Q)∧(Q→P)E10P∨PPE21PQ(P∧Q)∨(┐P∧┐Q)E11P∧PPE22┐(PQ) P┐Q常用的推理规则有:(1)前提引入规则:在证明的任何步骤上,都可以引入前提,简称P规则.(2)结论引入规则:在证明的任何步骤上,所证明的结论都可作为后续证明的前提,称为T规则.(3)置换规则:在证明的任何步骤上,命题公式的任何子命题公式都可以用与之等值的命题公式置换,也记作T规则.定理1.6.1 推理H1∧H2∧…∧Hn┣C是有效推理的充分必要条件是H1∧H2∧…∧Hn→C 为永真式.定义1.6.2 设H1,H2,…,Hn是可满足式,则称H1,H2,…,Hn是相容的,若H1,H2,…,Hn是永假式称H1,H2,…,Hn是不相容的.定理1.6.2 若H1∧H2∧…∧Hn∧┐C为永假式,则H1∧H2∧…∧Hn┣C成立.定理1.6.3 若H1∧H2∧…∧Hn∧R=>C,则H1∧H2∧…∧Hn =>R→C.本定理即:若H1,H2,…,Hn,R┣C,则H1,H2,…,Hn┣R→C定义2.1.1 由一个谓词,一些个体变元组成的表达式简称为谓词变项或称为命题函数. (命题函数不是命题,只有命题函数中的变元都取为特定具体的个体时,才是确定的命题.谓词变项摘,个体变元的数目为谓词变项的元数.)定义 2.2.1 由一个或几个原子命题函数以及逻辑联接词组合而成的表达式称为符合命题函数.定义2.2.2 谓词演算的合式公式,可由下述各条组成(合式公式A记为WffA):(1)原子谓词公式是合适公式.(2)若A是合式公式,则┐A是合式公式.(3)若A和B都是合式公式,则(A∨B),(A∧B),(A→B),(AB)是合式公式.(4)如果A是合式公式,x是A中出现的任何变元,则(x)A和(x)A都是合式公式.(5)只有经过有限次应用规则(1)(2)(3)(4)所得到的公式是合式公式.定义2.2.3 给定谓词合式公式A,其中一部分公式形式为(x)(Bx)或(x)(Bx),称量词,后面所跟的x为指导变元或作用变元.称B为相应量词的辖域(或作用域).在辖域中,x的一切出现称为约束出现.在B中除去约束出现的其他变项的出现称为自由出现.(1)约束改名规则,将量词辖域中,某个约束出现的个体变元及其相应指导变元改成本辖域中未出现过的个体变元,其余不变.(2)自由带入规则,对某个自由出现的个体变元可用个体常元或用与原子公式中与所有个体变元不同的个体变元取代入,且处处代入.定义2.3.1 给定任何两个谓词公式WffA和WffB,设它们有共同的个体域E,若对A和B的任一一组变元进行赋值,所得命题的真值相同,则称谓词公式A和B在E上市等价的,记作AB. 定义2.3.2 给定任意谓词公式WffA,其个体域为E,对于A的所有赋值WffA都为真,则称WffA在E上有效的(或永真的).定义2.3.3一个谓词公式WffA,对于A的所有赋值WffA都为假,则称WffA为不可满足的(或永假的).定义2.3.4一个谓词公式WffA,如果至少在一个赋值下为真,则称该WffA为可满足.等值公式表E23(x)((Ax)∨(Bx))( x)(Ax)∨(x)(Bx)E30(x)(Ax) →B(x) ((Ax)→B)E24(x)((Ax)∧(Bx))(x)(Ax)∧(x)(Bx)E31(x)(Ax) →B(x) ((Ax)→B)E25┐(x)(Ax)(x)┐(Ax)E32A→(x)(Bx) (x) (A→(Bx))E26┐(x)(Ax)(x)┐(Ax)E33A→(x)(Bx) (x) (A→(Bx))E27(x)(A∨(Bx))A∨(x)(Bx)I17(x)(Ax)∨(x)(Bx) =>(x)((Ax)∨(Bx))E28(x)(A∧(Bx))A∧(x)(Bx)I18(x)((Ax)∧(Bx)) =>(x)(Ax)∧(x)(Bx)E29(x)((Ax)→(Bx))(x)(Ax)→(x)(Bx)I19(x)(Ax)→(x)(Bx) =>(x)((Ax)→(Bx))定义 2.4.1 一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式.前束范式形式如下:(Q1V1)(Q2V2)……(QnVn)A.其中Qi(1≤i≤n)为或,A为不含有量词的谓词公式.定理2.4.1 任意一个谓词公式,均和一个前束范式等价.谓词演算推理规则(1)全称指定规定,US. ∵(x)P(x) ∴P(c)(2)全称推广规则,UG:∵P(x)∴(x)P(x)(3)存在指定规则,ES: ∵(x)P(x) ∴P(c)(4)存在推广规则,EG:∵:P(c) ∴(x)P(x)定义3.1.1 设A,B是任意两个集合,若A=B,当且仅当它们有相同的成员.定义3.1.2 设A,B是任意两个集合,加入A的每个元素都是B的元素,则称A为B的子集,或A包含在B内或B包含A.记作: AB或BA定理3.1.1 集合A和集合B相等的充分必要条件式两个集合互为子集.定义3.1.3 如果集合A的每一元素都属于B,但集合B中至少有一个元素不属于A,则称A为B的真子集,记作AB.定义3.1.4 不包含任何元素的集合称为空集,记作Φ或{ }.定理3.1.2 对于任何集合A必有ΦA.(空集包含在A内)定义3.1.5 设A为任意集合,以A的子集为元素所组成的集合,称为集合A的幂集.记作P(A). 定理3.1.3 如果有限集合A有n个元素,则其幂集P(A)有2n个元素.(2n-1个子集元素个数为奇数)定义3.1.6 在一定范围内,如果所有集合均为某一集合的子集,则称该集合为全集.全集记作E. 定义3.2.1 设任意两个集合A和B,由集合A和B的所有共有元素组成的集合S,称为A和B 的交集,记作A∩B.S=A∩B={x|(x∈A)∧(x∈B)}集合的交运算有如下性质:A∩A=A A∩B=B∩A A∩Φ=Φ A∩B定义3.2.2 设任意两个集合A和B,所有属于A或属于B的元素所组成的集合S称为A和B 的并集,记作A∪B.S=A∪B={x|(x∈A)∨(x∈B)}交运算性质:a)A∪(A∩B)=A b)A∩(A∪B)=A吸收率:c) 设集合ABA∪B=B d)设集合ABA∩B= A定义3.2.3 设A,B为任意两个集合,所有属于A而不属于B的一切元素组成的集合S,称为B 对于A的补集,或相对补,记作A-B.定义3.2.4 设E为全集,对任一集合A,关于E的补E-A,称为集合A的绝对补,记作~Aa)~(~A)=A b)~E=Φ c)~ Φ=E; d)A∪~A=E c)A∩~A=Φ定理3.2.2 设A,B为任意两个集合,则下列关系式成立.a) A-B=A∩~B b)A-B=A-(A∩B) c)~(A∪B)=~A∩~B d)~(A∩B)=~A∪~B定义3.2.5 设A,B为任意两个集,A和B的对称差为集合S,其元素或属于A,或属于B,但不能既属于B,又属于比,记作AB.定理3.2.3 设任意集合A,B,C,则有以下性质:a)AB=BA b)AΦ=A c)AA=Φ d)AB=(A∩~B)∪(~A∩B) e)(AB)C=A(BC)定义3.3.1 由两个客体x和y,按一定的顺序,组成一个二元组,称此二元组为有序对,或称序偶,记作或(x,y).其中x是该序偶的第一元素,y是该序偶的第二元素.定义3.3.2 两个序偶相等,=,iff x=u,y=v.定义3.3.3 设A,B为集合.用A中的元素x作为第一元素,B中的元素作为第二元素,构成有序对,所有这样的有序对组成的集合,叫做A和B的笛卡尔积,记作A×B.A×B={|x∈A,y∈B}定理3.3.1 设A,B,C为任意三个集合,则有:a) A×(B∪C)=(A×B)∪(A×C) b) A×(B∩C)=(A×B)∩(A×C) c)(A∪B)×C=(A∪C)×(B∪C) d) (A ∪B)×C=(A∪C)×(B∪C)定理3.3.2 设A,B,C,D,为非空集合,则A×BC×D的充要条件为AC,BD.定义3..3.4 设A,B是任意两个集合,A×B的子集R称为从A到B的二元关系.当A=B是,称R 为A上的二元关系.从这个定义可以表明A到B的二元关系,也是序偶的集合.故∈R,即称a与b有关系R,记作aRb.若R,则称a与b没有关系R,记作aRb.若R=Φ称为空关系,若R=A×B称R为全关系,当A=B时,全关系EA={|x∈A∧y∈A}=A×A,A 上的恒等关系IA={|x∈A}定义 3.3.5 设R为二元关系,由∈R的所有x所组成的集合domR,称为R的前域.domR={x|(y)(∈R)}使∈R得所有y组成的集合ranR称为R的值域. ranR={y|(x)(∈R)}R的前域和值域一起称为R的域,记作FLDR,即:FLDR=domR∪ranR.定理3.3.3 若Z和S是从集合X到Y的两个关系,则Z,S的交,并,差,补仍是X到Y的关系. 定义3.4.1 设R是集合X上的二元关系,(1)如果对任意x∈X,必有xRx,则称关系R在X上是自反的.(2)如果对任意x∈X,必有xRx,则称关系R在X上是反自反的.(3)如果对任意x,y∈X,若xRy必有yRx,则称关系R在X上是对称的.(4)如果对任意x,y∈X,若xRy且yRx必有x=y,则称R是反对称的.也可叙述为:若xRy,且xY,必有xRy.(5)如果对任意x,y,z∈X,xRy且yRz必有xRz,则称关系R在X上是传递的.定义3.5.1 设R是从X到Y的二元关系,如将R中每一序偶的元素顺序互换,所得到的集合称为R的逆关系,记作R-1(或Rc)即:R-1={|∈R}定义3.5.2 设R为A到B的关系,S为从B到C的关系,则R○S称为R和S的复合关系表示为:R○S={|x∈A∧z∈C∧(y)(y∈B∧∈R∧∈S)},R○S称为关系的合成运算.(复合运算不满足交换律)定理3.5.2 设A={a1,a2,…,am},B={b1,b2,……,bn},C={c1,c2,……,cr}从A到B的关系R1关系矩阵MR1=(xij)是m×n阶矩阵.从B到C的关系R2的关系矩阵MR2=(yij)是n×r阶矩阵,那么从A到C的关系矩阵:MR1○R2=(zij)是m×r阶矩阵,其中,i=1,2,……,m, j=1,2,……,r.定义3.5.3 设R是A上二元关系,如果有另一个关系R',满足:(1)R'是自反的(对称的,可传递的);(2)R'R;(3)对于任何自反的(对称的,可传递的)关系R",如果有R"R,就有R"R',则称关系R'为R的自反(对称,传递)闭包,记作r(R)(s(R),t(R)).定理3.5.3 设R为非空有穷集合A上的二元关系.(1)r(R)=R∪IA;(2)s(R)=R∪R-1;(2)t(R)=R∪R2∪……∪Rn,其中n是集合A中元素的数目. 定义3.6.1 给定集合A上的关系ρ,若ρ是自反的,对称的,则称ρ是A上的相容关系.定义3.6.2 若把一个集合A分成若干叫做分块的非空子集,使得A中每个元素,至少属于一个分块,那么这些分块的全体构成的集合叫做A的覆盖.定义3.6.1 给定集合A的覆盖,S={S1,S2,……Sn},由它确定的关系:ρ=S1×S1∪S2×S2∪……∪Sn×Sn是相容的.定义3.7.1 设R为定义在集合A上的一个关系,若R是自反的,对称的和传递的,则R称为等价关系.定义 3.7.2 设给定非空集合A,若有集合S={S1,S2,……Sm},其中SiA,Si(i=1,2,…,m),且Si∩Sj=(ij),同时有,称S是A的划分.定义3.7.3 设R为集合A上的等价关系,对任何a∈A,集合[a]R={x|x∈A,aRx}称为元素a形成的等价类.简记[a]或.定理3.7.1 设给定非空集合A上等价关系R,对于:a,b∈A有aRb iff[a]R=[b]R.定义3.7.4 集合A上的等价关系R,其等价类集合{[a]R|a∈A}称为A关于R的商集记作A/R. 定理3.7.2 集合A的等价关系R,确定了A的一个划分,该划分就是商集A/R.定理3.7.3 集合A的一个划分确定A的元素间的一个等价关系.设集合A有一个划分S={S1,S2,……Sm},现定义一个关系R,当aRb,当且仅当a,b在同一分块中,这样:(1)a与a在同一分块中,故必有aRa,即R是自反的.(2)若a,b在同一分块中,则b,a也在同一分块,即aRb=>bRa,故R是对称的.(3)若a与b在同一分块中,b与c在同一分块中,因为Si∩Sj=(ij),即b属于且属于一个分块,故a 与c必在同一个分块中,故有:aRb∧bRc=>aRc,即R是传递的.定义3.8.1 设A是一个集合,如果A上的关系R满足自反性,反对称性,以及传递性,则称R是A上的一个偏序关系,并记作"≤",序偶称作偏序关系.定义3.8.2 设集合A上有二元关系,R若是反自反和传递的,称R为A上的拟序关系.并把称为拟序集,或记作<A,.定理3.8.1 集合A上二元关系是拟序的,则R必为反对称的.定义3.8.3 集合A上二元关系是拟序集,对于任意x,y∈A,如果x≤y或者y≤x成立,称x和y 可比.定义3.8.4 在偏序集中,如果想x,y∈A,x≤y,且xy,且没有其他元素,z满足x≤z,z≤y,则称元素y 盖住元素x.记COV A{|x,y∈A;y盖住x}(设R是非空集合A上的偏序集,a,b是A中两个不同元素,如果∈R,且在A中没有其他元素c,使得∈R和∈R,称元素b盖住元素a.)定义3.8.5 设≤是集合A上的二元关系,如果对于A中任意两个元素a,b∈A,必有a≤b或b≤a,则称≤是A上的全序关系(或称线序关系).若≤是A上的全序关系,称是全序集.定义3.8.6 设是一个偏序关系,钱B是A的子集,对于B中的一个元素b,如果B中没有任何元素x,满足bx,且b≤x称b为B的极大元.同理对于b∈B,如果B中没有任何元素x,满足bx,且x≤b,则称b为B的极小元.定义3.8.7 令是一个偏序集,BA,若有某个元素b∈B,对B中每一个元素,x有x≤b,称b为的最大元,同理,若有某个元素b∈B,对于每个x∈B有,b≤x,则称b为的最小元.定义3.8.8 设为偏序集,对于BA,如果有a∈A,且对于B的任意元素x都满足x≤a,则称a为子集B的上界,同样对于B的任意元素x,都满足a≤x,则称a为B的下界.定义3.8.9 设为偏序集,若有子集BA,若a为B的任一上界,若对B的所有上界y均有a≤y,则称a是B的最小上界(上确界),同样若b为B的任一下界,若对B的所有下界z,均有z小于等于b,则称b为B的最大下界(下确界).定义3.8.10 设为全序集,如果A的任何非空子集都含有最小元,称为良序集.定义3.9.1 设X和Y是任何两个集合,而f是X到Y的一个关系,如果对于每一个x∈X,有惟一的y∈Y,使得∈f,称关系f为函数,记作f:XY或.假如∈f,称x为自变元,与x相对应的y称为函数在x处的值,记作y=f(x),即∈f.y称为f作用下的x的象.从函数定义可以知道它与关系有别于如下两点:(1)函数的定义域是X,而不能是X的某个真子集,这点可以表示为domf=X.(2)一个x∈X只能对应惟一的y∈Y,使得∈f称f为函数.定义3.9.2 设f,g,都是X到Y上函数,它们有相同的定义域与值域,即domf=domg,rang=rang,且对每个x∈X都有f(x)=g(x),称函数f与g是相等的,并记作f=g.定义3.9.3 设X,Y为集合,把所有从X到Y的函数构成的集合记作YX,即Yx={f|f: XY}.定义3.9.4 给定函数f: XY.(1)若ranf=Y称f是满射的或f为到上的.(2)若函数满足x1,x2∈X,若x1x2时必有f(x1) f(x2),则称f为入射的.(3)若函数f既是满射,又是入射,则称f为双射.定义3.10.1 设f: XY,g: YZ,合成关系fg={|(x∈X)∧(z∈Z)∧(y)(y∈Y)∧(y=f(x)∧z=g(y))},称fg为,f,g的做合成运算或复合运算.定理3.10.1设f: XY,g: YZ是两个函数,合成运算gf是XZ的函数,且对每一个x∈X有(gf)(x)=g(f(x)).定义3.10.2设函数f: XX,若对所有x∈X有f(x)=x,则称f为X上的恒等函数,并记作IX.定理3.10.2 设f: XY是任意函数,则IXf=fIX=f.定义3.10.3 给定集合X和Y,且有函数,f: XY,对所有x∈X,存在惟一y0∈Y,使得f(x)=y,即ranf=y0,则称f是常值函数.定理3.10.3 令gf是一个复合函数.(1)若g和f是满射的,则gf是满射的.(2)若g和f是如射的,则gf是入射的.(3)若g和f是双射的,则gf是双射的.定理3.10.4 设f: XY是一个双射函数,那么fc是YZ的双射函数.定义3.10.4设f: XY是一个双射函数,称YX的双射函数f-1为f的逆函数.注意:fc(逆关系)不一定是f-1(逆函数).一个函数f: XY,要有逆函数,必须f是双射的.否则只能保证有fc,但未必有逆函数f-1存在. 定理3.10.5设f: XY是一个双射函数,g: YZ是一个双射函数,则(1)f-1f=IX,f-1f-1=Iy; (2)(f-1)-1=f; (3)(gf)-1= g-1f-1定义4.1.1 设A,B为任意集合,一个从An到B的映射,称为集合A上的一个n元运算.如果BA,则称该n元运算时封闭的.定义4.1.2 一个非空集合A,连同若干个定义在该集合上的运算f1,f2,…,fk所组成的系统,称为一个代数系统,记作:.定义4.1.3 设A为任意非空集合,*是集合A上的二元运算.(1)封闭性:对任意a,b∈A,若有a*b∈A,则称运算*关于集合是封闭的.(2)结合律:对任意a,b,c∈A,若有a*(b*c)=(a*b)*c,则称运算*在集合A是可结合的,或称运算*在A上满足结合律.(3)交换律:对任意a,b∈A,若有a*b=b*a,称为运算*在A上市可交换的,或称*运算在A上满足交换律.(4)幂等率:若对a∈A,有a*a=a,则称运算*在A上市幂等的,或称运算×在A上满足幂等率.(5)分配律:若对a,b,c∈A有: a(b*c)=(ab)*(ac) 和(b*c)a=(ba)*(ca)成立,则称运算对*时可分配的,或称运算*满足分配律.(6)吸收率:若和*满足交换律而且有:a,b∈A,并有a(b*c)=a和a* (bc)=a,则称和*运算时可吸收的,或称和*运算满足吸收率.定义4.1.4 设*为集合A上的二元运算,若存在(或),使得对于x∈A,都有(或),则称(或)是A中关于*运算的左(或右)幺元(或单位元). 如果A中一个元素e,它既是左幺元,又是右幺元,则成e是A中关于运算* 的遥远.显然对于任一x∈A,e*x=x*e=x.定义4.1.5 设*式定义在集合A上的二元运算,如果有一个元素,对于任意元素都有,则称为A 中关于运算*的左零元;如果有一个元素,对于任意元素都有,则称为A中关于运算*的右零元.如果A中的一个元素,他既是左零元,又是右零元,则称为A上关于运算*的零元.定理4.1.1 设*是集合A上的二元运算,且在A中有关于运算*的左幺元和右幺元,则,且A中幺元是惟一的.定理4.1.2 设*是定义在集合A上的二元关系,在A中有关于运算*的左零元和右零元那么,且A中零元是惟一的.定理4.1.3 设有代数系统中,A的元素个数多于1,若其存在关于运算*的单位元e与零元O,则. 定义4.1.6 设代数系统中,e是关于*的单位元,若对A中某个元素a,存在A的一个元素b,使得b*a=e,则称b为a 的一个左逆元;若a*b=e,则称b为a的一个右逆元.若一个元素b,既是a 的左逆元,又是a的右逆元,则称b是a的一个逆元,记作.定理4.1.4 设代数系统,这里*是定义在A上的二元运算,A中存在幺元e,且每一个元素都有左逆元,如果*是可结合运算,那么这个代数系统中,任何一个元素的左逆元必定也是该元素的右逆元,且每个元素的逆元是惟一的.定义4.1.7 如果两个代数系统中运算的个数相同,对应运算的元数也相同,且代数常数的个数也相同,则称这两个代数系统具有相同的构成成分,也称它们是同类型的代数系统.同类型的代数系统仅仅是构成成分相同,不一定具有相同运算性质.定义4.1.8 设是代数系统,,且B对都是封闭的,B和S还含有相同的代数常数,则称是V的子代数系统,简称子代数.定义 4.2.1 设*是集合S上的二元运算,若运算*时封闭的,并且*是可结合的,则称代数系统<S,*》为半群.这个定义包括两点,及对于任意,(1),(2)(a*b)*c=a*(b*c)定理4.2.1 设是一个半群,,且*在B上封闭,那么也是一个半群,通常称是半群的子半群.定义4.2.2 若半群中存在一个幺元则称为独异点(或含幺半群).定理4.2.2 设是独异点,对于,且a, b均有逆元,则:(1),(2)若a*b有逆元,则.定义4.3.1 设是一个代数系统,其中G是非空集合,*是G上一个二元运算,(1)如果*是封闭的;(2)运算*时可结合的;(3)存在幺元e;(4)对于每一个元素,存在它的逆元;则称是一个群.定义4.3.2 设是一个群,如果G是有限群,那么称为有限群,G中元素的个数统称称为该有限群的阶数,记为.定义4.3.3 若群G中,只含有一个元素,即G=|e|,|G|=1,则称G为平凡群.,G关于*运算,构成一个群,这个群称为Klein四元群.定义4.3.4 设是一个群,若运算*在G上满足交换律,则称G为交换群或Abel群(阿贝尔群). 定义4.3.5 设是群,若,使得成立的最小正整数k称为a的阶,记作|a|.定理4.3.1 设为群,有:(1); (2); (3);(4);(5)若G为Abel群,.定理4.3.3 对|G|>1的群不可能有零元.定理4.3.4 设是一个群,对于.必存在惟一的,使a*x=b.定义4.3.7 设为群,若在G中存在一个元素a,使得G中存在一个元素a,使得G中的任意元素都由a的幂组成,则称该群为循环群,元素a称为循环群G的生成元.定义4.3.8 设是一个群,S是G的非空子集,如果也构成群,则称是的一个子群,记作S≤G.子群判别定理:定理4.3.5 设是群,H是G的非空子集,则H≤G iff.(1)a,b∈H,有a*b∈H;(2)a∈H,有a-1∈H.定理4.3.6 设是群,H是G的非空子集,iffa,b∈H,则a*b-1∈H.定理4.3.7设是群,H是G的有穷非空子集,则H是G的子群iffa,b∈H,有a*b∈H.设是群,C={a|a∈G,且对x∈G有a*x=x*a},C又称CentG.定义4.4.1 设是一个代数系统,如果满足(1)是阿贝尔群;(2)是半群;(3)运算*对于运算☆是可分配的;则称是环.定理4.4.1 设是一个环,则对任意a,b∈A有(1);(2);(3);(4);(5)其中是加法幺元,-a是a的加法逆元,a+(-b)记为a-b,注意上面各式中不能只理解是实数上的加法与乘法.定义4.4.2 设是环,对a,b∈R,a≠0,b≠0,但a·b=0;则称a是R中的一个左零因子,b是R中一个右零因子;若一个元素既是左零因子,又是右零因子,则称它是一个零因子.定义4.4.3 设R是一个环,对于任意的a,b∈R,若a·b=0,则a=0或b=0,就称R是一个无零因子环.(整数环,有理环,实数环,复数环都是无零因子环.)定理4.4.2 设是环, R是无零因子环的充分必要条件,是在R中乘法适合消去律,即对任意a,b,c ∈R,a≠0,若有a·b=a·c(或b·a=c·a),则有b=c.定义4.4.4 设是环.如果是可交换的,则称是可交换环.如果含幺元,则称是含幺元.定义4.4.5 设是一个代数系统,如果满足:(1)是阿贝尔群;(2)是可交换独异点,且无零因子,即对任意a,b∈A,a≠,b≠必有a·b≠;(3)运算对于运算+是可分配的.则称是整环.定义4.4.6 设是一个环,且|R|≥2,(1)R有幺元;(2)每个非零元有逆元;则称这个环是除环.如果一个除环是可交换的,称为域.当为域时,及是阿贝尔群,其中R*=R-|0|.定义4.5.1 设是一个偏序集,如果A中任意两个元素都有最小上界和最大下界,则称为格.定义4.5.2 设是一个格,P是由格中元素及≤,=,≥,∧,∨等符合所表示的命题,如果将P中的分别换成≥,≤,∨,∧得到的命题P*,称P*为P的对偶命题,简称对偶.格的对偶原理:如果命题P对一切格L为真,则P的对偶命题业对一切格为真.定义4.5.3 设是一个格,如果在A上定义两个二元运算∨和∧,使得对任意a,b∈A,a∨b等于a 和b的最小上界,a∧b等于a和b的最大下界.称为由格所诱导的代数系统.二元运算∨和∧分别称为并运算和交运算.定理4.5.1 在格中,对任意a,b∈A,都有:a≤a∨b,b≤a∨b, a∧b≤a,a∧b≤b.定理4.5.2 设是格,a,b∈A,(1)a≤b,且a≤c=>a≤b∧c; (2)a≥b且a≥c =>b∨c.定理4.5.3 在格中,对于a,b,c,d∈A,如果a≤b,c≤d,则a∨c≤b∨d,a∧c≤b∧d.定理4.5.4 设是一个格,由所诱导的代数系统为,则对于任意a,b,c,d∈A,有:(1);(交换律)(2);结合律(3)a∨a=a;a∧a=a(幂等律)(4)a∨(a∧b)=a;a∧(a∨b)=a;(吸收律)定理4.5.5 设是一个代数系统,其中∨和∧都是二元运算,且满足交换性,结合性和吸收性,则A 上存在偏序关系≤,使是一个格.定义4.5.4 设是代数系统,其中∧和∨是二元运算,若∧和∨运算满足交换律,结合律,吸收律,则称是一个格.定理4.5.6 设是格,则(1)a,b,c∈L有a≤b=>a∧c≤b∧c,且a∨c≤b∨c; (2)a,b,c,d∈L有a≤b且c≤d=>a∧c≤b∧d,且a∨c≤b∨c;定理4.5.5 设是格,S是L的非空子集,若S关于运算∧和∨是封闭的,则称是格L的子格.定义4.6.1 设是由格所诱导的代数系统,如果对任意a,b,c∈A满足:,称是分配格.定义4.6.2 设和是两个格,由它们分别诱导的代数系统为和,如果存在着一个从A1到A2的映射f,使得对任意a,b∈A1有:,称f为从到格同态,也可称是的格同态象.当f是双射时,格同态也称为格同构.定理4.6.1 格L是分配格,当且仅当L既不含有与五角格同构的子格,也不含有与钻石格同构的子格.(1)每一条链都是分配格.(2)小于五个元素的格都是分配格.定义4.6.3 设是一个格,如果存在元素a∈A对于任意x∈A,都有a≤x(或x≤a),则称a为格的全下界(全上界).记作0(全下界为1).存在全上界和全下界的格称为有界格,记作.定义4.6.4 设是有界格a∈A,若存在b∈A,使得a∨b=1,且a∧b=0,称b是a的补元.定义4.6.5 在一个有界格中,如果每个元素至少有一个补元,则称此格为有补格.定义4.7.1 一个有补格称为布尔格(或布尔代数).定理4.7.1 设有代数系统,其中B至少包含两个元素,∧,∨为B上两个二元运算, '为B上一元运算,对任何a,b∈B满足(H1)a∧b=b∧a,a∨b=b∨a (交换律)(H2)a∧(b∨c)=(a∧b)∨(a∧c),a∨(b∧c)=(a∨b)∧(a∨c) (分配率)(H3)在B中存在零元0,使a∨0=a,a∧0=0,存在单位元1,使得a∧1=a,a∨1=1 (同一律)(H4)a'∈B,使得a∧a'=0,a∨a'=1(补元律)则称是布尔格.定理4.7.2 设为代数系统,∧,∨,是B上的二元运算,'为B上的一元运算,满足条件(H1)-(H4)则称此代数系统为布尔代数.定义4.7.3 设B是布尔代数,函数称为B上的一个n元布尔函数.定义5.1.1 一个图是二元组,其中V是非空结点集,E是连接结点的边集.在一个图中,不与任何结点相邻接的结点称为孤立结点.在一个图中,若两点由一条有向边或一条无向边关联,则这两个结点称为邻接点.关联与同一结点的两条边称为邻接边.。

2.4 前束范式前束范式是谓词公式的标准型，存在但不唯一。

2.4.1 前束范式的定义定义2.19一个公式，如果量词均在公式的开头且它们的辖域都延伸到整个公式的末尾，则该公式称为前束范式。

前束范式的一般形式为Q1x1Q2x2… Q n x n A。

其中，A是一个没有量词的谓词公式，Q i(1≤i≤n)或为∀或为∃，x i是个体变元。

没有量词的谓词公式称为平凡的前束范式。

例2.10判断以下各式是否前束范式：1）﹁∀x∃yA(x, y)2）∀x∃y∀z(A(x)→B(y, z)) 3）A(x, y)4）∀xP(x)→∃xQ(x)解：1）不是前束范式；2）是前束范式；3）是前束范式；4）不是前束范式。

2.4.1 前束范式的定义定理2.7对于任一谓词公式，都存在着与它逻辑等价的前束范式。

谓词公式转换为与之逻辑等价的前束范式的步骤一般如下：第一步：消去冗余量词，且通过换名或代入规则使不同的个体变元不同名。

第二步：利用逻辑等价公式(A↔B)⇔(A→B)∧(B →A) 将公式中的联结词↔去掉。

第三步：利用逻辑等价式﹁﹁A ⇔A﹁(A∨B) ⇔﹁A∧﹁B；﹁(A∧B) ⇔﹁A∨﹁B﹁∀xP(x) ⇔∃x﹁P(x)；﹁∃xP(x) ⇔∀x﹁P(x)进行否定深入，将﹁号深入到原子谓词公式的前面。

第四步：利用量词轄域的扩张与收缩逻辑等价式和量词分配逻辑等价式将所有的量词移到公式的最前面。

求下面公式的前束范式1）∀xP(x)→∃xQ(x) 2）﹁∀xP (x)∧∃xQ(x)解：1）解法1∀xP(x)→∃xQ(x)⇔∀xP(x) →∃yQ(y) （换名规则）⇔∃x(P(x) →∃yQ(y))（∀x 辖域扩张）⇔∃x ∃y (P(x) →Q(y)（∃y 辖域扩张）2）﹁∀xP (x)∧∃xQ(x)⇔﹁∀xP (x)∧∃yQ(y) （换名规则）⇔∃x ﹁P (x)∧∃yQ(y) （量词否定逻辑等价式）⇔∃x ∃y (﹁P(x)∧Q(y))（量词辖域扩张）解法2∀xP(x)→∃xQ(x)⇔﹁∀xP (x)∨∃xQ(x)⇔∃x ﹁P (x)∨∃xQ(x) （量词否定逻辑等价式）⇔∃x(﹁P(x)∨Q(x)) （量词分配逻辑等价式）将公式∀x((∀yP(x)∨∀zQ(y, z))→﹁∀yR(x, y))化成前束范式。

121030前束范式存在定理与证明_27180100补充内容（选学）：?前束范式的存在定理及其证明--选自王宪钧编《数理逻辑引论》，1982，北京大学出版社定理谓词逻辑的任一公式A, 都可化成相应的?前束范式, 并且A是普遍有效的当且仅当其?前束范式是普遍有效的。

说明：对普遍有效的公式，它与其?前束范式是等值的。

而一般的公式与其?前束范式并不等值。

自然仅当A是普遍有效的, 方使用?前束范式。

定理的证明：上述定理可叙述为：谓词逻辑的任一公式D都有一?前束范式E，并且D和E可互推，亦即：D普遍有效是E普遍有效的充要条件。

（1）必有一前束范式E1，且├D ? E1。

（2）如E1中有自由个体变项⊿1,⊿2,…,⊿m，则可引用概括规则得E2 = (⊿1)(⊿2)…(⊿m)E1，m≥0。

E2和E1可以互推，如E1中无自由个体变项，则E2即是E1。

（3）如E2中只有命题变项而无谓词变项，即是说，E2为一命题演算的公式，则可引用定理├P ? (?x)(F(x)∨?F(x)∧P)引入一个处于最前方的存在量词。

（4）如E2为?前束范式，则E2即为E。

否则E2的形式为(?x1) (?x2)…(?x n)(?y)A (x1,…, x n, y)，n≥0。

在这里，A (x1,…,x n, y)为一前束范式，其中只有x1,…,x n, y 是自由个体变项。

E2有两种可能：（a）全称量词“(?y)”之前无存在量词，其后也无存在量词。

（b）“(?y)”后只有k – 1个全称量词出现于存在量词之前。

现在如果能够证明，在上述情形下，必然可以求得一前束范式E3，E3和E2可以互推，并且，如为情况（a），则E3的最前方为一存在量词，也就是说，E3是一个?前束范式。

如为情况（b），则E3中只有k – 1个全称量词出现于存在量词之前，也就是说，比E2少一个这样的全称量词。

在情况（b）下，经过k次这样的转换，就可以得到一?前束范式，因此存在定理得证。