# 【資工考研】離散：二元關係

## Relation

考慮集合 $A$, $B$ 之卡氏積 $A\times B$
若 $R$ 為 $A\times B$ 之一子集，稱 $R$ 為 $A$ 到 $B$ 之二元關係，記作 $R:A\rightarrow B$
若 $(a,b)\in R$ 則稱 $a$, $b$ 有 $R$ 關係，記作 $aRb$

除了用集合來看，也能用關係矩陣或是關係圖來看

例如 $A = \left\{ a_1,\cdots ,a_m \right\}, B = \left\{ b_1,\cdots ,b_n \right\}, R: A\rightarrow B$
$R$ 之關係矩陣 $M_R = (m_{ij})_{m\times n}$ ，其中 $m_{ij} = \begin{cases} 1 &\text{ if } (a_i,b_j)\in R \\ 0 &\text{ if } (a_i,b_j)\notin R\end{cases}$

### Inverse

$R: A\rightarrow B$ 之反關係 $R^{-1}:B\rightarrow A$ 定義為 $R^{-1} = \left\{ (b,a) | (a,b)\in R \right\}$
即 $\forall a\in A,b\in B, aRb\Leftrightarrow bR^{-1}a$

1. $(R^{-1})^{-1} = R$
2. $M_{R^{-1}} = (M_R)^T$

### Complement

$R: A\rightarrow B$ 之補關係 $\overline{R}:A\rightarrow B$ 定義為 $\overline{R} = \left\{ (a,b) | a\in A,b\in B, (a,b)\notin R \right\}$

### Composition

Let $R:A\rightarrow B, S:B\rightarrow C$ 則 $R$, $S$ 之合成 $R\circ S = \left\{ (a,c) | \exists b\in B, (a,b)\in R \wedge (b,c)\in S \right\}$

關係的合成如果採用左運算，可以得到 $M_{R\circ S} = M_RM_S$ 的結論；但是，有些書講的是右運算，這樣的話是比較與函數合成的右運算一致

- 關係的合成滿足結合性 $(R\circ S)\circ T = R\circ (S\circ T)$
- $R\circ R = R^2, R^{n} = R^{n-1}\circ R$

### 六大特殊的二元關係

| 二元關係 | 定義 | 在關係矩陣中 | 在關係圖中 |
| :---: | :---: | :---: | :---: |
| 反身性 (reflextive) | $\forall a\in A, (a,a)\in R$ | 對角項均為 $1$ | 每點均有 loop |
| 非反身性 (irreflextive) | $\forall a\in A, (a,a)\notin R$ | 對角項均為 $0$ | 每點均無 loop |
| 對稱性 (symmetric) | $\forall a,b\in A,\text{ if }(a,b)\in R\text{, then }(b,a)\in R$ | 對稱位置相等 | 兩點間若有邊必雙向 |
| 非對稱性 (asymmetric) | $\forall a,b\in A,\text{ if }(a,b)\in R\text{, then }(b,a)\notin R$ | 對稱位置不同時為 $1$ ，主對角必為 $0$ | 兩點間的邊必單向且每點均無 loop |
| 反對稱性 (antisymmetric) | $\forall a,b\in A,\text{ if }(a,b)\in R\wedge(b,a)\in R\text{, then }a=b$ | 對稱位置不同時為 $1$ | 兩點間的邊必單向 |
| 遞移性 (transitive) | $\forall a,b,c\in A,\text{ if }(a,b)\in R\wedge(b,c)\in R\text{, then }(a,c)\in R$ | 沒什麼特徵 | 若 $a$, $c$ 有兩布可達之 path 則必存在 $a$ 到 $c$ 的邊 |

- 除了**空集合上的空關係**，反身跟非反身不會同時成立。他們可以都不成立，沒有一定某個成立
- 除了空關係，對稱性與非對稱性不同時存在
- **非空集合**上的**空關係，除了反身性**其他皆有
- 對稱性跟反對稱性可以同時存在
- **有非對稱性就一定有反對稱性，反之不成立**

