一）考試說明

二）考前復(fù)習(xí)

【考試真題1】

【考試真題2】

[ 考點(diǎn)復(fù)習(xí) ]

1、數(shù)理邏輯

2、二元關(guān)系與格倫

3、圖論

4、代數(shù)系統(tǒng)

[ 本學(xué)期作業(yè) ]

三）學(xué)習(xí)筆記

第一章 命題邏輯

• 命題，表示法

• 聯(lián)結(jié)詞

（課后習(xí)題）

• 命題公式，翻譯

（課后習(xí)題）

• 真值表，等價公式

• 重言式，蘊(yùn)含式

（課后習(xí)題）

• 對偶式，范式

• 推理理論

① 直接證法
② 間接證法 / 反證法

③ CP 規(guī)則

第二章 謂詞邏輯

• 謂詞，表示法

一般地說，命題由主語和謂語兩部分組成

• 命題函數(shù)，量詞

簡單命題函數(shù)：一個謂詞、一些客體變元組成的表達(dá)式
全稱量詞：?（任意）
存在量詞：?（存在）

• 謂詞公式，翻譯

① 原子公式：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
約束變元：作用域中的作用變元，稱約束出現(xiàn)
自由變元：除了作用域中的作用變元，稱自由出現(xiàn)

B）例題

• 等價式，蘊(yùn)含式

① 量詞與聯(lián)結(jié)詞
┐(?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))

• 前束范式

• 推理理論

① 全稱指定規(guī)則（US）：若 (?x) P(x)，則 P(c)
例如：若全人類是傻子，則某個人是傻子
② 全稱推廣規(guī)則（UG）：若 P(x)，則 (?x) P(x)
例如：若每個人是傻子，則全人類是傻子
③ 存在指定規(guī)則（ES）：若 (?x) P(x)，則 P(c)
例如：若全人類存在傻子，則某個人是傻子
④ 存在推廣規(guī)則（EG）：若 P(c)，則 (?x) P(x)
例如：若某個人是傻子，則存在人類是傻子

第三章 集合與關(guān)系

• 集合

A）集合的表示
子集、真子集、空集 ?、全集 E、冪集 P
① 集合相等的充要條件是集合互為子集
② 若集合 A 有 n 個元素，則冪集元素個數(shù)：2^n

B）集合的運(yùn)算

• 序偶，笛卡爾積

• 關(guān)系，關(guān)系表示

A）關(guān)系，關(guān)系表示
任一序偶的集合確定了一個二元關(guān)系 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 的關(guān)系
① 子集 X × Y 叫 X 到 Y 的全域關(guān)系，子集 ? 叫 X 到 Y 的空關(guān)系
② Ix 是 X 上的二元關(guān)系，若 Ix = {〈 x, x 〉| x ∈ X } ， 則稱 Ix 為 X 上的恒等關(guān)系
③ 若 Z、S 是 X 到 Y 的兩個關(guān)系，則它們的交、并、補(bǔ)、差仍是 X 到 Y 的關(guān)系
D）關(guān)系的性質(zhì)

• 復(fù)合關(guān)系，逆關(guān)系

A）復(fù)合關(guān)系
R 為 X 到 Y 的關(guān)系，S 為 Y 到 Z 的關(guān)系，R S 稱為復(fù)合關(guān)系
∨ 代表邏輯加，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）逆關(guān)系
R 為 X 到 Y 的二元關(guān)系，若將 R 每一序偶的元素順序互換，得到逆關(guān)系 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 的關(guān)系，S 為 Y 到 Z 的關(guān)系，則 (R S)^c = S^c R^c
⑥ R 為 X 上的二元關(guān)系，R 對稱 ? R = R^c
R 為 X 上的二元關(guān)系，R 反對稱 ? R ∩ R^c ? Ix

• 閉包運(yùn)算

A）閉包
R 為 X 到 Y 的二元關(guān)系，若滿足 R ? R'
R' 自反 / 對稱 / 可傳遞，且對于任何自反 / 對稱 / 可傳遞的 R''
R ? R'’ 就有 R‘ ? R'’，則稱 R‘ 為 R 的閉包，記作 r(R) , ( s(R) , t(R) )
B）定理
( R 是含有 n 個元素的集合 X 上的二元關(guān)系 )
① 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}, , {c} }

• 等價關(guān)系，等價類

A）等價關(guān)系
R 為定義在集合 A 上的一個關(guān)系
若 R 是自反的、對稱的、傳遞的，則 R 稱為等價關(guān)系

B）等價類
R 為集合 A 上的一個等價關(guān)系
? a∈A，等價類 [ a ] _R = { x∈A , <a,x> ∈ R }

C）商集
R 為集合 A 上的一個等價關(guān)系 ，商集 A / R = { [ a ] _R | a ∈ A }

• 序關(guān)系

A）偏序關(guān)系
R 是集合 A 上的一個關(guān)系
若 R 滿足自反性、反對稱性、傳遞性，則稱 R 為 A 上的偏序關(guān)系
B）蓋住關(guān)系
< A, ≤ > 是一個偏序集合，若 x,y 屬于 A，
x ≤ z ，z ≤ y ，則稱元素 y 蓋住 x
記 COV A = {<x,y> | x,y 屬于 A; y 蓋住 x}
C）鏈與反鏈
< A, ≤ > 是一個偏序集合，若 A 的子集滿足每兩個元素都有關(guān)系，則稱這個子集為鏈
< A, ≤ > 是一個偏序集合，若 A 的子集滿足每兩個元素都沒有關(guān)系，則稱這個子集為反鏈
D）極大 (小) 元與最 (小) 元，下 (確) 界與上 (確) 界

第五章 代數(shù)結(jié)構(gòu)

• 代數(shù)系統(tǒng)的引入

① 對于集合 A，從 Aⁿ 到 B 的映射，稱為集合 A 上的 n 元運(yùn)算
若 B ? A，則稱該 n 元運(yùn)算是封閉的
② 非空集合 A 與若干在其定義上的運(yùn)算 f1, f2, ... , fn
所組成的系統(tǒng)稱為代數(shù)系統(tǒng)，記作 < A , f1 , f2 , ... , fn >

• 運(yùn)算性質(zhì)

• 半群

• 群與子群

• 交換群與循環(huán)群

1）若群 < G , * > 中運(yùn)算 * 可交換，則稱其為交換群（阿貝爾群）
2）設(shè) < G , * > 是群
① 滿足 (a * b) * (a * b) = (a * a) * (b * b) ? 它是交換群
② 若 G 中任意元素都是 a 的冪，則稱其為循環(huán)群，稱 a 為生成元
③ 任何一個循環(huán)群都是交換群