离散数学课堂ppt课件(左孝凌版).ppt

《离散数学课堂ppt课件(左孝凌版).ppt》由会员分享，可在线阅读，更多相关《离散数学课堂ppt课件(左孝凌版).ppt（442页珍藏版）》请在三一办公上搜索。

1、第一章 命题逻辑11 命题及其表示法1.什么是命题命题：能判断真假的陈述句。命题的值叫它的真值。真值：“真”：表示判断正确。记作True，用T表示。“假”：表示判断错误。记作False，用F表示。,例1 判断下列句子中哪些是命题？（1）2是素数。（2）雪是黑色的。（3）2+3=5（4）明年10月1日是晴天。（5）3能被2整除。（6）这朵花真好看呀！（7）明天下午有会吗？（8）请关上门！（9）X+Y5（10）地球外的星球上也有人。（11）我正在说谎。,2命题的符号化表示 命题的符号化就是用符号表示命题。简单命题（或原子命题）：简单陈述句表示的命题。用P，Q，R,Pi,Qi,Ri,表示。例 P:2

2、是偶数。Q:雪是黑色的。命题常量（或命题常元）：简单命题。命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。例：x+y5,命题变项也用P，Q，R,Pi,Qi,Ri,表示。复合命题：由简单命题用联结词联结而成的命题。,例2 将下列命题符号化。（1）3 不是偶数。（2）2 是素数和偶数。（3）林芳学过英语或日语。（4）如果角A和角B是对顶角，则角A 等于角B。解：（1）设P：3是偶数。P（：表示并非）（2）设P：2 是素数；Q：2是偶数。PQ(:表示和)（3）设P：林芳学过英语；Q：林芳学过日语。PQ(:表示或)（4）设P：角A和角B是对顶角；Q：角A 等于角B。PQ（个表示如果则）,1

3、2.联结词定义12.1 设P为任一命题，P的否定是一个新的命题，称为P的否定式，记作P。为否定联结词。,例 p：3是偶数。p：3不是偶数。,定义12.2 设P、Q为两命题，复合命题“P并且Q”（或“P和Q”）称为 P与Q的合取式，记作PQ，为合取联结词。表示自然语言中的“既又”，“不仅而且”，“虽然但是”,例3将下列命题符号化。（1）李平既聪明又用功。（2）李平虽然聪明，但不用功。（3）李平不但聪明，而且用功。（3）李平不是不聪明，而是不用功。解：设P：李平聪明；Q：李平用功。（1）PQ（2）PQ（3）PQ（4）（P）Q注意：不是见到“和”、“与”就用。例：“李文和李武是兄弟”，“王芳和陈兰是

4、好朋友”是简单命题。,定义12.3 设P、Q为两命题，复合命题“P或Q”称为 P与Q的析取式，记作PQ，为析取联结词。,析取式PQ表示的是一种相容性或，即允许P和Q同时为真。例：“王燕学过英语或日语”PQ自然语言中的“或”具有二义性，有时表示不相容的或。例：“派小王或小李中的一人去开会”。为排斥性的或。P：派小王去开会；Q：派小李去开会。（PQ）（PQ），（PQ）（PQ）,定义12.4 设P、Q为两命题，复合命题“如果P，则Q”称作 P与Q的蕴涵式，记作PQ，为蕴涵联结词。,在PQ中，Q是P的必要条件，P是Q的充分条件。表示自然语言“只要P就Q”，“P仅当Q”，“只有Q，才P”注意：1.在自然

5、语言中，“如果P，则Q”中的P与Q往往有某 种内在的联系，但在数理逻辑中，PQ中的P与Q不一定有内在的联系。2.在数学中，“如果P，则Q”表示P为真，Q为真的逻辑关系，但在数理逻辑中，当P为假时PQ为真。,例4将下列命题符号化。(1)只要不下雨，我就骑自行车上班。(2)只有不下雨，我才骑自行车上班。(3)若 2+24，则太阳从东方升起。(3)若 2+24，则太阳从东方升起。(4)若 2+24，则太阳从西方升起。(5)若 2+24，则太阳从西方升起。解：在（1）、（2）中，设P：天下雨；Q：我骑自行车上班。（1）PQ（2）Q P在（3）（6）中，设P：2+24；Q：太阳从东方升起；R:太阳从西方

