《命题逻辑基础》PPT课件.ppt

第八章 命题逻辑基础,孔子是孔仲尼；孔子是人；人是动物。这三句中“是”的符号含义分别为：“=”“”“”。,程序=算法+数据；算法=逻辑+控制。著名计算机软件设计大师戴克斯特拉（）曾经这样说：“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话，就要回去学逻辑。”我国著名数理逻辑学家甚至说得更加直截了当：“事实上，程序设计或者就是数理逻辑，或者是用计算机语言书写的数理逻辑，或者是数理逻辑在计算机上的应用。”可以说计算机的本质结构就是逻辑结构。,本章和下一章介绍数理逻辑的两个最基本逻辑-命题逻辑和谓词逻辑的基础。,8 1 命题与逻辑联结词,811 命题,“今天北京是阴天”，“我们班是三好班集体”，“1/5是自然数”，“公鸡能下蛋”，象这些表示判断的语句都是命题，也就是说命题（propositions）是表示判断的陈述句。称符合事实的判断其命题真值为真（true），记为“T”或“1”；不符合事实的判断其命题真值为假（false），记为“F”或“0”。,例8.1 判断下列语句哪些是命题；对于是命题的其真值是什么？（1）台湾是中国的一部分。（2）多伦多是加拿大的首都。（3）2是偶数并且也是素数。（4）天津解放的那天有100个婴儿出生。（5）大于2的偶数均可分解为两个质数的和（哥德巴赫猜 想）。（6）第28届奥林匹克运动会开幕时北京天晴。（7）好过瘾啊！（8）你去上机吗？（9）请随手关门！（10）我希望有一台笔记本电脑。（11）我只给那些不给自己刮胡子的人刮胡子。,解：显然（1），（2），（3）都是命题，并且（1）,（3）真值为真，（2）真值为假。事实上（4）,（5），（6）也是命题，因为它们都表示判断，虽然我们现在甚至将来一段时间都不知道它们是否符合客观实际，可他们确实是都表示对客观事物的判断。也就是说一个语句是否表示一个判断即能否分辨真假与我们是否知道它的真假是两回事。（7），（8）分别是感叹句和疑问句，（9），（10）都是祈使句，它们都不表示一个判断，因此都不是命题。（11）是著名的理发师悖论，悖论是自相矛盾的，即无论真假都会导致矛盾，（11）将导出“我”既不能给自己刮胡子，又不能不给自己刮胡子的矛盾结论。故它不是命题。,一个主语一个谓语，我们称这样的命题为原子命题(atoms)或简单命题，而由两个或更多个原子命题和连词组成的命题为复合命题（compositive propositions）。把连接原子命题的连结词称为逻辑联结词（logical connectives）或命题联结词。,一般用大写英文字母或带下标的大写字母如P，Q，A，B，P1,P2，来表示命题，若P表示一个确切的命题，则称其为命题常元（propositional constants）.若P表示任意一个命题，则称其为命题变元（propositional variables）。对一个命题变元指定它一个命题或一个真值，叫做赋值或真值指派(assignments)，,812 逻辑联结词,例8.2 下列语句都是复合命题，其中带下划线的词为逻辑联结词：（1）3不是奇数（并非3是奇数）。（2）今晚我去书店或者去打球。（3）他去了教室，也去了实验室。（用“又”表示逻辑联结词“并且”）（4）你作硬件，我作软件。（用逗号表示逻辑联结词“并且”）（5）如果有辆车，那么我去接你。（6）偶数a是质数，当且仅当a=2。,本节主要介绍上例所涉及的五个逻辑联接词，它们是逻辑中最基本最重要的逻辑联接词。,否定词(negation)“并非”（not），用符号 表示。设P表示一命题，那么 P表示命题P的否定。P真时 P假，而P假时 P真。,表8.1,例8.3 设P 表示“整数都是自然数”，则P表示“并非整数都是自然数”或“整数不都是自然数”，而不是“整数都不是自然数”。,合取词(conjunction)“并且”（and），用符号表示。设P，Q表示两命题，那么PQ表示合取P和Q所得的命题，当P和Q同时为真时PQ真，否则PQ为假。,表8.2,析取词(disjunction)“或”（or）用符号表示。设P，Q表示两命题，那么PQ表示P和Q的析取，当P和Q有一为真时，PQ为真，只有当P和Q均假时PQ为假。,表8.3,条件词(condition)“如果，那么”（ifthen），用符号表示。设P，Q表示两命题，那么PQ表示命题“如果P，那么Q”，并称P称为前件，Q称为后件。当P真而Q假时，命题PQ为假，否则均认为PQ为真。表8.4,例8.4“如果2+2=5，那么雪是黑的”“如果我是美国总统，我就不那样对待萨达姆”，都是真值为“真”的命题。某售房合同上写“如您在七日内交齐全部房款，则返给业主房款总额的1%”，那么只有当“您在七日内交齐全部房款，而房产公司又没返给业主房款总额的1%”才算违反合同。,双条件词(bicondition)“当且仅当”（if and only if），用符号表示之。设P，Q为两命题，那么PQ表示命题“P当且仅当Q”，且当P与Q同真值时PQ为真，否则为假。PQ读作“P双条件Q”或“P当且仅当Q”。表8.5描述了其真值状况。表8.5,813 命题公式与真值表,定义8.1 一个命题公式（proposition formula）按如下规则生成：（1）命题常元和命题变元是命题公式，也称为原子公式或原子。（2）如果A，B是命题公式，那么A，（AB），（AB），（AB），（AB）也是命题公式。（3）只有有限步使用规则（1），（2）所组成的符号串是命题公式。如：（PR），(P(QR)，（QP）都是命题公式，但（PQ），PR很明显都不合法，因而都不是命题公式。为简便起见，我们约定：（1）公式最外层括号一律可省略。（2）联结词运算的优先级依次为：，(，)，例如,PQ(RQS)所表示的是公式(P)(Q(RQ)S),把所有的变化情况对应的汇总一张表，即为该公式的真值表（truth table）。,定义8.2 B称为公式A的 子公式（sub formula），如果B是公式A的一部分，且B也为一公式。,例8.4构造公式PQ的真值表。解：该公式的真值表为：表8.6,说明：（1）若公式中含有两个命题变元，则真值组合共有4组；若公式中含有三个命题变元，则真值组合共有8组；即若公式中含有n个命题变元，则真值组合共有2n组,且为所有n位二进制数。（2）为简化计算，可以逐步算出各子公式的真值，最后求出所求公式的真值。,例8.5 求公式（PQ）PQ的真值表。解：该公式的真值表为：表8.7,例8.6 作出公式(p(qr)的真值表。解：该公式的真值表为:表8.8,814 语句的形式化,例8.7 将下列语句形式化：（1）海洋聪明但不用功。（2）我和他既是兄弟又是同学。（3）我和你之间至少有一个要去海南岛。解：（1）设A：海洋聪明，B：海洋用功，则原命题形式化为：AB。（2）设P：我和他是兄弟，Q：我和他是同学，则原命题形式化为：PQ。（3）设P：我去海南岛，Q：你去海南岛。则原命题形式化为：PQ。,解：（4）设P1：狗急了，P2：狗跳墙，则原命题形式化为：P1P2。（5）设A：你购买的电脑超过了一年，B：你的保修单有效。则原命题形式化为：BA。,（4）狗急跳墙。（5）只有你购买的电脑不超过一年，你的保修单才有效。,我们不难得出将语句形式化的步骤是：将所给语句所包含的原子命题找出，并将它们用符号表示；选用恰当逻辑联接词，将所给语句形式化；必要时可将原语句改变描述方式，使其能形式化，但一定要保持与原意等价。,例8.8 将下列语句符号化：（1）仅当计算机无病毒，它才正常工作。（2）除非我有特殊原因，否则我不会放弃学习。（3）如果他没来见你，那么他或者是生病了，或者是不在本地。解：（1）设P：计算机有病毒，Q：计算机能正常工作，则原命题符号化为：QP。（2）设P：我有特殊原因，Q：我放弃学习，则原命题符号化为：PQ。（3）设P：他来见你，Q：他生病，R：他在本地。则原命题符号化为：P(QR),（4）如果袁翼和王津都是聪明人，那么他们俩不会都去。（5）风雨无阻，我去上学。解：（4）设P：袁翼聪明，Q：王津聪明，R：袁翼会去，S：王津会去。则原命题符号化为：(PQ)(RS)。（5）设A：天刮风，B：天下雨，C：我去北京。则原命题符号化为：(ABC)(ABC)(ABC)(ABC)注意：一个语句形式化未必是惟一的。,