离散数学复习资料.doc

《离散数学复习资料.doc》由会员分享，可在线阅读，更多相关《离散数学复习资料.doc（239页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date离散数学复习资料第1章 命题逻辑 第1章 命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2. 六个联结词及真值表h“”否定联结词，P是命题，P是P的否命题，是由联结词

2、 和命题P组成的复合命题.P取真值1，P取真值0，P取真值0，P取真值1. 它是一元联结词.h “”合取联结词，PQ是命题P，Q的合取式，是“”和P，Q组成的复合命题. “”在语句中相当于“不但而且”，“既又”. PQ取值1，当且仅当P，Q均取1；PQ取值为0，只有P，Q之一取0.h “”析取联结词，“”不可兼析取(异或)联结词， PQ是命题P，Q的析取式，是“”和P，Q组成的复合命题. PQ是联结词“”和P，Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“PQ”“(PQ)(PQ)”. PQ取值1，只要P，Q之一取值1，PQ取

3、值0，只有P，Q都取值0. h “”蕴含联结词， PQ是“”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，PQ取值为0；其余各种情况，均有PQ的真值为1，亦即10的真值为0，01，11，00的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“PQ”.h “” 等价联结词，PQ是P，Q的等价式，是“”和P，Q组成的复合命题. “”在语句中相当于“当且仅当”，PQ取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别 h命题公式与赋值，命题P含有n个命题变项P1，P2,Pn，给P1，P2,Pn各指定一个真值，称为对P的一个赋值(真值指派). 若指定的

4、一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派. h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若

5、该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式AB，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。定理1 设F(A)是含命题公式A的命题，F(B)是用命题公式B置换F(A)中的A之后得到的命题公式. 如果AB，则F(A)F(B). 4. 范式h 析取(合取)范式，仅有有限个简单合取式(析取式)构成

6、的析取式(合取式)，就是析取(合取)范式. h 极小项(极大项)，n个命题变项P1,P2,Pn，每个变项或它的否定两者只有其一出现且仅出现一次，第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项). 以两个命题变项为例，m00=PQ，m01=PQ,m10=PQ,m11=PQ是极小项;M00=PQ，M01=PQ,M10=PQ,M11=PQ是极大项.h 主析取范式(主合取范式) 含有n个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。每项含有

7、n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律. 求析取(合取)范式的步骤： 将公式中的联结词都化成，(即消去个数中的联结词，)； 将否定联结词消去或移到各命题变项之前； 利用分配律、结合律等，将公式化为析取(合取)范式. 求命题公式A的主析取(合取)范式的步骤 求公式A的析取(合取)范式； “消去”析取(合取)范式中

8、所有永假式(永真式)的析取项(合取项)，如PP(PP)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如PP(PP)用P替代，mimi(MiMi)用mi(Mi)替代. 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或Pi，则添加PiPi(PiPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全； 将极小(极大)项按由小到大的顺序排列，用S(P)表示. 5. 命题演算的推理理论h设A1,A2,An,C是命题公式，如果是重言式，称C是前提集合 A1,A2,An的有效结论或A1,A2,An逻辑地推出C。记作掌握演绎或形式证明. 要理

9、解并掌握14个重言蕴含式(即I1I14)，17个等值式(E1E17)；二是会使用三个规则(P规则、T规则和CP规则)。推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)二、实例例1.1 判别下列语句是否命题？如果是命题，指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数.(3) 这座楼可真高啊！ (4) 请你跟我走!(5)火星上也有人. 解 (1) 是命题，真值为1. (2) 是命题，真值为0. (3), (4)不是命题因为不是陈述句.(5) 是命题. 真值是唯一的，迟早会被指出. 例1.2 将下列命题符号化：(1) 虽然

10、交通堵塞，但是老王还是准时到达火车站； (2) 张力是三好生，他是北京人或是天津人.(3) 除非天下雨，否则我骑车上班.解 (1) 设P：交通堵塞，Q：老王准时到达火车站. 该命题符号化为：PQ. (2)设P：张力是三好生； Q：张力是北京人，R：张力是天津人.该命题符号化为P(QR ). (3)设P：天下雨，Q：我不骑车上班.该命题符号化为：QP，义即“只有天下雨，我才不骑车上班”，不下雨是我骑车上班的必要条件。它的等价说法是“如果天不下雨，我就骑车上班”，即PQ“如果天下雨，我就不骑车上班”，这是蕴含关系，符号化为：PQ注：本例各小题都是复合命题。如“李枚和张樱花是好朋友”是简单命题，用字

