一）考试说明

二）考前复习

【考试真题1】

【考试真题2】

[ 考点复习 ]

1、数理逻辑

2、二元关系与格伦

3、图论

4、代数系统

[ 本学期作业 ]

三）学习笔记

第一章 命题逻辑

• 命题，表示法

• 联结词

（课后习题）

• 命题公式，翻译

（课后习题）

• 真值表，等价公式

• 重言式，蕴含式

（课后习题）

• 对偶式，范式

• 推理理论

① 直接证法
② 间接证法 / 反证法

③ CP 规则

第二章 谓词逻辑

• 谓词，表示法

一般地说，命题由主语和谓语两部分组成

• 命题函数，量词

简单命题函数：一个谓词、一些客体变元组成的表达式
全称量词：∀（任意）
存在量词：∃（存在）

• 谓词公式，翻译

① 原子公式：A (x1, x2, ... , xn)，x1, x2, ... , xn 是客体变元
② 谓词公式：A (x)，A (x, y)，A (f(x), y) 等等
若 A 是谓词公式，x 是 A 的变元，则 ┐A，(∀x)，(∃x) 也是谓词公式
若 A、B 都是谓词公式，则 (A∧B)，(A∨B)，(A→B)，(A⇄B) 也是谓词公式

③ 翻译

• 变元的约束

A） 概念
作用域：∀、∃ 后面的公式
作用变元：∀、∃ 后面的 x
约束变元：作用域中的作用变元，称约束出现
自由变元：除了作用域中的作用变元，称自由出现

B）例题

• 等价式，蕴含式

① 量词与联结词
┐(∀x) P(x) ⇔ (∃x) ┐P(x)
┐(∃x) P(x) ⇔ (∀x) ┐P(x)
② 量词的作用域
((∀x) A(x)→B) ⇔ (∃x) (A(x)→B)
((∃x) A(x)→B) ⇔ (∀x) (A(x)→B)
(B→(∀x) A(x)) ⇔ (∀x) (B→A(x))
(B→(∃x) A(x)) ⇔ (∃x) (B→A(x))

• 前束范式

• 推理理论

① 全称指定规则（US）：若 (∀x) P(x)，则 P(c)
例如：若全人类是傻子，则某个人是傻子
② 全称推广规则（UG）：若 P(x)，则 (∀x) P(x)
例如：若每个人是傻子，则全人类是傻子
③ 存在指定规则（ES）：若 (∃x) P(x)，则 P(c)
例如：若全人类存在傻子，则某个人是傻子
④ 存在推广规则（EG）：若 P(c)，则 (∃x) P(x)
例如：若某个人是傻子，则存在人类是傻子

第三章 集合与关系

• 集合

A）集合的表示
子集、真子集、空集 Ø、全集 E、幂集 P
① 集合相等的充要条件是集合互为子集
② 若集合 A 有 n 个元素，则幂集元素个数：2^n

B）集合的运算

• 序偶，笛卡尔积

• 关系，关系表示

A）关系，关系表示
任一序偶的集合确定了一个二元关系 R
任一序偶〈 x, y 〉可记作〈 x, y 〉∈ R 或 xRy
B）前域，值域，域
前域：dom R = { x | (∃ y) (〈 x, y 〉∈ R) }
值域：ran R = { y | (∃ x) (〈 x, y 〉∈ R) }

域：FLD R = dom R ∪ ran R

C）笛卡尔积 X × Y 的子集 R 称作 X 到 Y 的关系
① 子集 X × Y 叫 X 到 Y 的全域关系，子集 ∅ 叫 X 到 Y 的空关系
② Ix 是 X 上的二元关系，若 Ix = {〈 x, x 〉| x ∈ X } ， 则称 Ix 为 X 上的恒等关系
③ 若 Z、S 是 X 到 Y 的两个关系，则它们的交、并、补、差仍是 X 到 Y 的关系
D）关系的性质

• 复合关系，逆关系