6、升起。（1）PQ，真值为T（2）PQ，真值为T（3）PR，真值为F（4）PR 真值为T,定义1-2.5 设P、Q为两命题，复合命题“P当且仅当 Q”称作 P与Q的等价式，记作P Q，为等价联结词。PQ表示P与Q互为充分必要条件。,例5将下列命题符号化。（1）2+24，当且仅当3是奇数。（2）2+24，当且仅当3不是奇数。（3）2+24，当且仅当3是奇数。（4）2+24，当且仅当3不是奇数。（5）两圆的面积相等，当且仅当它们的半径相同。（6）两角相等当且仅当它们是对顶角。解：（1）（4）设P：2+24；Q：3是奇数。（1）PQ 真命题（2）PQ 假命题（3）PQ假命题（4）PQ真命题（5）设P：

7、两圆的面积相等；Q：两圆的面积相同。PQ真命题（6）设P：两角相等；Q：它们是对顶角。PQ假命题,4.5种联结词的优先级顺序：，,1-3命题公式与翻译 1.命题公式命题公式：由命题常量、命题变元、联结词、括号 等组成的符号串。命题公式中的命题变元称作命题公式的分量。,定义13.1（1）单个命题常量或命题变 元,Q,R,Pi,Qi,Ri,，F，T是合式公式。（2）如果A是合式公式，则（A）也是合式公式。（3）如果A、B是合式公式，则（AB）、（A B）、（AB）、（AB）也是合式公式。（4）只有有限次地应用（1）（3）组成的符号串才是合式公式。例：P,P,(P),(0P),P(PQ),(PQ)R

8、)(R)是公式；PQR,(P),PQ)不是公式。,2.翻译 翻译就是把自然语言中的有些句子符号化。复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化。（2）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。,例 将下列命题符号化。（1）小王是游泳冠军或是百米冠军。PQ（2）小王现在在宿舍或在图书馆。PQ（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。（P Q）（PQ）或（PQ）（排斥性或，可能同时为真）,(4)如果我上街，我就去书店看看，除非我很累。R(PQ)或（RP）Q（除非：如果不）(5)王一乐是计算机系的学生，他生于1968年或1969年，他是

9、三好学生。P（Q R）S（6）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。A：我们要做到身体好B：我们要做到学习好C：我们要做到工作好P：我们要为祖国四化建设面奋斗。命题符号化形式为：（ABC）P,14真值表与等价公式1.真值表定义14.1含n个（n1）个命题变元（分量）的命题公式，共有2n组真值指派。将命题公式A在所有真值指派之下取值的情况列成表，称为A的真值表。构造真值表的步骤：(1)找出命题公式中所含的所有命题变元P1,P2,Pn。列出所有可能的真值指派。(2)对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。,例1 构造求PQ的真值表。,例2 给出（P

10、Q）P的真值表。,例3 给出（PQ）（PQ）的真值表。,例4 给出（PQ）（PQ）的真值表。,由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为T（F）。如例4和例2,2等价公式 从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如PQ与PQ的对应真值相同。,（PQ）（PQ）与PQ对应的真值相同。,定义14.2 给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元,若给P1，P2，Pn任一组真值指派,A和B的真值都相同,则称A和B是等价的或逻辑相等。记作AB。例5 证明PQ（PQ）（QP）证明 列出真值表

11、,24个重要的等价式PP 双重否定律PPP等幂律PPPPQQP交换律PQQP（PQ）RP（QR）结合律（PQ）RP（QR）P（QR）（PQ）（PR）分配律P（QR）（PQ）（PR）（PQ）PQ 德摩根律（PQ）PQ,P（PQ）P吸收律P（PQ）PPT T零律PF FPFP同一律PT PPP T排中律PP F矛盾律PQ PQ蕴涵等价式P Q（PQ）（QP）等价等价式PQ QP假言易位P Q P Q等价否定等价式（PQ）（PQ）P归谬论 其中P、Q和R代表任意的命题公式。,例6 验证吸收律P（PQ）P和 P（PQ）P,定义1-4.3 如果X是合式公式A的一部分,且X本身也是一个合式 公式,则称X为

12、公式 A的子公式。定理14.1如果X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，所得到公式B与公式A等价，即AB。证明 因为在相应变元的任一种指派下，X与Y的真值相同，故以Y取代X后，公式B与公式 A在相应的指派下，其真值必相同，故AB。满足定理14.1的置换称为等价置换（等价代换）,例7 证明PQ（PQ）证明 PQ PQ，（根据蕴涵等价式）PQ（Pq），（德摩根律）即Pq（Pq）,例8 证明P(QR)(PQ)R证明 P(QR)P(QR)（蕴涵等价式）P(QR)（蕴涵等价式）(PQ)R（结合律）(PQ)R（德摩根律）(PQ)R（蕴涵等价式）,例9 证明 P(PQ)(PQ)证明 P

