给力离散小组倾血编制

1、第一章 命题逻辑1-1 命题及其表示法定义1：命题是一个具有确定真值的陈述语句。l 注：真值表示真假的性质，其可能的取值只有“真”和“假”，通常用T或1表示真，F或0表示假。l 例：5是一个整数。 3是偶数。 x+y=4。 你吃过饭了吗? 我正在说谎。 l 命题有两种形式：原子命题和复合命题。定义2：原子命题是不能再分解为更简单命题的命题。l 例：苏格拉底是哲学家。 如果天气好，那么我去散步。l 注：1 原子命题的界定不宜绝对化； 2 原子命题常用大写字母A，B，P，Q，或带下标的大写字母如P1来表示。定义3：由原子命题、联结词或标点符号的复合构成的命题称复合命题。l 例： 昨天下雨，今天也在

2、下雨。定义4：表示命题的符号称为命题标识符。l 例：P:北京是中国的首都。定义5：一个命题标识符如果表示确定的命题，称为命题常元；如果命题标识符可以表示某 类命题中的任何一个，称为命题变元。l 思考：命题变元是命题吗？定义6：将一个命题变元P用一特定命题或真值去代替，它就有确定的真值，这称对P的指派，或解释，记为S(P)或I(P)。l 显然，指派或解释是针对命题变元进行的。命题的联结词定义1：设P为一命题，P的否定是一个新的命题，记为P。若P为T， P为F；若P为T，P为F。l 例：P：上海不是一个大城市。 P：？定义2：两个命题P和Q的合取是一个复合命题，记作PQ。当且仅当P、Q同时为T时，

3、PQ为T，其他情况下PQ均为F。l 例：P：地球是球形的。 Q: 牛顿是物理学家。 PQ: 地球是球形的并且牛顿是物理学家。又如：P：拿破仑是科西嘉人。 Q: 拿破仑不是科西嘉人。 ( P) PQ:拿破仑是科西嘉人并且拿破仑不是科西嘉人。注：l 1.是汉语中“与”、“和”、“并”的翻译，但不能绝对化。l 2.合取在一起的两个命题不一定有实质的联系，也不一定是一致的，甚至可以将互为否定的命题合取在一起(该注释对其他逻辑联结词也适用)。定义3：两个命题P和Q的析取是一个复合命题，记作PQ。当且仅当P、Q同时为F时，PQ的真值为F；否则PQ的真值为T。l 例： P：机器有故障。 Q：开关有故障。 P

4、Q：机器有故障或开关有故障。l 注：是汉语中“或” 的翻译，但不能绝对化。特别应注意区分“可兼或”和“排斥或”。l 例：1.今晚我在家看电视或去同学家玩。 2.他可能是100米或400米赛跑的冠军。 3.他昨晚做了二十或三十道习题。 其中，例1中的“或”为“排斥或”，例2中的“或”为“可兼或”，而例3中的“或”，不是联结词，只表示习题的近似数，因此3不是一个复合命题，而是一个原子命题。（排斥或与可兼或的命题符号表达形式见后文）定义4：给定两个命题P和Q，其条件是一个复合命题，记作PQ，读作“如果P，那么Q” 或“P条件Q”。当且仅当P的真值为T，Q的真值为F时，PQ的真值为F;否则PQ的真值为

5、T。称P为前项，Q为后项。l 例：P： 月亮下山。 Q： 3+3=6。 PQ： 如果月亮下山,则3+3=6。注：1.虽然上例的P、Q之间并无实际联系，但只要P、Q可分别确定真值，即可用“”联结。 2.QP称为PQ的逆命题； PQ称为PQ的否命题； QP称为PQ的逆否命题。 3.前项P为F时，无论后项Q取何真值,PQ的真值均为T，这是所谓的“善意推定”。定义5：给定两个命题P和Q，复合命题PQ称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，PQ的真值为T，否则PQ的真值为F。l 注：双条件的其他表示法。l 例： P： 1+1=3。 Q： 雪是白的。 PQ： 1+1=3当且仅当雪是白的

6、。1-3 命题公式与翻译定义1：命题常元、命题变元统称为原子命题公式，简称原子公式。定义2： 合式公式是由下列规则形成的字符串： 1)真值T和F是合式公式。 2)原子命题公式是一个合式公式。 3)如果A是合式公式，那么A是合式公式。 4)如果A和B是合式公式，那么(AB)、(AB)、 (AB)和(AB)都是合式公式。 5)经过有限次地应用2)、3)和4)所得到的包含命题变元，联结词和括号的符号串是合式公式。l 例：指出(P(PQ)中的哪些部分是命题公式，如果是，则具体说明它是如何生成的 解： P 由规则2) Q 由规则2) (PQ) 由规则4)和 (P(PQ) 由规则4)和l 当合式公式中的原