#### 等價條件

Let $R\subseteq A\times A$ 為 $A$ 上的二元關係：

1. $R$ 具反身性 $\Leftrightarrow R^0\subseteq R$
2. $R$ 具非反身性 $\Leftrightarrow R^0\cap R = \emptyset$
3. $R$ 具對稱性 $\Leftrightarrow R = R^{-1}$
4. $R$ 具非對稱性 $\Leftrightarrow R\cap R^{-1} = \emptyset$
5. $R$ 具反對稱性 $\Leftrightarrow R\cap R^{-1} \subseteq R^0$
6. $R$ 具遞移性 $\Leftrightarrow R^2\subseteq R$

> [!Note]
> $R^0 = \left\{ (x,x) | \forall x\in A \right\}$ 為 $A$ 上之對角關係

| $R$ | | $R^{-1}$ | | $\overline{R}$ |
| :---: | :---: | :---: | :---: | :---: |
| 反身性 | $\Leftrightarrow$ | 反身性 | $\Leftrightarrow$ | 非反身性 |
| 非反身性 | $\Leftrightarrow$ | 非反身性 | $\Leftrightarrow$ | 反身性 |
| 對稱性 | $\Leftrightarrow$ | 對稱性 | $\Leftrightarrow$ | 對稱性 |
| 非對稱性 | $\Leftrightarrow$ | 非對稱性 | $\Rightarrow$ | 反身性 |
| 反對稱性 | $\Leftrightarrow$ | 反對稱性 | | |
| 遞移性 | $\Leftrightarrow$ | 遞移性 | | |

> [!Tip]
> $R$ 具備什麼性，$R^{-1}$ 就具備什麼性

> [!Note]
> $R$ 具非對稱性時，僅可得 $\overline{R}$ 具反身性

#### 運算

1. 若 $R$, $S$ 具反身性，則 $R\cap S, R\cup S, R\circ S, R^2$ 具反身性
2. 若 $R$, $S$ 具對稱性，則 $R\cap S, R\cup S, R^2$ 具對稱性
3. 若 $R$, $S$ 具遞移性，則 $R\cap S, R^2$ 具遞移性

#### Closure

- $r(R)$ 為包含 $R$ 之最小反身關係，稱作反身包 (reflexive closure)
- $s(R)$ 為包含 $R$ 之最小對稱關係，稱作對稱包 (symmetric closure)
- $t(R)$ 為包含 $R$ 之最小遞移關係，稱作遞移包 (transitive closure)，也可記作 $R^+$

> [!Tip]
> 1. $r(R) = R\cup R^0$
> 2. $s(R) = R\cup R^{-1}$
> 3. $\bigcup\limits_{i=1}^{\infty}R^{i} = R^+$
> 4. $t(s(r(R)))$ 為 $R$ 之等價包
> 5. **若 $R$ 有對稱性，則 $t(R)$ 亦有對稱性**
> 6. $s(R\cup S) = s(R)\cup s(S)$

#### 求遞移包