13、P1(同一律)P(QQ)（排中律）(PQ)(PQ)（分配律）,练习 1.证明 Q(PQ)P)T;2.证明(PP)(QQ)R)F 3.证明(PQ)PP,1,证明Q(PQ)P)Q(PP)(PQ)（分配律）Q(F(PQ)（矛盾律）Q(PQ)（同一律）Q(PQ)（德摩根律）(QQ)P（结合律）TP（排中律）T（零律）,2.证明(PP)(QQ)R)T(QQ)R)（排中律）T(FR)（矛盾律）TF（零律）TF（蕴涵等值式）FFF（等幂律）,3.证明(PQ)P(PQ)P（蕴涵等价值式）P（吸收律）,1-5 重言式与蕴涵式 定义15.1 给定一命题公式，若无论对分量作什么样的指派，其对应的真值永为T，则称该命

14、题公式 为重言式或永真式。定义15.2 给定一命题公式，若无论对分量作什么样的指派，其对应的真值永为F，则称该命题公式 为矛盾式或永假式。,定理15.1 任何两个重言式的合取或析取，仍然是一个重言式。定理15.2 一个 重言式，对同一分量，都 用任何合式公式 置换，其结果仍为一重言式。证明 由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。对于矛盾式也有类似于定理15.1和定理51.2的结果。,例1 证明（PS）R）（PS）R）为重言式。证明 因为 PPT，用（PS）R）置换P得（PS）R）（PS）R）T,定理15.3 设A、B为两命题公式AB，当且仅当

15、AB 为一个重言式。证明 若 AB，则A、B有相同的真值，即有AB 永为T。若 AB 为重言式，则AB 永为T，故A、B的真值相同，即AB。,例2 证明（PQ）（PQ）证明 做（PQ）（PQ）的真值表。,由以上真值表可知，（PQ）PQ 为重言式，根据定理15.3得（PQ）（PQ）,定义15.3 当且仅当 PQ 是重言式时，我们称“P蕴涵Q”，并记作PQ。做PQ QP，PQ，Qp 的真值表,由此得 PQ QP，QP PQ，因此要PQ，只要证明QP，反之亦然。,要证明PQ，即证PQ 是重言式，对于PQ 来说，除P的真值取T，Q的真值取F这样一种指派时，PQ 的真值为F外，其余情况PQ 的真值为T，

16、故要征PQ，只要对条件PQ 的前件P，指定真值为T，若由此指出Q的真值为T，则PQ 为重言式，即PQ 成立；同理，如对条件命题PQ 中，假定后件Q的真值为F，若由此推出P的真值为F，即推证了QP。故PQ成立。即 若P为T时，推出Q为T 或若Q为F时，推出P为F 则PQ。,例1 推证Q（PQ）P证法1 假定Q（PQ）为T，则Q为T，且PQ 为T。所以Q为F，PQ 为T，所以P为F，故P为T。证法2 假定P为F，则P为T，若Q为F，则PQ 为F，Q（PQ）为F，若Q为T，则Q为F，Q（PQ）为F，所以 Q（PQ）P,常用的蕴涵式如下：PQ PPQ QPPQPPQQPQ（PQ）P（PQ）QP（PQ）

17、QQ（PQ）pP（PQ）Q（PQ）（QR）PR（PQ）（PR）（QR）R（PQ）（RS）（PR）（QS）（PQ）（QR）（PR）,定理15.4 设P、Q为任意两个 命题公式，PQ 的充分必要条件是 PQ 且 QP证明 若PQ，则PQ为重言式。因为PQ（PQ）（QP），故 PQ为T，且QP 为T，因为PQ 且QP成立。反之，若PQ 且QP，则PQ为T，且QP 为T，因此PQ（PQ）（QP）为T，即PQ 这个定理也可以作为两个公式等价的定义。,蕴涵的几个常用的性质：（1）设A、B、C为合式公式，若AB且A为重言式，则B也是重 言式。证明 因为 AB 永为T，所以当A为T时，B必T。（2）若AB，B

18、C，则 AC 证明 由AB，BC 得AB，BC 为重言式 所以（AB）（BC）为重言式，根据（PQ）（QR）PR 所以（AB）（BC）AC，由性质（1）得：AC为重言式，即 AC,（3）AB，且AC，那么A（BC）证明 由假设知AB，AC为重言式。设A这T，则B、C为T，故BC为T，因此A（BC）为T，若A为F，则A（BC）为T，所以A（BC）,（4）若AB 且 CB，则ACB 证明 因为AB 为T，CB为T，故（AB）（C B）为T，则（AC）B 为T，即（AC）B为T，即（AC）B为T，所以（AC）B,16 其他联结词 定义16.3 设P、Q是两个命题公式，复合命题P Q称作P和Q的“与非

