（用逗号表示逻辑联结词“并且” （5）如果有辆车,那么我去接你。 （6）偶数a是质数,当且仅当a=2. 五个逻辑联接词 否定词(negation)“并非”（not）， 用符号 表示。 设P表示一命题， 那么 P表示命题P的否定。
P真时， P假， P假时， P真。 P读作 “非P”
其真值状况 P 0 1 P 1 0
P 0 0 1 1
其真值状况 Q 0 1 0 1
P→Q 1 1 0 1
如果有辆车,那么我去接你。 设P：我有辆车， Q：我去接你， 则该命题可表示为P→Q。 注意： P→Q中允许前件P为假， 且此时无论后件Q是真还是假， P→Q的真值都为真。
许多程序设计语言中用if…then… 结构，与逻辑中使用的不同。 在程序设计中往往是if p then S ， 其中p是命题，而S是一段程序。 当程序运行到这条语句时， 如果p为真，就执行S， 但若P为假，则S不执行。
且B也为一公式。 真值表（truth table） 一个命题公式的真值往往要随它 所含命题变元的真值变化而变化， 把所有变化情况对应的汇总一张
表，即为该公式的真值表。
例 构造公式P∨Q的真值表。 解：该公式的真值表为：
P Q P P∨Q
0 0
1 1 0 1
可能有二义性。为排除二义性, 在 数理逻辑中必须给出连接词的严格 定义，并用特定符号表示。
8.1.2 逻辑连接词 例 下列语句都是复合命题， 其中带下划线的词为逻辑连接词 （1）3不是奇数（并非3是奇数） （2）今晚我去书店或者去打球。 （3）他去了教室，也去了实验室 （用“也”表示逻辑联结词“并且 （4）你作硬件，我作软件。
真值不确定因而（P∧Q） R 的真值也就无法确定，这个符号串 也就不能再是命题，我们称它为 命题公式，而且随着我们赋值给 P，Q，R即对它们进行真值指派, 这个符号串就会对应有一个真值， 而这个所谓命题公式的真值往往 要随它所含命题变元的真值变化
而变化。 定义 一个命题公式按如下规则生成： （1）命题常元和命题变元是命题 公式，也称为原子公式或原子。 （2）如果A，B是命题公式， 那么A,(A∧B),(A∨B) (A→B),(AB)也是命题公式。
解:本例中的5个语句都是复合命题 都是由原子命题通过自然语言中的 连接词复合而成的。若将涉及到的 原子命题符号化如下， P: 6是偶数 q: 6是3的倍数 r: 3是奇数 则5个复合命题表示为
(1) 非p (2) P且q (3) p或q
(4) 如果p，则r (5) p当且仅当r 上述出现的非、且、或、如果,则 当且仅当等都是自然语言中常用的 连接词，但自然语言中的连接词
不能“对号入座”，如见到“或”
表示为“∨”。 在今后我们主要关心的是命题间 的真假值的关系, 而不讨论命题的 内容.
8.1.3 命题公式与真值表
当P,Q,R为命题常元即分别表示 某个确切的命题时,(P∧Q) R 可表示一个更复杂的命题，而且 可根据P,Q,R的真值来确定这个 复杂命题的真值；而当P，Q，R 为命题变元时，由于P，Q，R的 真值不确定因而（P∧Q） R
（3）只有有限步使用规则(1),(2) 所组成的符号串是命题公式。 一个命题公式就是一个合法的 符号串:(P∨R),( (P→(Q∧R)) (QP)都是命题公式，
但(PQ), P→∧R很明显都不合法，
因而都不是命题公式。
约定： （1）公式最外层括号一律可省略 （2）联结词运算优先级依次为： ，(∧，∨)，→， 例:P→Q∨(R∧QS) 所表示的 是公式((P)→(Q∨((R∧Q) S))) 定义 B称为公式A的子公式, 如果B是公式A的一部分，
说明： （1）若公式中含有两个命题变元 则真值组合共有4组；若公式中含 有三个命题变元，则真值组合共 有8组；即若公式中含有n个命题 变元，则真值组合共有2n组,且为 所有n位二进制数。
（2）为简化计算，可以逐步算出 各子公式的真值，最后求出所求 公式的真值。 例 求公式（P∨Q）P∧Q 的真值表。
例求p→(q→r), (p→q)→r的真值表 解：
8.1.4 语句的形式化 把命题和联接词都符号化了， 也就是说现在能够用符号即命题 公式来表示一个命题的语句了， 下面研究语句形式化问题。 语句形式化的步骤是： ① 将所给语句所包含的原子命题 找出，并将它们用符号表示；
原子命题(atoms)或简单命题 命题表示的都是一个基本的判断 由一个主语和一个谓语构成。 复合命题compositive propositions 由两个或更多个原子命题和连词 组成的命题
逻辑连接词（logical connectives） 或命题连接词 连接原子命题的连接词 原子命题非常简单,它只有真或假, 而复合命题的真值不仅要依赖于 组成它的原子命题的真值，而且 更要依赖于连接原子命题的逻辑 联接词。因此逻辑联接词是逻辑
符合事实的判断其命题真值为真 记为“T”或“1”； 不符合事实的判断其命题真值为 假，记为“F”或“0”。 因此一个命题的真值一定为“真、 假”其中的一个（也有其他的逻辑 不这样定义，如第10章的多值逻 辑和模糊逻辑）。
例 判断下列语句哪些是命题； 对于是命题的其真值是什么？
（1）台湾是中国的一部分。 （2）多伦多是加拿大的首都。 （3）2是偶数并且也是素数。 （4）天津解放的那天有100个 婴儿出生。 （5）大于2的偶数均可分解为两
设P 表示“3是奇数”， 则“3不是奇数”表示为 P， P的真值为真， P的真值为假。 设P 表示“整数都是自然数”， 则P表示“并非整数都是自然数” 或“整数不都是自然数”， 而不是“整数都不是自然数”。 因为P的真值为假，
P的真值应为真。 合取词(conjunction)“并且”（and 用符号∧表示。 设P，Q表示两命题， 那么P∧Q表示合取P和Q所得的 命题，当P和Q同时为真时P∧Q真， 否则P∧Q为假。 P∧Q读作 “P且Q”。
（9），（10）都是祈使句 它们都不表示一个判断，
因此都不是命题。 （11）是著名的理发师悖论， 悖论是自相矛盾的，即无论真假 都会导致矛盾， （11）将导出“我”既不能给自己
刮胡子，又不能不给自己刮胡子 的矛盾结论。故它不是命题。 例 判断下列语句哪些是命题； 是命题 (1) a > b 不是命题 (2) x > y (3) 我正在说假话。 不是命题 (4) 本命题是假的。不是命题
个质数的和（哥德巴赫猜想）。
（6）第29届奥林匹克运动会开幕 时北京天晴。 （7）好过瘾啊！ （8）你去上机吗？ （9）请随手关门！ （10）我希望有一台笔记本电脑。
（11）我只给那些不给自己刮胡
子的人刮胡子。 解： （1），（2），（3）都是命题， （1）,（3）真值为真, （2）真值为假。 （4）,（5），（6）也是命题， （7）是感叹句 （8）是疑问句
其真值状况
P 0 0 1 1
Q 0 1 0 1
P Q 1 0 0 1
偶数a是质数,当且仅当a=2. 设P：偶数a是质数， Q：a=2， 则该命题可表示为P Q。
这五个联接词可看成是逻辑运算， 其中 是一元运算， ∧，∨，，是二元运算。
上述五个联结词来源于日常使用 的相应词汇,但并不完全一致，在 使用时要注意： 以上联结词组成的复合命题的真 假值一定要根据它们的定义去理 解, 而不能据日常语言的含义去理 解。
第八章 命题逻辑基础 我们在日常生活中经常会遇到推 理.日常生活中使用的语言常称为 自然语言或元语言，而自然语言 含义丰富，有时甚至含糊多义。 例如我们说三句带“是”的语句： 孔子是孔仲尼； 孔子是人；
人是动物。 这三句中 “是”的符号含义分别为 “=”、“∈”、“”。 因此用自然语言进行的推理非常 灵活，结论不定。 数理逻辑（mathematical logic） 是用数学的方法来研究推理的一 门学科，它采用一套符号来简洁
重要而基本的内容。 一般用大写英文字母或带下标的 大写字母如P，Q，A，B，…， P1,P2，…来表示命题，并且若P 表示一个确切的命题，则称其为 命题常元propositional constants 若P表示任意一个命题，则称其为 命题变元propositional variables。 对一个命题变元指定它一个命题
其真值状况 P Q P∧Q 0 0 0 0 1 0 1 0 0 1 1 1
他去了教室，也去了实验室 设P：他去了教室， Q：他去了实验室， 则该命题可表示为P∧Q。 你作硬件，我作软件。 设A：你作硬件， B：我作软件， 则该命题可表示为A∧B
析取词(disjunction)“或”（or） 用符号∨表示 设P，Q表示两命题， 那么P∨Q表示P和Q的析取， 当P和Q有一为真时，P∨Q为真， 只有当P和Q均假时P∨Q为假。 P∨Q读作 “P或Q”。
或一个真值，我们叫做赋值或真值 指派(assignments)，而更多的我们 是给命题变元一个真值指派， 因为在逻辑演算和推理中我们更 关心它的真值。
例 将下列命题写成原子命题与连 接词的复合 (1) 6是偶数是不对的。 (2) 6是偶数且是3的倍数。 (3) 6是偶数或是3的倍数。 (4) 如果6是偶数，则3是奇数。 (5) 6是偶数当且仅当3是奇数。
地表达命题及其间的关系。 因此它表示的含义单一、明确， 在给定前提下会有确切的结论。
计算机科学中有两个常用的公式： 程序 = 算法 + 数据； 算法 = 逻辑 + 控制。 著名计算机软件设计大师戴克斯 特拉（E.W.Dijkstra）曾经这样
说：“我现在年纪大了，搞了这 么多年软件,错误不知犯了多少， 现在觉悟了。我想，假如我早年 在数理逻辑上好好下点功夫的话 我就不会犯这么多的错误。不少 东西逻辑学家早就说了，可我不 知道。要是我能年轻20岁的话，
数理逻辑的两个最基本逻辑---命题逻辑和谓词逻辑的基础。 §8.1 命题与逻辑连接词
8.1.1 命题 命题逻辑以命题作为研究对象， 那么什么叫命题呢？ 今天北京是阴天。