第3章命题逻辑-1

取真值的表，称为的真值表。
2013-8-4
50--14
例2.1 求公式：G1＝ ┐P∨Q 和 G2＝ (P → Q) ∧ (Q → P) 的真值表, 其中P 和Q 是 G1和 G2 的所有命题变元. 解 G1和 G2 的真值表为: P 0 0 1 1 Q 0 1 0 1 Q 0 1 0 1 ┐P 1 1 0 0 ┐P∨Q 1 1 0 1 G2 1 0 0 1 P→Q 1 1 0 1
(6) 我喜欢踢足球。
(7) 把门关上。
(8) 你要出去吗？
(9) 今天天气真好啊！ (11)明天我要去旅游。 (12)ｘ＝０。 (13)这个语句是假的。

(T或F)

2013-8-4
50--3
命题的分类
一般来说，命题可分两种类型：
原子命题(简单命题)：不能再分解为更为简单命 题的命题。
2013-8-4
例1.2
⑴ 用复合命题表示如下图所示的开关电路
P Q
图5-1
P Q
图5-2
P
图5-3
设：Ａ：开关Ｐ闭合；Ｂ：开关Ｑ闭合。
A∧B
2013-8-4
A∨B
A
50--6
例1.2（续）
⑵．用复合命题表示如下图所示的逻辑电路。

P PQ Q


