离散数学教程ch2谓词演算A13信息

1、1,第2章,逻辑代数(下)： 谓词演算,2,重点:量词及谓词演算永真式 掌握谓词的概念； 掌握两种量词及其用法； 掌握谓词公式的定义； 掌握基本的谓词演算的等价式和蕴涵式；,3,谓词演算引入的必要性,命题逻辑以由原子命题通过联结词构成的命题公式为讨论对象，不再对原子命题作进一步的分析，即命题逻辑只讨论以原子命题为基本元素的命题公式之间的推理关系，这种逻辑体表达能力很弱。,4,谓词演算引入的必要性,例如：考虑下面的语句： p：n是一个奇数。 数学中的常用判断无法用命题逻辑的形式准确描述。,5,谓词演算引入的必要性,再例： 在命题演算中 ，对下述论断无法判断 其正确性。 “苏格拉底三段论” ： 所

2、有的人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 命题演算不足的原因忽略了命题内部的细节。,P q r,原子命题内部究竟有那些细节？ 所有的人都是要死的 苏格拉底是人 苏格拉底是要死的 三个命题涉及三个概念： 1）表示事物的性质： “是人”、“是要死的” 称谓词。 2）表示主体： “人”、“苏格拉底” 称个体。 2）表示数量：“所有的人”中还使用了数量词“所有”称量词。,谓词演算引入的必要性,6,7,类似的例 还有许多。 例如： 所有的人都要呼吸 , 所有的正整数都大于0, 李莉是人 , 3是正整数, 所以李莉要呼吸。 所以3大于0。 例如： P：张三是学生 Q：李四是学生,谓词演算

3、引入的必要性,8,只有对简单命题做进一步剖析，才能认识这种推理规律。这就需要引入个体、谓词、引入变量并考虑到表示变量的数量上一般与个别的全称量词和存在量词，进而研究它们的形式结构和逻辑关系，这便构成了谓词演算。,谓词演算引入的必要性,9,2.1 谓词演算基本概念,在谓词演算中，可将原子命题分解为谓词与个体词两部分。 2.1.1 个体 一切讨论对象都称为个体（individuals） 注意：个体可以是客观世界中的具体客体， 也可以是抽象的客体，诸如数字、符号等。 个体通常在一个命题里表示思维对象。,10,确定的个体：常用a，b，c 等小写字母或字母 串表示。 个体常元 不确定的个体：常用字母 x

4、，y，z，u，v，w 等表示。 个体变元或变元,2.1.1 个体,11,2.1.1 个体,个体的全体称为个体域。 （个体变元的取值范围。） 常用字母D表示，并约定任何D都至少含有一个成员。 当讨论对象遍及一切客体时，个体域特称为全总域（universe），用字母U表示。 表示D上个体间运算的运算符与常元、变元组成所谓个体项。 一阶谓词演算：其变元只能取个体对象，不能取值命题、谓词、函数。,12,2.1.2 谓词,语句中表示个体性质或关系的语言成分（通常是谓语）称为谓词（predicate）。 谓词所携空位的数目称为谓词的元数。 一元谓词表达了个体的性质，而多元谓词表达了个体间的关系。,13,2

5、.1.2 谓词,例如：（1）李明是学生； （2）张亮比陈华高； （3）陈华坐在张亮与李明之间。 在这三个命题中，李明、张亮、陈华都是个体；“是学生”是一元谓词， “比高”是二元谓词， “坐在与之间”是三元谓词。,14,2.1.2 谓词,例如（1）“苏格拉底是人”中的“是人”。 （2）“苏格拉底是要死的”中的“是要 死的”。 （3）“实数的平方非负”中的“是非负 的”。 （4）“董旎生于青岛”中的“生于”。 （5）“3小于2”中的“小于”。 （6）“3 + 5 = 8”中的“+=”。,15,2.1.2 谓词,谓词演算中用携有空位的大写字母表示谓词(字母的选择是随意的,以方便记忆为好)。 M（ ）