7、子命题公式是命题变元时，合式公式是没有真假值的，仅当其中的命题变元用确定的命题代入时，才能得到一个命题。这时，这个命题的真值，依赖于代换命题变元的那个命题的真值。运算次序优先级：， 相同的运算符按从左至右次序计算，否则要加上括号，最外层圆括号可省去 翻译l 把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，或反之，均称为翻译。自然语句符号化的过程主要包括两个步骤:l (1)分析出各简单命题, 将它们符号化;l (2)根据自然语句中的逻辑关系,使用恰当的命题联结词, 把简单命题逐个联结起来, 构成复合命题的符号化表示。l 如何将语句形式化, 以及如何理解形式化了的语句。

8、语句形式化要注意:1.要善于确定简单命题, 不要把一个概念硬拆成几个概念。例 “我和他是同学”是一个简单命题。2.要善于识别自然语言中的联结词(有时它们被省略)。例 狗急跳墙。解：应理解为: P: 狗急了, Q: 狗才跳墙上述语句形式化成P®Q。3.否定词的位置要放准确。例 如果你和他不都是傻子, 那么你们俩都不会去自讨没趣。解：设 A: 你是傻子, B: 他是傻子, C: 你会去自讨没趣, D: 他会去自讨没趣。上述语句形式化为: (AB) ® (CD)。例：符号化下列命题。1.张明正在睡觉或游泳。解：令P:张明在睡觉，Q:张明在游泳，则此命题符号化为：(PQ)(QP)。

9、2.他可能是100米或400米赛跑的冠军。解：令P: 他可能是100米赛跑的冠军，Q: 他可能是100米赛跑的冠军 ，则此命题符号化为：PQ。3.除非你努力，否则你将失败。解：这个命题的实际含义是，你没有失败必定是你努力，令P:你失败，Q:你努力，则此命题符号化为PQ。4.除非天气好，我才骑自行车上班。解：这个命题的实际含义是，我骑自行车上班必定是天气好，令P:我骑自行车上班，Q:天气好，则此命题符号化为PQ。5.只有睡觉才能恢复疲劳。解：这个命题的实际含义是，能恢复疲劳必定是睡觉了，令P:恢复疲劳，Q:睡觉，则此命题符号化为PQ。6.只要我还有口气，我就要战斗。解：令P:我还有口气，Q:我要

10、战斗，则此命题符号化为PQ。1-4真值表与等价公式定义1：在合式公式中，根据对每个命题变元指派真值的各种可能组合，求解合式公式的对应真值，汇列成表，称为真值表。l 定义2：对于命题公式A中每个命题变元Pi，任给一个指派S(Pi)或解释I(Pi)，得到一种真值的组合S(P1) S(P2)S(Pn)或I(P1) I(P2)I(Pn) 称为A的一个真值指派，或称为A的一种解释，记为S(A)或I(A)。若S(A)或I(A)为T，称S(A)或I(A)为A的成真指派或说A的解释为真。类似地定义A的成假指派。 例：构造P(PQ)的真值表 解：PQP(PQ)00 1 1 101 1 1 110 0 1 011

11、 0 1 1步骤 一般说来，n个命题变元组成的命题公式共有2n种真值指派。定义3：一个命题公式如果对于其分量指派真值的各种可能组合，其真值恒为真(假)，称该命题公式是永真(假)式，记为T(F)。若至少有一个组合,其真值为真,则称该命题公式是可满足式。 例：PP PP PQ 例：前面的二个真值表的例子都是永真式.注：重言式一定是可满足式。l 永真式也称重言式；永假式也称矛盾式。 关于重言式，有如下性质：定理1：任何两个重言式的合取或析取，仍然是重言式。 证明：设A、B为两个重言式，则AB和AB的真值分别等于TT和TT。定理2：对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重

12、言式。（即代入规则） 证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变。定理3：设A、B是两个命题公式，AÛB当且仅当AB是一个重言式。（前面已证） 证明：若AÛB，则对于A、B所包含的分量的任意指派，A、B均取相同的真值，即AB是一个重言式；若AB是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即AÛB定义4：给定两个命题公式A和B，如果A和B在其任意指派（或解释）下，其真值都是相同的，即A(P1，P2.Pn)，B(P1，P2.Pn)若对于P1，Pn任一组真值指派，A，B真值相同，则称A和B是等价的，或