19、”。PQ（PQ）,联结词“”的几个性质：（1）PP（PP）p（2）（PQ）（PQ）（PQ）PQ（3）（PP）（QQ）PQ（Pq）PQ,定义16.3 设P、Q是两个命题公式，复合命题P Q称作P和Q的“或非”。P Q（PQ）,联结词“”的几个性质：（1）P P（PP）p（2）（P Q）（PQ）（PQ）PQ（3）（PP）（QQ）PQ PQ当有n个命题变元时，可构成22 n种不等价的命题公式，如n2时，有16种不等价的命题公式。，见27页表16.5。,最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。由于（1）（PQ）（PQ）（QP）（2）（PQ）PQ（3）PQ（P Q）（

20、4）PQ（Pq）故由“”、“”、“”，“”、“”这五个联结词组成的命题公式，必可以由，或，组成的命题公式所替代。,17 对偶与范式 定义17.1在给定的命题公式A中，将换成，换成，若有特殊变元F和T亦相互取代，所得命题公式A*称为A的对偶式。A和A*互为对偶式。例1:PQ与 PQ,(PQ)与(PQ)(PQ)R与(PQ)R(PT)Q 与(P F)Q 均为对偶式.例2：PQ、P Q的对偶式。解：PQ(PQ)，PQ的对偶式为(PQ)P Q（PQ），P Q的对偶式为(PQ),定理17.1设A和A*互为对偶式,P1,P2,Pn，是出现在A和A*中的全部的命题变元,则A(P1,P2,Pn)A*(P1,P2

21、,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)例:设 A(P,Q,R)P(QR)得:A*(P,Q,R)P(QR)(1)由知:A(P,Q,R)P(QR)由知:A*(P,Q,R)P(QR)所以:A(P,Q,R)A*(P,Q,R)类似地,有A(P,Q,R)A*(P,Q,R),定理17.2设P1,P2,Pn 是出现有命题公式A和B中的所有命题变元，若A B，则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)由定理17.1得 A*(P1,P2,Pn)B*(P1,

22、P2,Pn)因此A*B*,例4 如果A(P,Q,R)是P（Q（RP），求它的对偶式A*(P,Q,R)。并求与A及 A*等价，但仅包含联结词“”、“”、“”的公式。解：因 A(P,Q,R)是 P（Q（RP）故 A*(P,Q,R)是P（Q（RP）但P（Q（RP）P（Q（RP）（P（Q（RP）所以P（Q（RP）(P（Q（RP）),定义17.2 一个命题公式 称为合取范式，当且仅当它具有形式A1A2An（n1）。其中A1，A2，An 都是命题变元或其否定所组成的析取式。例P(PQ)(PP)(PR)定义17.3 一个命题公式 称为析取范式，当且仅当它具有形式A1A2 An（n1）。其中A1，A2，An

23、都是命题变元或其否定所组成的合取式。例(PQR)(PQ)(PQR),求合取范式或 析取范式的步骤：（1）将公式中的联结词化归成、。（2）将消去或内移。（3）利用分配律、交换律求合取范式或析取范式。（求合取范式：对；求析取范式：对）注意任何命题的析取范式和合取范式都不是唯一的。,例求下面命题公式的合取范式和析取范式。（PQ）R）P解（1）求合取范式（PQ）R）P（PQ）R）P(PQ)R)P(PQ)R)P(PQ)R)P(PQ)R)P(PQ)R)P(PQP)(RP)（PQ）(RP)(2)求析取范式(PQ)R)P(PR)(QR)PP（P R）(QR)P(QR),练习：求下面命题公式的合取范式和析取范式

24、。（1）求合取范式(PQ)R(PQ)R(PQ)R)(R(PQ)(PQ)R)(R(PQ)(PQ)R)(RPQ)(PR)(QR)(RPQ)（2）求析取范式(PQ)R)(RPQ)（(PQ)(RPQ)）(R(RPQ)(PQ)R)(PQ)P)(PQ)Q)(RR)(RP)(RQ)(PQR)(PPQ)(PQQ)(RR)(PR)(QR)(PQR)(PR)(QR),定义17.4 n个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。n个命题变元 共有2n个小项。例两个命题变元 P和Q，其小项为：PQ，PQ，PQ，PQ,3个命题变项P、Q、R可形成8个小项：m000

