江苏省高等教育自学考试【02324-离散数学】学习笔记

课程代号	课程名称	教材代号	教材名称	作者	出版社	版次
02324	离散数学	023241	离散数学(附大纲)	辛运帏	机械工业出版社	2014 年

命题与命题联结词

命题与命题的表示

由一个或几个已知的前提，推导出一个未知结论的思维过程称为推理。推理的基本要素就是表达这些前提的一些陈述句，每个陈述句或成立或不成立，一般来讲，限定于某种情况下，一个陈述句不可能既成立又不成立。成立或不成立可以看作是这个陈述句的一个属性，称之为真值。当陈述句成立时，就说其真值为真，表示为T；当陈述句不成立时，就说其真值为假，表示为F。

例如，“地球是行星”是一个陈述句，并且是正确的，即它的真值为真。而陈述句“2是无理数”是错误的，其真值为假。具有唯一真值的陈述句称作命题，也称为语句。真值为真的命题称为真命题；真值为假的命题称为假命题。

有些陈述句并不具有唯一的真值，也就是说，它有时为真，有时为假。这样的陈述句不是命题。例如，陈述句 “ $x + y > 5$ ”，它的真值要依变量 $x$ 与 $y$ 的值来确定。比如，当 $x = 5$ ， $y = 3$ 时， $x + y > 5$ 为真；当 $x = -1$ ， $y = 2$ 时， $x + y > 5$ 为假。因此在不确定变量 $x$ 、 $y$ 的值的情况下，无法确定 “ $x + y > 5$ ” 的真值。像这种有时为真有时为假的陈述句不是命题。请记住，命题的真值一定是唯一的，或者为真，或者为假，不能既真又假。

有些陈述句具有唯一的真值，但是依我们目前所掌握的知识及了解的情况，不能判断它的真假。例如“宇宙中存在与地球类似的有生命体的星球”，限于人类目前的认知水平，还不知道这样的星球是否存在。但这个句子的真值是唯一的，所以它是命题。

此外，疑问句、感叹句、祈使句等都不能构成命题。

例1.1 判断下列句子中哪些构成命题。

问题	是否构成命题
(1) 8 不是素数	正确的，为真命题。素数：大于1的自然数，除了 1 和它本身以外，不再有其他因数的数（比如能被2、3等整除，那它就不是素数）。
(2) 雪是黑的	错误的，为假命题
(3) 到 2049 年世界人口将超过 90 亿	是命题，所描述的情况我们目前不得而知，需要等到2049年时才能知道是对还是错，但不管怎样，它有唯一的真值
(4) 每台计算机都有唯一的 IP 地址	假命题，有些计算机是具有多IP地址
(5) 喜马拉雅山好高啊！	感叹句，不是命题
(6) 基本粒子是不可分的	假命题，现代物理学已经告诉我们，基本粒子是可分的
(7) 离散数学难学吗？	一般疑问句，不是命题
(8) 请遵守交通规则！	祈使句，不是命题
(9) $x + 1 = 2$	不是命题，它的真假值取决于 $x$ 的值

总而言之，判断命题有两个条件，一是语句本身是个陈述句，二是它有唯一的真值。

实际上，还有一种特殊的陈述句也不是命题，那就是悖论。悖论是指在逻辑上可以推导出互相矛盾之结论的陈述。对于一个悖论 $A$ ，如果认为它是真的，则可以推导出 $A$ 为假；如果认为 $A$ 是假的，则可以推导出 $A$ 为真。例如，“我正在说谎”就是一个悖论。悖论不是命题。

能对命题进行符号化

在数理逻辑中，常常使用符号来表示一个命题，就好像我们在程序中使用标识符表示变量一样，用符号来表示命题的这个过程称为命题的符号化。表示命题的符号既可以是大写的英文字母，也可以是小写的英文字母，如 $P$ 或 $p$ ；有时还可以用字母加数字来表示，为了清楚起见，数字常表示为下标，如 $P_1$ 或 $Q_2$ 。

表示命题的符号称为命题标识符。当命题标识符表示某个确定的命题时，称为命题常量或命题常项，如果命题标识符只表示命题位置，称为命题变元或命题变项。命题变元可以表示任意一个命题，即在确定它所代表的命题之前，命题变元不具有确定的真值。当用一个具体的命题去代替命题变元时，它的真值也就确定下来了，这称为对命题变元的指派。

命题为真时，其真值用 T 或 1 来表示，为假时，其真值用 F 或 0 来表示。

例 1.2 将下面命题符号化，并指出它们的真值。

分别使用 $P$ 、 $Q$ 和 $R$ 来表示上述三个命题：