13、逻辑相等，记为AÛB。读作A等价B，称AÛB为等价式。与Û的区别与联系l 区别: 是逻辑联结词,它出现在命题公式中;Û不是逻辑联结词,它表示两个命题公式之间的一种充分必要关系,它不属于两个公式中的任何一个中的符号。l 联系: 定理: AÛB当且仅当AB是永真式. 证明：（略） 所以又称AÛB是永真双条件式.等价式的性质:l 自反性:对任意公式A,有AÛAl 对称性:对任意公式A,B,若AÛB,则BÛAl 传递性:对任意公式A,B,C,若AÛB, BÛC,则AÛC基本等价式命题

14、定律 双否律: P Û P 幂等律： PPÛP, PPÛP 结合律： (PQ)RÛP(QR) (PQ)RÛP(Q R) 交换律： PQÛ QP， PQÛQP 分配律： P(QR)Û(PQ)(PR), P(QR)Û(PQ)(PR) 吸收律： P(PQ)ÛP, P(PQ)ÛP 德摩根律： (PQ)ÛPQ (PQ)ÛPQ 同一律： PFÛP， PTÛP 零律： PTÛT， PFÛF 互补律： P PÛT(排中律)， P P

15、ÛF(矛盾律) 条件式转化律： PQ Û PQ, PQ Û QP 双条件式转化律： PQÛ(PQ)(QP)Û(PQ)(QP),PQ Û (PQ) 输出律： (PQ)RÛP(QR) 归谬律： (PQ)(PQ) Û P定义5：如果X是命题公式A的一部分，且X也是命题公式，则称X是A的子公式。定理1：设A1是命题公式A的子公式，若A1ÛB1，则若将A中的A1用B1来替换，得到公式B ，则B与A等价，即AÛB.(替换规则)。 证明： 因为对变元的任一组指派， A1与B1真值相同，故以B1取代A1后，公式

16、B与公式A相对于变元的任一指派的真值也必相同，所以AÛB。定义：称满足定理1的替换为等价替换。定理2： 在一个永真式A中,任何一个原子命题变元R出现的每一处,用另一个公式代入,所得公式B仍是永真式.(代入规则)。证明:因为永真式对任意解释,其值都是真,与所给的某个命题变元指派的真值是真还是假无关,因此,用一个命题公式代入到原子命题变元R出现的每一处后,所得命题公式的真值仍为真.代入与替换的区别:l 代入是对原子命题变元而言的，而替换通常是可对命题公式实行之。l 代入必须是处处代入，替换则可部分替换，也可全部替换。l 代入是对一个永真式进行的，替换则是对一般公式进行的。1-5 蕴涵式定

17、义1：当且仅当PQ是一个重言式时，称“P重言蕴涵Q”，在不会引起歧义的情况下，简称为“蕴涵”，记作PÞQ。l 注：重言蕴涵“Þ”与条件（也叫实质蕴涵）“”的区别类似于Û 与的区别定理4：设P、Q为任意两个命题公式，PÛQ的充分必要条件是PÞQ且QÞP。证明：若PÛQ，则PQ为重言式，即PQ和QP是重言式；若有PÞQ且QÞP，则PQ和QP是重言式，即PQ为重言式l 蕴涵的性质：设A、B、C和D为命题公式，则 1.若A是重言式，且有AÞB，则B是重言式 2.若有AÞB、BÞC，则

18、有AÞC，即蕴涵关系是传递的 3.若有AÞB、AÞC，则有AÞ(BC) 4.如有AÞC、BÞC，则有ABÞC1-6其他联结词定义1：设P和Q是两个命题公式， P和Q的合取非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为T时，PQ为F ，其他情况下PQ的真值都是T 。“合取非”通常也称“与非”。l 根据此定义，可知 PQ Û (PQ)l 的性质： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定义2：设P和Q是两个命题公式， P和Q的

19、析取非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为F时，PQ为T ，其他情况下PQ的真值都是F 。“析取非”通常也称“或非”。l 根据此定义，可知 PQ Û (PQ)l 的性质： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定义3：设P和Q是两个命题公式， P和Q的条件非是一个新命题公式，记作PQ。当且仅当P为T而Q为F时，PQ为T，其他情况下PQ的真值都是F。也用符号'表示。l 根据此定义，可知 PQ Û (PQ)定义4：设P和Q是两个命题公式， P和Q的双条件非是一个新命题公

