资源描述
第一章第一章 命题逻辑命题逻辑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是偶数。是偶数。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是偶数。是偶数。P Q(:表示和表示和)（3）设）设P：林芳学过英语；：林芳学过英语；Q：林芳学过日语。：林芳学过日语。P Q(:表示或表示或)（4）设）设P：角：角A和角和角B是对顶角；是对顶角；Q：角：角A 等于角等于角B。PQ（个表示如果个表示如果则则）12.联结词定义定义12.1 设P为任一命题，P的否定是一个新的命题，称为P的否定式，否定式，记作P。为否定联结词。否定联结词。PP T F F T例例 p：3是偶数。是偶数。p：3不是偶数。不是偶数。定义定义12.2 设P、Q为两命题，复合命题“P并且Q”（或“P和Q”）称为 P与Q的合取式，合取式，记作PQ，为合取联结词。合取联结词。表示自然语言中的“既又”，“不仅而且”，“虽然但是”PQP QTTTTFFFTFFFF例例3将下列命题符号化。将下列命题符号化。（1）李平既聪明又用功。）李平既聪明又用功。（2）李平虽然聪明，但不用功。）李平虽然聪明，但不用功。（3）李平不但聪明，而且用功。）李平不但聪明，而且用功。（3）李平不是不聪明，而是不用功。）李平不是不聪明，而是不用功。解：设解：设P：李平聪明；：李平聪明；Q：李平用功。：李平用功。（1）P Q（2）P Q（3）P Q（4）（P）Q注意：不是见到注意：不是见到“和和”、“与与”就用就用 。例：例：“李文和李武是兄弟李文和李武是兄弟”，“王芳和陈兰是好朋友王芳和陈兰是好朋友”是简单命是简单命题。题。定义定义12.3 设P、Q为两命题，复合命题“P或Q”称为 P与Q的析取式，析取式，记作PQ，为析取联结词。析取联结词。PQP QTTTTFTFTTFFF 析取式析取式P Q表示的是一种相容性或，即允许表示的是一种相容性或，即允许P和和Q同时为真。同时为真。例：例：“王燕学过英语或日语王燕学过英语或日语”P Q自然语言中的自然语言中的“或或”具有二义性，有时表示不具有二义性，有时表示不相容的或。相容的或。例：例：“派小王或小李中的一人去开会派小王或小李中的一人去开会”。为排斥性。为排斥性的或。的或。P：派小王去开会；：派小王去开会；Q：派小李去开会。：派小李去开会。（P Q）（P Q），（P Q）（P Q）定义定义12.4 设P、Q为两命题，复合命题“如果P，则Q”称作 P与Q的蕴涵式，蕴涵式，记作PQ，为蕴涵联结蕴涵联结词。词。PQP QTTTTFFFTTFFT 在PQ中，Q是P的必要条件，P是Q的充分条件。表示自然语言“只要P就Q”，“P仅当Q”，“只有Q，才P”注意：注意：1.在自然语言中，在自然语言中，“如果如果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:太阳从西方升起。太阳从西方升起。（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互为充分必要条件互为充分必要条件。PQP QTTTTFFFTFFFT例例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：两圆的面积相等；：两圆的面积相等；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是合式公式，则（是合式公式，则（A B）、（）、（A B）、（）、（AB）、（）、（AB）也是合式公式。）也是合式公式。（4）只有有限次地应用（）只有有限次地应用（1）（）（3）组成的符号）组成的符号串才是合式公式。串才是合式公式。例：例：P,P,(P),(0 P),P(PQ),(P Q)R)(R)是公式；是公式；PQR,(P),PQ)不是公式。不是公式。2.翻译 翻译就是把自然语言中的有些句子符号化。翻译就是把自然语言中的有些句子符号化。复合命题符号化的基本步骤：复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化。）分析出各简单命题，将它们符号化。（2）使用合适的联结词，把简单命题逐个联结起来，）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。组成复合命题的符号化表示。例例 将下列命题符号化。将下列命题符号化。（1）小王是游泳冠军或是百米冠军。）小王是游泳冠军或是百米冠军。P Q（2）小王现在在宿舍或在图书馆。）小王现在在宿舍或在图书馆。P Q（排斥性或，不可能同时为真）（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。选小王或小李中的一人当班长。（P Q）（P Q）或）或 （PQ）（排斥性或，可能同时为真）（排斥性或，可能同时为真）PQ原命题原命题PQ（PQ）TTFTFTFTFTFTTFTFFFTF(4)如果我上街，我就去书店看看，除非我很累。如果我上街，我就去书店看看，除非我很累。R(PQ)或或（R P）Q （除非：如果不）（除非：如果不）(5)王一乐是计算机系的学生，他生于王一乐是计算机系的学生，他生于1968年或年或1969年，他年，他是三好学生。是三好学生。P（Q R）S（6）我们要做到身体好、学习好、工作好，为祖国四化建设）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。而奋斗。A：我们要做到身体好：我们要做到身体好B：我们要做到学习好：我们要做到学习好C：我们要做到工作好：我们要做到工作好P：我们要为祖国四化建设面奋斗。：我们要为祖国四化建设面奋斗。命题符号化形式为：（命题符号化形式为：（A B C）P 14真值表与等价公式真值表与等价公式1.真值表真值表定义定义14.1含含n个（个（n1）个命题变元（分量）的命题公式，）个命题变元（分量）的命题公式，共有共有2n组真值指派。将命题公式组真值指派。将命题公式A在所有真值指派之下取值在所有真值指派之下取值的情况列成表，称为的情况列成表，称为A的真值表。的真值表。构造真值表的步骤：构造真值表的步骤：(1)找出命题公式中所含的所有命题变元找出命题公式中所含的所有命题变元P1,P2,Pn。列出所。列出所有可能的真值指派。有可能的真值指派。(2)对应每种真值指派，计算命题公式的各层次的值，直到最对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。后计算出命题公式的值。例例1 构造求构造求P Q的真值表。的真值表。PQPP QTTFTTFFFFTTTFFTT例例2 给出（给出（P Q）P的真值表。的真值表。PQP QP（P Q）PTTTFFTFFFFFTFTFFFFTF例例3 给出（给出（P Q）（P Q）的真值表。）的真值表。PQ P QP QP Q（P Q）（P Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT例例4 给出给出（P Q）（P Q）的真值表。）的真值表。PQP Q（P Q）PQ P Q（P Q）（P Q）T T TFFFFTT F FTFTTTF T FTTFTTF F FTTTTT 由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为（假），我们把这类公式记为T（F）。如例）。如例4和例和例22等价公式等价公式 从真值表中可以看到，有些命题公式在分量的各从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如种指派下，其对应的真值都完全相同，如P Q与与PQ的对应真值相同。的对应真值相同。PQPP QPQTTFTTTFFFFFTTTTFFTTT（P Q）（P Q）与）与PQ对应的真值相同。对应的真值相同。定义定义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 TTTT24个重要的等价式个重要的等价式PP 双重否定律双重否定律PP P等幂律等幂律PP PP QQ P交换律交换律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 QP（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代表任意的命题公式代表任意的命题公式。例例6 验证吸收律验证吸收律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 FFFF定义定义1-4.3 如果如果X是合式公式是合式公式A的一部分的一部分,且且X本身也是一本身也是一个合式个合式 公式公式,则称则称X为公式为公式 A的子公式。的子公式。定理定理14.1如果如果X是合式公式是合式公式A的子公式，若的子公式，若XY，如果，如果将将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即AB。证明证明 因为在相应变元的任一种指派下，因为在相应变元的任一种指派下，X与与Y的真值相同，故的真值相同，故以以Y取代取代X后，公式后，公式B与公式与公式 A在相应的指派下，其真值必相同，在相应的指派下，其真值必相同，故故AB。满足定理满足定理14.1的置换称为等价置换（等价代换）的置换称为等价置换（等价代换）例例7 证明证明PQ（P Q）证明证明 PQ P Q，（根据蕴涵等价式）（根据蕴涵等价式）P Q（P q），（德），（德摩根律）摩根律）即即Pq（P q）例例8 证明证明P(QR)(P Q)R证明证明 P(QR)P(QR)（蕴涵等价式）（蕴涵等价式）P(Q R)（蕴涵等价式）（蕴涵等价式）(P Q)R（结合律）（结合律）(P Q)R（德（德摩根律）摩根律）(P Q)R（蕴涵等价式）（蕴涵等价式）例例9 证明证明 P(P Q)(P Q)证明证明 P P 1 (同一律同一律)P(Q Q)（排中律）（排中律）(P Q)(P Q)（分配律）（分配律）练习练习 1.证明证明 Q(P Q)P)T;2.证明证明 (P P)(Q Q)R)F 3.证明证明 (PQ)PP1,证明证明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（零律）（零律）2.证明证明(P P)(Q Q)R)T(Q Q)R)（排中律）（排中律）T(F R)（矛盾律（矛盾律）TF（零律）（零律）T F（蕴涵等值式）（蕴涵等值式）F FF（等幂律）（等幂律）3.证明证明 (PQ)P(P Q)P（蕴涵等价值式）（蕴涵等价值式）P（吸收律）（吸收律）1-5 重言式与蕴涵式重言式与蕴涵式 定义定义15.1 给定一命题公式给定一命题公式，若无论对分量作什么样的指，若无论对分量作什么样的指派，其对应的真值永为派，其对应的真值永为T，则称该命题公式，则称该命题公式 为为重言式重言式或或永真式永真式。定义定义15.2 给定一命题公式给定一命题公式，若无论对分量作什么样的指，若无论对分量作什么样的指派，其对应的真值永为派，其对应的真值永为F，则称该命题公式，则称该命题公式 为为矛盾式矛盾式或或永假式永假式。定理定理15.1 任何两个重言式的合取或析取，仍然是一个任何两个重言式的合取或析取，仍然是一个重言式。重言式。定理定理15.2 一个一个 重言式，对同一分量，都重言式，对同一分量，都 用任何合式公用任何合式公式式 置换，其结果仍为一重言式。置换，其结果仍为一重言式。证明证明 由于重言式的真值与分量的指派无关，帮对同一分由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。量以任何合式公式置换后，重言式的真值仍永为真。对于矛盾式也有类似于定理对于矛盾式也有类似于定理15.1和定理和定理51.2的结果。的结果。例例1 证明证明（PS）R）（P S）R）为）为重言式。重言式。证明证明 因为因为 P PTT，用，用（P S）R）置换）置换P得得 （P S）R）（P S）R）T 定理定理15.3 设设A、B为两命题公式为两命题公式AB，当且仅当，当且仅当ABB为为一个重言式。一个重言式。证明证明 若若 AB，则，则A、B有相同的真值，即有有相同的真值，即有AB 永为永为T。若若 AB 为重言式，则为重言式，则AB 永为永为T，故故A、B的真值相同，的真值相同，即即AB。例例2 证明证明（P Q）（P Q）证明证明 做做（P Q）（P Q）的真值表。）的真值表。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）定义定义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，只要证明，只要证明QP，反之亦然。，反之亦然。要证明要证明PQ，即证，即证PQ 是重言式，对于是重言式，对于PQ 来说，来说，除除P的真值取的真值取T，Q的真值取的真值取F这样一种指派时，这样一种指派时，PQ 的真值的真值为为F外，其余情况外，其余情况PQ 的真值为的真值为T，故要征，故要征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 常用的蕴涵式如下：常用的蕴涵式如下：1.P Q P2.P Q Q3.PP Q4.PPQ5.QPQ 6.（PQ）P7.（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）定理定理15.4 设设P、Q为任意两个为任意两个 命题公式，命题公式，PQQ的充分的充分必要条件是必要条件是P PQQ且且QQP P证明证明 若若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，BC，则，则 AC 证明证明 由由AB，BC 得得AB，BC 为重言式为重言式 所以（所以（AB）（BC）为重言式，）为重言式，根据（根据（PQ）（QR）PR 所以所以（AB）（BC）AC，由性质（由性质（1）得：）得：AC为重言式，即为重言式，即 AC（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）（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 16 其他联结词其他联结词 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称称作作P和和Q的的“与非与非”。PQ（P Q）PQP QTTFTFTFTTFFT联结词联结词“”的几个性质：的几个性质：（1）PP （P P）p（2）（PQ）（PQ）（PQ）P Q（3）（）（PP）（QQ）PQ （P q）P Q 定义定义16.3 设设P、Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称作称作P和和Q的的“或非或非”。P Q（P Q）PQP QTTFTFFFTFFFT联结词联结词“”的几个性质：的几个性质：（1）P P （P P）p（2）（P Q）（PQ）（PQ）PQ（3）（）（PP）（QQ）PQ PQ当有当有n个命题变元时，可构成个命题变元时，可构成22 n种不等价的命题种不等价的命题公式，如公式，如n2时，有时，有16种不等价的命题公式。，见种不等价的命题公式。，见27页页表表16.5。最小联结词组：对于任何一个命题公式，都能由仅含这些联最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。结词的命题公式等价代换。由于（由于（1）（）（PQQ）（PQ）（QP）（2）（）（PQ）P Q （3）P Q（P Q）（4）P Q（P q）故由故由“”、“”、“”，“”、“”这五个联结词组成的这五个联结词组成的命题公式，必可以由命题公式，必可以由，或或，组成的命题公式所替组成的命题公式所替代。代。17 对偶与范式对偶与范式 定义定义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)定理定理17.1设设A和和A*互为对偶式互为对偶式,P1,P2,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)定理定理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,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（R P）（P（Q（R P）所以所以P（Q（RP）(P（Q（R P）)定义定义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)(P Q)(P Q R)求合取范式或求合取范式或 析取范式的步骤：析取范式的步骤：（1）将公式中的联结词化归成）将公式中的联结词化归成、。（2）将）将消去或内移。消去或内移。（3）利用分配律、交换律求合取范式或析取范式。）利用分配律、交换律求合取范式或析取范式。（求合取范式：（求合取范式：对对；求析取范式：求析取范式：对对 ）注意任何命题的析取范式和合取范式都不是唯一的。注意任何命题的析取范式和合取范式都不是唯一的。例求下面命题公式的合取范式和析取范式。例求下面命题公式的合取范式和析取范式。（P Q）R）P解（解（1）求合取范式）求合取范式（P Q）R）P（P Q）R）P(P Q)R)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)练习：求下面命题公式的合取范式和析取范式。练习：求下面命题公式的合取范式和析取范式。（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 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)定义定义17.4 n个命题变元的合取式，称作布尔合取或小个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。现且仅出现一次。n个命题变元个命题变元 共有共有2n个小项。个小项。例两个命题变元例两个命题变元 P和和Q，其小项为：，其小项为：P Q，P Q，P Q，P Q3个命题变项个命题变项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 R小项的性质：小项的性质：（1）每一个小项当其真值指派与编码相同时，其真值为）每一个小项当其真值指派与编码相同时，其真值为T，其余均为，其余均为F。（2）任意两个不同小项的合取永为）任意两个不同小项的合取永为F。（3）m0 m1 m2 m3 m4 m5 m6 m7T 定义定义17.3 对于给定的命题公式，如果有一个等对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。作原式的主析取范式。定理定理17.3 在真值表中，一个在真值表中，一个 公式的真值为公式的真值为T的的指派所对小项的析取，即为此公式的主析取范式。指派所对小项的析取，即为此公式的主析取范式。例例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）例例7 设一公式设一公式A的真值表如下，求公式的真值表如下，求公式 A的主析取范式。的主析取范式。PQRATTTTTTFFTFTFTFFTFTTFFTFFFFTFFFFT解解 公式公式A的主析取范式的主析取范式 为：为：A（P Q R）（P R R）（P Q R）例例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）例例9求求P（P PQ）（Q P）的主析取）的主析取范式。范式。解：原式解：原式P（P Q）（Q P）P（P Q P）（Q Q P）P（Q P）P（Q Q）（P Q）（P Q）（P Q）（P Q）求主析取范式的步骤：求主析取范式的步骤：（1）求析取范式。）求析取范式。（2）去掉永假的析取项。）去掉永假的析取项。（3）去掉重复的合取项、合并相同变元。）去掉重复的合取项、合并相同变元。（4）对合取项补入没出现的命题变元。（）对合取项补入没出现的命题变元。（P P）定义定义17.6 n个命题变元的析取式，称作布尔析取个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。必须出现且仅出现一次。n个命题变元个命题变元 共有共有2n个小项。个小项。例例 两个命题变元两个命题变元 P和和Q，其小项为：，其小项为：P Q，P Q，P Q，P Q 3个命题变项个命题变项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 R大项的性质：大项的性质：（1）每一个大项当其真值指派与编码相同时，其真）每一个大项当其真值指派与编码相同时，其真值为值为F，其余均为，其余均为T。（2）任意两个不同大项的析取永为）任意两个不同大项的析取永为T。（3）M0 M1 M2 M3 M4 M5 M6 M7F定义定义17.7 对于给定的命题公式，如果有一个等价公对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。的主合取范式。定理定理17.4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F的指的指派所对大项的合取，即为此公式的主合取范式。派所对大项的合取，即为此公式的主合取范式。例例10 利用真值表求（利用真值表求（P Q）（P R）的主合取范式与主）的主合取范式与主析取范式。析取范式。PQRP QP R（P Q）（P R）TTTTFTTTFTFTTFTFFFTFFFFFFTTFTTFTFFFFFFTFTTFFFFFF主合取范式：主合取范式：（P Q R）（P Q R）（P Q R）（P Q R）主析取范式：主析取范式：（P Q R）（P Q R）（P Q R）（P Q R）求主合取范式的步骤：求主合取范式的步骤：（1）求合取范式。）求合取范式。（2）去掉所有为）去掉所有为T的合取项。的合取项。（3）合并相同的析取项和变元。）合并相同的析取项和变元。（4）补入没出现的命题变元。（即添加）补入没出现的命题变元。（即添加P P）例11 求（P Q）（P R）的主合取范式。）的主合取范式。解：原式解：原式（P Q）P）（P Q）R）（P p）（Q p）（P R）（Q R）（Q p）（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）用用表示小项的析取表示小项的析取用用表示大项的合取表示大项的合取例如例如（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,7 1-8推理理论推理理论推理是从前提推出结论的思维过程推理是从前提推出结论的思维过程,前提是指已前提是指已知的命题公式知的命题公式,结论是从前提出发应用推理规则推出结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个来的命题公式。前提可以是多个。定义定义18.1设设H1，H2，H n，C是命题公式，若是命题公式，若（H1 H2 Hn）C为重言式为重言式,则称则称C是一组前提是一组前提H1,H2,Hn的有效结论。记作：的有效结论。记作：H1 H2 Hn C 真值表法真值表法推理方法推理方法 直接证法直接证法 间接证法间接证法（1）真值表法）真值表法 若若H1，H2，H n 都为都为T的行，的行，C也为真；也为真；或若或若C为假的行，为假的行，H1，H2，H n 中至少有一个为假中至少有一个为假则则 H1 H2 Hn C 成立。成立。例例1 一份统计表格的错误或者是由于材料不可靠，或者是由于一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。以这份统计表格是由于计算有错误。解：设解：设 P：统计表格的错误是由于材料不可靠。：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算不可靠。：统计表格的错误是由于计算不可靠。前提是：前提是：P Q，P ，结论是：，结论是：Q，即证明，即证明 （P Q）P QPQP QPTTTFTFTFFTTTFFFT故（故（P Q）P Q 例例2 如果张老师来了，这个问题可以得到解答，如如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。老师或李老师来了，这个问题就可以得到解答。解：设解：设P：张老师来了。：张老师来了。Q：李老师来了。：李老师来了。R：这个问题可以得到解答。：这个问题可以得到解答。本题可译为：本题可译为：（P R）（QR）（P Q）RPQRPRQRP QTTTTTTTTFFFTTFTTTTTFFFTTFTTTTTFTFTFTFFTTTFFFFTTF（2）直接证法）直接证法 就是由一组前提，利用一些公认的推理规则，根据已知的等就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。价公式或蕴涵公式，推出有效结论。P规则：前提在推导过程中随时可以引用。规则：前提在推导过程中随时可以引用。T规则：已经推出的公式在以后的推导过程中可随时引用。规则：已经推出的公式在以后的推导过程中可随时引用。常用蕴涵式见常用蕴涵式见43页表页表18.3例例1 证明（证明（P Q）（PR）（QS）SR 证法证法1（1）P Q 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）S R T（7）E 证法证法2（1）PR P （2）P QR Q T（1）I （3）QS P （4）Q RS R T（3）I （5）P QS R T（2），（），（4）I （6）P Q P （7）S R T（5），（），（6）I例例2 证明（证明（W R）V，VC S，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)（W R）V P (9)V(C S)P (10)（W R）(C S)T(8),(9)I (11)(（W R）T(7),(10)I (12)W R T(11)E (13)W T(12)E(3)间接证法间接证法1(归谬法归谬法)要证要证 H1 H2 Hn C 即要证即要证 H1 H2 Hn C 为重言式为重言式 H1 H2 Hn C (H1 H2 Hn)C (H1 H2 Hn C)因此只要证因此只要证 H1 H2 Hn C 为矛盾式为矛盾式.例例3 证明证明 AB,(B C)可逻辑推出可逻辑推出A证明证明(1)AB P (2)A P(附加前提附加前提)(3)(B C)P (4)B C T(3)E (5)B T(1),(2)I (6)B T(4)I (7)B B(矛盾矛盾)T(5),(6)I 例例4 证明证明(P Q)(PR)(QS)S R证明证明(1)(S R)P (2)S R T(1)E (3)P Q P (4)PQ T(3)E (5)QS P (6)PS T(4),(5)I (7)SP T(6)(8)(S R)(P R)T(7)I (9)P R T(2),(8)I (10)PR P (11)P R T(10)E (12)(P R)T(11)E (13)(P R)(P R)(矛盾)T(9),(12)I(4)间接证法间接证法2(附加前提法附加前提法)要证要证 H1 H2 Hn RC 只要证只要证 (H1 H2 Hn)(R C)为重言式为重言式 (H1 H2 Hn)(R C)(H1 H2 Hn)(R C)(H1 H2 Hn R)C(H1 H2 Hn R)C 只要证只要证 (H1 H2 Hn R)C 由由(S R)C 证得证得S(R C)称为称为CP规则规则。例例5 证明证明 A(BC),D A,B 重言蕴涵重言蕴涵 DC证明证明(1)D P(附加前提附加前提)(2)D A 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 设有下列情况设有下列情况,结论是否有效结论是否有效?(a)或者是天晴或者是天晴,或者是下雨。或者是下雨。(b)如果是天晴，我去看电影。如果是天晴，我去看电影。(c)如果我去看电影，我就不看书。如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。结论：如果我在看书则天在下雨。解解 若设若设 M：天晴。：天晴。Q：下雨：下雨。S：我看电影。：我看电影。R：我看书。：我看书。即证：即证：MQQ，MMS，SR，推出，推出RQ其中其中 M Q(MQQ）(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 第二章第二章 谓词逻辑谓词逻辑 原子命题是命题逻辑研究的基本单位原子命题是命题逻辑研究的基本单位,没有对原子没有对原子的内部结构及其相互之间的逻辑关系进行分析的内部结构及其相互之间的逻辑关系进行分析,这样这样就无法处理一些简单而又常见的推理问题。就无法处理一些简单而又常见的推理问题。例如例如:所有的人都是要死的，苏格拉底是人，所以所有的人都是要死的，苏格拉底是人，所以,苏苏格拉底是要死的。格拉底是要死的。P:所有的人是要死的所有的人是要死的.Q:苏格拉底是人苏格拉底是人.R:所以所以,苏格拉底是要死的苏格拉底是要死的P QRR 不是重言式。不是重言式。21 谓词的概念与表示谓词的概念与表示原子命题由主语和谓语两部分组成。原子命题由主语和谓语两部分组成。主语一般是客体。主语一般是客体。客体：可以是一个具体的事物，也可以是一种抽象客体：可以是一个具体的事物，也可以是一种抽象事物。是命题所研究的对象。事物。是命题所研究的对象。谓词：用以刻划客体的性质或客体之间的性质。谓词：用以刻划客体的性质或客体之间的性质。例例 李明是一个学生。李明是一个学生。李明比王杰高。李明比王杰高。哥白尼指出地球绕着太阳转。哥白尼指出地球绕着太阳转。谓词用大写字母表示。谓词用大写字母表示。客体名称用小写字母表示。客体名称用小写字母表示。客体常元：客体常元：表示具体或特定的客体的词。表示具体或特定的客体的词。一般用小写字母一般用小写字母a,b,c,表示。表示。客体变元：客体变元：表示抽象的或泛指的客体的词。表示抽象的或泛指的客体的词。一般用小写字母一般用小写字母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时，它本身就是一个命题。时，它本身就是一个命题。由一个或几个简单命题函数以及联结词组合而成由一个或几个简单命题函数以及联结词组合而成的表达式称为的表达式称为复合命题函数复合命题函数。例例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）。）。命题函数不是命题，只有客体变元取特定客体命题函数不是命题，只有客体变元取特定客体名称时，才能成为命题。名称时，才能成为命题。个体域个体域：客体变元的取值范围。：客体变元的取值范围。个体域可以是有限的，也可以是无限的。个体域可以是有限的，也可以是无限的。例例 学生、工人，实数，学生、工人，实数，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是质数。是质数。符号化为：符号化为：（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活百岁以上。活百岁以上。第二种情况：考虑个体域为全总个体域，第二种情况：考虑个体域为全总个体域，对所有个体而言，如果它是人，则它是要死的。对所有个体而言，如果它是人，则它是要死的。存在着个体，它是人并且活百岁以上存在着个体，它是人并且活百岁以上/引进特性谓词：引进特性谓词：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）是）是原子谓词公式原子谓词公
展开阅读全文