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

Relation

考慮集合

$A$,

$B$ 之卡氏積

$A\times B$
若

$R$ 為

$A\times B$ 之一子集，稱

$R$ 為

$A$ 到

$B$ 之二元關係，記作

$R:A\to B$
若

$(a,b)\in R$ 則稱

$a$,

$b$ 有

$R$ 關係，記作

$aRb$

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

例如

$A=\{a_1,\cdots ,a_m\},B=\{b_1,\cdots ,b_n\},R:A\to B$

$R$ 之關係矩陣

$M_R=(m_{ij}{)}_{m\times n}$ ，其中

$m_{ij}=\{\begin{array}{ll}1& \text{ if }(a_i,b_j)\in R\\ 0& \text{ if }(a_i,b_j)\notin R\end{array}$

Inverse

$R:A\to B$ 之反關係

$R^{-1}:B\to A$ 定義為

$R^{-1}=\{(b,a)|(a,b)\in R\}$
即

$\mathrm{\forall }a\in A,b\in B,aRb\iff b{R}^{-1}a$

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

Complement

$R:A\to B$ 之補關係

$\bar{R}:A\to B$ 定義為

$\bar{R}=\{(a,b)|a\in A,b\in B,(a,b)\notin R\}$

Composition

Let

$R:A\to B,S:B\to C$ 則

$R$,

$S$ 之合成

$R\circ S=\{(a,c)|\mathrm{\exists }b\in B,(a,b)\in R\wedge (b,c)\in S\}$

關係的合成如果採用左運算，可以得到

$M_{R\circ S}=M_R{M}_S$ 的結論；但是，有些書講的是右運算，這樣的話是比較與函數合成的右運算一致

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

六大特殊的二元關係

二元關係	定義	在關係矩陣中	在關係圖中
反身性 (reflextive)	$\mathrm{\forall }a\in A,(a,a)\in R$	對角項均為 $1$	每點均有 loop
非反身性 (irreflextive)	$\mathrm{\forall }a\in A,(a,a)\notin R$	對角項均為 $0$	每點均無 loop
對稱性 (symmetric)	$\mathrm{\forall }a,b\in A,\text{ if }(a,b)\in R\text{, then }(b,a)\in R$	對稱位置相等	兩點間若有邊必雙向
非對稱性 (asymmetric)	$\mathrm{\forall }a,b\in A,\text{ if }(a,b)\in R\text{, then }(b,a)\notin R$	對稱位置不同時為 $1$ ，主對角必為 $0$	兩點間的邊必單向且每點均無 loop
反對稱性 (antisymmetric)	$\mathrm{\forall }a,b\in A,\text{ if }(a,b)\in R\wedge (b,a)\in R\text{, then }a=b$	對稱位置不同時為 $1$	兩點間的邊必單向
遞移性 (transitive)	$\mathrm{\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$ 具反身性
   $\iff R^0\subseteq R$
2. $R$ 具非反身性
   $\iff R^0\cap R=\mathrm{\varnothing }$
3. $R$ 具對稱性
   $\iff R=R^{-1}$
4. $R$ 具非對稱性
   $\iff R\cap R^{-1}=\mathrm{\varnothing }$
5. $R$ 具反對稱性
   $\iff R\cap R^{-1}\subseteq R^0$
6. $R$ 具遞移性
   $\iff R^2\subseteq R$

Note

$R^0=\{(x,x)|\mathrm{\forall }x\in A\}$ 為

$A$ 上之對角關係

$R$		$R^{-1}$		$\bar{R}$
反身性	$\iff$	反身性	$\iff$	非反身性
非反身性	$\iff$	非反身性	$\iff$	反身性
對稱性	$\iff$	對稱性	$\iff$	對稱性
非對稱性	$\iff$	非對稱性	$\Rightarrow$	反身性
反對稱性	$\iff$	反對稱性
遞移性	$\iff$	遞移性

Tip

$R$ 具備什麼性，

$R^{-1}$ 就具備什麼性

Note

$R$ 具非對稱性時，僅可得

$\bar{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 _{i=1}^{\mathrm{\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

個數計算

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\ne \mathrm{\varnothing },i=1,2,\cdots ,n$
2. $\bigcup _{i=1}^n{A}_i=A$
3. $\mathrm{\forall }i\ne j,A_i\cap A_j=\mathrm{\varnothing }$ (兩兩互斥)

設

$R$ 為

$A$ 上之等價關係，則

$R$ 的相異等價類形成

$A$ 之一分割

$A$ 上之分割亦可唯一決定一種

$A$ 上的等價關係

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

例如若集合

$A=\{1,2,3,4,5\}$，

$A=\{1,3\}\cup \{2,4\}\cup \left\{5\right\}$ 為

$A$ 上之一分割，則

$A$ 上的等價關係

$R$ 就可以寫出

$R=(\{1,3\}\times \{1,3\})\cup (\{2,4\}\times \{2,4\})\cup (\left\{5\right\}\times \left\{5\right\})$

而集合

$\{1,2,\cdots ,m\}$ 分割的方法數其實就可以看成

$m$ 相異物放入

$m$ 相同箱 (可空) 之方法數，即

$\sum _{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 如下：

source

偏序集的性質

令

$(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)\iff s{\le }_{1}u\wedge t{\le }_{2}v$ ，則
   $(S\times T,\le )$ 亦為偏序集

Lexicographic Ordering

令

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

定義

$S^m$ 上的關係

$\prec$ 為字典順序：

$\mathrm{\forall }a,b\in S^m,a=a_1{a}_2\cdots a_m,b=b_1{b}_2\cdots b_m,a_i,b_j\in S,\mathrm{\forall }i,j$

$a\prec b\iff \{\begin{array}{l}{a}_1\ne b_1\\ a_{1}R{b}_1\end{array}\text{ or }\{\begin{array}{l}{a}_1=b_1,\mathrm{\forall }i,1\le i\le k\\ a_{k+1}\ne b_{k+1}\\ a_{k+1}R{b}_{k+1}\end{array}\text{ for some }k,1\le k\le m$

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

令

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

稱

$\{\begin{array}{l}M\\ m\end{array}$ 為

$S$ 之

$\{\begin{array}{l}\text{極大}\\ \text{極小}\end{array}$ 元素，如果不存在其他

$S$ 中的元素

$x$ 使得

$\{\begin{array}{l}M\le x\\ x\le m\end{array}$

稱

$\{\begin{array}{l}I\in S\\ O\in S\end{array}$ 為

$S$ 之

$\{\begin{array}{l}\text{最大}\\ \text{最小}\end{array}$ 元素，如果對

$S$ 中的任意元素

$x$ 均有

$\{\begin{array}{l}x\le I\\ O\le x\end{array}$

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

令

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

$A$ 為

$S$ 之子集

稱

$\{\begin{array}{l}u\in S\\ l\in S\end{array}$ 為

$A$ 之

$\{\begin{array}{l}\text{上界}\\ \text{下界}\end{array}$ ，如果

$\mathrm{\forall }x\in A\{\begin{array}{l}x\le u\\ l\le x\end{array}$

稱

$\{\begin{array}{l}u\in S\\ l\in S\end{array}$ 為

$A$ 之

$\{\begin{array}{l}\text{最小上界 (lub)}\\ \text{最大下界 (glb)}\end{array}$ ，如果

$\{\begin{array}{l}u\\ l\end{array}$ 為

$A$ 之

$\{\begin{array}{l}\text{上界 }\\ \text{下界 }\end{array}$ 且對

$A$ 之其他

$\{\begin{array}{l}\text{上界 }{u}^{\prime }\\ \text{下界 }{l}^{\prime }\end{array}$ 均有

$\{\begin{array}{l}u\le u^{\prime }\\ l^{\prime }\le l\end{array}$

Totally Ordering Relation

Note

Comparable:
考慮偏序集

$(S,\le ),a,b\in S,a\ne 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}\{a,b\}$ 存在 (記作
  $a\vee b$ ，
  $a$ 與
  $b$ 的 joint)
• $\mathrm{glb}\{a,b\}$ 存在 (記作
  $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$ ，

$\mathrm{\exists }b\in S,\{\begin{array}{l}a\vee b=I\\ a\wedge b=O\end{array}$
稱

$b$ 為

$a$ 之補元素 (

$b=\bar{a}$)

Note

$\overline{\stackrel{―}{a}}=a$

Note

有界絡

$(S,\vee ,\wedge ,I,O)$ 中若

$S$ 之任意元素的補元素皆存在，稱之為互補絡

Note

若

$(S,\vee ,\wedge )$ 為絡且

$\mathrm{\forall }A\subseteq S$ ，

$\mathrm{lub}A,\mathrm{glb}A$ 均存在，稱之為完全絡
完全絡必定為有界絡

分配絡

如果

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

• $\mathrm{\forall }a,b,c\in S,a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
• $\mathrm{\forall }a,b,c\in S,a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$

則稱

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

Tip

元素個數

$<5$ 的絡必為分配絡

Important

$(N,max,min)$,

$(P(A),\cup ,\cap ,A,\mathrm{\varnothing })$,

$(D_m,\mathrm{lcm},\gcd ,m,1)$ 均為分配絡

若

$(S,\vee ,\wedge ,I,O)$ 同時為有界絡與分配絡，對

$S$ 中之元素

$a$ ，

$\bar{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 \bar{A}=\mathrm{\varnothing }$ 跟

$A\cup \bar{A}=U$ 為對偶敘述)

笛摩根定律，老朋友了：

$\mathrm{\forall }a,b\in B,\overline{a\vee b}=\bar{a}\wedge \bar{b},\overline{a\wedge b}=\bar{a}\vee \bar{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 \{x_i,\overline{x_i}\}$
稱

$E(x_1,\cdots ,x_n)=\widetilde{x_1}\vee \widetilde{x_2}\vee \cdots \vee \widetilde{x_n}$ 為極大項，其中

$\widetilde{x_i}\in \{x_i,\overline{x_i}\}$

若

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

例如

$E(x_1,x_2)=x_1{x}_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 (卡諾圖)

詳細可以參考下列文章：

• 利用卡諾圖化簡布林代數的條件判斷式
• 看完这篇还不会化简卡诺图？你来打我

布林函數

這個對考資工更重要

設

$B_s$ 為含

$s$ 個原子的布林代數，稱

$f:B_s^n\to B_s$ 為一具有

$n$ 變數的布林函數
在

$B_s$ 中，

$n$ 個變數的布林函數有

$(2^s{)}^{2^{ns}}$ 種

$s=1$ 時，記作

$B=\{I,O\}$ ，此時的布林函數稱為開關函數

每個標準的布林表達式都可以用布林函數來表示，但並非所有布林函數都可以找到對應的布林表達式 (

$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(\stackrel{―}{x_1},\cdots ,\stackrel{―}{x_n})}$

先想想看，題目這邊先考慮的應該是

$f:{\{0,1\}}^n\to \{0,1\}$
就是不談什麼 self-dual 的話，應該有

$2^{2^n}$ 種嘛

現在考慮到 self-dual 的話，那不就

${\{0,1\}}^n$ 那邊少考慮一半就好？
所以答案就是

$2^{2^{n-1}}$

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