离散数学课堂PPT.ppt

《离散数学课堂PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学课堂PPT.ppt（442页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章 命题逻辑命题逻辑11 命题及其表示法命题及其表示法1.什么是命题什么是命题命题：能判断真假的陈述句。命题：能判断真假的陈述句。命题的值叫它的真值。命题的值叫它的真值。真值：真值：“真真”：表示判断正确。记作：表示判断正确。记作True，用，用T表示。表示。“假假”：表示判断错误。记作：表示判断错误。记作False，用，用F表示。表示。1例例1 判断下列句子中哪些是命题？判断下列句子中哪些是命题？（1）2是素数。是素数。（2）雪是黑色的。）雪是黑色的。（3）2+3=5（4）明年）明年10月月1日是晴天。日是晴天。（5）3能被能被2整除。整除。（6）这朵花真好看呀！）这朵花真好看呀！

2、（7）明天下午有会吗？）明天下午有会吗？（8）请关上门！）请关上门！（9）X+Y5（10）地球外的星球上也有人。）地球外的星球上也有人。（11）我正在说谎。）我正在说谎。22命题的符号化表示命题的符号化表示 命题的符号化就是用符号表示命题。命题的符号化就是用符号表示命题。简单命题（或原子命题）：简单陈述句表示简单命题（或原子命题）：简单陈述句表示的命题。用的命题。用P，Q，R,Pi,Qi,Ri,表示。表示。例例 P:2是偶数。是偶数。Q:雪是黑色的。雪是黑色的。命题常量（或命题常元）：简单命题。命题常量（或命题常元）：简单命题。命题变项（或命题变元）：真值可以变化的命题变项（或命题变元）：真值

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

4、P Q(:表示和表示和)（3）设）设P：林芳学过英语；：林芳学过英语；Q：林芳学过日语。：林芳学过日语。P Q(:表示或表示或)（4）设）设P：角：角A和角和角B是对顶角；是对顶角；Q：角：角A 等于角等于角B。PQ（个表示如果个表示如果则则）512.联结词定义定义12.1 设P为任一命题，P的否定是一个新的命题，称为P的否定式，否定式，记作P。为否定联结词。否定联结词。PP T F F T例例 p：3是偶数。是偶数。p：3不是偶数。不是偶数。6定义定义12.2 设P、Q为两命题，复合命题“P并且Q”（或“P和Q”）称为 P与Q的合取式，合取式，记作PQ，为合取联结词。合取联结词。表示自然语言

5、中的“既又”，“不仅而且”，“虽然但是”PQP QTTTTFFFTFFFF7例例3将下列命题符号化。将下列命题符号化。（1）李平既聪明又用功。）李平既聪明又用功。（2）李平虽然聪明，但不用功。）李平虽然聪明，但不用功。（3）李平不但聪明，而且用功。）李平不但聪明，而且用功。（3）李平不是不聪明，而是不用功。）李平不是不聪明，而是不用功。解：设解：设P：李平聪明；：李平聪明；Q：李平用功。：李平用功。（1）P Q（2）P Q（3）P Q（4）（P）Q注意：不是见到注意：不是见到“和和”、“与与”就用就用。例：例：“李文和李武是兄弟李文和李武是兄弟”，“王芳和陈兰是好朋友王芳和陈兰是好朋友”是简是

6、简单命题。单命题。8定义定义12.3 设P、Q为两命题，复合命题“P或Q”称为 P与Q的析取式，析取式，记作PQ，为析取联结析取联结词。词。PQP QTTTTFTFTTFFF9 析取式析取式P Q表示的是一种相容性或，即允许表示的是一种相容性或，即允许P和和Q同时为真。同时为真。例：例：“王燕学过英语或日语王燕学过英语或日语”P Q自然语言中的自然语言中的“或或”具有二义性，有时表示具有二义性，有时表示不相容的或。不相容的或。例：例：“派小王或小李中的一人去开会派小王或小李中的一人去开会”。为排斥。为排斥性的或。性的或。P：派小王去开会；：派小王去开会；Q：派小李去开会。：派小李去开会。（P