20、式，记作PDQ。当且仅当P和Q的真值不同时，PDQ为T，其他情况下PDQ的真值都是F。“双条件非”也常称为“异或”。也常用 Å , D'表示l 根据此定义，可知 PDQ Û (PDQ)联结词定义3：可以表示所有可能的真值函数(即联结词)的联结词集合G，如果G满足下列两个条件：1. 由G中联结词构成的公式能等价表示任意命题公式2. G中的任一联结词不能用其余下联结词等价表示则称G为联结词功能完全组。， ， ， ，是联结词功能完全组。和也是联结词功能完全组。1-7对偶和范式对偶定义1：在只包含联结词， ，的命题公式A中，将联结词和互换，特殊变元F和T亦互换，所得公式A*

21、称为A的对偶式。l 例：求(PQ)R的对偶式。 (PQ)R定理1：设A*是A的对偶式，P1，P2，P3，Pn是出现于A和A*中的原子命题变元，则有 1)A(P1，P2，P3 ， Pn) Û A*(P1，P2，P3 ， Pn) 2) A*(P1，P2，P3 ， Pn) Û A(P1，P2，P3 ， Pn)l 例：A(P1，P2，P3)=P1(P2P3)，验证定理1。l 解：1) A(P1，P2，P3) Û(P1(P2P3) Û(P1)(P2P3) A*(P1，P2，P3) Û( P1)(P2P3)2) A(P1，P2，P3) ÛP1(P

22、2P3) A*(P1，P2，P3) Û (P1(P2P3) Û P1(P2P3)定理2：如果AÛB，则A* Û B*。 证明：设P1,P2,Pn是出现在命题公式A、B中的原子变元，因为AÛB，即：A(P1,P2,Pn)B(P1,P2,Pn)是一个重言式。故有： A(P1,P2,Pn)B(P1,P2,Pn)是一个重言式。即A(P1,P2,Pn)ÛB(P1,P2,Pn) 再由定理1， A* Û B* ，即A* Û B*1-7对偶和范式范式定义 命题变元和命题变元的否定,称为文字.如果一个文字恰为另一个文字的否定,则称它

23、们为一对相反文字.例:P和P都是文字,并且是一对相反文字, P不是文字.P和Q都是文字,但不是一对相反文字定义 设L1,L2,Lk都是文字,称L1L2 Lk为简单析取式,并称Li为析取项，即有限个文字的析取组成的公式称为简单析取式;称L1L2 Lk为简单合取式,并称Li为合取项，即有限个文字的合取组成的公式称为简单合取式.其中1ik.例：P、PQ、PQP等都是简单合取式. P、PQ、PQP、PQ等都是简单析取式.单个的文字既是简单合取式; 又是简单析取式。定理 (1)一简单合取式为永假式的充分必要条件是, 它至少含有一对相反文字，即至少同时包含某个命题变元P及其否定P。(2) 一简单析取式为永

24、真式的充分必要条件是，它至少含有一对相反文字，即至少同时包含某个命题变元P及其否定P。例： PQP为永假式定义 ：一个命题公式称为合取范式，当且仅当它具有形式：A1A2An，其中A1,A2,An都是简单析取式，n1，即：有限个简单析取式的合取组成的公式称为合取范式。定义 ：一个命题公式称为析取范式，当且仅当它具有形式：B1B2Bm，其中B1,B2,Bm都是简单合取式，m1，即：有限个简单合取式的析取组成的公式称为析取范式。析取范式和合取范式仅含联结词、和。例 ：P(QR)(P R) 是析取范式吗？P、QR、PQ、(PQ)(QR) 都是析取范式。P、QR、PQ、(PQ)(QR) 都是合取范式。单

25、个的文字、简单合取式和简单析取式既是析取范式; 又是合取范式。任何析取范式的对偶式为合取范式, 任何合取范式的对偶式为析取范式。定理 (范式存在定理) 对于任意公式, 都存在等价于它的析取范式和合取范式。l 求任意命题公式的合取(析取)范式的步骤 1)将公式中的联结词化成， ，如消除公式中的运算符“®”和“«”。可用等价式将 P®Q替换为PQP«Q替换为(P®Q)(Q®P)即 (PQ)(PQ) (析取范式)或 (PQ)(PQ) (合取范式) 2)利用双否律和德摩根律将否定符号直接移到各个命题变元之前，如将P替换成P (PQ)替换为 P