使用[Floyd-Warshall algorithm](https://hackmd.io/@RyoukiWei/graph_2#Floyd-Warshall-Algorithm)

#### 個數計算

If $\left| A \right| = n$ 則 $A$ 上有 $2^{n^2}$ 種二元關係：

| 反身性 | 非反身性 | 對稱性 | 非對稱性 | 反對稱性 |
| :---: | :---: | :---: | :---: | :---: |
| $2^{n^2-n}$ 種| $2^{n^2-n}$ 種 | $2^{\frac{n^2+n}{2}}$ 種 | $3^{\frac{n^2-n}{2}}$ 種 | $2^n\cdot 3^{\frac{n^2-n}{2}}$ 種 |

> [!Tip]
> 用關係矩陣來看 (所以你要熟悉這些特殊關係的矩陣有什麼特徵)

### 等價關係

同時具備**反身、對稱、遞移性** 的 $R$ 稱為等價關係

如果 $R$, $S$ 皆為等價關係，則 $R^2, R^{-1}, R\cap S$ 亦為等價關係
注意， $R\cup S$ 不一定為等價關係

> [!Important]
> 同餘關係 (congruence modulo $n$ relation) 是一種常見的等價關係

#### Partition

稱集合 $A$ 之子集合 $A_1,\cdots ,A_n$ 形成 $A$ 之一分割，若：

1. $A_i\neq\emptyset, i=1,2,\cdots ,n$
2. $\bigcup\limits_{i=1}^{n}A_i = A$
3. $\forall i\neq j, A_i\cap A_j = \emptyset$ (兩兩互斥)

設 $R$ 為 $A$ 上之等價關係，則 $R$ 的相異等價類形成 $A$ 之一分割
$A$ 上之分割亦可唯一決定一種 $A$ 上的等價關係

由此可知，**等價關係個數相當於集合分割的方法數**

例如若集合 $A = \left\{ 1,2,3,4,5 \right\}$，$A = \left\{ 1,3 \right\}\cup \left\{ 2,4 \right\}\cup \left\{ 5 \right\}$ 為 $A$ 上之一分割，則 $A$ 上的等價關係 $R$ 就可以寫出 $R = (\left\{ 1,3 \right\}\times \left\{ 1,3 \right\})\cup(\left\{ 2,4 \right\}\times \left\{ 2,4 \right\})\cup(\left\{ 5 \right\}\times \left\{ 5 \right\})$

而集合 $\left\{ 1,2,\cdots ,m \right\}$ 分割的方法數其實就可以看成 $m$ 相異物放入 $m$ 相同箱 (可空) 之方法數，即 $\sum\limits_{i=1}^{m}S(m,i)$ 其中 $S(m,n)$ 為 Stirling number (排列組合那邊的內容)

## Partial Ordering Set

若 $R$ 為集合 $S$ 上的二元關係，$R$ 具有**反身、反對稱、遞移性**，則稱 $R$ 為 $S$ 上的偏序關係，$(S,R)$ 為一偏序集，記作 $(S,\le)$

常見的偏序集有：

1. $(\mathbb{Z},\ge)$
2. $(\mathbb{Z},\le)$
3. $(\mathbb{N},\ge)$
4. $(\mathbb{N},\le)$
5. $(P(A),\subseteq)$ ，其中 $P(A)$ 為集合 $A$ 之 powerset
6. $(D_m,|)$ ，其中 $D_m$ 為正整數 $m$ 所有正因數所形成的集合
7. $(\mathbb{Z}^+,|)$

### Hasse Diagram

將偏序關係之圖形簡化，例如 $(D_{12}, |)$ 的 Hasse diagram 如下：

<center>
<img src="https://media.geeksforgeeks.org/wp-content/uploads/ex2-3.png" alt="(D_12, |) 之漢斯圖">
</center>

[source](https://www.geeksforgeeks.org/discrete-mathematics-hasse-diagrams/)

### 偏序集的性質

令 $(S,R)$ 為一偏序集

1. 若 $R$ 亦為等價關係，則 $R$ 為對角關係 ($R^0$)
2. $(S,R^{-1})$ 亦為一偏序集
3. 若 $T$ 為 $S$ 之子集，則 $(T,R)$ 亦為一偏序集
4. $R$ 之關係圖中不存在長度 $2$ 以上的 cycle
5. 若 $(S,\le_1)$ 與 $(T,\le_2)$ 皆為偏序集，定義 $S\times T$ 上 $(s,t)\le(u,v)\Leftrightarrow s\le_1 u \wedge t\le_2 v$ ，則 $(S\times T, \le)$ 亦為偏序集

### Lexicographic Ordering

令 $(S,R)$ 為一偏序集

定義 $S^m$ 上的關係 $\prec$ 為字典順序：$\forall a,b\in S^m, a=a_1a_2\cdots a_m, b = b_1b_2\cdots b_m, a_i,b_j\in S,\forall i,j$
$a\prec b \Leftrightarrow \begin{cases}
a_1\neq b_1 \\
a_1Rb_1
\end{cases} \text{ or }\begin{cases}
a_1 = b_1, \forall i, 1\le i\le k\\
a_{k+1}\neq b_{k+1} \\
a_{k+1}Rb_{k+1}
\end{cases}\text{ for some } k, 1\le k\le m$

### Maximal (極大), Minimal (極小), Greatest (最大), Least (最小)

令 $(S,\le)$ 為一偏序集

稱 $\begin{cases}M \\ m \end{cases}$ 為 $S$ 之 $\begin{cases}\text{極大} \\ \text{極小} \end{cases}$ 元素，如果不存在其他 $S$ 中的元素 $x$ 使得 $\begin{cases}M\le x \\ x\le m \end{cases}$

稱 $\begin{cases}I\in S \\ O\in S \end{cases}$ 為 $S$ 之 $\begin{cases}\text{最大} \\ \text{最小} \end{cases}$ 元素，如果對 $S$ 中的任意元素 $x$ 均有 $\begin{cases}x\le I \\ O\le x \end{cases}$

### Upper Bound (上界), Lower Bound (下界)

令 $(S,\le)$ 為一偏序集， $A$ 為 $S$ 之子集

稱 $\begin{cases}u\in S \\ l\in S \end{cases}$ 為 $A$ 之 $\begin{cases}\text{上界} \\ \text{下界} \end{cases}$ ，如果 $\forall x\in A\begin{cases}x\le u \\ l\le x \end{cases}$

稱 $\begin{cases}u\in S \\ l\in S \end{cases}$ 為 $A$ 之 $\begin{cases}\text{最小上界 (lub)} \\ \text{最大下界 (glb)} \end{cases}$ ，如果 $\begin{cases}u \\ l\end{cases}$ 為 $A$ 之 $\begin{cases}\text{上界 } \\ \text{下界 } \end{cases}$ 且對 $A$ 之其他 $\begin{cases}\text{上界 } u' \\ \text{下界 } l' \end{cases}$ 均有 $\begin{cases}u\le u' \\ l'\le l \end{cases}$

### Totally Ordering Relation

> [!Note]
> Comparable:
> 考慮偏序集 $(S, \le), a,b\in S, a\neq b$ ，若 $a\le b$ 與 $b\le a$ 恰一者成立，則稱 $a$, $b$ 可比較

考慮偏序集 $(S, \le)$ ，若 $S$ 中任相異元素均可比較，則稱 $\le$ 為全序關係
$(S, \le)$ 為全序集 (TOS)

### Chain and Antichain

考慮偏序集 $(S, \le)$ ，對 $S$ 之子集 $A$ ，若 $A$ 中任相異元素 $a$, $b$ ：

- $a\le b$ 與 $b\le a$ 恰一者成立，則 $A$ 為一個鍊
- $a\le b$ 與 $b\le a$ 均不成立，則 $A$ 為一個反鍊

鍊又叫線性有序集
若 $S$ 本身為鍊，則 $(S, \le)$ 為 TOS

鍊中的元素個數定義為其長度
如果 $\left| A \right| = n$ ，則偏序集 $(P(A),\subseteq)$ 最長鍊之長度為 $n+1$

若 $S$ 中最長鍊之長度為 $n$ 則 $S$ 可分割成 $n$ 個互斥的**反鍊**
若 $\left| S \right| = mn+1$ 則 $S$ 中包含長度為 $m+1$ 的反鍊 or 長度 $n+1$ 的鍊

## 絡 (Lattice)

若偏序集 $(S, \le)$ 任意 $S$ 中的元素 $a$, $b$ 滿足：

- $\mathrm{lub}\left\{ a,b \right\}$ 存在 (記作 $a\vee b$ ，$a$ 與 $b$ 的 joint)
- $\mathrm{glb}\left\{ a,b \right\}$ 存在 (記作 $a\wedge b$ ，$a$ 與 $b$ 的 meet)

則稱 $(S, \le)$ 為一個絡，記作 $(S,\vee ,\wedge)$

> [!Important]
> 如果 $(S, \le)$ 為全序集，則 $(S, \le)$ 為絡
> 逆敘述不為真

絡有以下性質：

1. 交換律
2. 一致率
3. 結合律
4. 等效律
5. 吸收律

### 有界絡

如果 $(S,\vee ,\wedge)$ 有宇上界 $I$ 跟宇下界 $O$ ，稱之有界絡
記作 $(S,\vee ,\wedge ,I, O)$

如果 $(S,\vee ,\wedge ,I, O)$ 為有界絡，對 $S$ 中之元素 $a$ ， $\exists b\in S, \begin{cases} a\vee b = I \\ a\wedge b = O \end{cases}$
稱 $b$ 為 $a$ 之補元素 ($b = \overline{a}$)

> [!Note]
> $\overline{\overline{a}} = a$

> [!Note]
> 有界絡 $(S,\vee ,\wedge ,I, O)$ 中若 $S$ 之任意元素的補元素皆存在，稱之為互補絡

> [!Note]
> 若 $(S,\vee ,\wedge)$ 為絡且 $\forall A\subseteq S$ ，$\mathrm{lub} A, \mathrm{glb} A$ 均存在，稱之為完全絡
> **完全絡必定為有界絡**

### 分配絡

如果 $(S,\vee ,\wedge)$ 滿足：

- $\forall a,b,c\in S, a\vee (b\wedge c) = (a\vee b)\wedge (a\vee c)$
- $\forall a,b,c\in S, a\wedge (b\vee c) = (a\wedge b)\vee (a\wedge c)$

則稱 $(S,\vee ,\wedge)$ 為一分配絡

> [!Tip]
> 元素個數 $\lt 5$ 的絡必為分配絡

> [!Important]
> $(N,\max ,\min)$, $(P(A),\cup,\cap,A,\emptyset)$, $(D_m,\mathrm{lcm}, \mathrm{gcd},m,1)$ 均為分配絡

若$(S,\vee ,\wedge ,I, O)$ 同時為有界絡與分配絡，對 $S$ 中之元素 $a$ ，$\overline{a}$ 若存在，其並定唯一

## 布林代數

$(S,\vee ,\wedge ,I, O)$ 若為有界、分配、互補的絡，則稱之為布林絡 or 布林代數
記作 $(B,\vee ,\wedge ,I, O, -)$

布林代數具有**對偶性質**，並符合**笛摩根定律**

對偶性質是說，設 $S$ 為 $B$ 中為真的敘述，則 $S^d$ 仍為真
($S^d$ 是把 $S$ 中的 $\vee,\wedge$ 互換、 $I,O$ 互換。例如 $A\cap \overline{A} = \emptyset$ 跟 $A\cup \overline{A} = U$ 為對偶敘述)

笛摩根定律，老朋友了：$\forall a,b\in B, \overline{a\vee b} = \overline{a}\wedge \overline{b},\overline{a\wedge b} = \overline{a}\vee \overline{b}$

### 布林表示式

$(B,\vee ,\wedge ,I, O, -)$ 為一布林代數，則布林表示式 $E(x_1,x_2,\cdots ,x_n)$ 可遞迴定義為：

1. $B$ 中任意元素皆為布林表示式
2. 任意變數 $x_1,x_2,\cdots ,x_n$ 皆為布林表示式
3. 若 $E_1$, $E_2$ 皆為布林表示式，則 $\overline{E_1}$, $\overline{E_2}$, $E_1\vee E_2$, $E_1\wedge E_2$ 均為布林表示式

我們經常用 $+$ 表示 $\vee$ 、以 $\cdot$ 表示 $\wedge$

#### Disjunctive Normal Form and Conjunctive Normal Form

> [!Note]
> 稱 $E(x_1,\cdots ,x_n) = \widetilde{x_1}\wedge\widetilde{x_2}\wedge\cdots\wedge\widetilde{x_n}$ 為極小項，其中 $\widetilde{x_i}\in\left\{ x_i, \overline{x_i} \right\}$
> 稱 $E(x_1,\cdots ,x_n) = \widetilde{x_1}\vee\widetilde{x_2}\vee\cdots\vee\widetilde{x_n}$ 為極大項，其中 $\widetilde{x_i}\in\left\{ x_i, \overline{x_i} \right\}$

若 $E(x_1,\cdots ,x_n)$ 為若干個極小項之 join 則稱其為一種 disjunctive normal form；若干個極大項之 meet 則稱作 conjuctive normal form

例如 $E(x_1,x_2) = x_1x_2 + x_1\overline{x_2} + \overline{x_1}x_2$ 為 disjunctive normal form ； $E(x_1,x_2) = (x_1 + \overline{x_2})(\overline{x_1} + x_2)$ 為 conjuctive normal form

#### 化簡

布林表達式可以對應 logic network ，並且有多種表示的方法
不同的表示法造成的邏輯閘數目也會有所不同

1. 代數化簡
2. Karnaugh Map (卡諾圖)

詳細可以參考下列文章：

- [利用卡諾圖化簡布林代數的條件判斷式](https://medium.com/%E4%B8%80%E5%80%8B%E5%B0%8F%E5%B0%8F%E5%B7%A5%E7%A8%8B%E5%B8%AB%E7%9A%84%E9%9A%A8%E6%89%8B%E7%AD%86%E8%A8%98/%E5%88%A9%E7%94%A8%E5%8D%A1%E8%AB%BE%E5%9C%96%E5%8C%96%E7%B0%A1%E5%B8%83%E6%9E%97%E4%BB%A3%E6%95%B8%E7%9A%84%E6%A2%9D%E4%BB%B6%E5%88%A4%E6%96%B7%E5%BC%8F-db89dfca409b)
- [看完这篇还不会化简卡诺图？你来打我](https://blog.csdn.net/weixin_44754436/article/details/105848985)

### 布林函數

這個對考資工更重要

設 $B_s$ 為含 $s$ 個原子的布林代數，稱 $f: B_s^n\rightarrow B_s$ 為一具有 $n$ 變數的布林函數
在 $B_s$ 中，$n$ 個變數的布林函數有 $(2^s)^{2^{ns}}$ 種
$s = 1$ 時，記作 $B = \left\{ I,O \right\}$ ，此時的布林函數稱為開關函數

每個標準的布林表達式都可以用布林函數來表示，但並非所有布林函數都可以找到對應的布林表達式 ($s = 1$ 時則皆可找到對應的布林表達式)

題目會這樣問：

> How many Boolean functions on $n$ Boolean variables are self-dual? A Boolean function $f$ one the Boolean variables $x_1,\cdots ,x_n$ is called self-dual if $f(x_1,\cdots ,x_n) = \overline{f(\overline{x_1},\cdots ,\overline{x_n})}$

先想想看，題目這邊先考慮的應該是 $f: \left\{ 0,1 \right\}^n\rightarrow \left\{ 0,1 \right\}$
就是不談什麼 self-dual 的話，應該有 $2^{2^n}$ 種嘛

現在考慮到 self-dual 的話，那不就 $\left\{ 0,1 \right\}^n$ 那邊少考慮一半就好？
所以答案就是 $2^{2^{n-1}}$

這邊考的觀念其實更多是要考你函數那邊觀念有沒有學好