第一篇----数理逻辑

1、离散数学DiscreteMathematics,福建师范大学福清分校数学与计算机科学系黄晓秋,第一篇数理逻辑,数理逻辑是研究推理（即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法，因此也称为符号逻辑。,第一章命题逻辑,1.命题及其表示命题：是指具有确定真值的陈述句或者能够判断真假的陈述句。命题的真值：命题的判断结果。真值只取两个值：真（1或T）、假（0或F）。,1.1命题及联结词,真命题：真值为真的命题。假命题：真值为假的命题。判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。,例1.1下列句子中那些是命题？（1）雪是白的。（2）2是奇数。（3）

2、（4）2200年的元旦是晴天。（5）火星上有生物。（6）请安静！（7）现在是几点钟?（8）我正在撒谎。,感叹句、祈使句、疑问句都不是命题.陈述句中的悖论以及判断结果不惟一确定的也不是命题。简单陈述句表达的命题称为简单命题或原子命题。命题逻辑不再进一步分析简单命题的内部结构。,命题的分类简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。复合命题：由简单命题通过联结词联结而成的陈述句。如：命题“如果2是素数，则3也是素数”通过“如果，则”组合而成，是复合命题，而“2是素数”和“3是素数”是简单命题。,命题表示用英文字母表示命题,用“1(或者T）”、“0（或者F）”分别表示真值的真、假。如P

3、：太阳从东边升起。Q：5是负数。R：2008北京举办奥运会。其真值依次为1、0、1。,2.命题联结词,在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句。例如可以说：“如果下星期日是晴天，那么我就去春游”。这里就是用：“如果，那么”把两个命题“下星期日是晴天”和“我去春游”联结起来组成的一个新复合命题。,在日常语言中还有许多联结词，如“不”、“并且”、“或者”、“当且仅当”，“只要就”，“除非否则”等都是联结词。使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题。下面介绍6种常用的联结词。,（1）否定联结词设p为命题，复合命题“非P”（或“P的否定”

4、）称为P的否定式，记作P，符号称为否定联结词。运算规则：属于一元运算符,（2）合取联结词设P,Q为二命题变元，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作PQ，符号称为合取联结词。运算规则：属于二元运算符,合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”等都可以用符号化。,例如：将下列命题符号化(1)北京不仅是中国的首都而且是一个故都。解：设P：北京是中国的首都；Q：北京是一个故都；则原命题符号化为：PQ。,（2）小丽既聪明，又能干。解：设P：小丽聪明；Q：小丽能干；则原命题符号化

5、为：PQ。（3）小刚聪明但不努力。解：设P：小刚聪明；Q：小刚努力；则原命题符号化为：PQ。（4）小刚和小明是同学。解：P：小刚和小明是同学,（3）析取联结词设P,Q为命题变元，复合命题“P或Q”称为P与Q的析取式，记作PQ，符号称为析取联结词。运算规则：属于二元运算符。,说明：联结词析取的意义与日常所使用的“或”意思并不完全相同。在日常生活中，“或”实际上分为“可兼或”和“排斥或”（异或），还有一种是描述模糊数据。“排斥或”用异或联结词表示，也可用等价的联结词代替。,（4）异或（排斥或）联结词(不做要求）运算规则：属于二元运算符。,例如:(1)老王学过俄语或英语。解：设P：老王学过俄语；Q：

6、老王学过英语；则原命题符号化为：PQ。（可兼或）,（2）张三生于1972年或1973年。解：设P：张三生于1972年；Q：张三生于1973年；则原命题符号化为：PQ（不可兼或）该命题中的“或”不是“可兼或”，不能用析取联结词也可以用一种等价形式来代替。(PQ)(PQ).,（3）小刚有20或30岁。解：这是原子命题，这里的“或”表示一个模糊数据。原命题符号化为P：小刚有20或30岁,（5）单条件联结词设P,Q为二命题变元,复合命题“如果P,则Q”称为P与Q的单条件（蕴涵式），记作PQ，并称P为单条件的前件，Q为单条件的后件，符号称为单条件联结词。,运算规则：属于二元运算符,说明：PQ的逻辑关系：

7、Q为P的必要条件，P为Q的充分条件。但P，Q间可以没有任何内在联系。例：如果小明去公园，那么意大利取得本届欧洲杯足球赛冠军。当P为假时，无论Q取何值，PQ均为真。前提不真，结论总是成立的。例：如果太阳是三角形的，那么月亮就是四边形的。是真命题。,“如果P，则Q”的不同表述法很多：“若P，就Q”“只要P，就Q”“因为P，所以Q”“P仅当Q”“只有Q才P”“除非Q,才P”“除非Q,否则非P”.等等，都可表示为PQ,例如：（1）如果天下雨，那么我们在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符号化为：PQ。（2）只要天下雨，我们就在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符

8、号化为：PQ。,（3）因为天下雨，所以我们在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符号化为：PQ。在实际的语言中，很多联结词可以转化为用单条件，但是要注意前件和后件的关系。,（4）只有天下雨，我们才在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符号化为：QP。（5）仅当天下雨，我们在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符号化为：QP。（6）除非天下雨，否则我们不在室内活动。解：设P：天下雨；Q：我们在室内活动；原命题符号化为：QP，或者PQ。,（6）双条件联结词设P,Q为二命题变元，复合命题“P当且仅当Q”称为P与Q的双条件，记作PQ，符号称为双条件

9、联结词。说明:(1)PQ的逻辑关系:P与Q互为充分必要条件(2)PQ为真当且仅当P与Q同真或同假。,运算规则：属于二元运算符。,例如：1+1=2当且仅当太阳从东边升起。解：设P：1+1=2；Q：太阳从东边升起；原命题符号化为：PQ。,P.4例1.3将下列命题符号化：1、李明是计算机系的学生，他住在312室或313室。2、张三和李四是朋友。3、虽然交通堵塞，但是老王还是准时到达了车站。4、李梅是三好学生或优秀团员。5、老王或小李中有一人去上海出差。,1.2命题公式与赋值1.命题公式（1）单个命题变项是合式公式，并称为原子命题公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公

10、式，则(AB)，(AB)，(AB)，(AB)也是合式公式。（4）只有有限次地应用(1)、（2）、(3)形成的包含命题变元、联结词和圆括号的符号串是命题合式公式。命题合式公式也称为命题公式或命题形式，并简称为公式。,例如：(PQ)，(RS)Q，QP等均为合式公式;而PQS,(P,Q）R，(PQ)R，(PW)Q)等不是合式公式。联结词运算的优先次序为:最高级，第二级，第三级，如果有括号，则先进行括号内的运算，同级的按从左到右顺序。,如公式(P）Q)R)Q)P)Q)R)可以简化为(PQRQP)QR但最好还是加上适当的括号，看得更清楚，如：,（(PQ）RQ）P)Q）R,2.真值表,设A是一个命题公式，

