离散数学2

什么是命题和非命题

数理逻辑研究的中心问题是推理，而推理的前提和结论都是命题。因而命题是推理的基本单位。

定义:

具有确切真值的陈述句称为命题(proposition)。该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种.

分别用“T”(或“1”) 和“F”(或“0”)表示。

例如:中国是我们的国家 真值：T

3 能被 2 整除。真值：F

非命题：

一切没有判断内容的句子，如命令句 (或祈使句)、感叹句、疑问句、二义性的陈述句等都不能作为命题。

这个人不行的(二义性)

把门关上(命令句)

请你离开！(感叹句)

你要走吗？(疑问句)

复合命题

原子命题 (简单命题)：不能再分解为更为简单命题的命题。

复合命题：可以分解为更为简单命题的命题。这些简单命题之间是通过如“或者”、“并且”、“不”、“如果......则......”、“当且仅当”等这样的关联词和标点符号复合而成

通常用大写的带或不带下标的英文字母表示命题 (包括原子命题和复合命题)。

复合命题的例子：

如果周末天气晴朗，则我们将到郊外旅游

两个三角形全等当且仅当三角形的三条边全部相等

我是学生或者是程序员

命题逻辑

回顾复合命题中，一般是通过联结词和标点符号将简单命题联结成复杂的语句，最常见的联结词主要有以下五种：“或者”、“并且”、“不”、“如果...... 则......”、“当且仅当”

否定联结词

设 P 是任意一个命题，复合命题“非 P”(或 “P 的否定”)称为 P 的否定式(negation)，记作¬P， “¬” 为否定联结词。P为真当且仅当 ¬P 为假。

p	¬p
0	1
1	0

合取联结词

设 P、Q 是任意两个命题，复合命题“P 并且 Q”(或 “P 和 Q”)称为 P 与 Q 的合取式(conjunction)，记作P ∧ Q，“∧” 为合取联结词。P ∧ Q 为真当且仅当 P，Q 同为真。

P：3 是素数；

Q：3 是奇数。

P ∧ Q：3 既是素数又是奇数。

p	q	p^q
0	0	0
0	1	0
1	0	0
1	1	1

析取联结词

设 P、Q 是任意两个命题，复合命题“P 或 Q”称为 P 与 Q 的析取式(disjunction)，记作P ∨ Q， “∨” 为析取联结词。P ∨ Q 为真当且仅当 P，Q 至少有一个为真。

P：张谦是大学生；

Q：张谦是运动员。

P ∨ Q：张谦是大学生或是运动员。

p	q	p∨ q
0	0	0
0	1	1
1	0	1
1	1	1

蕴涵联结词

设 P、Q 是任两个命题，复合命题“如果 P，则 Q”称为 P 与 Q 的蕴涵式(implication)，记作P → Q，“→” 为蕴涵联结词。P → Q 为假当且仅当 P 为真且 Q 为假。一般把蕴涵式 P → Q中的 P 称为该蕴涵式的前件，Q 称为蕴涵式的后件。

P：周末天气晴朗；

Q：我们将到郊外旅游。

P → Q：如果周末天气晴朗，则我们将到郊外旅游。

p	q	p->q
0	0	1
0	1	1
1	0	0
1	1	1

在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但对于数理

逻辑中的蕴涵联结词来说，当前件 P 为假时，不管 Q 的真假如何，则 P → Q 都为真。此

时称为 “善意推定”。

设 P：约翰学习微积分，Q：约翰是大学一年级学生。则以下的复合命题均可用 P → Q

表示。

1 如果约翰学习微积分，则他是大学一年级学生。如果 P，则 Q

2 因为约翰学习微积分，所以他是大学一年级学生。因为 P，所以 Q

3 只要约翰学习微积分，他就是大学一年级学生。只要 P，就 Q

4 约翰学习微积分仅当他是大学一年级学生。P 仅当 Q

5 只有约翰是大学一年级学生，他才能学习微积分。只有 Q，才 P

6 除非约翰是大学一年级学生，他才能学习微积分。除非 Q，才 P

7 除非约翰是大学一年级学生，否则他不学习微积分。除非 Q，否则 ¬P

等价联结词

设 P、Q 是任两个命题，复合命题“P 当且仅当 Q”称为 P 与 Q 的等价式(equivalence)，记作P ↔︎ Q，“↔︎” 为等价联结词(也称作双条件联结词)。P ↔︎ Q 为真当且仅当 P、Q 同为真假。

p	q	p↔︎q
0	0	1
0	1	0
1	0	0
1	1	1

逻辑总结：

联结词	记号	复合命题	读法	记法	真值结果
否定	¬	P 的否定	非 P	¬P	¬P 的真值为 “真” 当且仅当 P 的真值为 “假”
合取	∧	P并且 Q	P合取Q	P ∧ Q	P ∧ Q的真值为“真”当且仅当 P Q的真值同为''真'
析取	∨	P或者Q	P析取Q	P ∨ Q	P ∧ Q的真值为“真”当且仅当 P Q的真值至少一个为为''真'
蕴涵	→	若P，则Q	P蕴涵Q	P → Q	P → Q 的真值为 “假” 当且仅当 P的真值为“真”、Q的真值为“假”
等价	↔︎	P当且仅当Q	P 等价于 Q	P ↔︎ Q	P↔︎ Q 的真值为 “真” 当且仅当 P、Q 的真值同为 “ 真"或者同为“ 假”

命题联结词的优先级

