离散数学左孝凌(课堂PPT)

算应改为布尔加和布尔乘。
例6
设
M
1和
M
是两个关系矩阵
2
1 0 0
M
1
0
0
0 1
1
0
1 0 0
M 2 0
1
0
1
0
0
1 0 1
1 0 0
则
M
1
M
2
1 0
0 1
1
0
2021/1/17
1
-ห้องสมุดไป่ตู้
0
0
19
• 复合关系的关系矩阵
定理3.5.5 设A、B、C均是有限集， R 1 是一由A 到B的关系, R 2 是一由B到C的关系，它们的关系
R 1 R 2 { 1 , 1 , 2 , 1 , 2 , 3 , 3 ,2 , 4 , 1 }
234
123
12 3
1 1 0 0
2 1 0 0
1 1 0 0
M
R1
2 3
0
0
0 1
1
0
M R 2 3 0 4 1
1 0
0 1
M R1 R2
2 1 3 0
0 1
1
0
4
1
0
0
矩阵分别为 M R1 和 M R2 ，则复合关系 R1 R2 的
关系矩阵
MR1R2 MR1MR2
2021/1/17
-
20
例7 设有集合A{1,2,3,4，} B{2，,3,4} C{1,2,3}
A到B的关系 B到C的关系 则
R 1 { 1 ,2 ,2 ,4 ,3 ,3 ,4 ,2 }
R 2 { 2 ,1 ,3 ,2 ,4 ,1 ,4 ,3 }

例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) S∨R 证法2 (1) P→R P (2) P∨Q →R∨Q T(1) I3 (3) Q→S P (4) Q∨R →S∨R T(3) I (5) P∨Q →S∨R T(2),(4) I13 (6) P∨Q P (7) S∨R T(5),(6) I11P,P→Q Q假言 推理
E1 E2 ┐┐P P P∧Q Q∧P E12 E13 R ∨(P∧┐P) R R∧ (P ∨ ┐P) R
E3
E4 E5 E6 E7 E8 E9
P∨QQ∨P
(P∧Q) ∧R P∧ (Q∧R) (P ∨ Q) ∨ R P ∨(Q ∨ R)
E14
E15 E16
R ∨(P ∨ ┐P) T
T T T T T F F
从真值表看到，P→R，Q→R，P∨Q的真值都为T的 情况为第1行、第3行和第5行，而在这三行中R的真值均为 T。故 (P→R)∧(Q→R)∧(P∨Q) R
二、直接证法
• 直接证法：由一组前提，利用一些公认的推理规则， 根据已知的等价或蕴含公式推演得到有效结论。 • 常用的推理规则 P规则:（前提引入规则）前提在推导过程中的任何时候 都可以引用。 T规则（结论引用规则）在推导过程中，如果有一个或多 个公式重言蕴含着公式S，则公式S可以引入推导之。 如 P→Q, Q→R P→R，这时 P→R可引入推导之中
d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S) ┐S (1) (┐Q∨R) ∧┐R P (2) ┐Q∨R T(1),I1 (3) ┐R T(1),I2 (4) ┐Q T(2)(3),I10析取三段论 (5) P→Q P (6) ┐P T(4)(5),I12 (7) ┐(┐P∧┐S) P (8) P∨┐S T(7),E (9) ┐S T(6)(8),I10析取三段论

19
第一章 命题逻辑（Propositional Logic） 1.7对偶与
范式(Dual & Normal Form)
1.7.3命题公式的主析(合)取范式
为了使任意一个命题公式化成唯一的等价命题的 标准形式，下面给出主范式的有关概念。
1.命题公式的主析取范式
定义1-7.4: n个命题变元的合取式，称作布尔合取或小项， 其中每个变元与它的否定不能同时存在，但两者必须 出现且仅出现一次。
20
例
1.命题公式的主析取范式-小项
1. 两个命题变元P和Q的小项为： P∧Q，P∧┐Q，┐P∧Q，┐P∧┐Q。 2. 三个命题变元P、Q、R的小项为： P∧Q∧R，P∧Q ∧┐R ， P∧┐Q ∧R ， P∧┐Q ∧┐R ┐P∧Q ∧R ，┐ P∧Q ∧┐R ， ┐P∧┐Q ∧R ，┐P∧┐Q ∧┐R 。
同一命题公式可以有各种相互等价的表达形式,为了把命题公 式规范化,下面讨论命题公式的范式问题。
第一章 命题逻辑1.7对偶与范式
定义 (1) 一个命题公式称为合取范式，当且仅当它具有形式： A1 ∧ A2 ∧ … ∧ An， （n≥1） 其中A1，A2，…An都是由命题变元或其否定所组成的析取 式。 如：P ∧ ┐Q ， (P ∨ Q) ∧(P ∨┐Q ∨R), Q∧┐P (2) 一个命题公式称为析取范式，当且仅当它具有形式： A1 ∨ A2 ∨ … ∨ An， （n≥1） 其中A1，A2，…An都是由命题变元或其否定所组成的合取 式。 如：P∨┐Q ， (P ∧ Q) ∨(P ∧┐Q∧R), Q∨┐P. (3)范式：析取范式与合取范式统称为范式。 显然, 任何合(析)取范式的对偶式是析(合)取范式.
3
对合律 幂等律 结合律 交换律

例4将下列命题符号化。
(1)只要不下雨，我就骑自行车上班。
(2)只有不下雨，我才骑自行车上班。
(3)若 2+2＝4，则太阳从东方升起。
(3)若 2+2≠4，则太阳从东方升起。
(4)若 2+2＝4，则太阳从西方升起。
(5)若 2+2≠4，则太阳从西方升起。
解：在（1）、（2）中，设P：天下雨；Q：我骑自行车上
∧表示自然语言中的“既……又……”， “不仅……而且……”， “虽然……但是”
P Q P ∧Q
TT
T
TF
F
FT
F
FF
F
例3将下列命题符号化。 （1）李平既聪明又用功。 （2）李平虽然聪明，但不用功。 （3）李平不但聪明，而且用功。 （3）李平不是不聪明，而是不用功。
解：设P：李平聪明；Q：李平用功。 （1）P∧Q （2）P∧ᄀQ （3）P∧Q （4）ᄀ（ᄀP）∧ᄀQ
自然语言中的“或”具有二义性，有时表示
不相容的或。
例：“派小王或小李中的一人去开会” 。为排斥
性的或。
P：派小王去开会；Q：派小李去开会。 （P∧ᄀQ）∨（ᄀP∧Q） ， （P∨Q）∧ᄀ（P∧Q）
定义1－2.4 设P、Q为两命题，复合命题“如果P， 则Q”称作 P与Q的蕴涵式，记作P→Q，→为蕴涵联 结词。
1.命题公式 命题公式：由命题常量、命题变元、联结词、括号 等组成的符号串。
命题公式中的命题变元称作命题公式的分量。
定义1－3.1 （1）单个命题常量或命题变 元,Q,R,…,Pi,Qi,Ri,… ，F，T是合式公式。 （2）如果A是合式公式，则（ᄀA）也是合式公式。 （3）如果A、B是合式公式，则（A∧B）、（A