7、Q）（P Q），（P Q）（P Q）10定义定义12.4 设P、Q为两命题，复合命题“如果P，则Q”称作 P与Q的蕴涵式，蕴涵式，记作PQ，为蕴涵联蕴涵联结词。结词。PQP QTTTTFFFTTFFT11 在PQ中，Q是P的必要条件，P是Q的充分条件。表示自然语言“只要P就Q”，“P仅当Q”，“只有Q，才P”注意：注意：1.在自然语言中，在自然语言中，“如果如果P，则，则Q”中的中的P与与Q往往有某往往有某 种内在的联系，但在数理逻辑中，种内在的联系，但在数理逻辑中，PQ中的中的P与与Q不一定有内在的联系。不一定有内在的联系。2.在数学中，在数学中，“如果如果P，则，则Q”表示表示P为真，为真

8、，Q为真的为真的逻辑关系，但在数理逻辑中，当逻辑关系，但在数理逻辑中，当P为假时为假时PQ为真。为真。12例例4将下列命题符号化。将下列命题符号化。(1)只要不下雨，我就骑自行车上班。只要不下雨，我就骑自行车上班。(2)只有不下雨，我才骑自行车上班。只有不下雨，我才骑自行车上班。(3)若若 2+24，则太阳从东方升起。，则太阳从东方升起。(3)若若 2+24，则太阳从东方升起。，则太阳从东方升起。(4)若若 2+24，则太阳从西方升起。，则太阳从西方升起。(5)若若 2+24，则太阳从西方升起。，则太阳从西方升起。解：在（解：在（1）、（）、（2）中，设）中，设P：天下雨；：天下雨；Q：我骑自

9、行车上：我骑自行车上班。班。（1）PQ（2）Q P在（在（3）（）（6）中，设）中，设P：2+24；Q：太阳从东方升起；：太阳从东方升起；R:太阳从西方升起。太阳从西方升起。（1）PQ，真值为真值为T （2）PQ，真值为真值为T（3）PR，真值为真值为F （4）PR 真值为真值为T13定义定义1-2.5 设P、Q为两命题，复合命题“P当且仅当 Q”称作 P与Q的等价式，等价式，记作P Q，为等价联结等价联结词。词。PQ表示表示P与与Q互为充分必要条件互为充分必要条件。PQP QTTTTFFFTFFFT14例例5将下列命题符号化。将下列命题符号化。（1）2+24，当且仅当，当且仅当3是奇数。是奇

10、数。（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：两圆的面积相等；：两圆的面积相等；Q：两圆的面积相同。：两圆的面积相同。PQ真命题真命题（6）设）设

11、P：两角相等；：两角相等；Q：它们是对顶角。：它们是对顶角。PQ假命题假命题154.5种联结词的优先级顺序：种联结词的优先级顺序：，16 1-3命题公式与翻译命题公式与翻译 1.命题公式命题公式命题公式：由命题常量、命题公式：由命题常量、命题变元命题变元、联结词、括号、联结词、括号 等组成的符号串。等组成的符号串。命题公式中的命题变元称作命题公式的分量。命题公式中的命题变元称作命题公式的分量。17定义定义13.1（1）单个命题常量或命题变）单个命题常量或命题变 元元,Q,R,Pi,Qi,Ri,，F，T是合式公式。是合式公式。（2）如果）如果A是合式公式，则（是合式公式，则（A）也是合式公式。）

12、也是合式公式。（3）如果）如果A、B是合式公式，则（是合式公式，则（A B）、（）、（A B）、（）、（AB）、（）、（AB）也是合式公式。）也是合式公式。（4）只有有限次地应用（）只有有限次地应用（1）（）（3）组成的符号）组成的符号串才是合式公式。串才是合式公式。例：例：P,P,(P),(0 P),P(PQ),(P Q)R)(R)是公式；是公式；PQR,(P),PQ)不是公式。不是公式。182.翻译 翻译就是把自然语言中的有些句子符号化。翻译就是把自然语言中的有些句子符号化。复合命题符号化的基本步骤：复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化。）分析出各简单命题，将它们