11、P1，P2，.，Pn是出现在A中的所有命题变元，对这些命题变元赋予一个确定的真值称为对命题公式的一种赋值。将命题公式在所有的赋值下的真值情况汇成一个表，这个表就称为真值表。如果一个命题公式有n个命题变元，每个命题变元有两种真值情况，则共有2n种不同的赋值情况。,对公式A构造真值表的具体步骤为：(1)找出公式中所有的全体命题变项p1，p2，pn，列出2n个赋值。(2)按从高到低（从低到高）的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。,例如：求命题公式(PQ)R的真值表。,例求命题公式(PQ)(QP)的真值表。,例求命题公式PQ和(PQ)的真值表。,公

12、式的分类,重言式：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为1，则称该命题公式为重言式或永真式。永假式：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为0，则称该命题公式为矛盾式或永假式。可满足式：给定一个命题公式，若存在一种赋值使得公式的真值为1，则称该命题公式为可满足式。,3.等值演算,设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的记作AB.即AB的充要条件是AB为重言式。前面结果表明：PQ(PQ)判断两个公式等值的方法：1、真值表法2、公式法,例如：P(QR)(PQ)R,双重否定律:AA幂等律：AAA;AAA交换

13、律:ABBA;ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC)吸收律:A(AB)A,A(AB)A,最基本的等价公式，也称命题定律。,德摩根律:(AB)AB(AB)AB零律:A11,A00同一律:A0A,A1A排中律：AA1矛盾律：AA0蕴涵等值式:ABAB等价等值式:AB（AB）（BA）假言异位:ABBA,置换规则：设公式B是A的子公式，C是与B等值的公式，则用C置换B在A中的出现，得到的公式与公式A等值。即：若BC,则(B)(C)。,试证:,证明：,=左,右=,验证P(QR)(PQ)R证明：右(PQ)RPQRP(QR)P（Q