P P QQ
P
P
图5-4
2013-8-4
2013-8-4
50--23
3.两个定理
定理5.2(代入定理)设G(P1,P2,…,Pn)是一个命题公式， 其中：P1、P2、…、Pn 是命题变元， G1(P1,P2,…,Pn)、 G2(P1,P2,…,Pn)、...、Gn(P1,P2,…,Pn)
为任意的命题公式，此时若G是永真公式或永假公式,则
2013-8-4 50--9
例1.4 符号化语句： 除非你陪伴我或代我叫车子，否则我将 不出去。 解：设命题 P：你陪伴我； Q：你代我叫车子； R：我将出去。 则句子可符号化为： ┐(P∨Q)→┐R 或
2013-8-4
R→(P∨Q)
50--10
§5.2命题公式、解释与真值表
定义5.7 一个特定的命题是一个常值命题，它不
5.2.3-4 一些特殊的公式, 等价公式
1. 公式类型
例3.1 考虑 ┐(P→Q)→P 的真值表。 解 真值表为:
P 0 0 1 1
Q 0 1 0 1
P→Q
┐(P→Q)
┐(P→Q)→P
1 1 0 1
0 0 1 0
1 1 1 1
注: 该公式对所有可能的解释均有“真”值
2013-8-4 50--18
2013-8-4 50--8
解： 1. 如果明天上午七点不是雨夹雪，则我将去学校。
可符号化为： ┐(P∧Q)→R。
2. 如果明天上午七点不下雨并且不下雪，则我将去学校。 可符号化为: (┐P∧┐Q)→R。 3. 明天上午七点下雨或下雪，当且仅当我将不去学校。 可符号化为: (P∨Q) ┐R。 4. 明天上午我将雨雪无阻一定去学校。 可符号化为： (P∧Q∧R)∨(┐P∧Q∧R)∨ (P∧┐Q∧R)∨(┐P∧┐Q∧R)。 或 ((P∧Q)∨(┐P∧Q)∨(P∧┐Q)∨(┐P∧┐Q))∧R。
公式。 “”．假定公式GH是永真公式， 则对任意的解释
Ｉ ，GH 均为真，因此，G、H或同为真，或同为 假，由Ｉ的任意性，故有G＝H。■
2013-8-4 50--22
说明 1. 定理5.1表明:G=H GH 是永真公 式; 这是符号 = 与 的联系. 2. = 与 的区别:
（1）“”是逻辑联结词， 而 “＝”是关系符. 若G, H 是命题公式，则 GH 仍是一个命题公式; 而 G＝H 却不是命题公式。 （2）如果要用计算机来判断是否有 G ＝ H ，直接 “计算”那是办不到的，然而计算机却可通过“计算” 公式 GH 是否是永真公式而达目的。
2013-8-4
50--27
例3.3 证明 P→Q ＝ ┐Q → ┐P 证 P→Q ＝ ┐P∨Q ＝ Q ∨ ┐P ＝ ┐(┐Q )∨ ┐P ＝ ┐Q → ┐P 例3.4 判断P∨┐((P∨┐Q)∧Q) 是否永真公式。 解 原式 ＝P∨┐(P∨┐Q)∨┐Q ＝(P∨┐Q)∨┐(P∨┐Q) ＝T 所以, 原式是永真公式。
2013-8-4
50--12
例2.1 符号串： ┐(P∧Q)； (P→(┐(P∧Q)))； ((P→Q)∧(R→Q))→(P→R) ；
((P∧(Q∨R))→(Q∧(┐S∨R))) 。
等都是命题公式。 例2.2符号串： P∨Q∨, ┐P∨ (QR), (P→ ∨ Q)； (P→Q)∧┐Q)
等都不是合法的命题公式。
2013-8-4 50--13
5.2.2 公式的解释与真值表
定义5.9设命题变元P1, P2, P3, …, Pn是出现
在公式G中的所有命题变元，指定P1, P2, P3, …,
Pn一组真值，则这组真值称为G 的一个解释,常
记为Ｉ。 一般来说，若有 n个命题变元，则应有2n个 不同的解释。 定义5.10公式G在其所有可能的解释下所
P∧Q 0 0 0 0 0 0 1 1
(P∧Q)→R 1 1 1 1 1 1 0 1
50--16
例2.2（续）
该真值表可简化为：
P 0 0 0 0 1 1 1 1
2013-8-4
Q 0 0 1 1 0 0 1 1
R 0 1 0 1 0 1 0 1
(P∧Q)→R 1 1 1 1 1 1 0 1
50--17
2013-8-4 50--11
5.2.1 命题公式
定义5.8 (1) 命题变元本身是一个公式；
(2) 如果P是公式，则 (┐P) 也是公式； (3) 如果P，Q是公式，则 (P∧Q)、(P∨Q)、 (P→Q)、(PQ) 也是公式；
(4) 命题公式仅由有限步使用规则1-3后产生的 结果。该公式常用符号 G、H、…等表示。
题公式为H，若G1＝H1，则G＝H。 4. 基本等价公式 设G，H，S 是任意的公式，则： (1) Ｅ1: G∨(H∨S)＝(G∨H)∨S Ｅ2：G∧(H∧S)＝(G∧H)∧S
2013-8-4
(结合律)
50--25
(2)Ｅ3： G∨H＝H∨G Ｅ4： G∧H＝H∧G (交换律) (3)Ｅ5： G∨G＝G Ｅ6： G∧G＝G (幂等律) (4) Ｅ7： G∨(G∧H)＝ G Ｅ8: G∧(G∨H)＝ G (吸收律) (5) Ｅ9： G∨(H∧S)＝(G∨H)∧(G∨S) Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S) (分配律) (6)Ｅ11：G∨０＝G Ｅ12： G∧１＝G (同一律)
合取
析取 蕴涵 等价
∧
∨ →
A∧B (A并且B)
A∨B (A或者B) A→B (若A则B) AB (A当且仅当B)
A∧B为真当且仅当A,B同 为真
A∨B为真当且仅当A,B中 至少一个为真 A→B 为 假 当 且 仅 当 A 为 真B为假 AB 为 真 当 且 仅 当 A,B 同为真假
50--5
2013-8-4
50--21
2.等价公式
定义5.12公式G、H说是等价的(Equivalent)，记作G＝
H，如果在其任意的解释下，其真值相同。
定理5.1 公式G、H 等价的充分必要条件是公式 GH 是永真公式。
证明 “”．假定G，H 等价，则G，H在其任意解释
Ｉ 下或同为真或同为假，于是由“”的意义知， GH在Ｉ下为“真”，由Ｉ的任意性 GH 为永真
是具有值“T”(“1”)，就是具有值“F”(“0”)。
而一个任意的没有赋予具体内容的原子命题 是一个变量命题，常称它为命题变量(或命题变 元); 命题变量无具体的真值，其变域是集合 {T， F} (或{0，1})。
说明
含有命题变元的原子或复合命题实际上是
命题变元的“函数”，可称为“真值函数”，
或称为命题公式，命题公式没有确切真值。
定义5.11 (1)公式 G 称为永真公式(重言式)，如果
在它的所有解释之下都为“真”。 (2) 公式G 称为永假公式(矛盾式),如果在它的所 有解释之下都为“假”。
(3) 公式 G 称为可满足的，如果它不是永假的。
关系 (1)永真式的否定是矛盾式；矛盾式的否定是永真式。
(2) 永真式一定是可满足式。 两个术语 ：如果公式G 在解释Ｉ下是真的，则称Ｉ 满足 G；如果G 在解释Ｉ下是假的，则Ｉ称弄假G。
真值只有 “真”和“假”两种，分别用 “Ｔ”(或“１”)和“Ｆ”(或“０”)表示。
例1.1 (1) 加拿大是一个国家。 (2) 成都是中国的首都。 (3) 那个人是老师。
2013-8-4
(T) (F) (T或F)
50--2
(4) ３＋２≥１０。 (5)１＋１０１＝１１０。
(F)
(T或F)
(T或F)
例如: 今天下雨。
复合命题：可以分解为更为简单命题的命题。或者 说由简单命题经命题联结词复合而成的命题。
例如: 今天下雨并且刮风。
命题的表示
通常用大写的带或不带下标的英文字母Ａ,Ｂ,
Ｃ, ... , Ai, Bi ,Ci, ... 等表示命题.
2013-8-4 50--4
5.1.2 命题联结词
联接词 否定 记号 记法 (基本意思) ┐ ┐A (A的否定) 真值结果 ┐A为真当且仅当A为假
2013-8-4
50--19
例3.2 列出真值表，验证下列公式是否是永真公式。 (1) ((P→Q)∧P)→Q； (2) ┐(P ∨ Q) (┐P ∧ ┐ Q) 解 ⑴的真值表如下
P Q P→Q
(P→Q)∧P
((P→Q)∧P)→Q
0 0