13、符号化。（2）使用合适的联结词，把简单命题逐个联结起来，）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。组成复合命题的符号化表示。19例例 将下列命题符号化。将下列命题符号化。（1）小王是游泳冠军或是百米冠军。）小王是游泳冠军或是百米冠军。P Q（2）小王现在在宿舍或在图书馆。）小王现在在宿舍或在图书馆。P Q（排斥性或，不可能同时为真）（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。选小王或小李中的一人当班长。（P Q）（P Q）或）或 （PQ）（排斥性或，可能同时为真）（排斥性或，可能同时为真）PQ原命题原命题PQ（PQ）TTFTFTFTFTFTTFTF

14、FFTF20(4)如果我上街，我就去书店看看，除非我很累。如果我上街，我就去书店看看，除非我很累。R(PQ)或或（R P）Q （除非：如果不）（除非：如果不）(5)王一乐是计算机系的学生，他生于王一乐是计算机系的学生，他生于1968年或年或1969年，他年，他是三好学生。是三好学生。P（Q R）S（6）我们要做到身体好、学习好、工作好，为祖国四化建设）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。而奋斗。A：我们要做到身体好：我们要做到身体好B：我们要做到学习好：我们要做到学习好C：我们要做到工作好：我们要做到工作好P：我们要为祖国四化建设面奋斗。：我们要为祖国四化建设面奋斗。命题符

15、号化形式为：（命题符号化形式为：（A B C）P21 14真值表与等价公式真值表与等价公式1.真值表真值表定义定义14.1含含n个（个（n1）个命题变元（分量）的命题公式，）个命题变元（分量）的命题公式，共有共有2n组真值指派。将命题公式组真值指派。将命题公式A在所有真值指派之下取值在所有真值指派之下取值的情况列成表，称为的情况列成表，称为A的真值表。的真值表。构造真值表的步骤：构造真值表的步骤：(1)找出命题公式中所含的所有命题变元找出命题公式中所含的所有命题变元P1,P2,Pn。列出所。列出所有可能的真值指派。有可能的真值指派。(2)对应每种真值指派，计算命题公式的各层次的值，直到最对应每

16、种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。后计算出命题公式的值。22例例1 构造求构造求P Q的真值表。的真值表。PQPP QTTFTTFFFFTTTFFTT23例例2 给出（给出（P Q）P的真值表。的真值表。PQP QP（P Q）PTTTFFTFFFFFTFTFFFFTF24例例3 给出（给出（P Q）（P Q）的真值表。）的真值表。PQ P QP QP Q（P Q）（P Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT25例例4 给出给出（P Q）（P Q）的真值表。）的真值表。PQP Q（P Q）PQ P Q（P Q）（P Q）T T TFFFFTT

17、 F FTFTTTF T FTTFTTF F FTTTTT 由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为（假），我们把这类公式记为T（F）。如例）。如例4和例和例2262等价公式等价公式 从真值表中可以看到，有些命题公式在分量的各从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如种指派下，其对应的真值都完全相同，如P Q与与PQ的对应真值相同。的对应真值相同。PQPP QPQTTFTTTFFFFFTTTTFFTTT（P Q）（P Q）与）与PQ对应的

