离散数学 第6章 命题逻辑

1、离 散 数 学第3编 数理逻辑第六章第六章 命题逻辑命题逻辑6.1 命题的概念与表示 一、基本概念 命题：具有明确的判断结果的陈述句。 两个条件：1.陈述句 2.判断结果唯一确定 真值：命题的判断结果称为真值。真为1,假为0。 真命题：判断结果为真的命题。真值为1。 假命题：判断结果为假的命题。真值为0。 原子命题：命题的真假可以独立确定的命题。 复合命题：由原子命题、联结词和括号组合而成的命题。 命题变项：命题常用P,Q,R等表示，当它们表示任意命题时称为命题变元。1否定 否定表示一个命题的反面，P的否定记作 如果P：天气热，那么 ：天气不热， 如果P：教室里没有人，那么 ：教室里有人。 如

2、果命题P是真命题，则 是假命题。 如果命题P是假命题，则 是真命题。用符号表示为： 如果P的真值为1，则 的真值为0，即 。 如果P的真值为0，则 的真值为1，即 。PPP6.2 命题联结词 PPPP0110 2。合取 两个命题P、Q的合取记作 当P、Q都为真命题时， 才是真命题。P和Q中只要有一个是假命题时， 就是假命题。 命题的合取是将两个简单的命题组合在一起，构成一个复合命题。命题的合取具有两个命题同时成立的含义，“和”、“与”是命题的合取的关键字。命题的合取的真值表如右。QPQPQP 的真值表P Q0 0 00 1 01 0 01 1 1QPQP111001,010,0003。析取 两

3、个命题P和Q的析取记作 命题的析取是将两个简单的命题组合在一起，形成一个复合命题，它具有二者中任一成立即可的含义复合命题的真假是由两个简单命题的真假决定的。 当P,Q中至少有一个是真命题时， 即为真命题。只有当P,Q都是假命题时， 才是假命题。 命题的析取的真值表如右。 QPQPQP 的真值表P Q0 0 00 1 11 0 11 1 1QPQP111, 101, 110,0004。蕴含 两个命题P蕴含Q记作 ，它表示由P是真命题能否推论出Q是真命题。如果那么是蕴含命题的关键字。 如当P是真命题时Q一定是真命题，则 成立。但是，如果P是假命题，则无论Q是真命题还是假命题， 也都成立在蕴含命题中

