離散數(shù)學(xué)概念總結(jié)

命題邏輯

命題

能確定真值的陳述句

原子命題

不能再細分的命題

復(fù)合命題

由聯(lián)結(jié)詞父腕、標點符號和原子命題復(fù)合構(gòu)成的命題

重言式

給定一個命題公式质涛，若無論對分量作怎樣的指派，其對應(yīng)的真值永為 $T$ 境蜕，則稱命題公式為重言式

蘊含式

設(shè) $p, q$ 為兩個命題鳄梅，復(fù)合命題“如果 $p$ 則 $q$ ”稱為 $p$ 與 $q$ 的蘊含式纺讲，記作 $p \rightarrow q$

矛盾式

無論對分量作怎樣的指派，其對應(yīng)的真值永為 $F$ 综苔，記為 $F$

子公式

如果 $X$ 是合式公式 $A$ 的一部分惩系，且 $X$ 本身也是一個合式公式，則稱 $X$ 為公式 $A$ 的子公式

置換

設(shè) $X$ 是合式公式 $A$ 的子公式如筛，且 $X \Leftrightarrow Y$ ，將 $A$ 中的 $X$ 用 $Y$ 來置換抒抬，得到新的公式 $B$ 杨刨，則 $A \Leftrightarrow B$

命題公式

單個命題變元是一個命題公式

如果 $A$ 和 $B$ 是命題公式，那么 $\neg A, (A \land B), (A \lor B), (A \rightarrow B), (A \Leftrightarrow B)$ 都是命題公式

當且僅當能夠有限次地應(yīng)用(1),(2)生成的公式是命題公式

命題公式的等價

設(shè)命題公式 $A$ 和 $B$ 擦剑， $P_1$ , $P_2$ , ..., $P_n$ 為所有出現(xiàn)于 $A$ 和 $B$ 中的原子變元妖胀，若給 $P_1$ , $P_2$ , ..., $P_n$ 任一組真值指派， $A$ 和 $B$ 的真值都相同惠勒。則稱 $A$ 和 $B$ 是等價的

命題公式的對偶式

命題公式 $A$ 中含聯(lián)結(jié)詞 $\land$ 赚抡， $\lor$ ，將 $\land$ 與 $\lor$ 互換纠屋，T 與 F 互換所得公式 $A^{*}$ 稱為 $A$ 的對偶式

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

$\overline{\lor}$ ：不可兼析取

$\xrightarrow{c}$ ：條件否定

$\uparrow$ ：與非

$\downarrow$ ：或非

范式

求范式的步驟

將命題公式的聯(lián)結(jié)詞全部化為 $\neg, \land, \lor$

利用德·摩根律涂臣，將否定符號 $\neg$ 直接移到各命題變元之前

利用分配律、結(jié)合律將命題公式化為范式

小項

$n$ 個命題變元 $P_1, P_2, \dots, P_n$ 的合取式售担，稱為布爾合取或小項赁遗，在任一小項中
1. 每個變元 $P_i$ 與它的否定 $\neg P_i$ 不能同時出現(xiàn)
1. 但 $P_i$ 與 $\neg P_i$ 必須出現(xiàn)且僅出現(xiàn)一次

大項

$n$ 個命題變元 $P_1, P_2, \dots, P_n$ 的析取式，稱為布爾析取或大項族铆，在任一小項中
1. 每個變元 $P_i$ 與它的否定 $\neg P_i$ 不能同時出現(xiàn)
1. 但 $P_i$ 與 $\neg P_i$ 必須出現(xiàn)且僅出現(xiàn)一次

謂詞邏輯

謂詞公式

原子謂詞公式是謂詞公式

若 $A$ 是謂詞公式則 $\neg A$ 是一個謂詞公式

若 $A$ 和 $B$ 都是謂詞公式岩四，則 $(A \land B)$ ， $(A \lor B)$ 哥攘， $(A \rightarrow B)$ 和 $(A \Leftrightarrow B)$ 是謂詞公式

如果 $A$ 是謂詞公式剖煌， $x$ 是 $A$ 中出現(xiàn)的任何變元材鹦，則 $(\forall x)A$ 和 $(\exist x)A$ 都是謂詞公式

只有經(jīng)過有限次應(yīng)用規(guī)則(1), (2), (3), (4)所得到的公式是謂詞公式

謂詞公式的等價

任意給定兩個謂詞公式wff $A$ 和wff $B$ ，設(shè)它們有共同的個體域 $E$ 耕姊，若對 $A$ 和 $B$ 的任一組變元進行賦值侠姑，所得命題的真值相同，則稱謂詞公式 $A$ 和 $B$ 在 $E$ 上是等價的箩做，并記作： $A \Leftrightarrow B$

前束范式

定義

所有量詞都位于該公式的最左邊

所有量詞前都不含否定

量詞都轄域都延伸到整個公式都末端

運算方法

消去 $\Rightarrow$ 莽红、 $\Leftarrow$

否定 $\neg$ 右移

量詞左移（分配等值、轄域收縮擴張邦邦、變項改名）