18、真值相同。对应的真值相同。27 定义定义14.2 给定两个命题公式给定两个命题公式A和和B，设，设P1，P2，Pn为所有出现于为所有出现于A和和B中的原子变元中的原子变元,若给若给P1，P2，Pn任一组真值指派任一组真值指派,A和和B的真值都相同的真值都相同,则则称称A和和B是是等价等价的或的或逻辑相等逻辑相等。记作。记作AB。例例5 证明证明PQ（PQ）（QP）证明证明 列出真值表列出真值表P Q PQ QP(PQ）(QP）PQT T TTTTT F FTFFF T TFFFF F TTTT2824个重要的等价式个重要的等价式PP 双重否定律双重否定律PP P等幂律等幂律PP PP QQ P

19、交换律交换律P QQ P（P Q）RP（Q R）结合律结合律（P Q）RP（Q R）P（Q R）（P Q）（P R）分配律分配律P（Q R）（P Q）（P R）（P Q）P Q 德德摩根律摩根律（P Q）P Q29P（P Q）P吸收律吸收律P（P Q）PP T T零律零律P F FP FP同一律同一律P T PP P T排中律排中律P P F矛盾律矛盾律PQ P Q蕴涵等价式蕴涵等价式P Q（PQ）（QP）等价等价式等价等价式PQ QP假言易位假言易位P Q P Q等价否定等价式等价否定等价式（PQ）（PQ）P归谬论归谬论 其中其中P、Q和和R代表任意的命题公式代表任意的命题公式。30例例6

20、验证吸收律验证吸收律P（P Q）P和和 P（P Q）PP Q P QP（P Q）P QP（P Q）T T TTTTT F FTTTF T FFTFF F FFFF31定义定义1-4.3 如果如果X是合式公式是合式公式A的一部分的一部分,且且X本身也是一本身也是一个合式个合式 公式公式,则称则称X为公式为公式 A的子公式。的子公式。定理定理14.1如果如果X是合式公式是合式公式A的子公式，若的子公式，若XY，如果，如果将将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即AB。证明证明 因为在相应变元的任一种指派下，因为在相应变元的任一种指派下，X与与Y的真值

21、相同，故的真值相同，故以以Y取代取代X后，公式后，公式B与公式与公式 A在相应的指派下，其真值必相同，在相应的指派下，其真值必相同，故故AB。满足定理满足定理14.1的置换称为等价置换（等价代换）的置换称为等价置换（等价代换）32例例7 证明证明PQ（P Q）证明证明 PQ P Q，（根据蕴涵等价式）（根据蕴涵等价式）P Q（P q），（德），（德摩根律）摩根律）即即Pq（P q）33 例例8 证明证明P(QR)(P Q)R证明证明 P(QR)P(QR)（蕴涵等价式）（蕴涵等价式）P(Q R)（蕴涵等价式）（蕴涵等价式）(P Q)R（结合律）（结合律）(P Q)R（德（德摩根律）摩根律）(P

22、Q)R（蕴涵等价式）（蕴涵等价式）34例例9 证明证明 P(P Q)(P Q)证明证明 P P 1 (同一律同一律)P(Q Q)（排中律）（排中律）(P Q)(P Q)（分配律）（分配律）35练习练习 1.证明证明 Q(P Q)P)T;2.证明证明 (P P)(Q Q)R)F 3.证明证明 (PQ)PP361,证明证明Q(P Q)P)Q(P P)(P Q)（分配律）（分配律）Q(F (P Q)（矛盾律）（矛盾律）Q(P Q)（同一律）（同一律）Q(P Q)（德（德摩根律）摩根律）(Q Q)P（结合律）（结合律）T P（排中律）（排中律）T（零律）（零律）372.证明证明(P P)(Q Q)R)

23、T(Q Q)R)（排中律）（排中律）T(F R)（矛盾律（矛盾律）TF（零律）（零律）T F（蕴涵等值式）（蕴涵等值式）F FF（等幂律）（等幂律）383.证明证明 (PQ)P(P Q)P（蕴涵等价值式）（蕴涵等价值式）P（吸收律）（吸收律）391-5 重言式与蕴涵式重言式与蕴涵式 定义定义15.1 给定一命题公式给定一命题公式，若无论对分量作什么样的指，若无论对分量作什么样的指派，其对应的真值永为派，其对应的真值永为T，则称该命题公式，则称该命题公式 为为重言式重言式或或永真式永真式。定义定义15.2 给定一命题公式给定一命题公式，若无论对分量作什么样的指，若无论对分量作什么样的指派，其对应

24、的真值永为派，其对应的真值永为F，则称该命题公式，则称该命题公式 为为矛盾式矛盾式或或永假式永假式。40 定理定理15.1 任何两个重言式的合取或析取，仍然是一个任何两个重言式的合取或析取，仍然是一个重言式。重言式。定理定理15.2 一个一个 重言式，对同一分量，都重言式，对同一分量，都 用任何合式公用任何合式公式式 置换，其结果仍为一重言式。置换，其结果仍为一重言式。证明证明 由于重言式的真值与分量的指派无关，帮对同一分由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。量以任何合式公式置换后，重言式的真值仍永为真。对于矛盾式也有类似于定理对于矛盾式也有