A）复合关系
R 为 X 到 Y 的关系，S 为 Y 到 Z 的关系，R S 称为复合关系
∨ 代表逻辑加，0 ∨ 0 = 0，0 ∨ 1 = 1，1 ∨ 0 = 1，1 ∨ 1 = 1
∧ 代表逻辑乘，0 ∧ 0 = 0，0 ∧ 1 = 0，1 ∧ 0 = 0，1 ∧ 1 = 1
B）逆关系
R 为 X 到 Y 的二元关系，若将 R 每一序偶的元素顺序互换，得到逆关系 R^c
① (R1 ∪ R2)^c = R1^c ∪ R2^c
② (R1 ∩ R2)^c = R1^c ∩ R2^c
③ (A × B)^c = B × A
④ (R1 - R2)^c = R1^c - R2^c
⑤ R 为 X 到 Y 的关系，S 为 Y 到 Z 的关系，则 (R S)^c = S^c R^c
⑥ R 为 X 上的二元关系，R 对称 ⇔ R = R^c
R 为 X 上的二元关系，R 反对称 ⇔ R ∩ R^c ⊆ Ix

• 闭包运算

A）闭包
R 为 X 到 Y 的二元关系，若满足 R ⊆ R'
R' 自反 / 对称 / 可传递，且对于任何自反 / 对称 / 可传递的 R''
R ⊆ R'’ 就有 R‘ ⊆ R'’，则称 R‘ 为 R 的闭包，记作 r(R) , ( s(R) , t(R) )
B）定理
( R 是含有 n 个元素的集合 X 上的二元关系 )
① r (R) = R ∪ Ix
② s (R) = R ∪ R^c
③ t (R) = R1 ∪ R2 ∪ R3 ∪ ...
④ ∃ k ≤ n，t (R) = R1 ∪ R2 ∪ ... ∪ R^k
⑤ rs (R) = sr (R) ，rt (R) = tr (R) ，st (R) ⊆ ts (R)

• 集合的划分和覆盖

例：A = { a, b, c }
覆盖：S1 = { {a, b}, {a, c} } 、S2 = { {a}, {a, b}, {b, c} }
划分：G = { {a, b}, {c} }
最小划分：G1 = { {a, b, c} } ，最大划分：G2 = { {a}, {b}, {c} }

• 等价关系，等价类

A）等价关系
R 为定义在集合 A 上的一个关系
若 R 是自反的、对称的、传递的，则 R 称为等价关系

B）等价类
R 为集合 A 上的一个等价关系
∀ a∈A，等价类 [ a ] _R = { x∈A , <a,x> ∈ R }

C）商集
R 为集合 A 上的一个等价关系 ，商集 A / R = { [ a ] _R | a ∈ A }

• 序关系

A）偏序关系
R 是集合 A 上的一个关系
若 R 满足自反性、反对称性、传递性，则称 R 为 A 上的偏序关系
B）盖住关系
< A, ≤ > 是一个偏序集合，若 x,y 属于 A，
x ≤ z ，z ≤ y ，则称元素 y 盖住 x
记 COV A = {<x,y> | x,y 属于 A; y 盖住 x}
C）链与反链
< A, ≤ > 是一个偏序集合，若 A 的子集满足每两个元素都有关系，则称这个子集为链
< A, ≤ > 是一个偏序集合，若 A 的子集满足每两个元素都没有关系，则称这个子集为反链
D）极大 (小) 元与最 (小) 元，下 (确) 界与上 (确) 界

第五章 代数结构

• 代数系统的引入

① 对于集合 A，从 Aⁿ 到 B 的映射，称为集合 A 上的 n 元运算
若 B ⊆ A，则称该 n 元运算是封闭的
② 非空集合 A 与若干在其定义上的运算 f1, f2, ... , fn
所组成的系统称为代数系统，记作 < A , f1 , f2 , ... , fn >

• 运算性质

• 半群

• 群与子群

• 交换群与循环群

1）若群 < G , * > 中运算 * 可交换，则称其为交换群（阿贝尔群）
2）设 < G , * > 是群
① 满足 (a * b) * (a * b) = (a * a) * (b * b) ⇔ 它是交换群
② 若 G 中任意元素都是 a 的幂，则称其为循环群，称 a 为生成元
③ 任何一个循环群都是交换群