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

1. ~A = A的補集
2. A + B = （A- B）U（B-A）
3. p（A）有2的n次個：由集合A的所有子集所組成的集合---->冪集
4. 代數(shù)系統(tǒng)：非空集合，運算，封閉性
   如果倆個代數(shù)系統(tǒng)有相同個數(shù)的運算符，且每個相對應(yīng)的運算符有相同的元數(shù)，則稱這倆個代數(shù)系統(tǒng)有相同的類型，否則...不同類型。
   單位元素 e（x運算的e是1，+運算的e是0，串的并置運算e空串）
   若單位元素e存在，一定唯一
   零元素若存在，一定唯一
   逆元素（也唯一）：存在單位元素+結(jié)合律 eg：（R，x，+，-）：x：3與1/3、+：3與負3、減法沒有
   （零元素與逆元素不可能同時存在）
   補元素
5. 同構(gòu)：表面上不同而實質(zhì)上相同的代數(shù)系統(tǒng)，是同構(gòu)的。滿足3個條件：必須是同一類型，它們的集合有相同的基數(shù)，運算定義法則相同

群：

1. 群：單位元素+逆元素的半群
2. 半群：滿足結(jié)合律的代數(shù)
3. 單元半群：具有單位元素的半群
4. 阿貝爾群或可換群：滿足交換律的群
5. 可換半群：滿足交換律的半群
   ································································································
6. G群的階記為 |G|，有限群的階是群的元素個數(shù)，無限群的階無窮大
7. （5題）非平凡子群由Lagrange定理，群G的任何子群的階都應(yīng)該是|G|的因子，從而6階群不可能有4階子群；而非平凡子群應(yīng)該除去單位元構(gòu)成的群及其本身

1. 子群：左、右 陪集

圖

1. 結(jié)點V與邊E的關(guān)系是關(guān)聯(lián)，結(jié)點與結(jié)點或邊與邊的關(guān)系是鄰接
2. 簡單圖：不含環(huán)與多重邊的圖 。。。 反之是多重圖
3. （n，m）圖：n個結(jié)點與m條邊的圖 。。（n，0）圖即零圖。。（1,0）圖即平凡圖
4. 有向圖：出度deg+（v）是正，入度deg-（v）是負。。無向圖是次數(shù)
5. 關(guān)聯(lián)矩陣 臨接矩陣

關(guān)系

1. 單射：指將不同的變量映射到不同的值的函數(shù)。
   滿射：指陪域等于值域的函數(shù)。即：對陪域中任意元素，都存在至少一個定義域中的元素與之對應(yīng)。
   雙射（也稱一一對應(yīng)）：既是單射又是滿射的函數(shù)。直觀地說，一個雙射函數(shù)形成一個對應(yīng)，并且每一個輸入值都有正好一個輸出值以及每一個輸出值都有正好一個輸入值
2. 。：（1）表示復(fù)合運算符，，，復(fù)合關(guān)系R、S、T滿足結(jié)合律
   （2）二元關(guān)系R與S的復(fù)合（也叫作合成）
   例如R=｛<1,2>,<2,3>,<1,4>,<3,1>｝
   S={<2,3>,<3,4>,<1,2>,<4,1>}
   R。S={<1,3>,<2,4>,<1,1>,<3,2>}
   S。R=｛<2,1>,<1,3>,<4,2>,<4,4>｝
3. 自反：在集合X上的關(guān)系R，對任意x屬于X，有（x，x）屬于 R，則稱R是自反的，否則反自反。
   對稱：在集合X上的關(guān)系R，如果有（x，y）屬于R，必有（y，x）屬于R，稱R是對稱的；若（y，x）不屬于R，則反對稱
   傳遞：a-->b，b-->c，則a-->c

4. 偏序：自反、反對稱、傳遞（p28）
5. 哈斯圖（最大值、極大值、上界、上確界）

命題邏輯（P--->q::::非p析取q）

1. 只有陳述句才可能是命題（能分辨真假的語句是命題）
2. 合取式（下三角）、析取式（上三角）
   蘊含：如果p則q記為：p--->q（只有。。才//倘若。。就）F--》T
   等價：p<----->q
   規(guī)定5個連接詞的結(jié)合能力強弱順序：否定、合取、析取、蘊含、等價
3. 重言式===永真公式 。。。矛盾===永假公式
4. 范式：命題標準形式的稱謂
   析取范式：不出現(xiàn)聯(lián)結(jié)詞---->與<----->,否定符號僅出現(xiàn)在命題變元前（只能出現(xiàn)一次），每一個析取項是一個合取式（p175）
   合取范式：括號里是析取，括號外是合取
   步驟：①：將---》與《------》消掉
   ②將否定符號深入變元前
   ③：分配律形成形式
   主析取范式：每一析取項中都出現(xiàn)所有變元
   步驟：
   ①：化為析取范式
   ②：除去永假項，合并同一命題，利用pV非p補全項（析取與合取補全項符號相反）
   ③：分配律形成形式

樹

1. 沒有回路的圖是生成樹
2. 最小生成樹（權(quán)最?。?/li>
3. 最優(yōu)二叉樹（哈夫曼樹）
   eg：帶權(quán)為1,1,1,3,3,5,8的最優(yōu)二叉樹為：
   
   image.png
   
   WPL（帶權(quán)路徑長度）=（3+3+1）3+（1+1）4+（8+5）*2=55

1. 輪換的積：輪換也是置換。。。eg：（1、 3、 6）表示1--->3--->6--->1..寫為雙置換表達式是
   （1 2 3 4 5 6）
   （3 2 6 4 5 1）
2. 非p--->q = q 、、p--->非q = 非q（p166）