离散数学1.1-1.4

第1章 命题逻辑

数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。

这里所指的数学方法就是引进一套符号体系的方法。

所以数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的。

计算机及计算机科学与数理逻辑有着十分密切的关系。人们说数字电子计算机是数理逻辑与电子学结合的产物，这话不假。 现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。

本课程介绍的是数理逻辑最基本的内容，也是与计算机科学关系最为密切的：命题逻辑和谓词逻辑（一阶逻辑）

1.1 命题符号化及联结词 1.1.1 命题及其表示法

命题：能判断真假的陈述句。

真值：一个命题总具有一个“值”，即“真”（用T或1表示）

或“假”（用F或0表示），称为真值。

一切没有判断内容的句子，无所谓是非的句子，如感叹句、疑问句、祈使句等都不是命题。 例1：

（1） 2是素数 （2） 雪是黑色的 （3） 2+3=5

（4） 明年十月一日是晴天。 （5） 这朵花多好看呀！ （6） 明天下午有会吗？ （7） 请关上门！ （8） x+y>5

（9） 地球外的星球上也有人。 （10） 我学英语，或者我学日语。

判断的关键：1.是否是陈述句；2.真值是否是唯一的。

简单命题（原子命题）：不能分解为更简单的陈述句。 复合命题：由联结词、标点符号把几个原子命题联结起来的命题。

表示法：

表示法 例子 p: 2是素数 q:雪是黑色的 命题常项同上 （常元） 命题变项同上 （变元） q 复合命题 p∧ 有关概念简单命题 p,q,r,…,pi,qi,ri,… 命题符号化：将命放在该命题的前面 同上 p: x+y>5 真值确定的简单命题真值可以变化的简单2是素数和偶数 一个符号表示的是命题常项还是命题变项由上下文决定。

1.1.2 联结词（也称真值联结词或逻辑联结词或逻辑运算符）

p,q为两个命题

联…式 记作 结词 非p(p的否定)

为真的条件iff 优先级 1

其他 复合命题 否定

?p ? p为假

p∨q ∨ p与q至少一个为真 p→q → ?(P为真且q为假)

q ∧ p与q同时为真 合取 p并且q(p和q) p∧

P或q 如果p则q

2 既…又…,不仅…而3 相容或

析取

蕴涵 4 只要p就q，p仅当

等价 P当且仅当q p?q ? p，q真值相同

5

将复合命题符号化的步骤是 1） 分析出简单命题，符号化 2） 用联结词联结简单命题

例2：将下列各命题符号化 （1） 3不是偶数 （2） 李平即聪明又用功 （3） 李平虽然聪明，但不用功 （4） 李平不但聪明，而且用功 （5） 李平不是不聪明，而是不用功 （6） 李文与李武是兄弟 （7） 王燕学过法语或英语 （8） 派小王和小李中的一人去开会

（9） 只要不下雨，我就骑自行车上班（除非下雨，否则我就

骑自行车上班）

（10） 只有不下雨，我才骑自行车上班（如果下雨，我是不骑

自行车上班）

（11） 若2+2=4，则太阳从东方升起 （12） 若2+2≠4，则太阳从东方升起 （13） 若2+2=4，则太阳从西方升起