命题与逻辑连接词

《命题与逻辑连接词》由会员分享，可在线阅读，更多相关《命题与逻辑连接词（65页珍藏版）》请在金锄头文库上搜索。

1、第八章 命题逻辑基础 我们在日常生活中经常会遇到推 理.日常生活中使用的语言常称为 自然语言或元语言，而自然语言 含义丰富，有时甚至含糊多义。 例如我们说三句带“是”的语句： 孔子是孔仲尼； 孔子是人；人是动物。 这三句中 “是”的符号含义分别为 “=”、“”、“”。 因此用自然语言进行的推理非常 灵活，结论不定。 数理逻辑（mathematical logic） 是用数学的方法来研究推理的一 门学科，它采用一套符号来简洁地表达命题及其间的关系。 因此它表示的含义单一、明确， 在给定前提下会有确切的结论。计算机科学中有两个常用的公式： 程序 = 算法 + 数据； 算法 = 逻辑 + 控制。 著

2、名计算机软件设计大师戴克斯 特拉（E.W.Dijkstra）曾经这样说：“我现在年纪大了，搞了这 么多年软件,错误不知犯了多少， 现在觉悟了。我想，假如我早年 在数理逻辑上好好下点功夫的话我就不会犯这么多的错误。不少 东西逻辑学家早就说了，可我不 知道。要是我能年轻20岁的话，就要回去学逻辑。” 我国著名数理逻辑学家甚至说得 更加直截了当：“事实上，程序设 计或者就是数理逻辑，或者是用 计算机语言书写的数理逻辑，或 者是数理逻辑在计算机上的应用”. 可以说计算机的本质结构就是逻 辑结构。 数理逻辑是计算机程序设计、硬 件逻辑设计以及人工智能等学科 的重要理论基础。有趋势表明： 微积分在人类体力

3、劳动自动化的 过程中扮演了重要角色，数理逻 辑在人类脑力劳动自动化的过程 中将起越来越大的作用。 数理逻辑的两个最基本逻辑- 命题逻辑和谓词逻辑的基础。 8.1 命题与逻辑连接词8.1.1 命题 命题逻辑以命题作为研究对象， 那么什么叫命题呢？今天北京是阴天。我们班是三好班集体。 1/5是自然数。 公鸡能下蛋。 象这些表示判断的语句都是命题. 命题（propositions）是表示判断 的陈述句。 尽管这些判断有些是符合事实的, 有些是不符合事实的。符合事实的判断其命题真值为真 记为“T”或“1”； 不符合事实的判断其命题真值为 假，记为“F”或“0”。 因此一个命题的真值一定为“真、 假”其

4、中的一个（也有其他的逻辑 不这样定义，如第10章的多值逻 辑和模糊逻辑）。例 判断下列语句哪些是命题； 对于是命题的其真值是什么？ （1）台湾是中国的一部分。 （2）多伦多是加拿大的首都。 （3）2是偶数并且也是素数。 （4）天津解放的那天有100个 婴儿出生。 （5）大于2的偶数均可分解为两个质数的和（哥德巴赫猜想）。（6）第29届奥林匹克运动会开幕 时北京天晴。 （7）好过瘾啊！ （8）你去上机吗？ （9）请随手关门！ （10）我希望有一台笔记本电脑。（11）我只给那些不给自己刮胡子的人刮胡子。解： （1），（2），（3）都是命题， （1）,（3）真值为真, （2）真值为假。 （4）,（5

5、），（6）也是命题， （7）是感叹句 （8）是疑问句（9），（10）都是祈使句 它们都不表示一个判断，因此都不是命题。 （11）是著名的理发师悖论， 悖论是自相矛盾的，即无论真假 都会导致矛盾， （11）将导出“我”既不能给自己刮胡子，又不能不给自己刮胡子 的矛盾结论。故它不是命题。 例 判断下列语句哪些是命题； (1) a b(2) x y (3) 我正在说假话。(4) 本命题是假的。是命题不是命题不是命题不是命题原子命题(atoms)或简单命题 命题表示的都是一个基本的判断 由一个主语和一个谓语构成。 复合命题compositive propositions 由两个或更多个原子命题和连词