11、母P表示。显然P：李枚是好朋友，Q：张樱花是好朋友，符号化为QP是不通的.例1.3 证明：P(QR)PQR.证明 方法1 真值表法. 列公式P(QR)与PQR的真值表如表11. . 表11 公式P(QR)与PQR的真值表 PQRQRP(QR)PQPQRP(QR)PQR0001101100111011010010110111101110011011101110111100010111111111由表可知，公式P(QR)与PQR的真值完全相同，故P(QR)PQR. 或由表的最后一列可知，PQPQ是重言式，故P(QR)PQR.注：作为本例的证明可以不要最后1列。若本例改为判断P(QR)PQR的类型，

12、由最后列可知P(QR)PQR是重言式.方法2 等值演算法.P（QR）P(QR) (等值蕴含式)P(QR) (等值蕴含式)（PQ）R (结合律)(PQ)R (摩根律)PQR (等值蕴含式)所以，P（QR）(PQ)R例中等值演算的每一步都用到了置换规则. 由等值演算的传递性，可知第一个公式P(QR)和最后一个公式PQ)R等值. 方法3 主范式法.P(QR)P(QR)PQR(主合取范式)PQR(PQ)RPQR(主合取范式)P(QR)与PQR的主合取范式相同，故P(QR)PQR。注：(1)容易写出P(QR)与PQR的主析取范式均为m0m1m2m3m4m5m7即 (PQR)(PQR)(PQR) (PQR

13、)(PQR)(PQR) (PQR)(2) 由真值表求公式P(QR)的主析取范式，先列出P(QR)的真值表，见表11。主析取范式是公式P(QR)真值为1的项的析取，真值为1的项，即极小项，有第1,2,3,4,5,6,8共7项. 而极小项是合取式，合取式为1，必定是每个变元或其否定为1，如表11中第1行P，Q，R均取1，所以这一项为PQR，类似地，7个极小项为：PQR，PQR，PQR，PQR，PQR，PQR，PQR所以P(QR)的主析取范式为： (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (PQR)例1.4 用等值演算法判定公式P(QR)PQR是永真式？永假式？可满足式？解 等

14、值运算法. P(QR)PQR(P(QR)PQR (P(QR)P(QR)PQR (P(QR)(PQR)PQR (P(QR)(PQR)PQR (P(QR)(PQR)PQR (P(QR) PQR)(PQR)PQR) (对的分配律) (PP)QR(QR)1 111因此，P(QR)PQR是永真式. 注：也可以用真值表法或主范式法. 例1.5 化简下式： (ABC)(ABC)解(ABC)(ABC) 例1.6 求公式的主合取范式和主析取范式. 解 先将公式化为合取范式. (去掉) (去掉) (合取范式) (添齐命题变项) 所求主析取范式为主合取范式的缺项所对应的三个极小项，即为 m1m6m7或通过求析取范式

15、求主析取范式. (去掉) (去掉) (合取范式) 注：也可以用列真值表的方法，求主析取或主合取范式，见例1.3的注.试用P，Q和联结词，构造命题公式A，使得A与F等值. 解 取真值表中F为1的成真赋值01,10的析取,即为 例1.7 已知P，Q，F的真值表如下表.PQF000011101110即命题公式与F等值.例1.8 试证明：方法1 欲证明，只需证明是重言式，即其真值是1.证明 所以，推理正确。方法2 构造推理附加前提证明法(1) S CP规则(2) SP P(3) P (1),(2)析取三段论(4) P(QR) P(5)QR (3),(4)假言推理(6)Q P (7)R (5),(6)假

16、言推理例1.9 填空题 1. 1. 设命题公式GP(QR)，则使G的真值为1的指派是 ， ， . 答案：(1,0,0,),(1,0,1),(1,1,1)解答PQRQGP(QR)由真值表知：P，Q，R的真值指派为 (1,0,0,),(1,0,1),(1,1,1)则公式G的真值为1. 应填写(1,0,0,),(1,0,1),(1,1,1)0001 00011 00100 00110 01001 11011 11100 01110 12. 已知命题公式为G(PQ)R,则命题公式G的析取范式是 答案：(PQ)R解答 (PQ)R(PQ)R(PQ)R故应填写(PQ)R.注：一个命题公式的析取范式一般不唯一

17、。如(PQ)(PR)(PR)也是该公式的一个析取范式.例1.10 单项选择题 1. 设命题公式(P(QP)，记作G，使G的真值指派为0的P，Q的真值是( )(A) (0,0) (B) (0,1) (C) (1,0) (D) (1,1)答案：(C)解答 P(QP)P(QP)(PQ)(PP)PQ 当P，Q取值(1，0)时， PQ取真值为0. 故选择(C). 2. 与命题公式P（QR）等值的公式是( ) (A) (PQ)R (B)(PQ)R (C) (PQ)R (D) P(QR)答案：(B)解答 P（QR）P(QR)PQR(PQ)R(PQ)R故应选择(B)3. 命题公式(PQ）P是( )(A) 永真

18、式 (B) 永假式 (C) 可满足式 (D) 合取范式答案：(A)解答 (PQ）P所以是永真式. 故选择(A). 4. 设命题公式，则公式G与H满足( ) 答案：(D)解答 ，即为重言式. 或列真值表. PQPQG(PQ)HP(QP)GH0011 0 1 10110 0 1 11001 1 1 11100 0 0 1可见，GH，故应选择(D). 三、练习题1. 判定下列语句是否为命题，若是命题，指出是简单命题或复合命题. (1) 是无理数. (2) 5能被2整除.(3) 现在开会吗？ (4) 2是素数当且仅当三角形有3条边.(5) 如果雪是黑的，则太阳从东方升起.2. 将第1题的命题符号化，并

19、讨论其真值. 3. 设命题P,Q的真值为0，命题R,S的真值为1，求命题公式的真值. 4. 用多种方法判定命题公式的类型. 5. 用多种方法证明等值式成立. 6. 已知命题P，Q和真值函数F的真值，(P,Q,F)(,00,0),(0,1,0),(1,0,1),(1,1,0). 试用P，Q和联结词，构造命题公式C，使得FC. 7. 求命题公式的主析取范式和主合取范式. 8. 试证明：四、练习题答案1. (1) , (2)是简单命题，(3) 不是命题，(4)，(5)是复合命题. 2. (1) P:是无理数,P是真命题，真值为1.(2)P： 5能被2整除，P是假命题，真值为0(4)P：2是素数，Q：

20、三角形有3条边，原命题符号化为PQ.，真值为1 (5) P：雪是黑的，Q：太阳从东方升起，原命题符号化为PQ，其真值为1. 3. 真值为0. 4. 原式等值于，是非永真的可满足式。5. 提示：用分配律、否定律、同一律. 6. 7 主析取范式： 主合取范式：8. 前提： 结论： 证明 方法1，直接证明法 (1) QR P (2) R P (3) Q (1), (2)析取三段论 (4) (PQ P (5) PQ (4) 置换 (6) PQ (5)置换 (7) P (3),(6) 拒取式方法2，间接证明法(1) (P) 结论否定引入(2) P (1)置换(3) (PQ) P(4) PQ (3) 置换

21、(5) Q (2),(4)假言推理(6) QR P(7) R (5),(6)析取三段论(8) R P(9) RR (7),(8) 合取引入有(9)可知，构造推理是正确的. 第2章 谓词逻辑 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明. 一、重点内容1. 谓词与量词h谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a,b,c,表示)和个体变项(用x,y,z,表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,

22、表示. 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题. h量词，是在命题中表示数量的词，量词有两类：全称量词，表示“所有的”或“每一个”；存在量词$，表示“存在某个”或“至少有一个”. 在谓词逻辑中，使用量词应注意以下几点：(1) (1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变. (2) (2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域. (3) (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就

23、是使公式中的每一个变项都有个体域中的元素相对应. 在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地，使用全称量词，特性谓词后用；使用存在量词$，特性谓词后用.2. 公式与解释h谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式. 例如x(F(x)G(x)，$x(F(x)G(x)，xy(F(x)F(y)L(x,y)H(x,y)等都是谓词公式. h变元与辖域，在谓词公式xA和$xA中，x是指导变元，A是相应量词的辖域. 在x和$x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元. 也就是

24、说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效. h换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变. h代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号. h解释(赋值)，谓词公式A的个体域D是非空集合，则(1) 每一个常项指定D中一个元素；(2) 每一个n元函数指定Dn到D的一个函数；(3) 每一个n元谓词指定Dn到0,1的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值.在有限个体域下，消除量词的规则为：如Da1,a2,an，则h谓词公

25、式分类，在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；在任何解释下谓词公式A取真值0，公式A为永假式；至少有一个解释使公式A取真值1，公式A称为可满足式.3. 前束范式 一个谓词公式的前束范式仍是谓词公式. 若谓词公式F等值地转化成 那么就是F的前束范式，其中Q1，Q2，Qk只能是或$，x1,x2,xk是个体变元，B是不含量词的谓词公式. 每个谓词公式F都可以变换成与它等值的前束范式. 其步骤如下： 消去联结词，； 将联结词移至原子谓词公式之前； 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；将x,$x移至整个公式最左边； 得到公式的前束范

26、式. 4.谓词逻辑的推理理论谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行. 二、实例例2.1 将下列命题符号化：(1) 有某些实数是有理数；(2) 所有的人都呼吸； (3)每个母亲都爱自己的孩子.注意：一般地，全称量词“”后，跟蕴含联结词“”；存在

27、量词“$”后，跟合取联结词“”.解 (1) 设R(x)：x是实数，Q(x)：x是有理数。该命题符号化$x(R(x)Q(x). (2) 设全总个体域，设M(x)：x是人.，H(x)：x要呼吸，该命题符号化为：x(M(x)H(x)该命题等价说法：“不存在不需要呼吸的人”，符号化为：$x(M(x)H(x).其实它们是等值的，x(M(x)H(x) x(M(x)H(x)( x(M(x)H(x)$x(M(x)H(x)若个体域D为人的集合。H(x)：x要呼吸. 则该命题符号化为xH(x). (3) 在全总个体域，设M(x):x是母亲，L(x,y):x爱y，A(y):y是孩子, H(x,y):x属于y命题符号

28、化为： 或若个体域D是所有母亲的集合. M(x)：x爱自己的孩子，该命题符号化为xM(x).例 2.2 指出公式 中量词的每次出现辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元. 解 在公式中，x只有一次出现，辖域是；y只有一次出现，辖域是；$x只有一次出现，辖域是H(x,y). 变元x在该公式中有四次出现，其中第1次、第2次出现是在x及其辖域中，故是约束出现；第3次，第4次出现是在$x及其辖域中，也是约束出现。这四次出现都是约束出现，所以x是该公式的约束变元. 变元y在该公式中也有四次出现. 其中第1次是在y中，第2次和第3次出现是在y的辖域中，是约束出现，

29、第4次出现是自由出现，故y在该公式中有3次约束出现，1次自由出现，因此变元y既是该公式的约束变元，也是自由变元. 变元z在该公式中只有一次自由出现，所以z是该公式的自由变元. 注意，由例2.2看到，同一个个体变项，在同一个公式中，既可以是约束出现，也可以是自由出现，这种情况有时会造成一些混淆，带来不便. 要改变这种情况，使一个个体变项在同一个公式中，不同时既是约束出现，又是自由出现，采取换名规则或代入规则. 在求前束范式时，尤其需要.例2.3 给定解释I如下： D2,3; D中特定元素a=2； 函数为； 谓词F(x)为F(2)=0,F(3)=1，G(x,y)为G(2,2)=G(2,3)=G(3

30、,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解释I下各公式的真值. (1) ; (2) ；(3) .解 (3) 这是给定解释下，求谓词公式的真值，个体域有限，比较好求。只需将量词消去，函数值代入谓词，根据谓词的真值，即可求出谓词公式的真值.要判断一个谓词公式的真、假是较为难的. 在谓词逻辑中，在任何解释下都真的公式，才是永真式；在任何解释下公式A为假，才是永假式；公式A不总是假，或者至少有一个解释使得公式A为真，才是可满足式. 困难之点是在全总个体域中所有的解释如何说清楚.因此只能要求会作简单问题.例2.4 讨论公式的类型. 解

31、用A表示该公式.对任意解释I，A的前件为假，无论后件真假，公式A为真. 这说明A不是永假式；取解释I如下：个体域为整数集，F(x,y)：x y，在I下，x$yF(x,y)，即在整数中，任给整数x，存在y使得xy，显然为真，即A的前件为真. 但后件$yxF(x,y)，即存在y对任给x使得xy，显然这是不成立的，亦即后件为假. 由蕴含联结词的真值表10的真值为0，故A为假。这说明A不是永真式.综上所述，A是可满足式.由例2.4可知，量词的次序不能随便颠倒.例2.5 将公式化为前束范式. 解 消去联结词(若有，也要消去). 将联结词移至原子公式之前. 换名.(自由变元的y未改) 把量词提到整个公式的

32、前面.为所求前束范式. 写在一起，所求前束范式是 (自由变元的y未改) 注：重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为量词在最前面，后面不含量词的公式，即前束范式. 虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的. 例2.6 构造推理证明前提：$xF(x), x(F(x)G(x)H(x) 结论：$x(F(x)H(x) 证明： $xF(x) 前提引入 F(c) ES x(F(x)G(x)H(x) 前提引入 F(c)G(c)H(c) US G(c)H(c) ,假言推理 H(c)G(c) 置换 H(c) 化简

33、F(c)H(c) ,合取 $x(F(x)H(x) EG例2.7 单项选择题1. 谓词公式中量词x的辖域是( )(A) (B) P(x) (C) (D) 答案：(C)解答：x后面的公式是. 故应选择(C). 2. 谓词公式xA(x)xA(x)的类型是（ ）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 不属于(A),(B),(C)任何类型答案：(B)解答：对于任意解释I，xA(x)xA(x)0所以xA(x)xA(x)是永假式. 选择(B).3 设个体域为整数集，下列公式中其真值为1的是( )(A) (B) (C) (D) 答案：(A)解答：任意一个整数x，都能找到yx，使x+y

34、=0, 故(A)式是永真式. 4 设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )(A) (B) (C) (D) 答案：(B)解答：将命题符号化为，故应选择(B). 5 在谓词演算中，P(a)是的有效结论，根据是 ( ) (A)US规则 (B) UG规则 (C)ES规则 (D)EG规则答案：(A) 解答：全称量词消去规则的定义为,即A(c)是的有效结论. 应选择(A). 例2.8 填空题 1.公式的自由变元是 , 约束变元是 . 答案：y,x ; x,z解答：x的辖域是故x是约束出现，y是自由出现，的辖域是，故z是约束出现，y

35、是自由出现，而S(x)中的x是自由出现. 总之y,x是自由变元，x,z是约束变元. 2. 谓词逻辑公式的前束范式是 . 答案：解答：求前束范式 3. 设个体域Da,b,消去公式中的量词，则 答案：解答：由x和$x真值的定义，4. 换名规则施于 变元，代入规则施于 变元答案：约束；自由. 解答：见换名规则和代入规则的定义. 三、练习题1. 将下列命题符号化：(1) 丘华和李兵都是学生； (2) 存在偶素数；2. 指出谓词公式中量词的辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元. 3. 设个体域D岳飞，文天祥，秦荟，谓词F(x)：x是民族英雄。求xF(x)的真值

36、。4. 设P是二元谓词，给定解释I如下：Da,b,P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0求下列公式的真值：(1) ； (2) ; (3) 5.讨论公式的类型. 6. 用归谬法，构造下面的推理证明.四、练习题答案 1. (1) 设P(x)：:x是学生。. a：丘华，b：黎兵该命题符号化为：P(a)P(b)(2) 设N(x):x是自然数，F(x)：x是偶数，Q(x)：x是素数该命题符号化为$x(N(x)F(x)Q(x)2. 在公式中,x有二次出现，第一次出现的辖域是中; 第二次出现的辖域是. 变元x在该公式中有六次出现，其中第1，4次出现和第2，3，5次出现均是约束出现；第

37、6次是自由出现. 变元x在该公式中5次约束出现，1次自由出现. 因此变元x既是该公式的约束变元，也是自由变元. 3. 设a,b,c分别为岳飞，文天祥和秦桧，xF(x)F(a)F(b)F(c)04.(1)0；(2)x$y(P(y,x)$yP(y,a)$yP(y,b)(P(a,a)P(b,a)(P(a,b) P(b,b)100(3) $x$y(P(x,y)$yP(a,y)$xP(b,y)=P(a,a)P(a,b)P(b,a)P(b.b)15. 设I为任意一个解释，D为个体域. 为假，则xF(x)$xF(x)为真. xF(x)为真，即x, F(x)为真, 显然$x0D, F(x0)为真，即$xF(x)为真 则xF(x)$xF(x)为真. 故在任何解释I下xF(x)$xF(x)为真. xF(x)$xF(x)是永真式. 6. 前提： 结论： 证明：(1) 否定结论引入 (2) T(1)E (3) (2)ES (4) A(c)B(c) T(3) E (5) A(c) (4)化简 (6) B(c)A(c) T(4) .E (7) B(c) (6)化简 (8) P (9) x(A(x)B(x) (8