25、类似于定理15.1和定理和定理51.2的结果。的结果。41例例1 证明证明（PS）R）（P S）R）为）为重言式。重言式。证明证明 因为因为 P PTT，用，用（P S）R）置换）置换P得得 （P S）R）（P S）R）T42 定理定理15.3 设设A、B为两命题公式为两命题公式AB，当且仅当，当且仅当ABB为为一个重言式。一个重言式。证明证明 若若 AB，则，则A、B有相同的真值，即有有相同的真值，即有AB 永为永为T。若若 AB 为重言式，则为重言式，则AB 永为永为T，故故A、B的真值相同，的真值相同，即即AB。43例例2 证明证明（P Q）（P Q）证明证明 做做（P Q）（P Q）的

26、真值表。）的真值表。PQ P QP Q（P Q）P Q（P Q）P QTT TFFFFTTF FFTTTTFT FTFTTTFF FTTTTT由以上真值表可知，由以上真值表可知，（P Q）P Q 为重言式，根为重言式，根据定理据定理15.3得得 （P Q）（P Q）44定义定义15.3 当且仅当当且仅当 PQ Q 是重言式是重言式时，我，我们称称“P P蕴涵涵Q Q”，并并记作作PQPQ。做做PQ QP，PQ，Qp 的真值表的真值表PQ P QPQ QPQPPQTT FFTTTTTF FTFFTTFT TFTTFFFF TTTTTT由此得由此得 PQ QP，QP PQ，因此要因此要PQ，只要证

27、明，只要证明QP，反之亦然。，反之亦然。45要证明要证明PQ，即证，即证PQ 是重言式，对于是重言式，对于PQ 来说，来说，除除P的真值取的真值取T，Q的真值取的真值取F这样一种指派时，这样一种指派时，PQ 的真值的真值为为F外，其余情况外，其余情况PQ 的真值为的真值为T，故要征，故要征PQ，只要对条，只要对条件件PQ 的前件的前件P，指定真值为，指定真值为T，若由此指出，若由此指出Q的真值为的真值为T，则则PQ 为重言式，即为重言式，即PQ 成立；同理，如对条件命题成立；同理，如对条件命题PQ 中，假定后件中，假定后件Q的真值为的真值为F，若由此推出，若由此推出P的真值为的真值为F，即推证

28、了即推证了QP。故故PQ成立。即成立。即 若若P为为T时，推出时，推出Q为为T 或若或若Q为为F时，推出时，推出P为为F 则则PQ。46例例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）P47 常用的蕴涵式如下：常用的蕴涵式如下：1.P Q P2.P Q Q3.PP Q4.PPQ5.QPQ 6.（PQ）P7

29、.（PQ）Q8.P（PQ）Q9.Q（PQ）p10.P（P Q）Q11.（PQ）（QR）PR12.（P Q）（PR）（QR）R13.（PQ）（RS）（P R）（Q S）14.（PQ）（QR）（PR）48 定理定理15.4 设设P、Q为任意两个为任意两个 命题公式，命题公式，PQQ的充分的充分必要条件是必要条件是 P PQQ且且 Q QP P证明证明 若若PQ，则，则PQ为重言式。为重言式。因为因为PQ （PQ）（QP），），故故 PQ为为T，且且QP 为为T，因为因为PQ 且且QP成立。成立。反之，若反之，若PQ 且且QP，则则PQ为为T，且且QP 为为T，因此因此PQ （PQ）（QP）为）为T

30、，即即PQ 这个定理也可以作为两个公式等价的定义。这个定理也可以作为两个公式等价的定义。49蕴涵的几个常用的性质：蕴涵的几个常用的性质：（1）设）设A、B、C为合式公式，若为合式公式，若AB且且A为重言式，则为重言式，则B也也是重是重 言式。言式。证明证明 因为因为 AB 永为永为T，所以当，所以当A为为T时，时，B必必T。（2）若）若AB，BC，则，则 AC 证明证明 由由AB，BC 得得AB，BC 为重言式为重言式 所以（所以（AB）（BC）为重言式，）为重言式，根据（根据（PQ）（QR）PR 所以所以（AB）（BC）AC，由性质（由性质（1）得：）得：AC为重言式，即为重言式，即 AC5