14、R)P(QR)左,P.11例1.16另解设：p1：中国第一；p2：中国第二；p3：中国第三；q1：奥地利第一；r1：匈牙利第一；r3：匈牙利第三；甲的说法p1r3，乙的说法q1p3，丙的说法r1p2三位各猜对一半，所以（(p1r3）（p1r3）)(q1p3）（q1p3）（(r1p2）（r1p2）=1前两个用分配律，注意到没有并列名次，所以有,1（p1r3q1p3）（p1r3q1p3）（(r1p2）（r1p2）p1r3q1p3r1p2所以，r3=1，q1=1，p2=1即，匈牙利第三，奥地利第一，中国第二,1.4联结词的全功能集（不做要求）,1.5范式,文字：命题变元及其否定统称为文字。如：P,Q

15、，Q等，但P不是文字。相反文字，如P与P简单析取式与简单合取式：如果A1，A2，An都是文字，则称A1A2An为简单析取式A1A2An为简单合取式,析取范式：如果A1，A2，An都是简单合取式，则称A1A2An为析取范式；,合取范式：如果A1，A2，An都是简单析取式，则称A1A2An为合取范式。,P.14例1.22,一个命题公式总可以通过等值变化化为与之等值的析取范式和合取范式，但其析取范式和合取范式不惟一。为了能够惟一的表示一个命题公式，下面我们主要讨论命题公式的主范式。,极小项和极大项：设p1，p2，pn是不同的命题变元，A1，A2，An是文字，如果每个Ai是pi或pi，则称简单析A1A

16、2An为关于p1，p2，pn的极大项；称简单合取式A1A2An为关于p1，p2，pn的极小项。n个命题变项可构造2n个极大项和2n个极小项,极大项、极小项的编码：每个极大项只有一个成假赋值，每个极小项只有一个成真赋值，把这组赋值所对应的二进制数转换成十进制数，做为该极大项或极小项的编码，记成Mi或mi,例关于p,q,r三个命题变元的极小项pqr，极大项pqr，写出其对应的编码。解：极小项pqr的成真赋值是011，转换成十进制数为3，所以编码为m3，即pqr=m3极大项pqr的成假赋值是100，转换成十进制数为4，所以其编码为M4，即pqr=M4,由p,q,r三个命题变项形成的极小项与极大项,极

17、大项,极小项,M0M1M2M3M4M5M6M7,000001010011100101110111,pqrpqrpqrpqrpqrpqrpqrpqr,m0m1m2m3m4m5m6m7,000001010011100101110111,pqrpqrpqrpqrpqrpqrpqrpqr,名称,成假赋值,公式,名称,成真赋值,公式,极大项与极小项的关系miMi,Mimi主析取范式、主合取范式如果A1，A2，An是关于p1，p2，pn的不同极小项，则称A1A2An为关于p2，pn的主析取范式，如果A1，A2，An是关于p1，p2，pn的不同极大项，则称A1A2An为关于p1，p2，pn的主合取范式。,定

18、理任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的.求公式主范式的主要方法：方法一：真值表法方法二：等值添项法,方法一（真值表法）,定理：一个命题公式的真值表中，成真赋值对应的极小项的析取是该公式的主析取范式；成假赋值对应的极大项的合取是该公式的主合取范式。,真值表法求主析取范式的主要步骤：第1步：求公式的真值表；第2步:找出所有的成真赋值，并形成对应的极小项的编码；第3步:将极小项的编码转化成极小项，得到主析取范式。,真值表法求主合取范式的主要步骤：第1步：求公式的真值表；第2步:找出所有的成假赋值，并形成对应的极大项的编码；第3步:将极大项的编码转化成极大项，得到主合取范

19、式。P.16.例1.23,方法二（等值添项法）,求主析取范式的主要步骤：第1步：将命题公式化为析取范式；第2步：在每个不是极小项的简单合取式中用否定律增加缺少的文字；（注意按照一定顺序添加）第3步：用分配律展开得到新的析取范式；如果还存在简单合取式不是极小项时，重复第2步；第4步：删除重复的极小项，得到主析取范式。,求主合取范式的主要步骤：第1步：将命题公式化为合取范式；第2步：在每个不是极大项的简单析取式中用否定律增加缺少的文字；（注意按照一定顺序添加）第3步：用分配律展开得到新的合取范式；如果还存在简单析取式不是极大项时，重复第2步；第4步：删除重复的极大项，得到主合取范式。P.17.例1

20、.24,由真值表法很容易得到主范式的如下性质：主析取范式和主合取范式具有互补性（即它们的编码恰好构成全体赋值情况），知道主析取范式可以得到主合取范式，知道主合取范式也可以得到主析取范式。重言式的主析取范式是全体极小项的析取，其主合取范式规定为1；矛盾式的主合取范式是全体极大项的合取，其主析取范式规定为0。,如果两个不同形式的公式等值，则它们的真值表相同，因而它们有相同的主范式。这就是P.18.定理1.6主范式的应用实例P.19.例1.28(自己看）类似的问题有,例：某公司需要从A,B和C这3名骨干人员中派2名到国外考察，由于工作需要，选派时需要满足以下条件：若A去，则C同去；若B去，则C不能去

21、；若C不去，则A或B可以去。请问如何安排？,（1）A不去，B不去，C去；（2）A不去，B去，C不去。,如果只安排一个人参加，则有两种情况：,因此，符合条件的只有一种情况：A去，B不去，C去。,化为主析取范式为：,条件符号化为：,解：因为,其它赋值都是A的成真赋值：000，001，011，100，111。,所以A的成假赋值为（按照字母顺序）：,010，101，110；,1.6推理理论,推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是从前提出发应用推理规则推出的命题公式，前提可多个，由前提A1，A2，Ak推出结论B的严格定义如下：,设A1，A2，An，B是公式，如果(A1A2An)B

22、为永真式，则称从前提A1，A2，An推出结论B推理正确，也称B是的A1，A2，An的逻辑推论，记为：A1A2AnB,证明A1A2AnB的方法有：1、真值表法；2、等值演算法；3、主析取范式法。P.20.例1.29，例1.30但是，在前提和结论中，若命题变元的数目较大时，使用上述方法常会比较麻烦。此时可以采用推理的方法进行证明，这种方法需要一些等值定律和推理规则。,前提引入,证明：,（2）（4）假言三段论,（3）置换,（1）置换,前提引入,（5）置换（假言异位）,前提引入,（7）置换,（8）化简,（6）（9）假言三段论,（10）置换,所以，结论有效,注：课本中P.23-26例1.31(6),例1

23、.34(2),例1.36(2),(7),例1.38(2)实属多余，应删除,下列推理是否有效：如果今天是星期六，我们就要到西湖或大清谷去玩。如果西湖游人太多，我们就不到西湖去玩。今天是星期六。西湖游人太多。所以我们到大清谷玩。解：首先将命题符号化：p:今天是星期六。q:我们到西湖去玩。r:我们到大清谷去玩。s:西湖游人多。,前提：p(qr),sq,p,s结论：r证明：sq前提引入s前提引入q假言推理p前提引入p(qr)前提引入qr假言推理r析取三段论所以，结论有效,以上两个例子主要是直接证明的方法，下面讨论两种间接证明方法。（一）附加前提法（CP规则法）,欲证明(A1A2An)(AB)，只需证明

24、(A1A2AnA)B即可。,(A1A2An)(AB)(A1A2An)(AB)(A1A2An)(AB)(A1A2An)(AB)A1A2AnAB(A1A2AnA)B(A1A2AnA)B(A1A2AnA)B,例：用附加前提证明法证明下面推理前提：p(qr)，sp,q，结论：sr证明：sp前提引入s附加前提引入p析取三段论p(qr)前提引入qr假言推理q前提引入r假言推理,所以，结论有效。,例如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时小李也去。判断上述推理是否有效？,（二）归谬法（反证法）欲证明(A1A2An)B，只需将B作为前提能推出

25、矛盾来即可。因为：(A1A2An)B(A1A2An)B(A1A2AnB）若(A1A2AnB）为矛盾式，则(A1A2An)B为重言式，即(A1A2An)=B,例:构造下面的推理证明前提：pq,rq,rs结论：p证明：p结论否定引入pq前提引入q假言推理rq前提引入r析取三段论rs前提引入r化简rr合取,著名的苏格拉底三段论:所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的。,命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。为揭示命题内部结构及其不同命题的内部结构关系，就按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。,第2章一阶逻辑,2.1

26、一阶逻辑的基本概念.个体词和谓词在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。个体常元和个体变元：表示特定的个体，称为个体常元，以a，b，c或带下标的ai，bi，ci表示；表示不确定的个体，称为个体变元，以x，y，z或xi，yi，zi表示。,个体域：个体变项的取值范围全总个体域:宇宙间的一切事物组成个体域。谓词常项：表示具体的谓词谓词变项：表示不确定的谓词例:(1)ln5是无理数；(2)武松比武大郎高；(3)杭州位于北京和广州之间。这是三个简单命题,其中ln5、武松、武大郎、杭州、北京、广州等都是个体词,而“是无理数”,“比高”，“位于和之间”等都是谓词。

27、,例（1）中只需提供一个个体就可成为命题，这种谓词称为一元谓词，（2）中需提供两个个体才可成为命题，是二元谓词，（3）是三元谓词一般的，如果需要为一个谓词提供n个个体才能使其成为命题，则称该谓词为n元谓词。一元谓词:表示事物的性质多元谓词(n元谓词,n2):表示事物之间的关系，L(x,y)：x与y有关系L，如L(x,y)：xy，,0元谓词:不含个体变项的谓词谓词的表示：F(x)表示x具有性质F例：用谓词形式表示命题：小张是福州人解：设F(x)：x是福州人，a:小张，则原命题表示为F(a),在命题“杭州位于北京和广州之间”中，杭州、北京和广州是三个个体，而“位于和之间”是谓词，它刻划了杭州、北京

28、和广州之间的关系。设P（x,y,z)：x位于y和z之间，a：杭州，b：北京，c：广州，则P(a，b，c)：杭州位于北京和广州之间。注意：命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。如上述例子中，P(b,a,c)是假。,注意：n0时，n元谓词不是命题，例如：令S(x)：x是大学生。不是命题。只有其中的个体变元用个体常元替代时，才能成为一个命题。如个体常元a:小明，则S(a)是命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。,例如：令S(x)：x是大学生。若x的论域为福建师大福清分校的全体同学，则S(x)是真的；若x的论域是福州一中的全体学生，则S(

29、x)是假的；若x的论域是福清市街心公园的全体人员，则S(x)的真值是不确定的。,例将下列命题符号化：(1)张华和李明都是学生；(2)2既是偶数又是素数；(3)如果张三比李四高，并且李四比王五高，则张三比王五高。解(1)设个体域是人的集合。P(x)：:x是学生。a：张华b：李明该命题符号化为P(a)P(b),(2)设个体域为正整数集合ZP(x)：x是偶数，Q(x)：x是素数，a：2该命题符号化为P(a)Q(a)(3)设个体域是人的集合H(x,y)：x比y高，a：张三，b：李四，c：王五该命题符号化为H(a,b)H(b,c)H(a,c),例将下列命题符号化：（1）、张华的母亲爱张华。（2）、2与3

30、之和小于2与3之积。（3）、所有的人都要死的。（4）、有的人没上过大学。解：（1）、取人的集合为个体域设f(x)=x的母亲，P(x,y):x爱y,a：张华则命题符号化为P(f(a),a),(2)、取正整数的集合为个体域设f(x,y)=x+y,g(x,y)=xy,P(x,y):xy,a:2,b:3，则命题符号化为P(f(a,b),g(a,b)（3）、（4）涉及到数量关系，所以除个体词、谓词，还得有表示数量关系的词，否则无法准确刻画此类命题。,例如，S(x)：x是大学生，而x的个体域为某单位的职工，那么S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，需要

31、引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词，其定义如下：,量词:用来表示个体常项或变项之间数量关系的词量词分为两种：全称量词：“一切”、“所有”、“凡”、“每一个”、“任意”等意，符号记作。如：x表示个体域内所有的x。x称为全称量词，称x为指导变元。存在量词：“有一个”、“有的”、“存在”、“至少有一个”等，符号记作。如:y表示个体域内有的y。x称为存在量词，x称为指导变元,解（3）取个体域为人类集合令F(x):x要死的，则命题符号化为xF(x)(4)取个体域为人类集合设G（x):x上过大学，则命题符号化为xG(x)当个体域为全总个体域时：设F(x)、G(x)定义同上，M(

32、x):x是人则(3)x(M(x)F(x)(2)x(M(x)G(x),说明：（1）在不同的个体域，同一命题的符号化形式可能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相同也可能不同。（3）以后如不指定个体域，默认为全总个体域。（4）全称量词中，特性谓词常是条件式的前件，在存在量词中，特性谓词常是合取式的一项。,例将下列命题符号化1、在北京工作的人未必都是北京人（P.34例2.4(5)2、兔子比乌龟跑得快（P.35例2.5(1)3、不存在同样高的两个人（P.35例2.5(3)4、存在最小的自然数（P.35例2.5(4)解：1、取个体域为人的集合（可以不要）设B（x)：x是北京人，W(x

33、):x在北京工作则命题符号化为x(W(x)B(x)或x(B(x)W(x),2、设F(x):x是兔子，G(x):x是乌龟，H（x,y):x比y跑得快则命题符号化为x(F(x)y(G(y)H（x,y)或xy(F(x)G(y)H（x,y)3、设R(x):x是人，E(x,y):x=y,H(x,y):x和y同样高则命题符号化为xy(R(x)R(y)E(x,y)H(x,y)或xy(R(x)R(y)E(x,y)H(x,y),4、设N(x):x是自然数，G(x,y):xy,(与书中不同）则命题符号化为x(N(x)y(N(y)G(x,y),一阶语言及其解释,1、一阶语言的符号2、项、一阶公式的定义（P.36)3

34、、量词的辖域、自由变元、约束变元在公式xA和xA中，称x为指导变元，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现，这个变元成为约束变元；A中不是约束出现的其它变项均称为是自由出现，这个变元成为自由变元例x(P(x)Q(x)yG(x,y)xP(x)Q(x)yG(x,y),（2）个体常元,4、封闭公式（闭式）,5、公式的解释,公式的解释通常由以下四个部分构成,（1）个体域,（3）特定的运算符,（4）特定的谓词,P.38例2.8(自己看）,例给定公式A=xyP(f(x,a),y)yG(y)及其解释I：个体域为自然数集；二元算法f(x,y)=x+y；个体常元a=1；谓词P(x,y):x=y,G(x):x是奇数求公式A在I下的意义和真值.解：A在I下的意义是：如果对每个自然数x,都存在自然数y,使得x+1=y,那么，每一个自然数都是奇数。这是假命题，故A的真值为0.,如果公式改为B=xyP(f(x,a),y)G(x),解释I同上，这不是闭式，所以不是命题，要确定B的值，还得有一个对x的赋值,如v(x)=1（或其它值）,6、有限个体域的量词消去公式若解释I的个体域是有限集合D=e1,e2,en则在I中，公式xA(x)的意义为A(e1)A(e2)A(en)公