6、组成的命题逻辑连接词（logical connectives） 或命题连接词 连接原子命题的连接词 原子命题非常简单,它只有真或假, 而复合命题的真值不仅要依赖于 组成它的原子命题的真值，而且 更要依赖于连接原子命题的逻辑 联接词。因此逻辑联接词是逻辑重要而基本的内容。 一般用大写英文字母或带下标的 大写字母如P，Q，A，B， P1,P2，来表示命题，并且若P 表示一个确切的命题，则称其为 命题常元propositional constants 若P表示任意一个命题，则称其为 命题变元propositional variables。 对一个命题变元指定它一个命题或一个真值，我们叫做赋值或真值

7、指派(assignments)，而更多的我们 是给命题变元一个真值指派， 因为在逻辑演算和推理中我们更 关心它的真值。例 将下列命题写成原子命题与连 接词的复合 (1) 6是偶数是不对的。 (2) 6是偶数且是3的倍数。 (3) 6是偶数或是3的倍数。 (4) 如果6是偶数，则3是奇数。 (5) 6是偶数当且仅当3是奇数。解:本例中的5个语句都是复合命题 都是由原子命题通过自然语言中的 连接词复合而成的。若将涉及到的 原子命题符号化如下， P: 6是偶数 q: 6是3的倍数 r: 3是奇数 则5个复合命题表示为(1) 非p (2) P且q (3) p或q(4) 如果p，则r (5) p当且仅当

8、r 上述出现的非、且、或、如果,则 当且仅当等都是自然语言中常用的 连接词，但自然语言中的连接词可能有二义性。为排除二义性, 在 数理逻辑中必须给出连接词的严格 定义，并用特定符号表示。8.1.2 逻辑连接词 例 下列语句都是复合命题， 其中带下划线的词为逻辑连接词 （1）3不是奇数（并非3是奇数） （2）今晚我去书店或者去打球。 （3）他去了教室，也去了实验室 （用“也”表示逻辑联结词“并且”） （4）你作硬件，我作软件。（用逗号表示逻辑联结词“并且”） （5）如果有辆车,那么我去接你。 （6）偶数a是质数,当且仅当a=2. 五个逻辑联接词 否定词(negation)“并非”（not）， 用

9、符号 表示。 设P表示一命题， 那么 P表示命题P的否定。P真时， P假， P假时， P真。 P读作 “非P”其真值状况P P 01 10设P 表示“3是奇数”， 则“3不是奇数”表示为 P， P的真值为真， P的真值为假。 设P 表示“整数都是自然数”， 则P表示“并非整数都是自然数” 或“整数不都是自然数”， 而不是“整数都不是自然数”。 因为P的真值为假， P的真值应为真。 合取词(conjunction)“并且”（and） 用符号表示。 设P，Q表示两命题， 那么PQ表示合取P和Q所得的 命题，当P和Q同时为真时PQ真， 否则PQ为假。 PQ读作 “P且Q”。其真值状况P QPQ 0