分配等值：
- $(\forall x)(A(x) \land B(x)$ $\equiv$ $(\forall x)A(x) \land (\forall x)B(x)$ $\forall$ 對 $\lor$ 不滿足
- $(\exist x)(A(x) \lor B(x))$ $\equiv$ $(\exist x)A(x) \lor (\exist x)B(x)$ $\exist$ 對 $\land$ 不滿足
轄域收縮擴張： $(\forall x)(A(x) \lor B(x)) \equiv (\forall x)A(x) \lor B$ 安吁， $A(x)$ 含 $x$ 自由出現(xiàn)， $B$ 不含 $x$

推理理論

P規(guī)則

前提引入：前提在推導(dǎo)過程中的任何時候都可以引入

T規(guī)則

結(jié)論引用：在推導(dǎo)中燃辖，如果有一個或多個公式重言蘊含著公式 $S$ （結(jié)論）鬼店，則公式 $S$ 可以引入推導(dǎo)之中

CP規(guī)則

要證明，轉(zhuǎn)化為證明
- R：附加前提

全稱指定規(guī)則（US）

$\Large{\frac{(\forall x)P(x)}{\therefore P(c)}}$

$\Large{\frac{(\forall x)P(x)}{\therefore P(y)}}$

全稱推廣原則（UG）

$\Large{\frac{P(x)}{\therefore (\forall x)P(x)}}$

存在制定原則（ES）

$\Large{\frac{(\exist x)P(x)}{\therefore P(c)}}$

存在推廣原則（EG）

$\Large{\frac{P(c)}{\therefore (\exist x)P(x)}}$

集合論

平凡子集

非空集合 $A$ 的子集 $A$ 和 $\emptyset$

全集

在一定范圍內(nèi)黔龟，若所有集合均為某一集合的子集妇智，則稱該集合為全集，記作 $E$

冪集

給定集合 $A$ 氏身，以 $A$ 的全體子集為元素構(gòu)成的集合巍棱，稱為 $A$ 的冪集，記為 $\mathscr{P}$ （或 $2^A$ ）

商集

設(shè) $R$ 為非空集合 $A$ 上的等價關(guān)系蛋欣，其等價類集合 $\{[a]_R|a \in A\}$ 稱為 $A$ 關(guān)于 $R$ 的商集航徙，記為 $A \setminus R$

集合的劃分

設(shè) $A$ 為非空集合， $S = \{ S_1, S_2, ..., S_n \}$ 陷虎，其中 $S_i \subseteq A$ , $S_i \neq \varnothing (i = 1, 2, ..., m)$ 到踏，
$\bigcup_{i = 1}^m S_i = A$
$S_i \bigcap S_j = \varnothing$ $(i \neq j , i, j = 1, 2, ..., m)$ ，則稱 $S$ 為 $A$ 的劃分

例：集合 $A$ 的一個劃分確定 $A$ 的元素間的一個等價關(guān)系

證明：

設(shè)集合 $A$ 有一個劃分 $S = \{S_1, S_2, \cdots, S_m\}$ 尚猿，現(xiàn)定義一個關(guān)系 $R$ 窝稿， $aRb$ 當且僅當 $a, b$ 在同一分塊中≡涞啵可以證明這樣規(guī)定的關(guān)系 $R$ 是一個等價關(guān)系伴榔。因為

$a$ 與 $a$ 在同一分塊中，故必有 $aRa$ 缠劝。即 $R$ 是自反的

若 $a$ 與 $b$ 在同一分塊中傀顾， $b$ 與 $a$ 也必在同一分塊中例书，即 $aRb \Rightarrow bRa$ ,故 $R$ 是對稱的

若 $a$ 與 $b$ 在同一分塊中况褪， $b$ 與 $c$ 在同一分塊中通熄，因為

$S_i \cap S_j = \varnothing (i \neq j)$

即 $b$ 屬于且僅屬于一個分塊，故 $a$ 與 $c$ 必在同一分塊中脱羡，故有

$(aRb) \land (bRc) \Rightarrow (aRc)$

即 $R$ 是傳遞的萝究。

$R$ 滿足上述三個條件免都，故 $R$ 是等價關(guān)系，由 $R$ 的定義可知帆竹， $S$ 就是 $A \setminus R$

集合的覆蓋

設(shè) $A$ 為非空集合绕娘， $S = \{S_1, S_2, ..., S_n\}$ 其中 $S_n \subseteq A$ , $S_i \neq \varnothing$ $(i = 1, 2, ..., m)$
$\bigcup_{i = 1}^m S_i = A$
則稱 $S$ 為 $A$ 的覆蓋

交叉劃分

若 $\{A_1, A_2, \cdots, A_r\}$ 與 $\{B_1, B_2, \cdots, B_s\}$ 是同一集合 $X$ 的兩種劃分，則其中所有 $A_i \cap B_i \neq \varnothing$ 組成的集合栽连，稱為是原來兩種劃分的交叉劃分

劃分的加細

設(shè) $\{A_1, A_2, \cdots, A_r\}$ 與 $\{B_1, B_2, \cdots, B_s\}$ 是同一集合 $X$ 的兩種劃分险领，若對于每個 $A_j$ 均有 $B_k$ ，使 $A_j \subseteq B_k$ 秒紧，則 $\{A_1, A_2, \cdots, A_r\}$ 稱為是 $\{B_1, B_2, \cdots, B_s\}$ 的加細

集合的等勢

集合 $A$ 的元素與集合 $B$ 的元素之間存在一一對應(yīng)

集合的對稱差

設(shè) $A$ 和 $B$ 為任意兩個集合绢陌， $A$ 和 $B$ 的對稱差是由或者屬于 $A$ ，或者屬于 $B$ 熔恢，但不能既屬于 $A$ 又屬于 $B$ 但元素所組成的集合

集合的基數(shù)

所有與集合 $A$ 等勢的集合所組成的集合脐湾，叫做集合 $A$ 的基數(shù)，記為 $K[A]$ （或 $\overline{\overline{A}}$ ）

無限集

設(shè) $A$ 為一個集合叙淌，若 $A$ 為空集或與集合 $\{0, 1, \cdots, n - 1\}$ 等勢秤掌，則稱 $A$ 為有限集，否則 $A$ 為無限集
等價定義： $A$ 是無限集當且僅當與其某一個真子集等勢

可數(shù)集

與自然數(shù)集合等勢的集合

連續(xù)統(tǒng)的勢

$\aleph$ ：我們把集合 $(0, 1)$ 的基數(shù)記為" $\aleph$ "鹰霍，因為 $(0, 1)$ ~ $R$ 闻鉴，故 $K[R]=\aleph$

可數(shù)集合的基數(shù)

$\aleph_0$ ：與自然數(shù)集合等勢的任意集合稱為可數(shù)的，可數(shù)集合的基數(shù)用 $\aleph_0$ 表示

集合的置換

設(shè) $S$ 是一個非空集合衅谷，從集合 $S$ 到 $S$ 的一個雙射稱為 $S$ 的一個置換

集合的運算

集合的對稱差

$A \oplus B = (A - B) * (B - A) = \{x|x \in A \overline{\lor} x \in B\}$

又稱環(huán)和

關(guān)系

笛卡爾積的子集為關(guān)系

笛卡爾積

令 $A$ 和 $B$ 是任意兩個集合椒拗，若序偶的第一個成員是 $A$ 的元素，第二個成員是 $B$ 的元素获黔，所有這樣的序偶集合，稱為集合 $A$ 和 $B$ 的笛卡爾積在验，記作 $A \times B$

集合 $A$ 上的二元關(guān)系

$A \times A$ 的一個子集為集合 $A$ 上的一個二元關(guān)系

對稱關(guān)系

設(shè) $R$ 是 $X$ 上的關(guān)系玷氏，對于每一個 $x, y \in X$ ，每當 $xRy$ 時腋舌，就有 $yRx$ 盏触，則稱 $R$ 為 $X$ 上的對稱關(guān)系

反對稱關(guān)系

設(shè) $R$ 為 $X$ 上的關(guān)系，對于每一個 $x, y \in X$ 块饺，每當 $xRy$ 赞辩， $yRx$ 時，必有 $x = y$ 授艰，則稱 $R$ 為 $X$ 上的反對稱關(guān)系

等價關(guān)系

一個二元關(guān)系若滿足自反性辨嗽，對稱性和傳遞性則稱為等價關(guān)系

等價類

設(shè) $R$ 是非空集合 $A$ 上的等價關(guān)系， $\forall a \in A$ 淮腾，令

$[a]_R = \{x|x \in A \land aRx\}$

稱 $[a]_R$ 為 $a$ 關(guān)于 $R$ 的等價類

簡稱為 $a$ 的等價類糟需，簡記為 $[a]$

$a$ 稱為等價類 $[a]_R$ 的代表元素

相容關(guān)系

若集合 $A$ 上的二元關(guān)系 $R$ 是：
1. 自反的
1. 對稱的
則稱 $R$ 是 $A$ 上的相容關(guān)系

相容關(guān)系又稱相似關(guān)系

相容類

設(shè) $R$ 是集合 $A$ 的相容關(guān)系屉佳，子集 $B$ 滿足 $\forall x, y \in B, xRy$ ，則稱 $B$ 為 $A$ 關(guān)于 $R$ 的相容類

最大相容類

設(shè) $R$ 是集合 $A$ 的相容關(guān)系洲押，子集 $B$ 滿足：
1. $\forall x, y \in B, xRy$
1. $\forall x \in A - B, \exist z \in B, x$ R $z$
則稱 $B$ 為 $A$ 關(guān)于 $R$ 的最大相容類

完全覆蓋

在集合 $A$ 上給定相容關(guān)系 $R$ 武花，其最大相容類的集合，稱作集合 $A$ 的完全覆蓋杈帐，記作 $C_R(A)$

偏序關(guān)系

若集合 $A$ 上的二元關(guān)系 $R$ 是自反的体箕、反對稱的和傳遞的，則稱 $R$ 是 $A$ 上的偏序關(guān)系

序偶 $<A, R>$ 稱為偏序集

又稱半序

蓋住

設(shè) $<A, \preccurlyeq>$ 為偏序集挑童， $\forall x, y \in A$ 累铅，若 $x \preccurlyeq y，x \neq y$ 炮沐，且不存在 $z \in A$ 使得 $x \preccurlyeq z \preccurlyeq y$ 争群，則稱 $y$ 蓋住 $x$

哈斯圖

設(shè)有偏序集 $<A, \preccurlyeq>$ ， $\forall x, y \in A (x \neq y)$ 大年，適當排列結(jié)點的順序使得：
1. 若 $x \preccurlyeq y$ 换薄，則將 $x$ 畫在 $y$ 的下方
1. 若 $y$ 蓋住 $x$ ，則用一條直線連接 $x$ 和 $y$

偏序集合的子集的特殊元素

? 設(shè) $<A, \preccurlyeq>$ 為偏序集翔试， $B \subseteq A$ 轻要，對 $a \in A$ ， $b \in B$

極大元

若 $B$ 中不存在元素 $x$ 垦缅，使 $b \neq x$ 且 $b \preccurlyeq x$ 冲泥，則 $b$ 為 $B$ 的極大元

$(\forall x \in B)(b \preccurlyeq x \rightarrow x = b)$

極小元

若 $B$ 中不存在元素 $x$ ，使 $b \neq x$ 且 $x \preccurlyeq b$ 壁涎，則 $b$ 為 $B$ 的極小元

$(\forall x \in B)(x \preccurlyeq b \rightarrow x = b)$

最大元

若 $B$ 中任意元素 $x$ 凡恍，有 $x \preccurlyeq b$ ，則稱 $b$ 為 $B$ 的最大元

$(\forall x)(x \in B \rightarrow x \preccurlyeq b)$

最小元

若 $B$ 中任意元素 $x$ 怔球，有 $b \preccurlyeq x$ 嚼酝，則稱 $b$ 為 $B$ 的最小元

$(\forall x)(x \in B \rightarrow b \preccurlyeq x)$

最大元與極大元的比較

最大元與其他所有元素均可比；而極大元不一定與所有元素都可比竟坛，只要沒有比它大的元素闽巩，它就是極大元

都不一定存在，但非空有限元中極大元一定存在

最大元存在即唯一担汤，極大元可有多個

唯一的極大元 $\iff$ 最大元

上界

若 $(\forall x)(x \in B \rightarrow x \preccurlyeq a)$ 成立涎跨，則稱 $a$ 為 $B$ 的上界

下界

若 $(\forall x)(x \in B \rightarrow a \preccurlyeq x)$ 成立，則稱 $a$ 為 $B$ 的下界

上確界

設(shè) $a$ 是 $B$ 的一個上界崭歧，若對所有上界 $y$ 均有 $a \preccurlyeq y$ 隅很，則稱 $a$ 為 $B$ 的最小上界或上確界，記為 $\mathrm{LUB}B$ 或 $\mathrm{sup}B$

下確界

設(shè) $b$ 是 $B$ 的一個下界驾荣，若對 $B$ 的所有下界 $z$ 均有 $z \preccurlyeq b$ 外构，則稱 $b$ 為 $B$ 的最大下界或下確界普泡，記為 $\mathrm{GLB}B$ 或 $\mathrm{inf}B$

擬序關(guān)系

設(shè) $A$ 是一個集合，如果 $A$ 上的一個集合 $R$ 审编，滿足反自反的和傳遞的撼班，則稱 $R$ 是 $A$ 上的一個擬序關(guān)系

全序關(guān)系

在偏序集 $<A, \preccurlyeq>$ 中，若 $A$ 是一個鏈垒酬，則稱 $<A, \preccurlyeq>$ 為全序集合或線序集合

自反外永、反對稱剩失、傳遞纫事、每個元素之間都有關(guān)系

良序集合

在偏序集 $<A, \preccurlyeq>$ 中刹衫，若 $A$ 的每一個非空子集總含有最小元，則稱 $<A, \preccurlyeq>$ 為良序集合

自反口糕、反對稱缅阳、傳遞、每個元素之間都有關(guān)系景描、子集存在最小元

稱二元關(guān)系 $\preccurlyeq$ 為 $A$ 上的良序

$\{良序\} \subseteq \{全序\} \subseteq \{偏序\}$

對稱閉包

設(shè) $R$ 是一個二元關(guān)系十办，如果存在一個關(guān)系 $R'$ 滿足： $R'$ 是對稱的， $R' \supseteq R$ 超棺，對于任何對稱關(guān)系 $R''$ 向族，如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ ，則稱 $R'$ 為 $R$ 的對稱閉包

自反閉包

設(shè) $R$ 是一個二元關(guān)系棠绘，如果存在一個關(guān)系 $R'$ 滿足： $R'$ 是自反的件相； $R' \supseteq R$ ；對于任何自反的關(guān)系 $R''$ 如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ 氧苍，則稱 $R'$ 為 $R$ 的自反閉包

傳遞閉包

設(shè) $R$ 是一個二元關(guān)系夜矗，如果存在一個關(guān)系 $R'$ 滿足： $R'$ 是傳遞的； $R' \supseteq R$ 让虐；對于任何傳遞的關(guān)系 $R''$ 如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ 侯养，則稱 $R'$ 為 $R$ 的傳遞閉包

Warshall算法

procedure Warshell（ $M_R: n \times n$ 的 0-1 矩陣）

$W := M_R$

for $k := 1$ to $n$ //按列遍歷

? ? for $i := 1$ to $n$

? ? ? ? for $j := 1$ to $n$

? ? ? ? $w_{ij} := w_{ij} \lor (w_{ik} \land w_{kj})$ //若第 $j$ 列是1則把第 $j$ 行上的元素邏輯加到第 $i$ 行上

return $W\{W = [w_{ij}] 是 M_{R^*}\}$

主對角線可跳過

第 $i$ 行均為零可跳過

鏈

設(shè) $<A, \preccurlyeq>$ 是一個偏序集合，在 $A$ 的一個子集中澄干，如果每兩個元素都是有關(guān)系的，則這個子集為鏈

反鏈

設(shè) $<A, \preccurlyeq>$ 是一個偏序集合柠傍，在 $A$ 的一個子集中麸俘，如果每兩個元素都是無關(guān)的，則這個子集為反鏈

函數(shù)

設(shè) $X$ 和 $Y$ 是任何兩個集合惧笛， $f$ 是 $X$ 到 $Y$ 的一個關(guān)系从媚，如果對于每一個 $x \in X$ ，有唯一的 $y \in Y$ 患整，使得 $<x, y> \in f$ 拜效，則稱關(guān)系 $f$ 為函數(shù)

亦稱 $f$ 為 $X$ 到 $Y$ 的映射

滿射

對于映射 $f: X \rightarrow Y$ 喷众，如果 $ranf = Y$ 則稱這個映射為滿射

入射

對于映射 $f: X \rightarrow Y$ ，如果 $\forall y \in ranf$ 都存在唯一的 $x \in X$ 使得 $f(x) = y$ 紧憾，則稱 $f: X \rightarrow Y$ 是入射（或一對一映射）

雙射

若 $f: X \rightarrow Y$ 既是滿射又是入射到千，則稱 $f: X \rightarrow Y$ 是雙射

逆函數(shù)

設(shè) $f: X \rightarrow Y$ 是一雙射函數(shù)，稱 $Y \rightarrow X$ 的雙射函數(shù) $f^c$ 為 $f$ 的逆函數(shù)赴穗，記作 $f^{-1}$

常函數(shù)

函數(shù) $f: X \rightarrow Y$ 憔四， $\exist y_0 \in Y$ ，使得 $\forall x \in X$ 般眉， $f(x) = y_0$ 了赵，即 $f(X) = y_0$

恒等函數(shù)

如果 $I_X = \{<x, x>|x \in X\}$ ，則稱函數(shù) $I_X: X \rightarrow X$ 為恒等函數(shù)

基數(shù)的比較

概念

如果兩個集合能夠建立雙射函數(shù)甸赃，則該兩集合應(yīng)具有相同的基數(shù)
連續(xù)統(tǒng)的勢 $\aleph$ ：我們把集合 $(0, 1)$ 的基數(shù)記為" $\aleph$ "柿汛，因為 $(0, 1)$ ~ $R$ ，故 $K[R]=\aleph$
可數(shù)集合的基數(shù) $\aleph_0$ ：與自然數(shù)集合等勢的任意集合稱為可數(shù)的埠对，可數(shù)集合的基數(shù)用 $\aleph_0$ 表示
若從集合 $A$ 到集合 $B$ 存在一個入射络断，則稱 $A$ 的基數(shù)不大于 $B$ 的基數(shù)，記作 $K[A] \leqslant K[B]$
若從集合 $A$ 到集合 $B$ 存在一個入射鸠窗，但不存在雙射妓羊，則稱 $A$ 的基數(shù)小于 $B$ 的基數(shù)，記作 $K[A] < K[B]$

Cantor-Schroder-Bernstein 定理

設(shè) $A$ 和 $B$ 是任意集合稍计，若 $K[A] \leqslant K[B], K[B] \leqslant K[A]$ 躁绸，則 $K[A] = K[B]$

例題

證明 $[0,1]$ 和 $(0,1)$ 有相同的基數(shù)

證明：作入射函數(shù)：

$f: (0, 1) \rightarrow [0, 1], f(x) = x$

$g: [0, 1] \rightarrow (0, 1), g(x) = \frac{x}{2} + \frac{1}{4}$

設(shè) $A = N$ ， $B=(0,1)$ 臣嚣， $K[A] = \aleph_0$ 净刮， $K[B] = \aleph$ ，求證： $K[A \times B] = \aleph$

證明：
定義一個從 $A \times B$ 到正實數(shù)的函數(shù) $f$ 硅则，

$f: A \times B \rightarrow \{x|x \in R_+\}$ > $f(n, x) = n + x$

因為 $f$ 是一個入射函數(shù)淹父，且 $K[R_+] = \aleph$

所以 $K[A \times B] \leqslant \aleph$

此外，作映射 $g: (0, 1) \rightarrow A \times B$

$g(x) = <0, x>$

因為 $g$ 是入射的怎虫，故 $\aleph \leqslant K[A \times B]$

因此 $K[A \times B] = \aleph$

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

閉運算

對于集合 $A$ 暑认，一個從 $A^n$ 到 $B$ 的映射，稱為集合 $A$ 上的一個 $n$ 元運算大审，如果 $B \subseteq A$ 蘸际，則稱該 $n$ 元運算是封閉的（集合 $R$ 上的運算的結(jié)果都是在原來的集合 $R$ 中）

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

一個非空集合 $A$ 連同若干個定義在該集合上的運算 $f_1, f_2, \cdots , f_k$ 所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作 $<A, f_1, f_2, \cdots, f_k>$

二元運算

運算性質(zhì)

封閉性

設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算徒扶，如果對于任意的 $x, y \in A$ 粮彤，都有 $x * y \in A$ ，則稱二元運算 $*$ 在 $A$ 上是封閉的
- 表中每個元素都屬于 $A$

可交換性

設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算，如果對于任意的 $x, y \in A$ 导坟，都有 $x * y = y * x$ 屿良，則稱該二元運算是可交換的
- 表關(guān)于主對角線是對稱的

可結(jié)合性

設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算，如果對于任意的 $x, y \in A$ 惫周，都有 $(x * y) * z = x * (y * z)$ 尘惧，則稱該二元運算 $*$ 是可結(jié)合的

可分配性

設(shè) $*, \triangle$ 是定義在集合 $A$ 上的兩個二元運算，如果對于任意的 $x, y \in A$ 闯两，都有

$x * (y \triangle z) = (x * y) \triangle (x * z)$
$(y \triangle z) * x = (y * x) \triangle (z * x)$
則稱運算 $*$ 對運算 $\triangle$ 是可分配的

吸收律

設(shè) $*, \triangle$ 是定義在集合 $A$ 上的兩個二元運算褥伴，如果對于任意的 $x, y \in A$ ，都有

$x * (x \triangle y) = x$
$x \triangle (x * y) = x$
則稱運算 $*$ 和運算 $\triangle$ 滿足吸收律

等冪性

設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算漾狼，如果對于任意的 $x \in A$ 重慢，都有 $x * x = x$ ，則稱運算 $*$ 是等冪的
- 運算表的主對角線上的每個元素與它所在的行（列）表頭元素相同

幺元

左幺元： $\exist e_l \in A$ 逊躁， $\forall x \in A$ 都有 $e_l * x = x$
右幺元： $\exist e_r \in A$ 似踱， $\forall x \in A$ 都有 $x * e_r = x$
幺元： $\exist e \in A$ ， $\forall x \in A$ 稽煤，有 $e * x = x * e = x$
- 設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算核芽，且在 $A$ 中有關(guān)于運算 $*$ 的左幺元 $e_l$ 和右幺元 $e_r$ ，則 $e_l = e_r = e$ 酵熙，且 $A$ 中的幺元是唯一的
表中元素所對應(yīng)的行和列依次與運算表的行和列一致

零元

左零元： $\exist \theta_l \in A$ 轧简， $\forall x \in A$ 都有 $\theta_l * x = \theta_l$
右幺元： $\exist \theta_r \in A$ ， $\forall x \in A$ 都有 $x * \theta_r = \theta_r$
幺元： $\exist \theta \in A$ 匾二， $\forall x \in A$ 哮独，有 $\theta * x = x * \theta = \theta$
- 設(shè) $*$ 是定義在集合 $A$ 上的一個二元運算，且在 $A$ 中有關(guān)于運算 $*$ 的左零元 $\theta_l$ 和右零元 $\theta_r$ 察藐，則 $\theta_l = \theta_r = \theta$ 皮璧，且 $A$ 中的零元是唯一的
表中元素所對應(yīng)的行和列中的元素都與該元素相同

逆元

左逆元： $\exist b \in A$ ， $\exist a \in A$ 分飞，使得 $b * a = e$
右逆元： $\exist b \in A$ 铲敛， $\exist a \in A$ 叮叹，使得 $a * b = e$
逆元： $\exist b \in A$ ， $\exist a \in A$ 绷旗， $b$ 既是 $a$ 的右逆元又是 $a$ 的左逆元
- $b = a^{-1}$
左右逆元不一定相等掸读、不一定唯一咆疗、不一定同時存在
表中 $a$ 和 $b$ 互逆舟误，當且僅當位于 $a$ 所在行颠毙， $b$ 所在列的元素以及 $b$ 所在行， $a$ 所在列的元素都是幺元

群

群的概念

群的定義

$\{群\} \subset \{獨異點\} \subset \{半群\} \subset \{廣群\}$

廣群

一個代數(shù)系統(tǒng) $<S, *>$ 肌索，其中 $S$ 是非空集合， $*$ 是 $S$ 上的一個二元運算，如果 $*$ 是封閉的诚亚，則稱代數(shù)系統(tǒng) $<S, *>$ 為廣群

半群

一個代數(shù)系統(tǒng) $<S, *>$ 晕换，其中 $S$ 是非空集合， $*$ 是 $S$ 上的一個二元運算站宗，如果：
1. 運算 $*$ 是封閉的
1. 運算 $*$ 是可結(jié)合的闸准，即對任意的 $x, y, z \in S$ 滿足
  
  $(x * y) * z = x * (y * z)$
  
  則稱代數(shù)系統(tǒng) $<S, *>$ 為半群

子半群

設(shè) $<S, *>$ 是一個半群， $B \subseteq S$ 且 $*$ 在 $B$ 上是封閉的梢灭，那么 $<B, *>$ 也是一個半群夷家。通常稱 $<B, *>$ 是半群 $<S, *>$ 的子半群

獨異點

含有幺元的半群稱為獨異點
- 性質(zhì)：
  - 設(shè) $<S, *>$ 是一個獨異點，則在關(guān)于運算 $*$ 的運算表中任何兩行和兩列都是不相同的
  - 設(shè) $<S, *>$ 是獨異點敏释，對于任意 $a, b \in S$ 库快，且 $a, b$ 均有逆元，則
  - $(a^{-1})^{-1} = a$
  - $a * b$ 有逆元钥顽，且 $(a * b)^{-1} = b^{-1} * a^{-1}$

群

設(shè) $<G, *>$ 是一個代數(shù)系統(tǒng)义屏，其中 $G$ 是非空集合， $*$ 是 $G$ 上的一個二元運算蜂大，如果
1. 運算 $*$ 是封閉的
1. 運算 $*$ 是可結(jié)合的
1. 存在幺元 $e$
1. 對于每一個元素 $x \in G$ 闽铐，存在這它的逆元 $x^{-1}$
則稱 $<G, *>$ 是一個群

有限群

設(shè) $<G, *>$ 是一個群。如果 $G$ 是有限集奶浦，那么稱 $<G, *>$ 為有限群

有限群的階數(shù)

有限集 $G$ 中元素的個數(shù)兄墅，記為 $|G|$

無限群

設(shè) $<G, *>$ 是一個群。如果 $G$ 是無限集澳叉，那么稱 $<G, *>$ 為無限群

等冪元

代數(shù)系統(tǒng) $<G, *>$ 中隙咸，如果存在 $a \in G$ ，有 $a * a = a$ 耳高，則稱 $a$ 為等冪元

子群

設(shè) $<G, *>$ 是一個群扎瓶， $S$ 是 $G$ 的一個非空子集，如果 $<S, *>$ 也構(gòu)成群泌枪，則稱 $<S, *>$ 是 $<G, *>$ 的一個子群

阿貝爾群

如果群 $<G, *>$ 中的運算 $*$ 是可交換的概荷，則該群為阿貝爾群，或稱交換群

循環(huán)群

設(shè) $<G, *>$ 為群碌燕，若存在 $a \in G$ 误证，使得 $G$ 中的任意元素都由 $a$ 的冪組成，則稱該群為循環(huán)群修壕，元素 $a$ 稱為循環(huán)群 $G$ 的生成元

左陪集

設(shè) $<H, *>$ 是群 $<G, *>$ 的一個子群愈捅， $a \in G$ ，則集合 $\{a\}H$ 稱為由 $a$ 所確定的 $H$ 在 $G$ 中的左陪集

拉格朗日定理

設(shè) $<H, *>$ 是有限群 $<G, *>$ 的一個子群慈鸠， $|G|=n$ 蓝谨， $|H|=m$ ，則 $m|n$

群的性質(zhì)

群中不可能有零元
- 零元 $\theta$ 不存在逆元
設(shè) $<G, *>$ 是一個群，對于 $a, b \in G$ 譬巫，必存在唯一的 $x \in G$ 咖楣，使得 $a * x = b$
消去律：設(shè) $<G, *>$ 是一個群，對于任意的 $a, b, c \in G$ 芦昔，如果有 $a * b = a * c$ 或者 $b * a = c * a$ 诱贿，則必有 $b = c$
群 $<G, *>$ 的運算表中的每一行或每一列都是 $G$ 的元素的一個置換
設(shè) $<G, *>$ 是一個群， $B$ 是 $G$ 的非空子集咕缎，如果 $B$ 是一個有限集珠十，那么，只要運算 $*$ 在 $B$ 上封閉凭豪， $<B, *>$ 必定是 $<G, *>$ 的子群
設(shè) $<G, \triangle>$ 是群焙蹭， $S$ 是 $G$ 的非空子集，如果對于 $S$ 中的任意元素 $a$ 和 $b$ 有 $a \triangle b^{-1} \in S$ 墅诡，則 $<S, \triangle>$ 是 $<G, \triangle>$ 的子群
群是阿貝爾群的充要條件：對任意的 $a, b \in G$ 壳嚎，有 $(a * b) * (a * b) = (a * a) * (b * b)$
設(shè) $<G, *>$ 是一個由元素 $a \in G$ 生成的有限循環(huán)群。如果 $|G| = n$ 末早，則 $a^n = e$ 烟馅，且 $G = \{a, a^2, a^3, \cdots, a^{n-1}, a^n=e\}$
- $n$ 為元素 $a$ 的階
群的積：設(shè) $<G, *>$ 是一個群， $A, B \in \mathscr{P}(G)且 A \neq \varnothing, B \neq \varnothing$ , 記 $AB = \{a * b|a \in A, b \in B\}$
群的逆： $A^{-1} = \{a^{-1}|a \in A \}$

拉格朗日定理

推論：
1. 任何質(zhì)數(shù)階的群不可能有非平凡子群
- 非平凡子群： $<\{e\}, *>$ , $<G, *>$
1. 有限群 $<G, *>$ 中任何元素 $a$ 的階可整除 $|G|$ 然磷，進而有 $a^{|G|}=e$
1. 質(zhì)數(shù)階的群一定是循環(huán)群

陪集

設(shè) $<H, *>$ 是群 $<G, *>$ 的子群郑趁， $\forall a \in G$
- 左陪集： $\{a\}H = \{a * h|h \in H\}$ 稱為由 $a$ 所確定的 $H$ 在 $G$ 中的左陪集，簡稱為 $H$ 關(guān)于 $a$ 的左陪集記為 $aH$
- 右陪集： $H\{a\} = \{h * a|h \in H\}$ 稱為由 $a$ 所確定的 $H$ 在 $G$ 中的右陪集姿搜，簡稱為 $H$ 關(guān)于 $a$ 的右陪集記為 $Ha$

同態(tài)與同構(gòu)

同態(tài)

設(shè) $<A, *>$ 和 $<B, \triangle>$ 是兩個代數(shù)系統(tǒng)寡润，若
1. $f: A \rightarrow B$ 是一函數(shù)
1. $\forall a, b \in A$ ，有 $f(a*b) = f(a) \triangle f(b)$
則稱 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 到一個同態(tài)映射舅柜，簡稱同態(tài)
$<A, *>$ 同態(tài)于 $<B, \triangle>$ 梭纹，記作 $A \sim B$
稱 $<f(A), \triangle>$ 為 $<A, *>$ 到一個同態(tài)象
先算后映 = 先映后算
- 例： $a \rightarrow a_1$ , $b \rightarrow b_1$ $\Leftrightarrow$ $a * b \rightarrow a_1 \triangle b_1$

自同態(tài)

設(shè) $<A, *>$ 是一個代數(shù)系統(tǒng)，若 $f$ 是 $<A, *>$ 到 $<A, *>$ 的一個同態(tài)致份，則稱 $f$ 為自同態(tài)

滿同態(tài)

設(shè) $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一個同態(tài)变抽，若 $f$ 是 $A$ 到 $B$ 的滿射，則稱 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的滿同態(tài)（或同態(tài)滿射）

單一同態(tài)

設(shè) $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一個同態(tài)氮块，若 $f$ 是 $A$ 到 $B$ 的入射（即單射）绍载，則稱 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的單一同態(tài)

同態(tài)核

設(shè) $f$ 是群 $<G, *>$ 到群 $<H, \triangle>$ 的同態(tài)， $e_H$ 是 $<H, \triangle>$ 的幺元滔蝉，稱 $Ker(f) = \{x|x \in G \land f(x) = e_H\}$ 為同態(tài)映射的核击儡，簡稱同態(tài)核

同態(tài)的性質(zhì)

設(shè) $f$ 是代數(shù)系統(tǒng) $<A, *>$ 到 $<B, \triangle>$ 的同態(tài)映射
- 若 $<A, *>$ 是半群，則 $<f(A), \triangle>$ 也是半群
- 若 $<A, *>$ 是獨異點蝠引，則 $<f(A), \triangle>$ 也是獨異點
- 若 $<A, *>$ 是群阳谍，則 $<f(A), \triangle>$ 也是群
- 若 $<A, *>$ 是阿貝爾群蛀柴，則 $<f(A), \triangle>$ 也是阿貝爾群
設(shè) $f$ 是群 $<G, *>$ 到群 $<H, \triangle>$ 的同態(tài)，則 $<Ker(f), *>$ 是群 $<G, *>$ 的子群边坤；若令 $K = Ker(f)$ 名扛，則 $\forall a \in G, aK = Ka$

同構(gòu)

設(shè) $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一個同態(tài)，若 $f$ 是 $A$ 到 $B$ 的雙射（即一一映射）茧痒，則稱 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的同構(gòu)映射，并稱 $<A, *>$ 與 $<B, \triangle>$ 同構(gòu)

記作 $A \cong B$

自同構(gòu)

設(shè) $<A, *>$ 是一個代數(shù)系統(tǒng)融蹂，若 $g$ 是 $<A, *>$ 到 $<A, *>$ 的一個同構(gòu)旺订，則稱 $g$ 為自同構(gòu)

同構(gòu)關(guān)系的性質(zhì)

同構(gòu)關(guān)系是等價關(guān)系

證明：

自反性：

$\forall <A, *> \in G$ ，作恒等映射 $f: A \rightarrow A$ 超燃， $f(a) = a区拳， a \in A$ ，

則 $f$ 是雙射意乓，并且 $\forall a, b \in A$ 有：

$f(a * b) = a * b = f(a) * f(b)$

所以樱调， $<A, *> \cong <A, *>$

對稱性：

設(shè)代數(shù)系統(tǒng) $<A, *> \cong <B, \triangle>$ ，

則存在雙射 $f: A \rightarrow B$ 届良，并且 $\forall a_1, a_2 \in A$ ，有：

$f(a_1 * a_2) = f(a_1) \triangle f(a_2)$

所以， $f^{-1}: B \rightarrow A$ 也是雙射泻仙， $\forall b_1, b_2 \in B$ 哈踱， $\exist a_1, a_2 \in A$ ，使得：

$f^{-1}(b_1) = a_1$ 慢显， $f^{-1}(b_2) = a_2$ 爪模，即 $f(a_1) = b_1$ ， $f(a_2) = b_2$ 荚藻，故有：

$f^{-1}(b_1 \triangle b_2) = f^{-1}(f(a_1) \triangle f(a_2)) = f^{-1}(f(a_1 * a_2))$

因此屋灌， $<B, \triangle> \cong <A, *>$

傳遞性

設(shè) $<A, *> \cong <B, \triangle>, <B, \triangle> \cong <C, \oplus>$

則存在雙射 $f: A \rightarrow B$ 和 $g: B \rightarrow C$ ，故 $g \circ f$ 也為雙射

$\forall a, b \in A$ 有：

$\begin{aligned} g \circ f(a * b) &= g(f(a * b)) \\\\ &= g(f(a) \triangle f(b)) \\\\ &= g(f(a)) \oplus g(f(b)) \\\\ &= g \circ f(a) \oplus g \circ f(b) \end{aligned}$
所以应狱， $<A, *> \cong <C, \oplus>$

因此共郭，代數(shù)系統(tǒng)間的同構(gòu)關(guān)系是等價關(guān)系

同余

同余關(guān)系

設(shè) $<A, *>$ 是一個代數(shù)系統(tǒng)， $R$ 是 $A$ 上的等價關(guān)系侦香，若 $\forall <a, b> \in R, <c, d> \in R$ 落塑，有：

$<a * c, b * d> \in R$

則稱 $R$ 是 $A$ 上關(guān)于運算 $*$ 的同余關(guān)系

同余類

同余關(guān)系 $R$ 將非空集合 $A$ 劃分稱的等價類稱為同余類

同余與同態(tài)關(guān)系

設(shè) $<A, *>$ 是一個代數(shù)系統(tǒng)， $R$ 是 $A$ 上的同余關(guān)系. $B = \{[a]|a \in A\}$ 是由 $R$ 誘導(dǎo)的一個劃分罐韩，則必存在同態(tài)映射 $f$ 憾赁，使 $<B, \triangle>$ 是 $<A, *>$ 的同態(tài)象

推論：設(shè) $f$ 是群 $<A, *>$ 到群 $<B, \triangle>$ 的同態(tài)映射， $e'$ 為 $B$ 的幺元散吵， $H = Ker(f)$ 龙考，定義 $A$ 上的二元關(guān)系 $R$ ：

$<a, b> \in R \Leftrightarrow f(a) = f(b)$

$\forall x_1, x_2, y_1, y_2 \in G$ 蟆肆，若 $x_1 H = y_1 H$ ，則

$(x_1 * x_2)H = (y_1 * y_2)H$

環(huán)與域

$\{環(huán)\} \subseteq \{整環(huán)\} \subseteq \{域\}$

環(huán)

設(shè) $<A, \triangle晦款， *>$ 是代數(shù)系統(tǒng)炎功，若
1. $<A, \triangle>$ 是阿貝爾群
  - 封閉、可結(jié)合缓溅、幺元蛇损、逆元、交換律
1. $<A, *>$ 是半群
  - 封閉坛怪、可結(jié)合
1. 乘法 $*$ 對加法 $\triangle$ 可分配淤齐，即 $\forall a, b, c \in A$ 有
  
  $a*(b \triangle c) = a * b \triangle a * c$
  
  $(b \triangle c) = b * a \triangle c * a$
  
  則稱 $<A, \triangle, *>$ 是一個環(huán)
稱第一個運算 $\triangle$ 為加法，并記為 $+$
稱第二個運算 $*$ 為乘法袜匿，并記為 $\cdot$
在環(huán)中
- 加法幺元記為 $\theta$
- 加法逆元 $a^{-1}$ 記為 $-a$
- $a + (-b)$ 記為 $a - b$

環(huán)的性質(zhì)

設(shè) $<A, +, \cdot>$ 是環(huán)更啄， $\forall a, b, c \in A$

環(huán)的加法幺元必為乘法零元，即 $\theta \cdot a = a \cdot \theta = \theta$

$(-a) \cdot b = a \cdot (-b) = -(a \cdot b)$

$(-a) \cdot (-b) = a \cdot b$

$a \cdot (b - c) = a \cdot b - a \cdot c$

$(b - c) \cdot a = (b + (-c)) \cdot a = b \cdot a + (-c) \cdot a$

零因子

設(shè) $<A, +, \cdot>$ 是環(huán)居灯，若 $\exist a, b \in A, a \neq \theta, b \neq \theta$ 祭务，使 $a \cdot b = \theta$ ，則稱 $a, b$ 為零因子怪嫌， $<A, +, \cdot>$ 是零因子環(huán)

無零因子

$\forall a, b \in A, a \neq \theta, b \neq \theta$ 义锥，必有 $a \cdot b = \theta$
無零因子的環(huán)稱為無零因子環(huán)

性質(zhì)

環(huán) $<A, +, \cdot>$ 無零因子，當且僅當 $<A, \cdot>$ 滿足消去律
- 即 $\forall a, b, c \in A$ 喇勋，若 $a \cdot b = a \cdot c$ 缨该， $a \neq \theta$ ，必有 $b = c$

整環(huán)

交換環(huán)

給定環(huán) $<A, +, \cdot>$ 川背，若 $<A, \cdot>$ 可交換贰拿，則稱 $<A, +, \cdot>$ 為交換環(huán)

含幺環(huán)

給定環(huán) $<A, +, \cdot>$ ，若 $<A, \cdot>$ 含幺元熄云，則稱 $<A, +, \cdot>$ 為含幺環(huán)

整環(huán)

給定環(huán) $<A, +, \cdot>$ 膨更，若 $<A, \cdot>$ 可交換、含幺元缴允、無零因子（或滿足消去律）荚守，則稱 $<A, +, \cdot>$ 為整環(huán)
整環(huán) = 環(huán) + 乘法幺元 + 乘法可交換 + 無零因子（或乘法消去律）
設(shè) $<A, +, \cdot>$ 是代數(shù)系統(tǒng)，若
1. $<A, +>$ 是阿貝爾群
1. $<A, \cdot>$ 是可交換獨異點练般，且無零因子（或滿足消去律）
1. 運算 $\cdot$ 對 $+$ 可分配
則稱 $<A, +, \cdot>$ 是一個整環(huán)

域

設(shè) $<A, +, \cdot>$ 是代數(shù)系統(tǒng)矗漾，若
1. $<A, +>$ 是阿貝爾群
1. $<A - \{\theta\}, \cdot>$ 是阿貝爾群
1. 運算 $\cdot$ 對 $+$ 可分配
則稱 $<A, +, \cdot>$ 是域

域與整環(huán)

整環(huán)	域
$<A, \cdot>$ 是可交換獨異點，且無零因子	$<A - \{\theta\}, \cdot>$ 是阿貝爾群

域 = 整環(huán) + 除了零元外薄料，每個元素都有逆元
域無零因子
域一定是整環(huán)
有限整環(huán)一定是域

兩個運算代數(shù)系統(tǒng)間的同態(tài)

同態(tài)映射

設(shè)和是兩個代數(shù)系統(tǒng)敞贡，若存在映射滿足：，有
1. $f(a + b) = f(a) \oplus f(b)$
2. $f(a \cdot b) = f(a) \otimes f(b)$
  則稱 $f$ 是 $<A, +, \cdot>$ 到 $<B, \oplus, \otimes>$ 的一個同態(tài)映射摄职，并稱 $<f(A), \oplus, \otimes>$ 是 $<A, +, \cdot>$ 的同態(tài)象

同態(tài)映射的性質(zhì)

任一環(huán)的同態(tài)象是一個環(huán)

格

格的定義

若偏序集 $<A, \preccurlyeq>$ 中任意兩個元素 $a, b$ 都有最小上界 $（LUB\{a, b\}）$ 和最大下界 $（GLB\{a, b\}）$ 誊役，則稱 $<A, \preccurlyeq>$ 是格
通常記： $a \lor b = LUB\{a, b\}$ , $a \land b = GLB\{a, b\}$
由于最小上界获列、最大下界若存在則唯一，所以 $\lor$ 蛔垢、 $\land$ 是二元運算击孩，分別稱為并運算和交運算
稱 $<A, \lor, \land>$ 為由格 $<A, \preccurlyeq>$ 所誘導(dǎo)的代數(shù)系統(tǒng)

子格

設(shè) $<A, \preccurlyeq>$ 是格， $<A, \lor, \land>$ 是由 $<A, \preccurlyeq>$ 所誘導(dǎo)的代數(shù)系統(tǒng)鹏漆，設(shè) $B \subseteq A$ 且 $B \neq \varnothing$ 巩梢，若運算 $\lor$ 和 $\land$ 在 $B$ 中封閉，則稱 $<B, \preccurlyeq>$ 是 $<A, \preccurlyeq>$ 的子格

格的對偶

設(shè)是偏序集艺玲，用表示偏序關(guān)系的逆關(guān)系且改，則
- $<A, \succcurlyeq>$ 也是偏序集
- $<A, \preccurlyeq>$ 和 $<A, \succcurlyeq>$ 的哈斯圖是互為顛倒的
- 稱 $<A, \preccurlyeq>$ 與 $<A, \succcurlyeq>$ 為彼此對偶的偏序集
- 若是格，則也是格板驳，反之亦成立，稱這兩個格互為對偶
  - $\forall a, b \in A$ 碍拆， $<A, \preccurlyeq>$ 的 $LUB\{a, b\}$ 對應(yīng)于 $<A, \succcurlyeq>$ 的 $GLB\{a, b\}$
  - $\forall a, b \in A$ 若治， $<A, \preccurlyeq>$ 的 $GLB\{a, b\}$ 對應(yīng)于 $<A, \succcurlyeq>$ 的 $LUB\{a, b\}$

格的對偶原理

設(shè) $P$ 是對任意格都為真的命題，將 $P$ 中的 $\preccurlyeq$ , $\lor$ , $\land$ 分別換成, $\succcurlyeq$ , $\land$ , $\lor$ 得命題 $P'$ 感混，則 $P'$ 對任意格也是真的命題

格的基本性質(zhì)

自反性

$a \preccurlyeq a, a \succcurlyeq a$
反對稱性

$(a \preccurlyeq b) \land (b \preccurlyeq a) \Rightarrow a = b$

$(a \succcurlyeq b)\land(b \succcurlyeq a) \Rightarrow a = b$
傳遞性

$(a \preccurlyeq b) \land (b \preccurlyeq c) \Rightarrow a \preccurlyeq c$

$(a \succcurlyeq b) \land (b \succcurlyeq c) \Rightarrow ac$
確界描述一

$a \preccurlyeq a \lor b, b \preccurlyeq a \lor b$

$a \land b \preccurlyeq a, a \land b \preccurlyeq b$
確界描述二

$(a \preccurlyeq c) \land (b \preccurlyeq c) \Rightarrow a \lor b \preccurlyeq c$

$(c \preccurlyeq a) \land (c \preccurlyeq b) \Rightarrow c \preccurlyeq a \land b$
蓋住的等價

$a \preccurlyeq b \Leftrightarrow a \land b = a \Leftrightarrow a \lor b = b$
交換律

$a \lor b = b \lor a, a \land b = b \land a$
結(jié)合律

$(a \lor b) \lor c = a \lor (b \lor c)$

$(a \land b) \land c = a \land (b \land c)$
冪等律

$a \lor a = a, a \land a = a$
吸收律

$a \lor (a \land b) = a$

$a \land (a \lor b) = a$
若 $a \preccurlyeq b, c \preccurlyeq d$ 端幼，則

$a \lor c \preccurlyeq b \lor d$

$a \land c \preccurlyeq b \land d$
保序性

若 $b \preccurlyeq c$ ，則

$a \lor b \preccurlyeq a \lor c$

$a \land b \preccurlyeq a \land c$
分配不等式

$a \lor (b \land c) \preccurlyeq (a \lor b) \land (a \lor c)$

$(a \land b) \lor (a \land c) \preccurlyeq a \land (b \lor c)$
模不等式

$a \preccurlyeq c \Leftrightarrow a \lor (b \land c) \preccurlyeq (a \lor b) \land c$
推論：

$(a \land b) \lor (a \land c) \preccurlyeq a \land (b \lor (a \land c))$

$a \lor (b \land (a \lor c)) \preccurlyeq (a \lor b) \land (a \lor c)$
引理：若 $<A, \lor, \land>$ 是一個代數(shù)系統(tǒng)弧满，其中 $\lor$ 婆跑， $\land$ 都是二元運算且滿足吸收律，則 $\lor$ 庭呜， $\land$ 必滿足冪等律
定理一：設(shè) $<A, \lor, \land>$ 是一個代數(shù)系統(tǒng)滑进，其中 $\lor$ ， $\land$ 都是二元運算且滿足交換律募谎，結(jié)合律和吸收律扶关，則 $A$ 上存在偏序關(guān)系 $\preccurlyeq$ ，使 $<A, \preccurlyeq>$ 是一個格

格同態(tài)與格同構(gòu)

格同態(tài)

設(shè) $<A_1, \preccurlyeq_1>, <A_2, \preccurlyeq_2>$ 是格数冬，它們所誘導(dǎo)的代數(shù)系統(tǒng)分別是 $<A_1, \lor_1, \land_1>, <A_2, \lor_2, \land_2>$ 节槐，若存在映射 $f: A_1 \rightarrow A_2$ ，對 $\forall a, b \in A_1$ 拐纱，有：

$f(a \lor_1 b) = f(a) \lor_2 f(b)$

$f(a \land_1 b) = f(a) \land_2 f(b)$

則稱 $f$ 是從 $<A_1, \lor_1, \land_1>$ 到 $<A_2, \lor_2, \land_2>$ 的格同態(tài)

稱 $<f(A_1), \preccurlyeq_2>$ 是 $<A, \preccurlyeq_1>$ 的格同態(tài)象

格同構(gòu)

若 $f$ 是雙射铜异，則稱 $f$ 是從 $<A_1, \lor_1, \land_1>$ 到 $<A_2, \lor_2, \land_2>$ 的格同構(gòu)
也稱格 $<A, \preccurlyeq_1>$ 與 $<A, \preccurlyeq_2>$ 同構(gòu)

格同構(gòu)的性質(zhì)

設(shè) $f$ 是格 $<A, \preccurlyeq_1>$ 到 $<A, \preccurlyeq_2>$ 的格同態(tài)， $\forall a, b \in A_1$ 秸架，若 $a \preccurlyeq_1 b$ 揍庄，必有 $f(a) \preccurlyeq_2 f(b)$
- 逆命題不成立
設(shè)兩個格 $<A, \preccurlyeq_1>$ 和 $<A, \preccurlyeq_2>$ ， $f$ 是 $A_1$ 到 $A_2$ 的雙射咕宿，則 $f$ 是格 $<A, \preccurlyeq_1>$ 到 $<A, \preccurlyeq_2>$ 的格同構(gòu)币绩，當且僅當

$\forall a, b \in A_1, a \preccurlyeq_1 b \Leftrightarrow f(a) \preccurlyeq_2 f(b)$

分配格

設(shè) $<A, \lor, \land>$ 是由格 $<A, \preccurlyeq>$ 所誘導(dǎo)的代數(shù)系統(tǒng)蜡秽，若 $\forall x, y, z \in A$ ，滿足

$x \land (y \lor z) = (x \land y) \lor (x \land z)$

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$

則稱 $<A, \preccurlyeq>$ 是分配格

分配格的性質(zhì)

若在一個格中交運算對并運算可分配缆镣，則并運算對交運算也一定可分配芽突，反之亦然

設(shè) $<A, \preccurlyeq>$ 是分配格，則 $\forall a, b, c \in A$ 董瞻，有

$a \land c = b \land c 且 a \lor c = b \lor c \Rightarrow a = b$

分配格的判定

定義

$x \land (y \lor z) = (x \land y) \lor (x \land z)$

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$

其一成立

格 $<A, \preccurlyeq>$ 是分配格當且僅當 $A$ 中不含與鉆石格或五角格同構(gòu)的子格

分配格的子格必是分配格

每個鏈是分配格

模格

模格的定義

設(shè) $<A, \lor, \land>$ 是由格 $<A, \preccurlyeq>$ 所誘導(dǎo)的代數(shù)系統(tǒng)寞蚌，若 $\forall a, b, c \in A$ ，當 $b \preccurlyeq a$ 時钠糊，滿足

$a \land (b \lor c) = b \lor (a \land c)$

則稱 $<A, \preccurlyeq>$ 是模格

分配格與模格的關(guān)系

分配格必是模格
- 模格不一定是分配格
  - 例：鉆石格是模格但不是分配格

有界格

全下界

設(shè)是格挟秤，若存在，對任意有抄伍，則稱為的全下界艘刚，記為0
- 若存在必唯一

全上界

設(shè)是格，若存在截珍，對任意有攀甚，則稱為的全上界，記為1
- 若存在必唯一

有界格

具有全下界和全上界的格稱為有界格

有界格的性質(zhì)

設(shè) $<A, \preccurlyeq>$ 為有界格岗喉，則 $\forall a \in A$ 有

$a \lor 1 = 1, a \land 1 = a$

$a \lor 0 = a, a \land 0 = 0$

在有界分配格中秋度，若某元素有補元，則必唯一

補元

設(shè)是有界格钱床，荚斯，若，使

則稱是的補元
- $a$ 和 $b$ 互為補元

有補格

在一個有界格中查牌，如果每個元素至少有一個補元事期，則稱此格為有補格

布爾代數(shù)

布爾格

若一個格既是有補格，又是分配格僧免，則此格稱為有補分配格刑赶，又稱布爾格

布爾格中任一元素 $a$ 的補元存在且唯一，記為 $\overline{a}$

原子

設(shè)格 $<A, \preccurlyeq>$ 具有全下界0懂衩，若有元素 $a$ 蓋住0颓哮，則稱元素 $a$ 為原子

布爾代數(shù)

布爾格 $<A, \preccurlyeq>$ 可以誘導(dǎo)一個代數(shù)系統(tǒng) $<A, \lor, \land, \overline{\over}>$ 驾凶，則此代數(shù)系統(tǒng)為布爾代數(shù)

布爾代數(shù)的性質(zhì)

設(shè)是布爾代數(shù)中任一兩個元素买雾，則
- $\overline{(\overline{a})} = a$
- $\overline{(a \lor b)} = \overline{a} \land \overline犁跪$
- $\overline{(a \land b)} = \overline{a} \lor \overline$

設(shè) $<A, \preccurlyeq>$ 是一個具有全下界0的有限格法希，若 $b \neq 0$ 枷餐，則至少存在一個原子 $a$ ，使 $a \preccurlyeq b$

布爾代數(shù)的同構(gòu)

設(shè)和是兩個布爾代數(shù)苫亦，則存在雙射滿足：毛肋，有：
1. $f(a \lor b) = f(a) \lor f(b)$
2. $f(a \land b) = f(a) \land f(b)$
3. $f(\overline{a}) = \overline{f(a)}$
  
  則稱 $<A, \lor, \land, \overline{\over}>$ 和 $<B, \lor, \land, \overline{\over}>$ 同構(gòu)

有限布爾代數(shù)

具有有限個元素的布爾代數(shù)

有限布爾代數(shù)的結(jié)論

對任一正整數(shù) $n$ 怨咪，必存在含有 $2^n$ 個元素的布爾代數(shù)

任一有限布爾代數(shù)的元素的個數(shù)必為 $2^n$ ， $n$ 為正整數(shù)

元素個數(shù)相同的布爾代數(shù)是同構(gòu)的

有限布爾代數(shù)的引理

在布爾格中润匙， $b \land \overline{c} = 0$ 當且僅當 $b \preccurlyeq c$

設(shè) $<A, \lor, \land, \overline{\over}>$ 是一個有限布爾代數(shù)诗眨，若 $b \in A$ ，且 $b \neq 0$ 孕讳，又設(shè) $a_1, a_2, \cdots, a_k$ 是 $A$ 中滿足 $a_j \preccurlyeq b(j = 1, 2, \cdots, k)$ 的所有原子匠楚，則

$b = a_1 \lor a_2 \lor a_3 \cdots \lor a_k$

設(shè) $<A, \lor, \land, \overline{\over}>$ 是一個有限布爾代數(shù)，若 $b \in A$ 厂财，且 $b \neq 0$ 芋簿，又設(shè) $a_1, a_2, \cdots, a_k$ 是 $A$ 中滿足 $a_j \preccurlyeq b(j = 1, 2, \cdots, k)$ 的所有原子，則

$b = a_1 \land a_2 \land a_3 \cdots \land a_k$

是將 $b$ 表示為原子的的并的唯一形式

設(shè) $<A, \preccurlyeq>$ 是布爾格璃饱， $a$ 為任意一個原子与斤， $b \neq 0$ ，則

$a \preccurlyeq b$ 和 $a \preccurlyeq \overline荚恶$ 兩式中幽告，有且僅有一個成立

布爾表達式

設(shè) $<A, \lor, \land, \overline{\over}>$ 是布爾代數(shù)
1. $A$ 中任何元素(即布爾常元)是布爾表達式
1. 任何布爾變元是布爾表達式
1. 若 $e_1, e_2$ 是布爾表達式，則 $\overline{e_1}, (e_1 \lor e_2), (e_1 \land e_2)$ 都是布爾表達式
1. 尤其僅有通過有限次地運用規(guī)則(2),(3)所構(gòu)造的符號串是布爾表達式

布爾常元

$A$ 中的元素

布爾變元

以 $A$ 為取值范圍的變元

n元布爾表達式

一個含 $n$ 格相異變元的布爾表達式裆甩，稱為 $n$ 元布爾表達式，記作

$E(x_1, x_2, \cdots, x_n)$

其中 $x_1, x_2, \cdots, x_n$ 為布爾變元

布爾表達式的值

設(shè) $<A, \lor, \land, \overline{\over}>$ 是布爾代數(shù)齐唆， $n$ 元布爾表達式 $E(x_1, x_2, \cdots, x_n)$ 的值是指：

將 $A$ 中的布爾常元作為變元 $x_i$ 的值來代替表達式中相應(yīng)的變元(即對變元賦值)嗤栓，從而計算得出表達式的值

布爾表達式的等價

設(shè) $E_1(x_1, x_2, \cdots, x_n)$ 和 $E_2(x_1, x_2, \cdots, x_n)$ 是布爾代數(shù) $<A, \lor, \land, \overline{\over}>$ 上的兩個 $n$ 元布爾表達式，若對 $n$ 格變元的任意賦值 $x_i = a_i, a_i \in A, i = 1, 2, \cdots, n$ 均有

$E_1(a_1, a_2, \cdots, a_n) = E_2(a_1, a_2, \cdots, a_n)$

則稱布爾表達式 $E_1, E_2$ 是等價的箍邮，記作：

$E_1(x_1, x_2, \cdots, x_n) = E_2(x_1, x_2, \cdots, x_n)$

布爾表達式的小項

布爾函數(shù)

設(shè) $<A, \lor, \land, \overline{\over}>$ 是布爾代數(shù)茉帅，一個由 $A^n$ 到 $A$ 的函數(shù)若能用 $<A, \lor, \land, \overline{\over}>$ 上的一個 $n$ 元布爾表達式來表示，則該函數(shù)為布爾函數(shù)

布爾函數(shù)的小項

一個含有 $n$ 個變元 $x_1, x_2, \cdots, x_n$ 的布爾表達式锭弊，如果它有形式

$() \land () \land \cdots \land ()$

其中 $()$ 是 $x_i$ 或 $\overline{x_i}$ 中的任一個堪澎，則我們稱這個布爾表達式為小項

布爾函數(shù)的大項

一個含有 $n$ 個變元 $x_1, x_2, \cdots, x_n$ 的布爾表達式，如果它有形式

$() \lor () \lor \cdots \lor ()$

其中 $()$ 是 $x_i$ 或 $\overline{x_i}$ 中的任一個味滞，則我們稱這個布爾表達式為大項

布爾函數(shù)的析取范式

析取范式

形如 $m_0 \lor m_1 \lor \cdots \lor m_t$ 的表達式稱為析取范式

其中 $m_i$ 表示小項

一般布爾代數(shù)上的析取范式

設(shè) $E(x_1, x_2, \cdots, x_n)$ 是布爾代數(shù) $<A, \lor, \land, \overline{\over}>$ 上任一布爾表達式樱蛤，若

布爾函數(shù)的合取范式

形如 $M_0 \land M_1 \land \cdots \land M_t$ 的表達式稱為合取范式

其中 $M_i$ 表示大項

圖論

相關(guān)概念及約定

圖

一個圖 $G$ 是一個三元組 $<V(G), E(G), \varphi_G>$ ，其中
- $V(G)$ 是一個非空的結(jié)點集合
- $E(G)$ 是邊集合
- $\varphi_G$ 是從邊集合 $E(G)$ 到結(jié)點無序偶（有序偶）集合上的函數(shù)

無向圖

每條邊都是無向邊的圖

有向圖

每條邊都是有向邊的圖

混合圖

既有無向邊又有有向邊的圖

多重圖

包含平行邊的圖

零圖

僅由孤立點組成的圖

平凡圖

由一個孤立結(jié)點構(gòu)成的圖

簡單圖

不含平行邊和環(huán)的圖

完全圖

簡單圖 $G = <V, E>$ 中剑鞍，若每對結(jié)點之間均有邊相連昨凡，則稱該圖為完全圖

有個結(jié)點的無向完全圖記作
- 邊數(shù)為 $\frac{1}{2}n(n-1)$

補圖

由圖 $G$ 的所有結(jié)點和所有能使圖 $G$ 稱為完全圖的添加邊所組成的圖，稱為圖 $G$ 相對于完全圖的補圖蚁署，或簡稱為 $G$ 的補圖便脊，記作 $\overline{G}$

設(shè)圖 $G_1 = <V_1, E_1>$ 是 $G = <V,E>$ 的子圖，令 $G_2 = <V_2, E_2>$ 光戈，如果
- $E_2 = E - E_1$
- $V_2$ 中僅包含 $E_2$ 中的邊所關(guān)聯(lián)的結(jié)點
則稱 $G_2$ 為子圖 $G_1$ 相對于圖 $G$ 的補圖

子圖

給定圖和
- 如果 $E_1 \subseteq E, V_1 \subseteq V$ 哪痰，則稱 $G_1$ 為 $G$ 的子圖
- 如果 $V_1 = V$ 遂赠，即 $G_1$ 包含 $G$ 的所有結(jié)點，則稱 $G_1$ 為 $G$ 的生成子圖

連通圖

只有一個連通分支的圖

圖的同構(gòu)

給定圖 $G = <V, E>$ 和 $G' = <V', E'>$ 晌杰，如果存在雙射 $g: V \rightarrow V'$ 跷睦，且 $e = (v_i, v_j)$ 是 $G$ 的一條邊當且僅當 $e' = (g(v_i), g(v_j))$ 是 $G'$ 的一條邊，則稱 $G'$ 與 $G$ 同構(gòu)乎莉，記作 $G \backsimeq G'$

兩圖同構(gòu)的必要條件

結(jié)點數(shù)相同

邊數(shù)相同

對應(yīng)結(jié)點的度數(shù)相等

鄰接點

若兩個結(jié)點與同一條邊相關(guān)聯(lián)送讲，則稱兩個結(jié)點是鄰接點

鄰接邊

關(guān)聯(lián)于同一結(jié)點的兩條邊叫鄰接邊

端點

設(shè)圖 $G = <V, E>， e_k= <v_i, v_j>$ 惋啃，則 $v_i, v_j$ 叫 $e_k$ 的端點哼鬓，并稱 $e_k$ 與 $v_i, v_j$ 相關(guān)聯(lián)

環(huán)

關(guān)聯(lián)于同一結(jié)點的一條邊，稱為自回路或環(huán)

孤立點

不與任何結(jié)點相鄰的結(jié)點边灭，稱為孤立點

平行邊

關(guān)聯(lián)于同一對結(jié)點的多條邊（有向邊應(yīng)同向）叫平行邊

度數(shù)

在圖 $G = <V, E>$ 中异希，與結(jié)點 $v$ 相關(guān)聯(lián)的邊數(shù)，叫該結(jié)點的度數(shù)绒瘦，記作 $deg(v)$

稱 $\triangle (G) = max\{deg(v)|v \in V(G)\}$ 為圖 $G$ 的最大度

稱 $\delta (G) = min\{deg(v)|v \in V(G)\}$ 為圖 $G$ 的最小度

每個環(huán)在其對應(yīng)的結(jié)點上称簿，度數(shù)增加2

每個圖中，結(jié)點度數(shù)的總和等于邊數(shù)的 2 倍
- 任何圖中惰帽，度數(shù)為奇數(shù)的結(jié)點必為偶數(shù)個

度數(shù)為入度和出度的總和

入度

射入一個結(jié)點的邊數(shù)

出度

由一個結(jié)點射出的邊數(shù)

所有點出度之和等于入度之和

路

給定圖 $G = <V, E>$ 憨降，設(shè) $v_0, v_1, v_2, \cdots, v_n \in V$ ， $e_1, e_2, \cdots, e_n \in E$ 该酗，其中 $e_i$ 是關(guān)聯(lián)結(jié)點 $v_{i - 1}$ 的邊授药，點邊交替序列 $v_0 e_1 v_1 e_2 v_2 \cdots e_n v_n$ 稱為聯(lián)結(jié) $v_0$ 到 $v_n$ 的路

$v_0$ 和 $v_n$ 分別稱為該路的起點和終點

回路

$v_0 = v_n$ 的路

跡

各邊均不相同的路

通路

各結(jié)點均不相同的路

圈

各結(jié)點均不相同的閉合通路

連通

在無向圖 $G$ 中，如果從結(jié)點 $u$ 到 $v$ 存在一條路呜魄，則稱結(jié)點 $u$ 和結(jié)點 $v$ 是連通的

連通分支

對無向圖 $G = <V, E>$ 而言悔叽，結(jié)點集合 $V$ 上的連通關(guān)系是等價關(guān)系. 該連通關(guān)系將結(jié)點集合作出一個劃分，每個劃分塊連同它們所關(guān)聯(lián)的邊稱為圖 $G$ 的一個連通分支. 把圖 $G$ 的連通分支數(shù)記為 $W(G)$

點割集

設(shè)無向圖 $G = <V, E>$ 中爵嗅，若有結(jié)點集 $V_1 \subset V$ 娇澎，使圖 $G$ 刪除了 $V_1$ 的所有結(jié)點后所得的子圖不是連通的，而刪除了 $V_1$ 的任一真子集后所得的子圖仍是連通的睹晒，則稱 $V_1$ 是圖 $G$ 的點割集

割點

如果某一個結(jié)點構(gòu)成一個點割集趟庄，則稱該結(jié)點為割點

連通性

連通度

非完全圖的點連通度（簡稱連通度）定義為： $k(G) = min\{|V_i| \mid V_i 是點割集\}$

連通度是為了產(chǎn)生一個不連通圖所要刪除結(jié)點的最少數(shù)目
- 非連通圖的連通度為 0
- 存在割點的連通圖的連通度為 1
- 對于完全圖 $K_p$ ， $k(K_p) = p - 1$

邊割集

設(shè)無向圖 $G = <V, E>$ 為連通圖伪很，若有邊集 $E_1 \subset E$ 岔激，使圖 $G$ 刪除了 $E_1$ 中所有邊后所得的子圖是不連通的，而刪除了 $E_1$ 的任一真子集后所得的子圖仍是連通的是掰，則稱 $E_1$ 是圖 $G$ 的邊割集

割邊

如果一條邊構(gòu)成一個邊割集虑鼎，則稱該邊為割邊（或橋）

連通度

非平凡圖 $G$ 的邊連通度定義為： $\lambda (G) = \min \{|E_1| \mid E_1 是邊割集\}$
非連通圖和平凡圖的邊連通度為 0

圖的直徑

- 不可達記為∞

單側(cè)連通

任何一對結(jié)點間，至少從一個結(jié)點到另一個結(jié)點可達

強連通

圖中任何一對結(jié)點之間相互可達

弱連通

圖中略去邊的方向后的無向圖是連通的

強分圖

具有強連通性的最大子圖

單側(cè)分圖

具有單側(cè)連通性的最大子圖

弱分圖

具有弱連通性的最大子圖

矩陣表示

鄰接矩陣

設(shè) $G = <V, E>$ 是一個簡單圖，它有 $n$ 個結(jié)點 $V = \{v_1, v_2, \cdots, v_n\}$ 炫彩，則 $n$ 階方陣 $A(G) = (a_{ij})$ 稱為 $G$ 的鄰接矩陣匾七，其中
$a_{ij} = \begin{cases} 1, v_i adj v_j \\\\ 0, v_i nadj v_j 或 i = j \end{cases}$

鄰接矩陣的應(yīng)用

計算連結(jié) $v_i$ 與 $v_j$ 的長度為 $n$ 的路的數(shù)目

為 $(A(G))^n$ 中第 $i$ 行第 $j$ 列元素 $a^{(2)}_{ij}$

$n = 2$ 時，路徑為 $v_i \rightarrow v_k \rightarrow v_j$

例如： $k = 3$ 時江兢， $a_{23}a_{31} = 1 \cdot 1$ 昨忆，表示有路

$n > 2$ 時，可視為： $(a^{(3)}_{n \times n)}) = (A(G)) \cdot (A(G))^2$