6、表示“是人”。 D（ ）表示“是要死的”。 R（ ） 表示“是实数”。 NN（ ）表示“是非负的”。 B（ ， ）表示“生于”。 L（ ， ）表示“小于”。 ADD（ ， ，）表示“+=”。,x,x,x,x,x,y,x,y,x,y,z,16,2.1.2 谓词,谓词填式 n元谓词P(x1,xn)填满对象后的表达式P(t1,tn)常称为谓词填式，表示对象序列t1,tn满足n元谓词P(x1,xn)。,17,2.1.2 谓词,当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值。 一些复杂的性质和关系，可以用谓词和联结词复合的形式来描述， 例如： “如果一个人生于北京，那么他不生于上海”可表

7、示为 B(x,Beijing)B(x,Shanghai),18,2.1.3 量词,使用前面介绍的概念，还不足以表达日常生活中的各种命题。 例如：对于命题 “ 所有的正整数都是素数 ” 和“ 有些正整数是素数 ” 仅用个体和谓词是很难表达的。,19,2.1.3 量词,量词用来表示个体数量的词是量词，也可看作是对个体所加的限制、约束的词，但主要不是对数量一个、二个、三个的具体描述，而是讨论两个最通用的数量限制词，一个是所有的一个是至少有一个，分别称作全称量词和存在量词。,17,20,2.1.3 量词,（1） 全称量词 “ ” 如 “所有人都是要死的。” 令D(x)：x是要死的； 可表示为 x D（

8、x）， x的个体域为全体人的集合。 xD(x) ：读作“所有（任意，每一个）x满足D(x)”。 表示个体域中所有的个体满足谓词D(x)。 x ：用在量词后的变元x 称为量词的指导变元，指导变元同时填在谓词D(x) 中。,21,2.1.3 量词,（2）存在量词 “ ” 如 “有些有理数是整数。” 令I(x)：x是整数； 于是命题可表示为 xI(x) 其中x的个体域为有理数集合。 xI(x)： 读作“有（存在，至少有一个）x满足I(x)”。表示个体域中至少有一个体满足谓词I(x)。,22,说明,（1）指导变元，其名字不重要。量词的指导变元和量词所“管辖”的谓词填式中的变元是可以改名(rename)