10、0 1 1 0 1 0 1 0 0 0 1 设P：他去了教室， Q：他去了实验室， 则该命题可表示为PQ。他去了教室，也去了实验室你作硬件，我作软件。 设A：你作硬件， B：我作软件， 则该命题可表示为AB析取词(disjunction)“或”（or） 用符号表示 设P，Q表示两命题， 那么PQ表示P和Q的析取， 当P和Q有一为真时，PQ为真， 只有当P和Q均假时PQ为假。 PQ读作 “P或Q”。其真值状况 PQPQ 0 0 1 1 0 1 0 1 0 1 1 1 今晚我去书店或者去打球。 设P：今晚我去书店， Q：今晚我去打球， 则该命题可表示为PQ。条件词(condition 如果，那么”

11、（ifthen）用符号表示。设P，Q表示两命题， 则PQ表示命题“如果P,那么Q”， 并且P称为前件，Q称为后件。 当P真而Q假时，命题PQ为假 否则均认为PQ为真。 PQ常读作“若P则Q”。其真值状况PQPQ 0 0 1 1 0 1 0 1 1 1 0 1 如果有辆车,那么我去接你。 设P：我有辆车， Q：我去接你， 则该命题可表示为PQ。 注意： PQ中允许前件P为假， 且此时无论后件Q是真还是假， PQ的真值都为真。许多程序设计语言中用ifthen 结构，与逻辑中使用的不同。 在程序设计中往往是if p then S ， 其中p是命题，而S是一段程序。 当程序运行到这条语句时， 如果p为

12、真，就执行S， 但若P为假，则S不执行。“如果2+2=5，那么雪是黑的” “如果我是美国总统， 我就不那样对待萨达姆” 都是真值为“真”的命题。 双条件词(bicondition)“当且仅当” （if and only if） 用符号表示之。设P，Q为两命题， 则PQ表示命题“P当且仅当Q”， 且当P与Q同真值时PQ为真， 否则为假。 PQ读作“P双条件Q” 或“P当且仅当Q”。其真值状况PQP Q 0 0 1 1 0 1 0 1 1 0 0 1 偶数a是质数,当且仅当a=2. 设P：偶数a是质数， Q：a=2， 则该命题可表示为P Q。这五个联接词可看成是逻辑运算， 其中 是一元运算， ，是

13、二元运算。上述五个联结词来源于日常使用 的相应词汇,但并不完全一致，在 使用时要注意： 以上联结词组成的复合命题的真 假值一定要根据它们的定义去理 解, 而不能据日常语言的含义去理 解。不能“对号入座”，如见到“或”就表示为“”。 在今后我们主要关心的是命题间 的真假值的关系, 而不讨论命题的 内容.8.1.3 命题公式与真值表 当P,Q,R为命题常元即分别表示 某个确切的命题时,(PQ) R 可表示一个更复杂的命题，而且 可根据P,Q,R的真值来确定这个 复杂命题的真值；而当P，Q，R 为命题变元时，由于P，Q，R的 真值不确定因而（PQ） R真值不确定因而（PQ） R 的真值也就无法确定，

14、这个符号串 也就不能再是命题，我们称它为 命题公式，而且随着我们赋值给 P，Q，R即对它们进行真值指派, 这个符号串就会对应有一个真值， 而这个所谓命题公式的真值往往 要随它所含命题变元的真值变化而变化。 定义 一个命题公式按如下规则生成： （1）命题常元和命题变元是命题 公式，也称为原子公式或原子。 （2）如果A，B是命题公式， 那么A,(AB),(AB) (AB),(AB)也是命题公式。（3）只有有限步使用规则(1),(2) 所组成的符号串是命题公式。 一个命题公式就是一个合法的 符号串:(PR),( (P(QR) (QP)都是命题公式，但(PQ), PR很明显都不合法，因而都不是命题公式

15、。约定： （1）公式最外层括号一律可省略 （2）联结词运算优先级依次为： ，(，)， 例:PQ(RQS) 所表示的 是公式(P)(Q(RQ) S) 定义 B称为公式A的子公式, 如果B是公式A的一部分，且B也为一公式。 真值表（truth table）一个命题公式的真值往往要随它 所含命题变元的真值变化而变化， 把所有变化情况对应的汇总一张表，即为该公式的真值表。例 构造公式PQ的真值表。 解：该公式的真值表为： PQPPQ0 0 1 10 1 0 11 1 0 01 1 0 1说明： （1）若公式中含有两个命题变元 则真值组合共有4组；若公式中含 有三个命题变元，则真值组合共 有8组；即若公式中含有n个命题 变元，则真值组合共有2n组,且为 所有n位二进制数。（2）为简化计算，可以逐步算出 各子公式的真值，最后求出所求 公式的真值。 例 求公式（PQ）PQ 的真值表。解：该公式的真值表为： P Q P Q(P Q)P Q P Q (PQ) PQ 00 11 0101 0111 1000 1 1 0 01 0 1 01 0 0 01 1 1 1例求公式(p(QR)的真值表解：该公式的真值表为：例求p(qr), (pq)r的真值表 解：8.1.4 语句的形式化把命题和联接词都符号化了， 也就是说现在能够用符号即命题 公式来表示一个命题的语句了， 下面研究语句形式