26、Q (PQ)替换为 PQ 3)利用分配律、结合律将公式化为合取范式(析取)范式，如P(QR)= (PQ)(PR) (析取范式) P(QR)= (PQ)(PR) (合取范式) 例 求公式(PQ)®R)®P的合取范式和析取范式。解 (1)求合取范式 (PQ)® R) ® P Û(Ø (PQ)R)® P (消去第一个) Û Ø (Ø(PQ)R)P (消去第二个) Û Ø(ØP ØQ)R)P (Ø内移) Û(Ø ØP 

27、16; ØQ) ØR)P (Ø内移) Û(PQ) ØR)P (Ø消去) Û(PQP)(ØRP) (对分配律) Û(PQ)(ØRP) (交换律和等幂律) 可见,(PQP)(ØRP),(PQ)(ØRP)都是原公式的合取范式,这说明与某个命题公式等值的合取范式是不唯一的.(2)求析取范式用对的分配律就可得到析取范式,即 (PQ) ® R) ® P Û Û(PQ)ØR)P Û(PØR)(QØR)P (对分

28、配律) ÛP(Q ØR) (交换律和吸收律) 可见, (PØR)(QØR)P, P(Q ØR)都为原公式的析取范式.即：与命题公式等值的析取范式也是不唯一的.范式的应用定理 (1)公式A为重言式的充分必要条件是, A的合取范式中每一简单析取式至少包含一对相反文字。 (2)公式A为矛盾式的充分必要条件是, A的析取范式中每一简单合取式至少包含一对相反文字。例 (PR)(QR)P是否为重言式或矛盾式。解 (PR)(QR)PÛ (PR)QRP在析取范式中共有4个简单合取式, 但任何一个都没有一对相反文字出现。 原公式不是矛盾式。应用对的分配

29、律有:Û (PQRP)(RQRP)第一个简单析取式同时包含有P和P，第二个简单析取式同时包含有R和R。原公式是重言式。定义 ：在含有n个命题变元的简单合取式中，若每个命题变元与它的否定不同时存在，且两者之一必须出现一次且仅出现一次，则称此简单合取式为小项,或布尔积。l 如：两个命题变元P和Q构成的小项有PQ，PQ，PQ，PQ 。注：n个命题变元的小项有2n个。3个命题变元，8个小项对应情况如下： PQR 000 0, 记作m0； PQR 001 1, 记作m1； PQR 010 2, 记作m2； PQR 011 3, 记作m3； PQR 100 4, 记作m4； PQR 101 5,

30、 记作m5； PQR 110 6, 记作m6； PQR 111 7, 记作m7. 一般情况下,n个命题变元共产生2n个小项,分别记为m0,m1,.m2n-1.小项有如下性质：1. 没有两个小项是等价的，即各小项的真值表都是不同的。2. 任意两个不同的小项的合取式是永假的3. 所有小项的析取为永真的4. 每个小项只在一组真值指派下为T，且其真值1位于主对角线上。这表明每个小项与其成真指派之间建立了一一对应关系。定义 ：在给定公式的析取范式中，若其简单合取式都是小项，则称该范式为主析取范式。定理：一个公式的主析取范式是唯一的。定理：在真值表中，一个命题公式A的真值为T的指派所对应的小项的析取，即为

31、该命题公式的主析取范式。 证明：对A为真的某一解释，除其对应为真的小项外，而其余小项均为假，故所有这些小项的析取范式B为真；其次，对A为假的某一解释，其对应的小项不包含在B中，即这些小项均为假，故所有这些小项的析取范式B为假。因此A与B等价。并且B又是小项的析取式，故B是一个主析取范式定理 ：任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式。等价变换法求主析取范式的一般步骤 1)把给定公式化为析取范式 2)除去析取范式中所有永假的析取项 3)合并重复项 4)补入合取项中没有出现的命题变元，例如添加(PP)等，再用分配律展开例：求下式给出的命题公式的主析取范式.(PQ) ®

32、; R) ® P.由前例可知, 原公式的析取范式为, P (Q ØR)用P(ØQQ)(ØRR)取代P.用(ØPP)(Q ØR)取代(Q ØR).然后展开得小项.(PQ) ® R) ® P Û P(Q ØR) (析取范式) Û P(ØQQ) (ØRR)(ØPP)(Q ØR) Û (PØQØR)(PØQR) (P Q ØR)(P Q R) (ØPQØR)(P Q 

33、6;R) Û m4 m5 m6m7m2m6 Û m2m4m5m6m7定义 ：在n个命题变元的简单析取式中，若每个命题变元与它的否定不能同时存在，而两者必须出现一次且仅出现一次，则称此简单析取式为大项，或布尔和。如：两个命题变元P和Q构成的大项有PQ，PQ，PQ，PQ 。注：n个命题变元的大项有2n个l 注：可以为大项指定一种编码，如果将命题变元按字典序排列，并且把命题变元与0对应，命题变元的否定与1对应，则可对2n个大项依二进制数编码。例如：M00对应PQ，M101对应PQRl 注意:编码正好与小项相反 大项具有如下性质：（类似小项）1. 没有两个大项是等价的2. 任意两个