31、0（3）AB，且，且AC，那么，那么A（B C）证明证明 由假设知由假设知AB，AC为重言式。为重言式。设设A这这T，则，则B、C为为T，故故B C为为T，因此因此A（B C）为）为T，若若A为为F，则，则A（B C）为）为T，所以所以A（B C）51（4）若）若AB 且且 CB，则，则A CB 证明证明 因为因为AB 为为T，CB为为T，故（故（AA B）（C B）为）为T，则（则（A C）B 为为T，即即（A C）B为为T，即即 （A C）B为为T，所以（所以（A C）B 52 16 其他联结词其他联结词 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称

32、称作作P和和Q的的“与非与非”。PQ（P Q）PQP QTTFTFTFTTFFT53联结词联结词“”的几个性质：的几个性质：（1）PP （P P）p（2）（PQ）（PQ）（PQ）P Q（3）（）（PP）（QQ）PQ （P q）P Q54 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称作称作P和和Q的的“或非或非”。P Q（P Q）PQP QTTFTFFFTFFFT55联结词联结词“”的几个性质：的几个性质：（1）P P （P P）p（2）（P Q）（PQ）（PQ）P Q（3）（）（PP）（QQ）PQ P Q当有当有n个命题变元时，可构成个命题变元时，可构成

33、22 n种不等价的命题种不等价的命题公式，如公式，如n2时，有时，有16种不等价的命题公式。，见种不等价的命题公式。，见27页页表表16.5。56最小联结词组：对于任何一个命题公式，都能由仅含这些联最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。结词的命题公式等价代换。由于（由于（1）（）（PQQ）（PQ）（QP）（2）（）（PQ）P Q （3）P Q（P Q）（4）P Q（P q）故由故由“”、“”、“”，“”、“”这五个这五个联结词组成的命题公式，必可以由联结词组成的命题公式，必可以由，或或，组成组成的命题公式所替代。的命题公式所替代。57 17 对偶与范式对偶

34、与范式 定义定义17.1在给定的命题公式在给定的命题公式A中，将中，将换成换成，换成换成，若有特殊变元，若有特殊变元F和和T亦相互取代，所得命题公式亦相互取代，所得命题公式A*称为称为A的对的对偶式。偶式。A和和A*互为对偶式。互为对偶式。例例1:P Q与与 P Q,(P Q)与与(P Q)(P Q)R与与 (P Q)R (P T)Q 与与(P F)Q 均为对偶式均为对偶式.例例2：PQ、P Q的对偶式。的对偶式。解：解：PQ(P Q)，PQ的对偶式为的对偶式为(P Q)P Q（P Q），P Q的对偶式为的对偶式为(P Q)58 定理定理17.1设设A和和A*互为对偶式互为对偶式,P1,P2,

35、Pn，是出现在，是出现在A和和A*中的全部的命题变元中的全部的命题变元,则则(1)A(P1,P2,Pn)A*(P1,P2,Pn)(2)A(P1,P2,Pn)A*(P1,P2,Pn)例例:设设 A(P,Q,R)P(Q R)得得:A*(P,Q,R)P(Q R)(1)由由知知:A(P,Q,R)P(Q R)由由知知:A*(P,Q,R)P(Q R)所以所以:A(P,Q,R)A*(P,Q,R)类似地类似地,有有A(P,Q,R)A*(P,Q,R)59 定理定理17.2设设P1,P2,Pn 是出现有命题公式是出现有命题公式A和和B中的所有中的所有命题变元，若命题变元，若A B，则，则A*B*。证明：因为证明：

36、因为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,P2,Pn)因此因此A*B*60例例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

37、（R P）（P（Q（R P）所以所以P（Q（RP）(P（Q（R P）)61 定义定义17.2 一个命题公式一个命题公式 称为称为合取范式合取范式，当且仅当它具有形，当且仅当它具有形式式A1A2 An（n1）。其中）。其中A1，A2，An 都是命题变都是命题变元或其否定所组成的析取式。元或其否定所组成的析取式。例例P(P Q)(P P)(P R)定义定义17.3 一个命题公式一个命题公式 称为称为析取范式析取范式，当且仅当它具有，当且仅当它具有形式形式A1 A2 An（n1）。其中）。其中A1，A2，An 都是命题都是命题变元或其否定所组成的合取式。变元或其否定所组成的合取式。例例(P Q R)