25、 PQRm001PQRm010PQR m011PQRm100PQR M101PQR m110PQR m111PQR,小项的性质：（1）每一个小项当其真值指派与编码相同时，其真值为T，其余均为F。（2）任意两个不同小项的合取永为F。（3）m0m1m2m3m4m5m6m7T,定义17.3 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。定理17.3 在真值表中，一个 公式的真值为T的指派所对小项的析取，即为此公式的主析取范式。,例6给定P Q，PQ和（PQ），求这些公式的主析取范式。解：真值表如下：,故P Q（PQ）（PQ）（PQ）PQ（PQ）（PQ

26、）（PQ）（PQ）（PQ）（PQ）（PQ）,例7 设一公式A的真值表如下，求公式 A的主析取范式。,解 公式A的主析取范式 为：A（PQR）（PRR）（PQR）,例8 求（PQ）（PR）（QR）的主析取范式。解：原式（PQ（RR）（PR（QQ）（QR（Pp）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）,例9求P（PQ）（QP）的主析取范式。解：原式P（PQ）（QP）P（PQP）（QQP）P（QP）P（QQ）（PQ）（PQ）（PQ）（PQ）,求主析取范式的步骤：（1）求析取范式。（2）去掉永假的析取项。（3）去掉重复的合取项、合并相同变元。

27、（4）对合取项补入没出现的命题变元。（PP）,定义17.6 n个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。n个命题变元 共有2n个小项。例 两个命题变元 P和Q，其小项为：PQ，PQ，PQ，PQ,3个命题变项P、Q、R可形成8个大项：M000 PQRM001PQRM010PQR M011PQRM100PQR M101PQR M110PQR M111PQR,大项的性质：（1）每一个大项当其真值指派与编码相同时，其真值为F，其余均为T。（2）任意两个不同大项的析取永为T。（3）M0M1M2M3M4M5M6M7F,定义17.7 对于给定的命题公

28、式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。定理17.4 在真值表中，一个公式的真值为F的指派所对大项的合取，即为此公式的主合取范式。,例10 利用真值表求（PQ）（PR）的主合取范式与主析取范式。,主合取范式：（PQR）（PQR）（PQR）（PQR）主析取范式：（PQR）（PQR）（PQR）（PQR）,求主合取范式的步骤：（1）求合取范式。（2）去掉所有为T的合取项。（3）合并相同的析取项和变元。（4）补入没出现的命题变元。（即添加PP）,例11 求（PQ）（PR）的主合取范式。解：原式（PQ）P）（PQ）R）（Pp）（Qp）（PR）（QR）（Qp）（PR

29、）（QR）（QP（RR）（PR（QQ）（QR（PP）（QPR）（QPR）（PRQ）（PRQ）（QRP）（QRP）（PQR）（PQR）（PQR）（PQR）,用表示小项的析取用表示大项的合取例如（PQ）（PR）（PQR）（PQR）（PQR）（PQR）M000M010M100M101 0,2,4,5 m001m011m110m111 1,3,6,7,1-8推理理论推理是从前提推出结论的思维过程,前提是指已知的命题公式,结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个。定义18.1设H1，H2，H n，C是命题公式，若（H1H2Hn）C为重言式,则称C是一组前提H1,H2,Hn的有效结论。

30、记作：H1H2Hn C 真值表法推理方法 直接证法 间接证法,（1）真值表法 若H1，H2，H n 都为T的行，C也为真；或若C为假的行，H1，H2，H n 中至少有一个为假则 H1H2Hn C 成立。,例1 一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解：设 P：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算不可靠。前提是：PQ，P，结论是：Q，即证明（PQ）P Q,故（PQ）P Q,例2 如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了

31、，这个问题就可以得到解答。解：设P：张老师来了。Q：李老师来了。R：这个问题可以得到解答。本题可译为：（P R）（QR）（PQ）R,（2）直接证法 就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。P规则：前提在推导过程中随时可以引用。T规则：已经推出的公式在以后的推导过程中可随时引用。常用蕴涵式见43页表18.3,例1 证明（PQ）（PR）（QS）SR 证法1（1）PQ P（2）PQ T（1）E（3）QS P（4）PS T（2），（3）I（5）SP T（4）E（6）PR P（7）SR T（5），（6）I（8）SR T（7）E,证法2（1）PR P（2）PQR