34、不同大项的析取为T3. 全体大项的合取必为F4. 每个大项只有一个解释为假，且其真值0位于主对角线上。这表明每个大项与其成假指派之间建立了一一对应关系。定义 ：在给定公式的合取范式中，若所有简单析取式都是大项，则称该合取范式为主合取范式。定理：一个公式的主合取范式是唯一的。l 定理：在真值表中，一个命题公式的真值为的指派所对应的大项的合取，即为该命题公式的主合取范式。l 定理 ：任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式。主合取范式亦可由等价变换求得，基本步骤如下 1)化为合取范式 2)除去合取范式中所有永真合取项 3)合并重复项 4)补入合取项中没有出现的命题变元，例如添

35、加(PP)等，再用分配律展开例 求PQR的主合取范式. 解 (PQ) R Û(PR)(QR) (合取范式) Û(P(Q ØQ)R)(P ØP)QR) Û(PQR)(P ØQR) (PQR) (Ø PQR) Û(PQR)(P Ø QR)(ØPQR) Û M000M010M100 Û M0M2M4由于小项与大项之间有关系：mi ÛMi Mi Ûmi 因此，主析取范式和主合取范式有着“互补”的关系 ，即由给定公式的主析取范式可以求出其主合取范式。例：A中含3个命

36、题变元,主析取范式为 A Û m0m1m5m7则主合取范式为 A Û M2M3M4M6主范式的用途1.判断两命题公式是否等价.2.判断命题公式的类型3.求命题公式的成真和成假赋值.1.判断两命题公式是否等价.由于任何命题公式的主范式都是唯一的,因而若A Û B,说明A与B有相同的主析取（合取）范式.反之,若A,B有相同的主析取（合取）范式,必有A ÛB.2.判断命题公式的类型设A是含n个命题变项的命题公式, A为重言式,当且仅当A的主析取范式中含全部2n个小项.A为矛盾式,当且仅当A的主合取范式中含全部2n个大项.若A不与T或者F等价，且又不含2n个小项

37、或者大项,则A是可满足式.例 判断下列命题公式的类型. (PQ)P)Q；Û Ø(ØPQ)P)Q （消去）Û Ø(ØPQ) ØPQ （ Ø内移）Û (PØQ) ØPQ （得到析取范式） Û(PØQ)(ØP(ØQQ)(ØPP)Q)（加项）Û (ØPØQ)(Ø PQ)(P Ø Q)(PQ)Û m0m1m2m3由于主析取范式中含全部2n=4个小项,故原命题公式为永真式.3.求命题公式的

