当前位置：首页 > news >正文

离散数学 | 1 命题逻辑

news 2026/4/25 6:54:08

1.1 命题

一个命题（statement / proposition）是一个陈述句（declarative sentence），它要么为真，要么为假，但不能同时为真又为假。

【例】以下表述均不是命题：
（1）快去学离散数学！『该表述为祈使句（imperative sentence）』
（2）离散数学怎么学？『该表述为疑问句（interrogative sentence）』
（3）我在撒谎。『该表述为悖论（paradox）』
（4）3-x=5 『该表述中变量未赋值导致真假值不确定』

命题要求客观上存在唯一的真值，不要求我们当下就知道它的真假。

【例】“太阳将会在明天升起”是命题：
无论我们是否能在当下确定它的结果，它在明天到来时，必然能确定唯一的结果，
太阳升起 → 命题为真
太阳未升起 → 命题为假
但这与表述中存在未赋值的变量有本质的区别，后者不是命题。

命题变项（propositional variable）是用来指代命题的符号，本身不具有真假值，只有被赋予具体的命题时才有意义。常用符号：p，q，r，s。

原子命题（atomic proposition）是指不可再分的最简单命题。

【例】“离散数学本质不是数学”不是原子命题：
否定句均不是原子命题，因为它含有一元联结词，可以继续被拆分。

1.2 逻辑联结词

原子命题可通过逻辑联结词（logical connective）组合成复合命题（compound statement）。

真值表（truth table）是一种根据复合命题的组成部分，给出该复合命题真值的表格。复合命题的真值仅取决于被组合的原子命题的真值与所使用的逻辑联结词类型。

注意，自然语言中的逻辑联结词有时会含有因果关系，但在离散数学语言中，这仅是该复合命题的组成部分。因为命题逻辑是建立一套可计算的、无歧义的推理系统，必须剥离所有主观的、依赖语境的额外含义。这体现了计算机处理逻辑运算的“思维方式”。

【例】对于命题“如果1+1=3，那么我会飞”：
从自然语言看：该表述假设与结论是没有任何关联的
从命题逻辑看：该蕴含式是真命题

【结论】含有n个命题变项的真值表有行，可以构造出个互不等价的命题。
每个命题变元都有“真”或“假”两种取值，n个变元的所有取值组合数为，即为真值表的行数；一个命题的本质是对真值表中每一行赋予一个“真”或“假”的结果，赋值方案数是，不同的赋值方案对应互不等价的命题。

1.2.1 一元联结词

一元联结词（unary）是指只需要一个命题就能操作的联结词。

否定（negation）：设原命题为p，则p的否定是复合命题“非p”（¬p）

真值表：
p ¬p
T F
F T

p	¬p
T	F
F	T

1.2.2 二元联结词

二元联结词（binary）是指需要两个命题才能操作的联结词。

合取（conjunction）：若p与q是命题，则p与q的合取是复合命题“p且q”（p∧q）

真值表：
p q p ∧ q
T T T
T F F
F T F
F F F
析取（disjunction）：可兼或（inclusive ‘or’）：若p与q是命题，则p与q的析取是复合命题“p或q”（p∨q）

真值表：
p q p∨q
T T T
T F T
F T T
F F F
析取（disjunction）：异或（exclusive ‘or’）：若p与q是命题，则p与q的异或是复合命题“要么p要么q”（p⊕q）

真值表：
p q p⊕q
T T F
T F T
F T T
F F F
广义的析取泛指所有表示选择关系的逻辑联结词，包括“可兼或”与“异或”。但我们约定，“析取”默认指的是“可兼或”，因为“异或”本质上是可兼或、合取、否定的组合（(p∨q)∧¬(p∧q)），并非独立的基础联结词。

p	q	p⊕q
T	T	F
T	F	T
F	T	T
F	F	F

蕴含（implication）：若p与q是命题，则复合命题“如果p，那么q”（p→q）是蕴含式。蕴含式也被称为条件命题（conditional statement），其中命题p是前件（antecedent）或假设（hypothesis），命题q是后件（consequent）或结论（conclusion）。

真值表：

p	q	p→q
T	T	T
T	F	F
F	T	T （善意推断）
F	F	T （善意推断）

P→Q的常用表述：

英文表述	中文翻译
If P, then Q	如果 P，那么 Q
If P, Q	如果 P，则 Q
P implies Q	P 蕴含 Q
P only if Q	P 仅当 Q
P is a sufficient condition for Q	P 是 Q 的充分条件
A sufficient condition for Q is P	Q 的充分条件是 P
Q if P	如果 P，则 Q
Q whenever P	每当 P 成立，Q 就成立
Q when P	当 P 成立时，Q 成立
Q follows from P	Q 由 P 推导而来
Q is a necessary condition for P	Q 是 P 的必要条件
Q unless ¬P	除非非 P，否则 Q

蕴含式的逆与反：

命题名称	形式	等价关系
原命题	P→Q
逆命题（converse）	Q→P
反命题（inverse）	¬P→¬Q	与逆命题等价
逆否命题（contrapositive）	¬Q→¬P	与原命题等价

等价（equivalence）：若p与q是命题，则复合命题“p当且仅当q”（p↔q）是等价式。等价式也被称为双条件命题（biconditional）。

真值表：

p	q	p↔q
T	T	T
T	F	F
F	T	F
F	F	T

P↔Q的常用表述：

英文表述	中文翻译
P is necessary and sufficient for Q	P 是 Q 的必要且充分条件
if P then Q, and conversely	如果 P 那么 Q，反之亦然
P if and only if Q	P 当且仅当 Q
P exactly when Q	P 恰好当 Q 成立时成立