32、Q T（1）I（3）QS P（4）QRSR T（3）I（5）PQSR T（2），（4）I（6）PQ P（7）SR T（5），（6）I,例2 证明（WR）V，VCS，SU，C U W证明（1）C U P（2）U T（1）I（3）SU P（4）S T（2）,（3）I(5)C T（1）I(6)C S T(4),(5)I(7)(C S)T(6)E(8)（WR）V P(9)V(CS)P(10)（WR）(CS)T(8),(9)I(11)(（WR）T(7),(10)I(12)W R T(11)E(13)W T(12)E,(3)间接证法1(归谬法)要证 H1H2Hn C 即要证 H1H2Hn C 为重言式 H

33、1H2Hn C(H1H2Hn)C(H1H2Hn C)因此只要证 H1H2Hn C 为矛盾式.,例3 证明 AB,(BC)可逻辑推出A证明(1)AB P(2)A P(附加前提)(3)(BC)P(4)BC T(3)E(5)B T(1),(2)I(6)B T(4)I(7)BB(矛盾)T(5),(6)I,例4 证明(PQ)(PR)(QS)SR证明(1)(SR)P(2)SR T(1)E(3)PQ P(4)PQ T(3)E(5)QS P(6)PS T(4),(5)I(7)SP T(6)(8)(SR)(PR)T(7)I(9)PR T(2),(8)I(10)PR P(11)P R T(10)E(12)(P R

34、)T(11)E(13)(P R)(P R)(矛盾)T(9),(12)I,(4)间接证法2(附加前提法)要证 H1H2Hn RC 只要证(H1H2Hn)(R C)为重言式(H1H2Hn)(R C)(H1H2Hn)(R C)(H1H2HnR)C(H1H2Hn R)C 只要证(H1H2Hn R)C 由(SR)C 证得S(R C)称为CP规则。,例5 证明 A(BC),DA,B 重言蕴涵 DC证明(1)D P(附加前提)(2)DA P(3)A T(1),(2)I(4)A(BC)P(5)BC T(3),(4)I(6)B P(7)C T(5),(6)I(8)DC CP,例6 设有下列情况,结论是否有效?(

35、a)或者是天晴,或者是下雨。(b)如果是天晴，我去看电影。(c)如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。解 若设 M：天晴。Q：下雨。S：我看电影。R：我看书。即证：MQ，MS，SR，推出RQ其中 MQ(MQ）,(1)R P（附加前提）(2)SR P(3)R S T(2)E(4)S T(1),(3)I(5)MS P(6)M T(4),(5)I(7)(M Q）P(8)M Q T(7)E(9)(MQ)(QM)T(8)E(10)QM T(9)I(11)MQ T(10)E(12)Q T(6),(11)I(13)RQ CP,第二章 谓词逻辑 原子命题是命题逻辑研究的基本单位,没有对原子

36、的内部结构及其相互之间的逻辑关系进行分析,这样就无法处理一些简单而又常见的推理问题。例如:所有的人都是要死的，苏格拉底是人，所以,苏格拉底是要死的。P:所有的人是要死的.Q:苏格拉底是人.R:所以,苏格拉底是要死的PQR 不是重言式。,21 谓词的概念与表示原子命题由主语和谓语两部分组成。主语一般是客体。客体：可以是一个具体的事物，也可以是一种抽象事物。是命题所研究的对象。谓词：用以刻划客体的性质或客体之间的性质。例 李明是一个学生。李明比王杰高。哥白尼指出地球绕着太阳转。,谓词用大写字母表示。客体名称用小写字母表示。客体常元：表示具体或特定的客体的词。一般用小写字母a,b,c,表示。客体变元

37、：表示抽象的或泛指的客体的词。一般用小写字母x,y,z,表示。例如：A表示“是个大学生”，c表示张三，e表示李四，则 A（c）表示“张三是个大学生”，A（e）表示“李四是个大学生”，,“b是A”类型的命题可用A（b）表示。两个客体之间关系的命题可表示为B（a,b）。A（b）为一元谓词。B（a,b）为二元谓词。依此类推。单独一个谓词不是命题，只有将变元x,y,z等取特定客体时，才确定了一个命题。,22 命题函数与量词 定义22.1 由一个谓词，一些客体变元组成的表达式称为简单命题函数。例 B（x,y）。n元谓词就是有n个客体变元的命题函数。当n0时，它本身就是一个命题。,由一个或几个简单命题函数

38、以及联结词组合而成的表达式称为复合命题函数。例1（1）2是素数且是偶数。解：设A（x）：x是素数；B（x）：x是偶数；a：2 则命题表示为：A（a）B（a）（2）如果2大于3，则2大于4。解：设L（x,y）：x大于y；a：2；b：3；c：4 则命题表示为：L（a,b）L（a,c）。,（3）如果张明比李民高，李民比赵亮高，则张明比赵亮高。解：设 H（x,y）：x比y高；a：张明；b：李民；c：赵亮。则命题符号化为：H（a,b）H（b，c）H（a,c）。命题函数不是命题，只有客体变元取特定客体名称时，才能成为命题。,个体域：客体变元的取值范围。个体域可以是有限的，也可以是无限的。例 学生、工人，实

39、数，a,b，c。全总个体域：宇宙间的一切事物。,量词：表示数量的词。全称量词“”用来表达“对所有的”、“每一个”，“对任何一个”。例2（1）所有的人都是要呼吸的。解：设M（x）：X是人；H（x）：x要呼吸。则符号化为：（x）（M（x）H（x）域为全总域。,（2）每个学生都要参加考试。解：设P（x）：x是学生；Q（x）：x要参加考试。符号化为:（x）（P（x）Q（x）(3)任何整数或是正的或是负的。解：设 I（x）：x是整数；R（x）：X是正数；M（x）：x是负数。符号化为：（x）（I（x）R（x）M（x）,存在量词“”：表示“存在一些”。例3（1）存在一个数是质数。解：设 P（x）：x是质数。

40、符号化为：（x）（P（x）（2）一些人是聪明的。解：设 M（x）：x是；R（x）：x是聪明的。符号化为：（x）（M（x）R（x）,注意：（1）在不同的个体域中，命题符号化的形式可能不一样。（2）如果事先没有给出个体域，都应以全总个体域为个体域。（3）在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。对全称量词，特性谓词常作蕴涵的前件；对存在量词，特性谓词常作合取 项。,例：（1）所有的人都是要死的。（2）有的人活百岁以上。解：第一种情况：考虑个体域D为人类集合。（1）符号化为：x F(x)。其中F(x)：x是要死的。（2）xF(x)。其中F(x)：x活百岁以上。第二种情况：考虑个体

41、域为全总个体域，对所有个体而言，如果它是人，则它是要死的。存在着个体，它是人并且活百岁以上/引进特性谓词：M（x）：X是人。（1）符号化为：x（M（x）F(x)）（2）符号化为：x（M（x）F(x)）,23 谓词公式与解释原子谓词公式：若P（x1,x2,xn）是n元谓词，则称P（x1,x2,xn）是原子谓词公式。其中x1,x2,xn是客体变元。例 Q，R（x），A（x,y),A(f(x),y),A(a,y,z),合式公式定义如下：（1）原子公式是合式公式；（2）若A是合式公式，则（A）也是合式公式；（3）若A、B是合式公式，则（AB）、（AB）、（A B）、（AB）也是合式公式；（4）若A是合

42、式公式，则xA、xA也是合式公式；（5）只有有限次地使用(1)(4）生成的符号串才是合式公式.,例1并非每个实数都是有理数。解：设 R（x）：x是实数；Q（x）：x是有理数。谓词公式为：（x R(x)Q（x）例2 一切人都不一样高。解：设M（x）：x是人；H（x，y）：x y；L（x，y）：x与y一样高。谓词公式为：x y（M(x)M（x）H（x，y）L（x，y）,例3 每个自然数都有后继数。解：设F（x）：x是自然数；H（x，y）：y是x的后继数。谓词公式为：x（F(x)y（F(y)H（x，y）例4 这只大红书包摆满了那些古书。解：设F（x，y）：x摆满了y；Q（y）：y是古书；a:这只；b

43、：那些。谓词公式为：R（a）Q（b）F(a,b),24 变元的约束1、变元的约束 定义24.1 在合式公式xA或xA中,称x为指导变项，称A为相应量词的辖域。在辖域中，x的所有出现称为约束出现（即x受相应量词指导变元的约束），A中不是约束出现的其它变元称为自由出现。,例1 指出下列合式公式中的指导变元、量词的辖域与客体变元的自由出现和约束出现。(1)x(F(x)yH(x,y);(2)xF(x)G(x,y);(3)xy(R(x,y)L(y,z)x H(x,y),2、变元的改名（1）约束变元的改名：将量词的辖域中出现的某个约束出现的客体变元及对应的指导变元，改成作用域上未出现的变元名称，公式其余部

44、分不变。（换名规则）（2）自由变元的改名：将自由变元用原公式中的所有客体变元符号不同的变元符号去代替，且处处代替。（代替规则）,例2：在xF(x)G(x,y)中，利用换名规则，将约束出现的x改成z,得：z F(z)G(x,y)。利用代替规则，将自由出现的x用z代替，得：xF(x)G(z,y)。例3：在xy(R(x,y)L(y,z)x H(x,y)中，将x H(x,y)中的x利用换名规则换成t,对y利用代替规则，用w代替，得：xy(R(x,y)L(y,z)t H(t,w).,3、谓词公式的解释谓词公式的解释:对谓词公式中各种变项用具体的常项元去代替。通过对谓词的解释，求出谓词公式的真值。谓词公式

45、的解释由四部分组成（1）非空的个体域D；（2）D中的一些特定元素；（3）D上一些特定函数；（4）D上的一些特定的谓词。,例4 给定解释I如下：1）DI2，3；2）DI中特定元素a=2;3）函数f(x)为 f(2)=3,f(3)=2;4）谓词 F(x)为 F(2)=F,F(3)=T;G(x,y)为G(i,j)=T,i,j=2,3;L(x,y)为 L(2,2)=L(3,3)=T,L(2,3)=L(3,2)=F;在解释I下,求x(F(x)G(x,a)的真值。解:x(F(x)G(x,a)（F（2）G（2，2）（F（3）G（3，2）（FT）（TT）F,例5给定解释I如下：1）DI2，3；2）DI中特定元

46、素a=2;3）函数f(x)为 f(2)=3,f(3)=2;4）谓词 F(x)为 F(2)=F,F(3)=T;G(x,y)为G(i,j)=T,i,j=2,3;L(x,y)为 L(2,2)=L(3,3)=T,L(2,3)=L(3,2)=F;在解释I下,求x(F(f(x)G(x,f(x)的真值。解：x(F(f(x)G(x,f(x)（F(f(2）G（2，f（2）(F(f(3)G(3,f(3)(F(3)G(2,3)(F(2)G(3,2)(TT)(FT)T,例6 给定解释I如下：1）DI2，3；2）DI中特定元素a=2;3）函数f(x)为 f(2)=3,f(3)=2;4）谓词 F(x)为 F(2)=F,F

47、(3)=T;G(x,y)为G(i,j)=T,i,j=2,3;L(x,y)为 L(2,2)=L(3,3)=T,L(2,3)=L(3,2)=F;在解释I下,求 xyL(x,y)的真值。解：xyL(x,y)(L(2,2)(L(2,3)(L(3,2)L(3,3)TTT,4、谓词公式的类型定义 设A为一谓词公式，如果A在任何解释下都是真的，则称A为逻辑有效式（或称永真式）；如果A在任何解释下都是假 的，则称A是矛盾式（或称永假式）；若至少存在一个解释使A为真，则称A是可满足式。,例7 判断下列公式中哪些是逻辑有效式?哪些是矛盾式?（1）x F（x）xF（x）解:(1)设I为任意的解释,其个体域为D.若存

48、在x0 D,使得F（x0）为假,则x F（x）为假,所以x F（x）xF（x）为真.若对任意的x D,都有F（x）为真,则有 x F（x）,xF（x）为真,所以x F（x）xF（x）为真.故在任何解释I下,原公式为真,由于I的任意性,所以原公式为逻辑有效式。,（2）x F（x）(xyG（x,y）x F（x）)解：因为P(QP)P(QP)P(QP)(PP)QT由于P(QP)是重言式,而(2)中公式是该式的代换实例,因而（2）是逻辑有效式。（3）x F（x）(xF(x)yG（y）)解：因为 P(PQ)P(PQ)(PP)Q T由于P(PQ)是重言式,而(3)中公式是该式的代换实例,因而是逻辑有效式。

49、,（4）(F(x,y)R(x,y)R(x,y)解：因为(PQ)Q(PQ)Q PQQ F(4)中公式是(PQ)Q的代换实例,而(PQ)Q是重言式,因而(4)中的公式是逻辑有效式。,25 谓词演算的等价式与蕴涵式 定义25.1 设A和B是谓词公式，若A和B在任何解释下的取值都相同，则称A和B是等价的，记为AB。（1）命题公式的推广：如：x（P(x)Q(x)x(P（x）Q(x)x P(x)yR（x,y）(x P(x)yR(x,y)x H（x,y）x H（x,y）F,(2)量词与联结词之间的关系例1 设P(x):x今天来上课,则p(x):x今天没来上课.不是所有的人今天来上课与存在一些人今天没来上课意

50、义相同.即:x P（x）x P（x）不存在一些人今天来上课与所有的人今天都没来上课相同.x P（x）x P（x）关于量词的转化律可以在有限个体域上证明.,(3)量词作用域的扩张与收缩x(A（x）B)(x A（x）B)x(A（x）B)(x A（x）B)x(A（x）B)(x P（x）B)x(A（x）B)(x P（x）B)(x A（x）B)x(A（x）B)(x A（x）B)x(A（x）B)(Bx A（x）)x(BA（x）)(Bx A（x）)x(B A（x）),例2 证明(x A（x）B)x(A（x）B)证明:(x A（x）B)x A（x）B x A（x）B x(A（x）B)x(A（x）B),(4)量