所有五个联接词的优先顺序为：否定，合取，析取，蕴涵，等价；

2 同级的联结词，按其出现的先后次序 (从左到右)；

3 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最高优先级。

设命题 P : 你陪伴我;

Q : 你代我叫车子;

R : 我将出去.

符号化下述语句：

1

如果你陪伴我并且代我叫辆车子，则我将出去。

符号化为：

(P ∧ Q) → R

2

如果你不陪伴我或不代我叫辆车子，我将不出去。

符号化为：

(¬P ∨ ¬Q) → ¬R

3

除非你陪伴我或代我叫车子，否则我将不出去。

符号化为：R → (P ∨ Q) 或 (¬P∧ ¬Q) → ¬R

命题变元

一个特定的命题是一个常值命题，它不是具有值 “T”(“1”)，就是具有值 “F”(“0”).

一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量 (或命题变元)(propositional variable)，该命题变量无具体的真值，它的变域是集合{T, F}(或 {0, 1})

复合命题是由原子命题与联结词构成的命题。所以，当其中的原子命题是命题变元时，此

复合命题也即为命题变元的函数，且该函数的值仍为“真”或“假”值，这样的函数可形

象地称为“真值函数” 或 “命题公式”，此命题公式没有确切的真值。

例如：G = P ∧ Q → ¬R.

命题公式

命题演算的合式公式 (well formed formula，wff)，又称命题公式 (简称公式)，按如下规则生成

1.命题变元本身是一个公式

2.如 G 是公式，则(¬ G)也是公式

3.如 G，H 是公式，则(G ∧ H)、(G ∨ H)、(G → H)、(G ↔︎ H)也是公式；（如：P ∧ Q ,(¬ Q) → R , · · · ）

仅由有限步使用规则 (1)、(2)、(3)后所得到的包含命题变元、联结词和括号的符号串才是命题公式.

如果

G 是含有 n 个命题变元 P1、P2、P3、· · · 、*P**n* 的公式，可记为：G(P1, P2, P3, · · · , P n) 或简写为 G 。

1 原子命题变元是最简单的合式公式，称为原子合式公式，简称原子公式；

2 命题公式没有真值，只有对其命题变元进行真值指派后，方可确定命题公式的真值；

3 整个公式的最外层括号可以省略；公式中不影响运算次序的括号也可以省略。

4 在实际应用中，为了便于存储和运算，命题公式常用二元树的方式来表达。

公式的解释

设 P1、P2、P3、· · · 、P n 是出现在公式 G 中的所有命题变元，指定 P1、P2、P3、· · · 、P n 一组真值，则这组真值称为 G 的一个解释，常记为 I。

设有公式：G = P → (*¬**Q* ∧ R)

1 : P = 0, Q = 1, R = 0是 G 的一个解释，使得 G 的真值为 1。

2 P = 1, Q = 0, R = 0是 G的一个解释，使得 G 的真值为 0。

一般来说，若有 n 个命题变元，则应有 2^n 个不同的解释。

利用真值表，可得到公式的所有成真赋值和成假赋值

公式 G 称为永真公式(重言式,tautology)，如果在它的所有解释之下其真值都为“真”。

公式 G 称为永假公式(矛盾式,contradiction)，如果在它的所有解释之下其真值都为“假”。有时也称永假公式为不满足公式。

公式 G 称为可满足公式(satisfiable)，如果它不是永假的。

公式的逻辑关系

考虑上一个例子中的永真公式 G1 = (P → Q) ↔︎ (¬ P ∨ Q)，将这个公式拆开，令

G = P → Q，H = ¬ P ∨ Q，从而 G1 = G ↔︎ H，由于 G1 是永真公式，根据等价联接词的定义可知 G,H 必同为真或者同为假。此时我们称公式 G,H 具有逻辑等价关系。

对于任意两个公式 G 和 H，G = H 的充分必要条件是公式 G ↔︎ H 是永真公式。

基本等价关系及其应用

(幂等律)

G ∨ G = G;

G ∧ G = G

(交换律)

G ∨ H = H ∨ G

G ∧ H = H ∧ G

(结合律)

G ∨ (H ∨ S) = (G ∨ H) ∨ S

G ∧ (H ∧ S) = (G ∧ H) ∧ S

(同一律)

G ∧ 1 = G

G ∨ 0 = G

(零律)

G ∨ 1 = 1

G ∧ 0 = 0

(分配律)

G ∨ (H ∧ S) = (G ∨ H) ∧ (G ∨ S)

G ∧ (H ∨ S) = (G ∧ H) ∨ (G ∧ S)

(吸收律)

G ∨ (G ∧ H) = G

G ∧ (G ∨ H) = G.

(矛盾律)

¬ G ∧ G = 0

(排中律)

¬ G ∨ G = 1

(双重否定律)

¬(¬ G) = G

(德摩根律)

¬(G ∨ H) = ¬ G ∧ ¬ H

¬(G ∧ H) = ¬ G ∨ ¬ H

(蕴涵式)

G → H = ¬ G ∨ H.

(假言易位)

G → H = ¬ H → ¬ G

(等价式)

G ↔︎ H = (G → H) ∧ (H → G) = (¬ G ∨ H) ∧ (¬ H ∨ G)

(等价否定等式)

G ↔︎ H = ¬ G ↔︎ ¬ H

(归谬论)

(G → H) ∧ (G → ¬ H) = ¬ G

利用命题公式的基本等价关系，证明 (P → Q) ∧ P → Q 是重言式