问题	命题符号化	真值
(1) $\pi$ 是有理数；	$P$ ： $\pi$ 是有理数。	$\pi$ 是无理数，所以 $P$ 的真值为 $F$ 。
(2) 所有的素数都是奇数；	$Q$ ：所有的素数都是奇数。	2 是素数，也是偶数，除此之外，其他的素数都是奇数。 $Q$ 的真值为 $F$ 。
(3) 6 是一个合数。	$R$ ：6 是一个合数。	因为 2 和 3 都是 6 的因子，所以 6 是合数， $R$ 的真值为 $T$ 。

复合命题与联结词，掌握命题联结词，能够使用联结词熟练构造复合命题。

在例 1.2 所举的命题示例中，都是不能再分解的命题，这样的命题称为原子命题或简单命题。实际中，我们常常要表达更丰富的信息，例如“如果今年有假期，我将去欧洲旅游”，这个句子中表达了两层含义，一是“今年有假期”，二是“我去欧洲旅游”，而且这两个含义之间还是有关联的，前一个是前提，后一个是结果。在自然语言中，我们常使用连词来表示两个句子之间的关系，例如本例中的“如果”。在命题符号化时，这样的连词将表示为联结词，联结词都具有特定的符号。由原子命题通过联结词联结而成的命题，称为复合命题。

一般而言自然语言都具有二义性，即有些句子的含义多于一种。在数理逻辑中，为了能精确地进行推导，命题及联结词的含义必须是确定的。

数理逻辑中常用的联结词共有五个，下面详细介绍。

1.否定

定义 1.1 设 $P$ 为命题， $P$ 的否定是一个复合命题，记作 $\neg P$ 。符号 $\neg$ 称作否定联结词。若 $P$ 为 $T$ ， $\neg P$ 为 $F$ ；若 $P$ 为 $F$ ， $\neg P$ 为 $T$ 。命题 $\neg P$ 读作“非 $P$ ”。

由定义可知， $\neg P$ 是一个复合命题。复合命题的真值依命题中所含各原子命题的真值来确定，可用一张表来表示，这样的表称为真值表。联结词 $\neg$ 的定义如表所示。

$P$	$\neg P$
$T$	$F$
$F$	$T$

例 1.3 给出命题 $P$ ：“今天是星期五”的否定，并用自然语言表示出来。

解： $P$ ：今天是星期五。

$\neg P$ ：今天不是星期五。

2. 合取

定义 1.2 设 $P, Q$ 为两个命题， $P$ 和 $Q$ 的合取是一个复合命题，记作 $P \land Q$ 。符号 $\land$ 称为合取联结词。当且仅当 $P, Q$ 同时为 $T$ 时， $P \land Q$ 为 $T$ ，其余情况 $P \land Q$ 为 $F$ 。

$P$ 和 $Q$ 的合取表示的是“ $P$ 并且 $Q$ ”的含义。联结词 $\land$ 的定义如表所示。

$P$	$Q$	$P \land Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

自然语言中的“并且”可以对应于合取，其根本的含义是表示两件事情同时成立。与此类似的词语还有“既……又……”“不但……而且……”“虽然……但是……”“一面……一面……”等。但有时，表示并列的“与”“和”等词语并不对应于合取。例如，“我与王强是同学”中的“与”用在主语中，它连接的是两个并列的主语，而不是两个原子命题。所以这个命题并不是合取命题，实际上，它仅仅是一个原子命题。

例 1.4 将下面命题符号化。

(1) 既是偶数，也是素数；

(2) 我今天不听了离散数学课，还听了数据结构课；

(3) 今天的离散数学课停上，美元上涨。

解：(1) 设 $P$ ： $2$ 是偶数， $Q$ ： $2$ 是素数。

故 (1) 可表示为 $P \land Q$ 。

(2) 设 $P$ ：我今天听了离散数学课， $Q$ ：我今天听了数据结构课。

故 (2) 可表示为 $P \land Q$ 。

(3) 设 $P$ ：今天的离散数学课停上， $Q$ ：今天美元上涨。

故 (3) 可表示为 $P \land Q$ 。

复合命题 $P \land Q$ 中的两个原子命题可以互换位置，即 $P \land Q$ 与 $Q \land P$ 的含义是相同的，它们的真值表也是一样的。这表示合取 $\land$ 具有对称性。

自然语言除了要符合语法外，还要有合理的语义，即表达的意思要合乎逻辑。但是复合命题所含的多个原子命题之间可以没有逻辑关联性。例如(3)中的两个原子命题之间不存在任何逻辑关系，上述离散数学课，不会影响美元的走势。在命题逻辑中，我们仅关心它的表示，而忽略其语义。所以它的真值只与原子命题的真值有关，与语义无关。

特别地，命题联结词“合取”可将两个互为否定的命题联结在一起。以 $P$ 表示命题， $P \land \neg P$ 的真值也是 $F$ 。如表 1.3 所示。