▪ 命题变项与合式公式 ▪ 公式的赋值
含n个变项的公式有多少个赋值？ 2n个
▪ 真值表 ▪ 命题的分类
重言式 矛盾式 可满足式
4
1.3 等值演算
▪ 等值式 ▪ 基本等值式 ▪ 等值演算 ▪ 置换规则
5
基本等值式
1、双重否定律 : AA
2、等幂律： AAA, AAA
3、交换律:
ABBA, ABBA
13
由 p, q, r 三个命题变项形成的极小项:
公式
p q r p q r p q r p q r p q r p q r p q r
pqr
成真赋值
000 001 010 011 100 101 110 111
极小项
m0 m1 m2 m3 m4 m5 m6 m7
14
主析取范式: 由极小项构成的析取范式. A的主析取范式: 与A等值的主析取范式. 用等值演算法求公式的主析取范式的步骤： (1)先求析取范式; (2)将不是极小项的简单合取式化成与之等值的
该式成立的条件是： ①无论A(y)中自由出现的个体变项y取何值，A(y)
应该均为真; ②取代自由出现的y的x, 不能在A(y)中约束出现.
36
(14) 存在量词引入规则（简记为EG规则或EG）
A( c ) xA( x)
该式成立的条件是： ①c是使A为真的特定个体常项; ②取代c的x不能在A(c)中出现过.
7
12、蕴涵等值式: ABAB
13、等价等值式: AB(AB)(BA)
14、假言易位:
ABBA
15、等价否定等值式: ABAB
16、归谬论:
(AB)(AB) A
8
等值演算与置换规则
等值演算: 由已知的等值式推演出新的等值式的过程。
置换规则：设 (A)是含公式A的命题公式， 若BA，则 (B) (A) .
3.3 集合中元素的计数
集合的基数与有穷集合 包含排斥原理 有穷集的计数
46
第4章 二元关系与函数
4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数
47
A1A2Ar , 其中A1, A2, , Ar 是简单析取式 求公式A的范式的步骤：
(1) 消去A中的, （若存在） (2) 内移或消去否定联结词 (3) 利用分配律
对分配（析取范式） 对分配（合取范式）
11
例1.1 求( pq) (p r) 的析取范式.
解: ( pq) (p r)
( pq) ( p r)
相对补 AB = { x | xA xB }
对称差 AB = (AB)(BA)
= (AB)(AB)
绝对补 A = EA
42
文氏图表示
43
集合运算的算律
交换 AB=BA AB=BA
结合 (AB)C= A(BC)
(AB)C= A(BC)
幂等 AA=A
AA=A
AB=BA (AB)C= A(BC)
与
分配 A(BC)=(AB)(AC) A(BC)=(AB)(AC)
29
例2.2 求下列公式的前束范式: (1) x(M(x)F(x))
解： x(M(x)F(x)) x(M(x)F(x)) (量词否定等值式) x(M(x)F(x))
两步结果都是前束范式，说明前束范式不惟一.
30
(2) xF(x)xG(x) 解: xF(x)xG(x)
xF(x)xG(x) x(F(x)G(x)) 另有一种形式:
33
推理规则
(1)前提引入规则 (3)置换规则 (5)附加规则 (7)拒取式规则 (9)析取三段论规则 (11)合取引入规则
(2)结论引入规则 (4)假言推理规则 (6)化简规则 (8)假言三段论规则 (10)构造性二难推理规则
34
(12) 全称量词消去规则（简记为UI规则或UI）
xA( x)
xA( x)
32
重要的推理定律
1. 命题逻辑推理定律代换实例 如 xF(x)yG(y) xF(x)为化简律代换实例.
2. 由基本等值式生成 如 由 xA(x)xA(x) 生成 xA(x)xA(x), xA(x)xA(x), …
3. 关于量词分配的推理定律 x A(x) xB(x) x(A(x) B(x)) x(A(x) B(x)) x A(x) x B(x) x(A(x) B(x)) xA(x) xB(x) x(A(x) B(x)) xA(x) xB(x)
(2) 令F(x): x为有理数, G(x): x能表示成分数, x(F(x)G(x)) 或 x(F(x) G(x))
(3) 令F(x): x参加考试, G(x): x取得好成绩, x(F(x) G(x)) 或 x(F(x) G(x))
23
2.2 一阶逻辑公式及解释
▪ 字母表 ▪ 合式公式(简称公式) ▪ 个体变项的自由出现和约束出现 ▪ 解释 ▪ 永真式（逻辑有效式） ▪ 矛盾式（永假式） ▪ 可满足式
39
3.1 集合的基本概念
集合的定义与表示
集合与元素 集合之间的关系 空集 全集 幂集
40
3.2 集合的基本运算
集合基本运算的定义
文氏图（John Venn） 例题 集合运算的算律 集合包含或恒等式的证明
41
集合基本运算的定义
并
AB = { x | xA xB }
交
AB = { x | xA xB }
若干个极小项的析取，需要利用同一律、排中 律、分配律、等幂律 …… (3)极小项用名称mi 表示，按角标从小到大顺序排序.
15
例1.2 求下列公式的主析取范式. ( p q) r
16
主合取范式: 由极大项构成的合取范式. A的主合取范式: 与A等值的主合取范式. 用等值演算法求公式的主合取范式的方法：
离散数学期末复习
1
第一章 命题逻辑
1.1 命题与联结词 1.2 命题公式与赋值 1.3 等值演算 1.4 析取范式与合取范式 1.5 命题逻辑的推理理论
2
1.1 命题与联结词
命题与真值
原子命题
复合命题
命题常项
命题变项
联结词： , , , , ，
优先顺序为：, , , , ;
①
②
③
3
1.2 命题公式与赋值
18
推理定律——重言蕴涵式
重要的推理定律 1. A (AB) 2. (AB) A 3. (AB)A B 4. (AB)B A 5. (AB)B A 6. (AB)(BC) (AC) 7. (AB)(BC) (AC) 8. (AB)(CD)(AC) (BD)
附加 化简 假言推理 拒取式 析取三段论 假言三段论 等价三段论 构造性二难
26
3. 量词辖域收缩与扩张等值式
设A(x)是含x自由出现的公式，B中不含x的出现 5)关于全称量词的： ① x(A(x)B)x A(x)B
② x(A(x)B)x A(x)B ③ x(A(x)B)x A(x)B ④ x(BA(x))Bx A(x)
27
ቤተ መጻሕፍቲ ባይዱ
6) 关于存在量词的: ① x(A(x)B)xA(x)B ② x(A(x)B)xA(x)B ③ x(A(x)B)xA(x)B ④ x(BA(x))BxA(x) 4. 量词分配等值式 7) x(A(x)B(x))xA(x)xB(x) 8) x(A(x)B(x))xA(x)xB(x) 注意：对无分配律，对无分配律!
A( y) 或 A(c)
两式成立的条件是：
①在第一式中，取代x的y应为任意的不在A(x)中
约束出现的个体变项;
②在第二式中，c为任意个体常项;
③用y或c去取代A(x)中的自由出现的x时，一定
要在x自由出现的一切地方进行取代.
35
(13) 全称量词引入规则（简记为UG规则或UG）
A( y) xA( x)
28
前束范式
定义 设A为一个一阶逻辑公式, 若A具有如下形 式Q1x1Q2x2…QkxkB, 则称A为前束范式, 其中Qi (1 i k)为或，B为不含量词的公式.
例如，xy(F(x)(G(y)H(x, y))) x(F(x)G(x)) 是前束范式,
而 x(F(x)y(G(y)H(x, y))) x(F(x)G(x)) 不是前束范式，
24
2.3 一阶逻辑等值式与前束范式
▪等值式 ▪基本等值式 ▪前束范式
25
基本等值式: 1. 消去量词等值式 设D = { a1, a2, …, an }
1) xA(x) A(a1)A(a2)…A(an) 2) xA(x) A(a1)A(a2)…A(an)
2. 量词否定等值式 3) xA(x) xA(x) 4) xA(x) xA(x)
等值演算的基础： (1)基本的等值式 (2)置换规则
9
1.4 析取范式与合取范式
▪ 简单析取式与简单合取式 ▪ 析取范式与合取范式 ▪ 主析取范式与主合取范式
10
析取范式: 由有限个简单合取式组成的析取式.
A1A2Ar , 其中A1, A2, , Ar 是简单合取式 合取范式: 由有限个简单析取式组成的合取式.
(量词否定等值式) (量词分配等值式)
xF(x)xG(x)
xF(x)xG(x) xF(x)yG(y) xy(F(x)G(y)) 两种形式是等值的.
(代替规则) (辖域扩张等值式)
31
2.4 一阶逻辑推理理论
▪ 推理的形式结构 ▪ 判断推理是否正确的方法 ▪ 重要的推理定律 ▪ 推理规则 ▪ 构造证明 ▪ 附加前提证明法
37
(15) 存在量词消去规则（简记为EI规则或EI）
xA( x) A(c)