可達性矩陣

設(shè) $G = <V, E>$ 為簡單有向圖杉允， $V= \{v_1, v_2, \cdots, v_n\}$ 邑贴，定義一個 $n \times n$ 矩陣 $P = (p_{ij})$ ，其中

$p_{ij} = \begin{cases} 1, 從 v_i 到 v_j 至少存在一條路 \\\\ 0, 從 v_i 到 v_j 不存在路 \end{cases}$

則稱 $P$ 為圖 $G$ 的可達性矩陣

完全關(guān)聯(lián)矩陣

設(shè) $G = <V, E>$ 為無向圖叔磷， $V = \{v_1, v_2, \cdots, v_p\}$ 拢驾， $E = \{e_1, e_2, \cdots, e_q\}$ ，定義矩陣 $M(G) = (m_{ij})_{p \times q}$ 改基，其中

$m_{ij} = \begin{cases} 1, 若 v_i 關(guān)聯(lián)e_j \\\\ 0, 若v_i 不關(guān)聯(lián) e_j \end{cases}$

則稱 $M(G)$ 為圖 $G$ 的完全關(guān)聯(lián)矩陣

置換等價

兩個矩陣可以通過交換行和列而相互得出

$n$ 階布爾矩陣集合上的一個等價關(guān)系

最后編輯于：2020.10.19 15:42:06

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末繁疤，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子秕狰，更是在濱河造成了極大的恐慌稠腊，老刑警劉巖，帶你破解...
沈念sama閱讀 218,941評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件鸣哀，死亡現(xiàn)場離奇詭異架忌，居然都是意外死亡，警方通過查閱死者的電腦和手機我衬，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,397評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門鳖昌，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人低飒，你說我怎么就攤上這事《危” “怎么了褥赊？”我有些...
開封第一講書人閱讀 165,345評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長莉恼。經(jīng)常有香客問我拌喉，道長，這世上最難降的妖魔是什么俐银？我笑而不...
開封第一講書人閱讀 58,851評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任尿背，我火速辦了婚禮，結(jié)果婚禮上捶惜，老公的妹妹穿的比我還像新娘田藐。我一直安慰自己，他們只是感情好，可當我...
茶點故事閱讀 67,868評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布汽久。她就那樣靜靜地躺著鹤竭，像睡著了一般。火紅的嫁衣襯著肌膚如雪景醇。梳的紋絲不亂的頭發(fā)上臀稚，一...
開封第一講書人閱讀 51,688評論 1贊 305
城市分裂傳說
那天，我揣著相機與錄音三痰，去河邊找鬼吧寺。笑死，一個胖子當著我的面吹牛散劫，可吹牛的內(nèi)容都是我干的稚机。我是一名探鬼主播，決...
沈念sama閱讀 40,414評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼舷丹，長吁一口氣：“原來是場噩夢啊……” “哼抒钱！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起颜凯，我...
開封第一講書人閱讀 39,319評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤谋币，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后症概，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蕾额，經(jīng)...
沈念sama閱讀 45,775評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,945評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年彼城，在試婚紗的時候發(fā)現(xiàn)自己被綠了诅蝶。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,096評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡募壕，死狀恐怖调炬，靈堂內(nèi)的尸體忽然破棺而出衍慎，到底是詐尸還是另有隱情徐勃，我是刑警寧澤遍希，帶...
沈念sama閱讀 35,789評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布倦西，位于F島的核電站侧纯，受9級特大地震影響绊率，放射性物質(zhì)發(fā)生泄漏缭付。R本人自食惡果不足惜拆火，卻給世界環(huán)境...
茶點故事閱讀 41,437評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一干毅、第九天我趴在偏房一處隱蔽的房頂上張望宜猜。院中可真熱鬧，春花似錦硝逢、人聲如沸姨拥。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,993評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽垫毙。三九已至霹疫，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間综芥，已是汗流浹背丽蝎。一陣腳步聲響...
開封第一講書人閱讀 33,107評論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留膀藐，地道東北人屠阻。一個月前我還...
沈念sama閱讀 48,308評論 3贊 372
代替公主和親
正文我出身青樓，卻偏偏與公主長得像额各，于是被迫代替她去往敵國和親国觉。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 45,037評論 2贊 355