38、(P Q)(P Q R)62求合取范式或求合取范式或 析取范式的步骤：析取范式的步骤：（1）将公式中的联结词化归成）将公式中的联结词化归成、。（2）将）将消去或内移。消去或内移。（3）利用分配律、交换律求合取范式或析取范式。）利用分配律、交换律求合取范式或析取范式。（求合取范式：（求合取范式：对对；求析取范式：求析取范式：对对 ）注意任何命题的析取范式和合取范式都不是唯一的。注意任何命题的析取范式和合取范式都不是唯一的。63例求下面命题公式的合取范式和析取范式。例求下面命题公式的合取范式和析取范式。（P Q）R）P解（解（1）求合取范式）求合取范式（P Q）R）P（P Q）R）P(P Q)R)

39、P(P Q)R)P(P Q)R)P(P Q)R)P(P Q)R)P(P Q P)(R P)（P Q）(R P)(2)求析取范式求析取范式(P Q)R)P(P R)(Q R)PP（P R）(Q R)P(Q R)64练习：求下面命题公式的合取范式和析取范式。练习：求下面命题公式的合取范式和析取范式。（1）求合取范式）求合取范式(PQ)R(P Q)R(P Q)R)(R(P Q)(P Q)R)(R(P Q)(P Q)R)(R P Q)(P R)(Q R)(R P Q)（2）求析取范式）求析取范式(P Q)R)(R P Q)（(P Q)(R P Q)）(R(R P Q)(P Q)R)(P Q)P)(P

40、Q)Q)(R R)(R P)(R Q)(P Q R)(P P Q)(P Q Q)(R R)(P R)(Q R)(P Q R)(P R)(Q R)65定义定义17.4 n个命题变元的合取式，称作布尔合取或小个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。现且仅出现一次。n个命题变元个命题变元 共有共有2n个小项。个小项。例两个命题变元例两个命题变元 P和和Q，其小项为：，其小项为：P Q，P Q，P Q，P Q663个命题变项个命题变项P、Q、R可形成可形成8个小项：个小项：m000 P Q Rm

41、001P Q Rm010P Q R m011P Q Rm100P Q R M101P Q R m110P Q R m111P Q R67小项的性质：小项的性质：（1）每一个小项当其真值指派与编码相同时，其真值为）每一个小项当其真值指派与编码相同时，其真值为T，其余均为，其余均为F。（2）任意两个不同小项的合取永为）任意两个不同小项的合取永为F。（3）m0 m1 m2 m3 m4 m5 m6 m7T68 定义定义17.3 对于给定的命题公式，如果有一个等对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。作原

42、式的主析取范式。定理定理17.3 在真值表中，一个在真值表中，一个 公式的真值为公式的真值为T的的指派所对小项的析取，即为此公式的主析取范式。指派所对小项的析取，即为此公式的主析取范式。69例例6给定给定P Q，P Q和和（P Q），求这些公式的主析），求这些公式的主析取范式。取范式。解：真值表如下：解：真值表如下：PQP QP Q（P Q）TTTTFTFFTTFTTTTFFTFT故故P Q（P Q）（P Q）（P Q）P Q（P Q）（P Q）（P Q）（P Q）（P Q）（P Q）（P Q）70例例7 设一公式设一公式A的真值表如下，求公式的真值表如下，求公式 A的主析取范式。的主析取范式

43、。PQRATTTTTTFFTFTFTFFTFTTFFTFFFFTFFFFT解解 公式公式A的主析取范式的主析取范式 为：为：A（P Q R）（P R R）（P Q R）71例例8 求（求（P Q）（P R）（Q R）的主析取范）的主析取范式。式。解：原式解：原式（P Q（R R）（P R（Q Q）（Q R（P p）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）（P Q R）72例例9求求P（P PQ）（Q P）的主析取）的主析取范式。范式。解：原式解：原式P（P Q）（Q P）P（P Q P）（Q Q P）P（Q