9、的（两者必须同时改为相同的变元）。 （2）量词不仅可用于谓词填式之前，还可用于复合的谓词表达式之前，这时应对该表达式使用括号。 例如：x (M(x)B(x),23,说明,当量词用于一谓词填式或复合的谓词表达式式时，该谓词或复合的谓词表达式称为量词的辖域（domains of quantifiers）。,24,说明,（3）量词的指导变元和量词辖域内的同名变元与通常谓词填式中的个体变元不同，因为它可以改名却不能取值代入， 例如 5P(5), x2 P (x)都是毫无意义的。,25,说明,（3）约束变元 量词辖域内与该量词指导变 元同一的变元 例：xP(x) 和 xP(x) 中变元x 自由变元 可以

10、取值代入的变元,26,说明,而综合(1)，(3)可知，约束变元是形式记号的一部分，对它可以改名但不能代入。其实数学中常常使用这种约束变元作为数学符号的一部分。,27,说明,（4）对于一元谓词P(x)，xP(x)为一命题，它断言所有个体满足性质P(x),其真值已经被给定的个体域所确定。 同理 xP(x) 也是命题。,28,说明,例：D表示某班全体学生。 G(x)表示x是男生。 xG(x):全班每个人都是男生。 xG(x):全班存在一个人是男生。 含量词的一元谓词的真值不再依赖于x的取值。,29,说明,特别是,当个体域中个体有穷时， 例如D = a1, ,an， xP(x) 的意义与命题 P(a1

11、)P(an) 等价， xP(x) 的意义与命题 P(a1)P(an) 等价。,30,2.1.4 谓词公式及语句的形式化,定义2.1 归纳定义谓词公式(predicate forrmula)， 谓词公式又称合式公式，简称公式。 （1）谓词填式是公式，命题常元是公式（看作零元谓 词），常称原子公式。 （2）如果A，B是公式，x为任一变元，那么(A)， (AB)， (AB)，(AB)， (AB)， (xA)，(x A) 都是公式。 （3）只有有限步使用（1），（2）条款所形成的符 号串是公式。,31,括号省略原则同命题公式，并约定，(xA)，(x A)中最外层括号也可省略。,(1)公式最外层括号一律

12、可省略。 (2)联结词的结合能力强弱依次为 ，(，)， (，)表示与平等。 (3)结合能力平等的联结词在没有括号表 示其结合状况时，采用左结合约定。,32,例：,依定义 p, P(x, y)Q(y),( x(A(x)B(x), x (A(x) yB(x, y) 都是合式公式。 注意，yL(3,2)也是公式。 一般地，当A中无变元x时，xA，x A，均被看作与A相同。,33,说明,注：对于一个谓词公式，如其每个变量均在量词的管辖下，则该公式不是命题函数，而是命题了，它有确定的真值。,34,改名,对约束变元进行改名：将量词辖域内出现的某个约束变元及相应量词中的指导变元，可以改成一个其他变元，改变元

13、不能与本辖域内的其他变元同名，公式中的其他部分不改变。 xf(x,y) xG(x,y),35,例：,指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题： P(x)(yx(P(x)B(x,y)P(x) 解：全称量词，辖域x(P(x)B(x,y)，其中 y为约束变元。 存在量词，辖域P(x)B(x,y)，其中 x为约束变元。 不在量词辖域中的P(x)中的x为自由变元。P(x)(yx(P(x)B(x,y)P(x)不是命题。,36,当个体域给定，谓词公式中的谓词都有明确意义（关于个体域中个体的某个性质或关系），并且在谓词公式中自由变元均已取定个体时，谓词公式也就具有了确定

14、的意义，成了关于个体域的一个断言，可判定其真值。,谓词公式,37,例2.3 ：,设D为实数域，E(x,y)表示D上关系“x = y”，L(x,y)：x y那么 （1）x L(0,x2+1) （4）xE(x2,y) 允许常用的数学符号表示谓词，例如用x y代替L(x,y)，x2 = y代替E(x2,y)。,38,（7）x y(x+y=0) （8）y x (x+y=0) （9）y x (xy=0) （10）x y(xy=0),例2.3 ：,39,例 ：,对个体域0，1判定下列公式的真值, E(x)表示“x是偶数”： （1）x(E(x)x=1) 解：（1）x(E(x)x=1) 真 x(E(x)x=1

15、) 可表示成命题公式(E(0)0=1)(E(1)1=1) 其中E(0)0=1真，E(1)1=1也真，故(E(0)0=1)(E(1)1=1)真。,40,使用计算机来处理由自然语句或非形式化陈述的问题，首要的工作是问题本身的形式描述。命题逻辑的表达问题的能力，仅限于联结词的使用。而谓词逻辑由于个体、谓词、量词的引入具有强得多的表达问题的能力，已成为描述计算机所处理的知识的有力工具。人工智能学科将谓词逻辑看作是一种基本的知识表示方法和推理方法。,语句的形式化,41,使用谓词逻辑描述以自然语句表达的问题，首先要将问题分解成一些原子谓词，引入谓词符号，进而使用量词、联结词来构成合式公式。这种形式描述是进

16、而作推理的先决条件，所以从实用角度显得十分重要。,2.1.4 语句的形式化,42,例： 个体域是人类 (1) “有的人活百岁以上。” （ (2) 有人勇敢，但不是所有的人都勇敢。,2.1.4 语句的形式化,43,语句形式化过程的四个关键问题是：,（1）准确地从语句中提取谓词，表示性质的谓语用一元谓词表示， 表示关系的谓语用二元或更多元数的谓词来表示。 （2）准确地使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用。 （3）准确地使用谓词之间的真值联结词，正确地反映谓词之间关系。 （4）准确地使用多个重叠的量词以及它们配套的指导变元，其排列次序应与原语句意义一致。,44,例：（3

17、）大家都不相互依靠，但互相帮助。 用R(x,y)表示“x依靠y”，H(x,y)表示“x帮助y”， 它译为 xyR(x,y) xyH(x,y) （4）我为人人，人人为我。 用i表示“我”，S(x,y)表示“x为y服务”， 它可译为 xS(i,x) xS(x,i),2.1.4 语句的形式化,45,例 （5）每个人都有人爱，但没有人为所有人爱。 用L(x,y)表示“x爱y”， 它可译为 x yL(y,x) y x L(x,y) （6）勇敢者未必都是成功者。 用B(x)表示“x勇敢”，W(x)表示“x是成功者”， 它可译为x(B(x)W(X) 或 x(B(x) W(X),2.1.4 语句的形式化,43

18、,46,在全总域讨论,首先，在讨论全总域的某个局部域上的所有个体或某些个体时，要使用把量词限于该局部域的所谓“限定谓词”。 其次，限定谓词与其它谓词之间应使用适当的联结词。当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入；当限定谓词用于限定存在量词时，它必须作为合取词的合取项加入。,43,47,在全总域讨论,当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入；当限定谓词用于限定存在量词时，它必须作为合取词的合取项加入。 x(限定谓词A(x)Q(x) x(限定谓词A(x)Q(x),48,例：1）所有的有理数都是实数。 P(x)表示x是有理数，Q(x)表示x是实数，这句话的形式描述应

19、为 x(P(x)Q(x) 不能形式化为 x(P(x)Q(x) 所有的都是，这类语句的形式描述只能使用而不能使用。 （,2.1.4 语句的形式化,49,例： （ 2）所有运动员都钦佩某些教练。 解: 令P（x）：x是运动员；T（x）：x是教练；Q（x，y）：x钦佩y。 则该命题可表示为 x(P(x) y(T(y) Q(x,y) 3)实数的加运算满足交换律。 R (x)：x是实数， xy(R(x)R(y)x+y=y+x),2.1.4 语句的形式化,50,例 4)苏格拉底三段论可用谓词公式表示。,令 M（x）：x是人； D（x）：x是要死的； a：苏格拉底,则三段论可表示为 ( x（M（x）D（x）

20、 M（a）) D（a）,51,例：,每人都有自己喜欢的水果，有人喜欢所有的水果。 F(x)：“x是水果”， M(x)：“x是人”， L(x,y)：“x喜欢y”， 它译为 x(M(x)y (F(y)L(x,y) x (M(x)y(F(y)L(x,y),52,2.2.1 谓词公式的语义 （1）x(M(x)B(x) （2）x (f(x)=0) （3）x (ax2+bx +c=0)y=1,2.2 谓词演算永真式,53,2.2.1 谓词公式的语义,谓词公式的真值不仅依赖于个体域，依赖于公式中各个个体变元的取值状况，还依赖于对公式中谓词符号、函数符号、常元符号所作的解释，即符号与个体域上具体性质、关系、函

21、数、对象间的映射，常用I表示一种解释。I恒把命题常元（零元谓词）解释为真值0或1。,54,2.2.1 谓词公式的语义,例 分别给定个体域D1=3，4，D2=3，5，以及解释I1 ，I2， I1把P(x)解释为“x是质数”， I2把P(x)解释为“x是合数”时的情况。 分别讨论 P(x) ，y P(y) 和yP(y)P(x)的真值。,55,2.2.1 谓词公式的语义,56,真值概念,定义2.2 给定个体域D及公式A中各谓词符号的解释I，如果A中个体变元x1 ,xn分别取值u1 ,un时A真，则称A在u1 ,un处真；当x1 ,xn无论取D中怎样的个体u1 ,un, A在u1 ,un处均真，则称A

22、在解释I下真。,57,真值概念,定义2.3 给定个体域D，若公式A在每一解释I下均真，那么称A在D上永真。 若公式A对任何个体域D均有D上永真，则称A为永真式，或称A永真。 A永真仍记为 A。,58,沿用命题演算中引入一些符号和称谓： A B表示“AB”永真，称A逻辑蕴涵B。A B当且仅当对任意个体域和解释，一切使A真的变元取值状况均使B亦真。 A同前，可作类似的定义。 AB表示“AB”永真，称A逻辑等价B。AB当且仅当对一切域、解释和变元取值状况，A与B都具有相同的真值。,真值概念,59,真值概念,定义2.4 公式A称为可满足的，如果对某一个体域、某一解释和变元的某一取值状况，A在此处取值真

23、。否则，称公式A不可满足。公式A不可满足时也称A为永假式。 当公式A永真时，A必定是永假式。,60,例 试说明下列各公式的类型（个体域取为 全总个体域）,解 (1) 永真式,(2) 可满足公式,(3) 可满足公式,(4) 永假式,1）xF(x) F(y) 2) xF(x) F(y) 3) F(x) （其中F(x): x+6=5） 4) x(F(x) F(x),61,（1）所有命题演算中的重言式,2.2.2 谓词演算永真式,由于谓词演算中允许使用命题常元，因而谓词公式中仍包含命题公式，其中的重言式显然在谓词演算中仍然是永真式。,62,在命题演算中，任一逻辑等价式或逻辑蕴涵式，其中同一命题变元，当

24、用同一命题公式取代时，其结果仍是逻辑等价式或逻辑蕴涵式。 将此情况推广到谓词公式中，用谓词公式去取代命题演算中逻辑等价式或逻辑蕴涵式的命题变元时，便得到谓词演算的逻辑等价式或逻辑蕴涵式。,（1）所有命题演算中的重言式,63,例2.8 A(x)A(x) A(x)(B(x)A(x) (A(x)B(x)(B(x)A(x),（1）所有命题演算中的重言式,64,又例：,AAA xA(x) xA(x) xA(x) AB AB xA(x) xB(x) xA(x) xB(x),65,x AA x AA 由于A与自由变元x无关，根据我们的约定两式显然成立。,（2）当A不含自由变元x时,66,x A(x) A(x

25、) A(x) x A(x) x A(x) x A(x),（3）对任意含有自由变元x的公式A(x),67,量词与否定词交换 x A(x) x A(x) x A(x) x A(x) x A(x) x A(x) x A(x) x A(x),(4)否定型逻辑等价式,68,在1, 2域上分析 xA(x) (A(1)A(2) A(1) A(2) x A(x) xA(x) (A(1)A(2) A(1) A(2) x A(x) 否定词越过量词的内移规律, 就是摩根律的推广。,69,设个体域D=d1,dn，试用消去量词的方法证明下列基本逻辑等价式： xA(x)xA(x) 解 xA(x)（A（d1）A（dn） A

26、（d1）A（dn） xA(x),70,例2.9,xyz(x=y+z) x yz(x = y+z) x y z(x = y+z) x yz(x y+z),71,x A(x)Bx (A(x)B) x A(x)Bx (A(x)B) x A(x)Bx (A(x)B) x A(x)Bx (A(x)B) 这是一组量词对、的分配律，其中B与变元x无关，这是很重要的条件。,(5) 量词对、的分配率,72, 在， 逻辑下，辖域可以扩充到一切不含指导变元的任意公式上。 两个条件： 1 B中不含指导变元x 2 只能与， ,(5) 量词对、的分配率,73,证明： x A(x)Bx (A(x)B),1）先证 x A(x

27、)Bx (A(x)B) 设在任一个体域D和解释I下, xA(x)B 真，那么a）若 B 为真, 则 x(A(x)B) 真b）若 B 为假, 必有 xA(x) 真, 即任一xD有A(x) 真, 于是对任一xD有A(x)B 真, 故x(A(x)B) 真。 1）得证。,74,证明： x A(x)Bx (A(x)B),2）再证x (A(x)B)x A(x)B 设在任一个体域D和解释I下, x(A(x)B) 真即任一xD, 有A(x)B 真a）若 B 真, 则xA(x)B 真b）若 B 假, 对任一xD有A(x) 真。 即有xA(x) 真, 故仍有xA(x)B 真。 2）得证 综合1）和2）命题得证。,

28、75,(6) 量词对、量词对的分配率,这是当A(x)、B(x)都含有个体变元x时, 量词 对, 量词对所遵从的分配律。然而 对， 对的分配律一般并不成立。 x (A(x)B(x)x A(x)x B(x) x (A(x)B(x)xA(x)x B(x) x A(x)x B(x) x (A(x)B(x) x (A(x)B(x) x A(x)x B(x),76,证明：x A(x)x B(x) x (A(x)B(x),证：对任一个体域D和解释I 。 若x A(x)x B(x)真， （a）若x A(x)真，即对一切个体dD，A(d)真，从而A(d)B(d)真,故有x (A(x)B(x)真。 （b）若x B

29、(x)真时，同理可证 x (A(x)B(x)亦真。,77,证明：x A(x)x B(x) x (A(x)B(x),相反的逻辑蕴涵却是不成立的。 即x (A(x)B(x) x A(x)x B(x)不成立 令D为整数集， A(x)表示“x是偶数”， B(x)表示“x是奇数”。 显然x (A(x)B(x)真， 但x A(x)假，x B(x)也假， 从而x A(x)x B(x)假。,78,证明逻辑蕴涵式 甲乙不成立,只要给出一个个体域，一种解释和对自由变元（如果有的话）的一种赋值，它们使得“甲”为真，但使得“乙”为假。,79,(7)相邻量词(两量词交换次序的逻辑等价式和逻辑蕴涵式),xyA(x,y)y

30、x A(x,y) xyA(x,y)yx A(x,y) xyA(x,y) y x A(x,y) xyA(x,y) y x A(x,y) yxA(x,y) x y A(x,y) 相邻的同名量词的次序无关紧要， 不同名量词的次序是不可随意变更的。,80,当C中无自由变元x时， x(CA(x)Cx A(x) x(A(x)C)x A(x)C x(CA(x)Cx A(x) x(A(x)C) x A(x)C x (A(x)B(x) x A(x)x B(x) x (A(x)B(x)xA(x)x B(x),(8) 量词对的分配率,81,证： x (A(x)B(x) x A(x)x B(x),设任一个体域D和解释

31、I下x (A(x)B(x)真，即对任意dD，A(d)B(d)真。 为证xA(x)xB(x)在个体域D和解释I下真，设xA(x) 在域D和解释I下真，从而对任意dD，A(d)均真。 由A(d)B(d) 真及A(d) 真，可知对任意dD，B(d)真，此即表明xB(x)在域D解释I下真。即x A(x)x B(x)真。原式得证。,82,证： x (A(x)B(x) x A(x)x B(x),该式之逆不成立。 令D为整数集， A(x)，B(x)解释为“x是偶数”和“x是奇数”， 这时xA(x)假， xB(x)假， 从而xA(x)x B(x)真， 但x(A(x)B(x)假，因为“所有的偶数都是奇数”显然是

32、荒谬的。,83,2.2.3 谓词公式等价变换的几个基本原理,定义2.5 设谓词公式A中含自由变元x，设t为一个体项，且t中无自由变元为A中的约束变元，那么称t是在A中对x可代入的，其代入实例记为A(t/x)。,84,定理2.1（代入原理）若A是永真式，那么对A中变元可代入的代入实例都是永真式。,2.2.3 谓词公式等价变换的几个基本原理,85,定理1.2 设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。 定理1-2常被称为代入原理 (rule of substitution)，简记为RS,十

33、、代入原理,86,定理2.2（替换原理）设A，D为谓词公式，C为A的子公式，且CD。若B为将A中子公式C的某些出现（未必全部）替换为D后所得的公式，那么AB。,2.2.3 谓词公式等价变换的几个基本原理,87,定理1.3 设A为一命题公式，C为A的子公式，且CD。若将A中子公式C的某些（未必全部）出现替换为D后得到的公式记为B，那么AB。 定理1.3常被称为替换原理 (rule of replacement),简记为RR。,十一、替换原理,88,例2.12,利用替换原理可由已知永真式导出其它永真式。 证明 x(A(x)B(x) x(A(x)B(x) (x(A(x)B(x) (xA(x)xB(x

34、) xA(x)xB(x) xA(x)x B(x),89,例2.12,（2）可证对任意A(x)，B(x) x (A(x)B(x)xA(x)x B(x) 证明 x (A(x)B(x) x(A(x)B(x) xA(x)x B(x) xA(x)x B(x) xA(x)x B(x),90,定理2.3 （改名原理） 若公式A(x)中无自由变元y，那么， xA(x)yA(y) xA(x)yA(y),2.2.3 关于永真式的几个基本原理,91,例2.14,求证：对任意公式A(x,y)， x yA(x,y)y x A(y,x) 证明 x yA(x,y)x z A(x,z) y z A(y,z) y x A(y,

35、x),92,定义2.6 设A为仅含联结词 ，的谓词公式，A*为将A中符号，t，f， , 分别换为，f，t, ， 后所得的公式，那么称A*为A的对偶式。 注意：第一章中关于对偶式的一切讨论，现在对于谓词演算都仍然成立。,2.2.3 谓词公式等价变换的几个基本原理,对偶原理,定理1.4 设公式A中仅含命题变元p1,pn， 及联结词，那么 AA*(p1/p1, pn/pn) 这里A*(p1/p1, pn/pn)表示在A*中 对p1,pn分别作代入p1, pn后所得 的公式。,94,例2.13,由AA*(p1/p1, , pn/pn) 可立即推得 xp(x)xp(x)xp(x),对偶原理,定理1.5设A，B为仅含联结词，和命题变元p1,pn的命题公式， 且满足A B，那么有B