離散數(shù)學(xué)概念總結(jié)

命題邏輯

命題

命題

原子命題

復(fù)合命題

重言式

蘊含式

矛盾式

子公式

置換

命題公式

命題公式

命題公式的等價

命題公式的對偶式

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

范式

求范式的步驟

小項

大項

謂詞邏輯

謂詞公式

謂詞公式

謂詞公式的等價

前束范式

定義

運算方法

推理理論

P規(guī)則

T規(guī)則

CP規(guī)則

全稱指定規(guī)則（US）

全稱推廣原則（UG）

存在制定原則（ES）

存在推廣原則（EG）

集合論

平凡子集

全集

冪集

商集

集合的劃分

集合的覆蓋

交叉劃分

劃分的加細

集合的等勢

集合的對稱差

集合的基數(shù)

無限集

可數(shù)集

連續(xù)統(tǒng)的勢

可數(shù)集合的基數(shù)

集合的置換

集合的運算

集合的對稱差

關(guān)系

關(guān)系

笛卡爾積

集合上的二元關(guān)系

對稱關(guān)系

反對稱關(guān)系

等價關(guān)系

等價類

相容關(guān)系

相容關(guān)系

相容類

最大相容類

完全覆蓋

偏序關(guān)系

偏序關(guān)系

蓋住

哈斯圖

偏序集合的子集的特殊元素

極大元

極小元

最大元

最小元

最大元與極大元的比較

上界

下界

上確界

集合 $A$ 上的二元關(guān)系