44、P）P（Q Q）（P Q）（P Q）（P Q）（P Q）73求主析取范式的步骤：求主析取范式的步骤：（1）求析取范式。）求析取范式。（2）去掉永假的析取项。）去掉永假的析取项。（3）去掉重复的合取项、合并相同变元。）去掉重复的合取项、合并相同变元。（4）对合取项补入没出现的命题变元。（）对合取项补入没出现的命题变元。（P P）74 定义定义17.6 n个命题变元的析取式，称作布尔析取个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。必须出现且仅出现一次。n个命题变元个命题变元 共有共有2n个小项。个

45、小项。例例 两个命题变元两个命题变元 P和和Q，其小项为：，其小项为：P Q，P Q，P Q，P Q 753个命题变项个命题变项P、Q、R可形成可形成8个大项：个大项：M000 P Q RM001P Q RM010P Q R M011P Q RM100P Q R M101P Q R M110P Q R M111P Q R76大项的性质：大项的性质：（1）每一个大项当其真值指派与编码相同时，其真）每一个大项当其真值指派与编码相同时，其真值为值为F，其余均为，其余均为T。（2）任意两个不同大项的析取永为）任意两个不同大项的析取永为T。（3）M0 M1 M2 M3 M4 M5 M6 M7F77定义定

46、义17.7 对于给定的命题公式，如果有一个等价公对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。的主合取范式。定理定理17.4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F的指的指派所对大项的合取，即为此公式的主合取范式。派所对大项的合取，即为此公式的主合取范式。78例例10 利用真值表求（利用真值表求（P Q）（P R）的主合取范式与主）的主合取范式与主析取范式。析取范式。PQRP QP R（P Q）（P R）TTTTFTTTFTFTTFTFFFTFFFFFFTTFTTFTFFFFFF

47、TFTTFFFFFF79主合取范式：主合取范式：（P Q R）（P Q R）（P Q R）（P Q R）主析取范式：主析取范式：（P Q R）（P Q R）（P Q R）（P Q R）80求主合取范式的步骤：求主合取范式的步骤：（1）求合取范式。）求合取范式。（2）去掉所有为）去掉所有为T的合取项。的合取项。（3）合并相同的析取项和变元。）合并相同的析取项和变元。（4）补入没出现的命题变元。（即添加）补入没出现的命题变元。（即添加P P）81例11 求（P Q）（P R）的主合取范式。）的主合取范式。解：原式解：原式（P Q）P）（P Q）R）（P p）（Q p）（P R）（Q R）（Q p）

48、（P R）（Q R）（Q P（R R）（P R（Q Q）（Q R（P P）（Q P R）（Q P R）（P R Q）（P R Q）（Q R P）（Q R P）（P Q R）（P Q R）（P Q R）（P Q R）82用用表示小项的析取表示小项的析取用用表示大项的合取表示大项的合取例如例如（P Q）（P R）（P Q R）（P Q R）（P Q R）（P Q R）M000 M010 M100 M101 0,2,4,5 m001 m011 m110 m111 1,3,6,783 1-8推理理论推理理论推理是从前提推出结论的思维过程推理是从前提推出结论的思维过程,前提是指已前提是指已知的命题公式知

49、的命题公式,结论是从前提出发应用推理规则推出结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个来的命题公式。前提可以是多个。定义定义18.1设设H1，H2，H n，C是命题公式，若是命题公式，若（H1 H2 Hn）C为重言式为重言式,则称则称C是一组前提是一组前提H1,H2,Hn的有效结论。记作：的有效结论。记作：H1 H2 Hn C 真值表法真值表法推理方法推理方法 直接证法直接证法 间接证法间接证法84（1）真值表法）真值表法 若若H1，H2，H n 都为都为T的行，的行，C也为真；也为真；或若或若C为假的行，为假的行，H1，H2，H n 中至少有一个为假中至少有一个为假则则 H

50、1 H2 Hn C 成立。成立。85例例1 一份统计表格的错误或者是由于材料不可靠，或者是由一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。所以这份统计表格是由于计算有错误。解：设解：设 P：统计表格的错误是由于材料不可靠。：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算不可靠。：统计表格的错误是由于计算不可靠。前提是：前提是：P Q，P ，结论是：是：Q，即，即证明明 （P Q）P QPQP QPTTTFTFTFFTTTFFFT故（故（P Q