4、，P 称为蕴含的前项，Q 称为蕴含的后项。当前项为假命题时，蕴含命题一定是真命题。QPQPQP 的真值表P Q0 0 10 1 11 0 01 1 1QP QP 111, 110, 100,0015。等价 如果两个命题P和Q有同时又有 则记作 就是 合取、析取和等价都满足交换律，而蕴含是不满足交换律的。例如， 在一个命题公式中如果没有括号，各种联结词的运算顺序从先到后依次为： QP 的真值表 P Q 0 0 1 0 1 0 1 0 0 1 1 1QP PQ QP QP QP )()(PQQP,PQQPPQQPPQQP, 祈使句、感叹句、带有“也许”、“可能”字样的句子和悖论都不是命题。 将命题

5、符号化的方法是定义命题。不同的定义法，符号化的结果是不同的。课本P.164有6个例子。例如有命题：张三没有病。 如定义P:张三没有病，命题符号化的结果为P， 如定义P:张三有病，命题符号化的结果为 P。再如有命题：张三胖但没有病。 定义：P:张三胖，Q:张三有病，命题符号化的结果为 。要注意：命题只有P才Q，符号化的结果是而不是 。QPPQ QP 例题1： 设P：我们划船，Q：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为 。例题2：设P：他生病了。Q：他出差了。R：我同意他不参加学习。则命题“若不是他生病或出差了，我不会同意他不参加学习”符号化的结果为 。例题3：符号化命题：除非天下

6、雨，否则我们不去郊游。此命题的意义为：只有天下雨，我们才去郊游。P：天下雨，Q：我们去郊游。符号化为：)(QPRQP)(PQ 1.合式公式 单个命题变元是一个合式公式， 如果A是合式公式，则 是合式公式，如果A、B是合式公式，则 是合式公式，有限次运用所得到的符号串是合式公式。2.命题公式 由命题变元、联结词和园括号组成的合式公式称为命题公式。命题公式是没有确定的判断结果的，只有在真值指派下才有确定的判断结果。ABABABA,BA 6.3 命题公式的翻译 6.4 真值表与等价公式一、赋值 对于一个命题公式P中的所有命题变元指定一组真值，则称为P的一个赋值。 如果在某种赋值下，命题公式P的值为1

7、，这种赋值称为成真赋值， 如果在某种赋值下，命题公式P的值为0，这种赋值称为成假赋值。 命题公式P的所有赋值的总和就构成了真值表。二、真值表 在命题公式中，对所有的命题变元指派所有可能取得的真值，从而可以确定此命题公式在各种情况下的真值情况，所得到的表称为真值表。如果对于两个命题公式A和B，在任意一组真值指派下， A和B的真值都相同，则称A和B等值。 记作 。注意： 用于两个命题的等价， 用于两个命题公式的等价，称为等值。两者不可混淆。BA三、等价公式 等价公式又称为命题定律，是14组重要的等值式，在命题公式的化简和证明中经常用到。 课本P.167中有这14组等价公式的汇总表，其中要特别记住的

8、有： 5.分配律 6.吸收律 7.摩根律)()()(RPQPRQP)()()(RPQPRQPPQPPPQPP)()(QPQP)(QPQP)( 9.零律 10.否定律 11.蕴含等价 12.双条件等价 13.假言易位律 14.归谬律PQPQP)()(QPQPPQQP)()(PQQPQPPPPP1001PPPP四、等值演算 用命题定律对命题公式进行化简称为等值演算。例题4： 化简命题公式解：PQPQP)()(PQPQP)()()()(PQPPQP0)(QP)()(PQPPQPQP一、重言式、矛盾式、可满足式 如果命题公式P在各种赋值下的值均为真，则称P为永真式或重言式， 如果命题公式P在各种赋值下

9、的值均为假，则称P为永假式或矛盾式， 如果命题公式P既不是矛盾式，又不是永真式，则称P为可满足式。三、真值表法 判断一个命题公式是重言式、矛盾式还是可满足式，可用真值表法。列出真值表，综观所有的真值。6.5 重言式与蕴含式例题5： 用真值表证明命题公式 是重言式解：)(RQPPPQR0000100111010110111110011101111101111111)(RQPPRQP三、蕴含式 如果命题公式 是永真式是则称“P蕴含Q” 记作 蕴含式有14个重要的命题公式，见课本P.170在证明中经常用到。课本P.170有5处错误。 蕴含式中常用的有：1。化简2。附加3。析取三段论4。假言推理5。拒

10、取式QQPPQP,QQPP)(QQPP)(PQPQ)(QP QP QPP6.6 范式一、析取范式和合取范式 由若干个括号通过析取符号连接而成的命题公式称为析取范式，其中每一个扩号是命题变元或其否定构成的合取式。如 由若干个括号通过合取符号连接而成的命题公式称为合取范式，其中每一个扩号是命题变元或其否定构成的析取式。如 任何命题公式都存在与之等值的析取范式和合取范式，且形式不唯一。)()(TSPRQP)()(TSRQP二、主析取范式 如组成析取范式的每一个括号中都包括所有的命题变项或其否定形式，则该析取范式称为主析取范式。在主析取范式中的每一个括号是一个包括所有的命题变项或其否定形式的简单合取式

11、，称为小项。 如果将小项中各命题变项看成为1，其否定看成为0, 按字母顺序排列后的二进制数为i,该小项表示为 ， 因此，由两个命题变项组成的小项为由三个命题变项组成的小项为 ， 在真值表中，真值为1的项是小项，主析取范式就是真值表中所有真值为1的项的析取范式。im30 mm70 mm例题6 求 的主析取范式解： 小项RQP)(PQR0000000101010000110110000101011101111111RQP)(QPRQPRQPRQPRPRQP)7 , 6 , 5 , 3 , 1 ()(76531mmmmmRQP三、主合取范式 如组成合取范式的每一个括号中都包括所有的命题变项或其否定形

12、式，则该合取范式称为主合取范式。在主合取范式中的每一个括号是一个包括所有的命题变项或其否定形式的简单析取式，称为大项。 如果将大项中各命题变项看成为0，其否定看成为1, 按字母顺序排列后的二进制数为i,该大项表示为 ，注意： 不是 ，而是例如，在某命题公式A中P,Q,R为(0,0,1)和(1,1,1)时真值为0，则A的主合取范式可记作为： iM1M)(RQP)(RQP)7 , 1 ()()(RQPRQP由主析取范式可直接求出主合取范式 例如，上面的例3 主析取范式已经求得，为那么，它的主合取范式为： 有下列结论，请记住： 任意两个小项的合取式为永假式，全体小项的析取式为永真式。 任意两个大项的

13、析取式为永真式，全体大项的合取式为永假式。)7 , 6 , 5 , 3 , 1 ()4 , 2 , 0()()()(RQPRQPRQPRQP)(6.7 命题逻辑的推理理论一、有效结论 如果命题公式 是重言式，则称C是前提集合 的有效结论，记作二、推理方法 真值表法 真值表法就是用真值表验证是重言式。例如，前面的例1就是用真值表证明了： CAAAm)(21,21mAAACAAAm21CAAAm)(21)()()(RPRQQP等值演算法 等值演算法就是用等值演算的方法验证命题公式的化简结果为1。例如，前面的例1证明，证明： )()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()(RPPRQQ)1 ()()(RRQQQ11)(RQ直接证法 先介绍两条规则：P规则：前提中的命题在任何需要时都可以引入。T规则：在推导过程中可根据前提和已得到的结论，按推理规则得到新的结论。推理证明过程的书写方法： 1.在左边第一列中给推理步骤编号， 2.在左边第二列中书写引入的前提和推出的结论， 3.在右边一列中注明运用的规则，是T规则时要注明依据的步骤的编号和推理规则的种类。 E表示运用的是等价公式，I表示运用的是蕴含公式例题7： 证明证明： P TI TI TI P T I P TE TIDDACCBBA)()()(CCCB