38、成真和成假赋值.1-8推理理论例 张三说李四在说谎, 李四说王五在说谎, 王五说张三、李四都在说谎。问谁说真话, 谁说假话？解 设A:张三说真话; B:李四说真话; C:王五说真话依题意有 AØÛB, BØÛC, CØÛAØB。(A « ØB)(B « ØC)(C « ØAØB)Û (AØ®B)(ØB®A)(BØ®C)(ØC® B) (C®(ØA&

39、#216;B)(ØAØB)®C)Û (ØABØC)(AB)C) (ØAØBØC)(AØC)(BØC)Û ØABØC即: 李四说真话, 张三和王五说假话。本章构造推论参照证明题集锦第二章 谓词逻辑（部分*内容为了解）在谓词逻辑中，为揭示命题内部结构及其不同命题的内部结构关系，就按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。.个体、谓词和命题的谓词形式l 定义 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称

40、为谓词。 个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，精神等。表示特定的个体，称为个体常元，以a，b，c或带下标的ai，bi，ci表示；表示不确定的个体，称为个体变元，以x，y，z或xi，yi，zi表示。 谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上个体相联系时，它刻划了个体之间的关系。表示特定谓词，称为谓词常元，表示不确定的谓词，称为谓词变元，都用大写英文字母，如P，Q，R，或其带上、下标来表示。在教材中，不对谓词变元作更多地讨论。 对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆

41、括号( )内。 例如，在命题“张明是位大学生”中，“张明”是个体，“是位大学生”是谓词，它刻划了“张明”的性质。设S：是位大学生，c：张明，则“张明是位大学生”可表示为S(c)，或者写成S(c)：张明是位大学生。定义 一个原子命题用一个谓词(如P)和n个有次序的个体常元(如a1，a2，an)表示成P(a1，a2，an)，称它为该原子命题的谓词形式或命题的谓词形式。应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。.原子谓词原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的n个个体常元被替换成个体变元，如x1,x2,··

42、;·,xn，这样便得了一种关于命题结构的新表达形式，称之为n元原子谓词。定义 由一个谓词(如P)和n个体变元(如x1，x2，xn)组成的P(x1，x2，xn)，称它为n元原子谓词或n元命题函数，简称n元谓词。而个体变元的论述范围，称为个体域或论域。l 当n=1时，称一元谓词，如S(x)l 当n=2时，称为二元谓词，如P(x，y)l l 特别地，当n=0，称为零元谓词。零元谓词是简单命题，这样命题与谓词就得到了统一。注意：1. n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。 例如，令S(x)：x是大学生,这是一元谓词，不是命题； S(c)：张明是位大

43、学生，这就是一个命题。2. 个体变元在哪些论域取特定的值，对命题的真值有影响。 例如，令S(x)：x是大学生。若x的论域为某大学的计算机系中的全体同学，则S(x)是真的；若x的论域是某中学的全体学生，则S(x)是假的；若x的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则S(x)是真值是不确定的。 通常，把一个n元谓词中的每个个体的论域综合在一起作为它的论域，称为n元谓词的全总论域。定义了全总论域，为深入研究命题提供了方便。 当一个命题没有指明论域时，一般都把全总论域作为其论域。而这时又常常要采用一个谓词如P(x)来限制个体变元x的取值范围，并把P(x)称为特性谓词。特性谓词：

44、用来限制个体变元的取值范围的谓词P(x) 称为特性谓词。例如，在全总论域中，用M(x)表示x是人；用R(x)表示x是实数等。.量词在命题中分析出个体和谓词后, 仍不足以表达日常生活中的各种问题 ，例如S(x)表示x是大学生，x的个体域为某单位的职工S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生。 为了避免理解上的歧义，在谓词逻辑中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词，其定义如下：定义 l 符号"称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”等词语；"x称为全称量词，x称为指导变元。l 符号$称

45、为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、“某个”等词语；$x称为存在量词，x称为指导变元。l 符号$!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语；$!x称为存在唯一量词，称x为指导变元。l 全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家Fray引入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。例 试用量词、谓词表示下列命题： 所有大学生都热爱祖国； 每个自然数都是实数； 一些大学生有远大理想； 有的自然数是素数。解 令S(x)：x是大学生，L(x)：x热爱祖国，则所有大学生都热爱祖国 ("x)(S(x)L(x) 令N

46、(x)：x是自然数，R(x)：x是实数，则每个自然数都是实数 ("x)(N(x)R(x) l 全称量词("x)后跟条件式。令S(x)：x是大学生， I(x)：x有远大理想，则一些大学生有远大理想 ($x)(S(x)I(x)令N(x)：x是自然数， P(x)：x是素数。则有的自然数是素数 ($x)(N(x)P(x)l 存在量词($x)后跟合取式。 如果在解答时，指明了个体域，便不用特性谓词，例如在、中令个体域为全体大学生，和中的个体域为全部自然数，则可符号化为：("x)L(x) ("x)R(x)($x)I(x) ($x)P(x)谓词前加上了量词，称为谓词的

47、量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数f(x)， 的值是不确定的，但 可确定其值。2.2 谓词公式与翻译.谓词公式为了方便处理数学和计算机科学的逻辑问题及谓词表示的直觉清晰性，将引进项的概念。定义 项由下列规则形成： 个体常元和个体变元是项； 若f是n元函数，且t1，t2，tn是项，则f(t1，t2，tn)是项； 所有项都由和生成。有了项的定义，函数的概念就可用来表示个体常元和个体变元。这里函数是就广义而言的。 例如，令f(x,y)表示x+y，谓词N(x)表示x是自然数，那么f(2,3)表示个

48、体自然数5，而N(f(2,3)表示5是自然数。定义 若P(x1，x2，xn)是n元谓词，t1，t2，tn是项，则称P(t1，t2，tn)为原子谓词公式，简称原子公式。定义 合式谓词公式当且仅当由下列规则形成的符号串l 原子公式是合式谓词公式；l 若A是合式谓词公式，则(A)是合式谓词公式；l 若A，B是合式谓词公式，则(AB)，(AB)，(AB)和(A«B)都是合式谓词公式；l 若A是合式谓词公式，x是个体变元，则("x)A、($x)A都是合式谓词公式；l 仅有有限项次使用、和形成的才是合式谓词公式。.谓词逻辑的翻译l 把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑

49、的翻译或符号化；反之亦然。l 一般说来，符号化的步骤如下：l 正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。l 把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。l 找出恰当量词。应注意全称量词("x)后跟条件式，存在量词($x)后跟合取式。l 用恰当的联结词把给定命题表示出来。l 例 将命题“没有最大的自然数”符号化。解 命题中“没有最大的”显然是对所有的自然数而言，所以可理解为“对所有的x，如果x是自然数，则一定还有比x大的自然数”，再具体点，即“对所有的x如果x是自然数，则一定存在y，y也是自然数，并且y比x大”

50、。令N(x):x是自然数，G(x,y):x大于y，则原命题表示为：("x)(N(x)($y)(N(y)G(y,x)。2.3 约束变元与自由变元定义 给定一个谓词公式A，其中有一部分公式形如("x)B(x)或($x)B(x)，则称它为A的x约束部分，称B(x)为相应量词的作用域或辖域。在辖域中，x的所有出现称为约束出现，x称为约束变元； B(x)中不是约束出现的其它个体变元的出现称为自由出现，这些个体变元称为自由变元。l 对于给定的谓词公式，能够准确地判定它的辖域、约束变元和自由变元是很重要的。l 通常，一个量词的辖域B(x)是某公式A的一部分，称此辖域为A的子公式。因此，确

51、定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：若量词后有括号，则括号内的子公式就是该量词的辖域；若量词后无括号，则与量词邻接的子公式为该量词的辖域。 判定给定公式A中个体变元是约束变元还是自由变元，关键是要看它在A中是约束出现，还是自由出现。例 指出下列各合式公式中的量词辖域、个体变元的约束出现和自由出现。(1) ("x) (P(x)($y) Q(x,y),量词("x)的辖域是P(x) ($y) Q(x,y),量词($y)的辖域是Q(x,y),对于($y)的辖域而言，y为约束出现，x为自由出现。对于("x)的辖域而言，x和y均为约束出现，x约束

52、出现2次，y约束出现1次。(2) ($x) H(x)L(x,y),量词($x)的辖域是H(x) ，x为约束出现，L(x,y)中的x和y都为自由出现。对于整个公式而言，x的约束出现1次，自由出现1次，y自由出现1次。(3) ("x) ("y) (P(x,y)Q(y,z)($x)R(x,y),在公式("x) ("y) (P(x,y)Q(y,z)中，量词("x)的辖域是("y) (P(x,y)Q(y,z)，量词("y)的辖域是(P(x,y)Q(y,z)，x和y为约束出现，z为自由出现；在公式($x)R(x,y)中,量词("

53、;x)的辖域是R(x,y)，x为约束出现，y为自由出现。在整个公式中，x为约束出现，y为约束出现又为自由出现，z为自由出现。 今后常用元语言符号A(x)表示x是其中的一个个体变元自由出现的任意公式，一旦在A(x)前加上量词("x)或($x)，即得公式("x)A(x),或($x)A(x)。这时，x即是约束出现了。 类似地，用A(x,y)表示x和y是自由出现的公式。定义 设A为任意一个公式，若A中无自由出现的个体变元，则称A为封闭的合式公式，简称闭式。若A中没有约束变元出现，则称A为开放公式，简称开式。 由闭式定义可知，闭式中所有个体变元均为约束出现。同样，开式中所有个体变元均

54、为自由出现。例如：("x)(P(x)Q(x)和($x)("y)(P(x)Q(x,y)是闭式("x)(P(x)Q(x,y)和($y)("z)L(x,y,z)不是闭式P(x)Q(x,y)和L(x,y,z)是开式("x)(P(x)Q(x,y)既不是闭式也不是开式l 从约束变元的概念可以看出, P(x1, x2, , xn)是n元谓词, 它有n个相互独立的自由变元, 若对其中k个变元进行约束，则成为n k元谓词。 当多个量词连续出现, 它们之间无括号分隔时,我们约定从左到右的次序读出。后面的量词在前面量词的辖域之中, 且量词对变元的约束与量词的次序有关。量词的次序不能随意颠倒, 否则将与原命题意义不符。例:令f(x,y):x小于y减2，谓词公式("y)($x) f(x,y), x, y的个体域为实数集。 量词"y的辖域为($x) f(x,y), 量词$x的辖域为f(x,y), 公式表示“任何实数y均有实数x, x< y 2”，是真命题。 若将量词次序改为($x)("y) f(x,y), 则公式表示“存在一个实数x, 对任何实数y均有x<y2”，是假命题。 从前面讨论可以看出，在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面