文章目录
 
一、 集合论体系
二、 集合表示
三、 数集合
三、 集合关系
1、 包含关系
2、 相等关系
3、 集合间包含关系性质
 

 

 

 

 

 
一、 集合论体系
 
 

 
集合论体系 :
 
朴素集合论 : 包含悖论 ; 朴素集合论 中 不能精确定义集合 ;
公理集合论 : 为了消除朴素集合论中的悖论 , 所建立的公理集合论 ; 公理集合论比较严密 , 通过一组公理描述什么是集合 ;
 

 

 

 

 
二、 集合表示
 
 

 
集合表示 : 使用 大写字母 表示集合 , 小写字母 表示集合中的元素 ;
 
列举法 : 列举出集合中的所有元素 , 元素之间使用逗号分开 ,  使用花括号 “{}” 括起来 ; 如 : 
    
     
      
       
        A
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        3
       
       
        }
       
      
      
       A = \{0, 1, 2, 3\}
      
     
    A={0,1,2,3} , 
    
     
      
       
        B
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        3
       
       
        ,
       
       
        ⋯
        
       
        }
       
      
      
       B = \{0, 1, 2, 3, \cdots\}
      
     
    B={0,1,2,3,⋯}
 
描述法 : 使用 谓词 $P(x)$ 表示 $x$ 具有性质 $P$ , 使用 
     
      
       
        
         {
        
        
         x
        
        
         ∣
        
        
         P
        
        
         (
        
        
         x
        
        
         )
        
        
         }
        
       
       
        \{x | P(x)\}
       
      
     {x∣P(x)} 表示具有性质 $P$ 的集合 ;
 

 
$P(x)$ 表示 $x$ 是英文字母 , 
    
     
      
       
        {
       
       
        x
       
       
        ∣
       
       
        P
       
       
        (
       
       
        x
       
       
        )
       
       
        }
       
      
      
       \{ x | P(x) \}
      
     
    {x∣P(x)} 表示英文字母集合 ;
 
$P(x)$ 表示 $x$ 是偶数 , 
    
     
      
       
        {
       
       
        x
       
       
        ∣
       
       
        P
       
       
        (
       
       
        x
       
       
        )
       
       
        }
       
      
      
       \{ x | P(x) \}
      
     
    {x∣P(x)} 表示偶数集合 ;
 

 

 
集合表示注意事项 :
 
不重复 : 集合中 不能有重复元素 ;
 
无顺序 : 集合中的元素是 无序的 ;
 
集合表示方法转化 : 集合的表示方法可以互相转化 , 描述法 和 列举法 可以互相转化 ;
 

 
表示方法转化示例 :
 
列举法 : 
    
     
      
       
        A
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        2
       
       
        ,
       
       
        4
       
       
        ,
       
       
        6
       
       
        ,
       
       
        ⋯
        
       
        }
       
      
      
       A=\{ 0, 2, 4 , 6 , \cdots \}
      
     
    A={0,2,4,6,⋯}
 
描述法 : 
    
     
      
       
        A
       
       
        =
       
       
        {
       
       
        x
       
       
        ∣
       
       
        x
       
       
        ≥
       
       
        0
       
       
        并
       
       
        且
       
       
        x
       
       
        是
       
       
        偶
       
       
        数
       
       
        }
       
      
      
       A = \{ x | x \geq 0 并且 x 是偶数 \}
      
     
    A={x∣x≥0并且x是偶数}
 

 

 

 

 
三、 数集合
 
 

 
自然数集合 : 
    
     
      
       
        N
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        ⋯
        
       
        }
       
      
      
       N = \{ 0, 1 , 2 , \cdots \}
      
     
    N={0,1,2,⋯}
 
整数集合 : 
    
     
      
       
        Z
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        ±
       
       
        1
       
       
        ,
       
       
        ±
       
       
        2
       
       
        ,
       
       
        ⋯
        
       
        }
       
      
      
       Z = \{ 0, \pm 1 , \pm 2 , \cdots \}
      
     
    Z={0,±1,±2,⋯}
 
有理数集合 : $Q$
 
实数集合 : $R$
 
复数集合 : $C$
 

 

 

 

 
三、 集合关系
 
 

 
集合关系 有 包含关系 , 相等关系 , 另外关系的性质有 自反省 , 反对称性性 , 传递性 ;
 

 

 
1、 包含关系
 

 
集合的包含关系 :
 
描述 : $A,B$ 两个集合 , 如果 $B$ 中的元素  都是 $A$ 中的元素 , 称 $B$ 集合 是 $A$ 集合的 子集 , $A$ 包含 $B$ , $B$ 包含于 $A$ ;
 
记作 : $B\subseteq A$
 
符号化形式 : $B\subseteq A\iff \forall x(x\in B\to x\in A)$ , 对于所有的对象 , 只要属于 $B$ 集合 , 就属于 $A$ 集合 ;
 

 

 
集合的不包含关系 :
 
描述 : 如果 集合 $B$ 不是 集合 $A$ 的子集
 
记作 : $B⊈A$ ;
 
符号化形式 : $B⊈A\iff \exists x(x\in B\wedge x\notin A)$ , 对于所有的对象 , 存在对象属于 $B$ 集合 , 不属于 $A$ 集合 ;
 

 

 
包含示例 :
 
$A=1,2,3,4$ , $B=1,2,3$ , $C=1,2$
 
有 $C\subseteq B$ , $C\subseteq A$ , $B\subseteq A$
 

 

 
2、 相等关系
 

 
集合的相等关系 :
 
描述 : $A,B$ 两个集合 , 如果 $A$ 包含 $B$ , 并且 $B$ 包含 $A$ , 则称 $A$ 与 $B$ 相等 ;
 
记作 : $A=B$
 
符号化表示 : $A=B\iff \forall x(x\in B\leftrightarrow x\in A)$
 

 

 
3、 集合间包含关系性质
 

 
集合间包含关系性质 : 下面的 $A,B,C$ 是三个集合 , 以下的命题是真命题 ;
 
自反性 : $A\subseteq A$ , 集合真包含它自己 ;
 
反对称性 :  若 $A\subseteq B$ 且 $B\ne A$ , 则 $B⊈A$
 ( 该性质等价于 若 $A\subseteq B$ 且 $B\subseteq A$ , 则 $A=B$ )
 
传递性 : 若 $A\subseteq B$ 且 $B\subseteq C$ , 则 $A\subseteq C$

$\color{blue}{\S 2.3 命题公式的等价关系和蕴涵关系}$
 
$\color{blue}{2.3.1 公式的等价}$
 
$定义2.3.1.公式G，H说是等价的，记以G = H，如果G，H在其任意解释I下，\\  
其真值相同。$ 
 $显然，G = H时，公式G，H等价的充要条件是公式G \leftrightarrow H是恒真的。$ 
 $两个公式间的等价关系，有反射性，对称性和传递性。$
 
$基本等价公式：$ 
 $1) (G \leftrightarrow H) = (G \to H) \land (H \to G);$ 
 $2) (G \to H) = (\lnot G \lor H);$ 
 $3) G \lor G = G, G \land G = G; (等幂律)$ 
 $4) G \lor H = H \lor G, G \land H = H \land G; (交换律)$ 
 $5) G \lor (H \lor S) = (G \lor H) \lor S, \\  
\quad G \land (H \land S) = (G \land H) \land S; (结合律)$ 
 $6) G \lor (G \land H) = G, G \land (G \lor H) = G; (吸收律)$ 
 $7)G \lor (H \land S) = (G \lor H) \land (G \lor S), \\  
\quad G \land (H \lor S) = (G \land H) \lor (G \land S); (分配律)$ 
 $8)G \lor 0 = G; G \land 1 = G; (同一律)$ 
 $9)G \land 0 = 0, G \lor 1 = 1;  (零一律)$ 
 $10)\lnot (G \lor H) = \lnot G \land \lnot H, \\  
\quad \lnot (G \land H) = \lnot G \lor \lnot H (De Morgan律)$
 
$定义2.3.2.设Q是逻辑运算符集合，若所有逻辑运算都能由Q中元素表示出来，\\  
而Q的任意真子集无此性质，则称Q是一个完备集。$ 
 $可以证明,\lbrace \lnot, \land \rbrace, \lbrace \lnot, \lor \rbrace都是完备集。$
 
$定义2.3.3.设P，Q是两个命题，命题“P与Q的否定”称为P与Q的与非式，\\  
记作P \uparrow Q。\uparrow称为与非联结词。P \uparrow Q为真当且仅当P，Q不同时为真。\\  
即: P \uparrow Q = \lnot (P \land Q)$
 
$定义2.3.4.设P，Q是两个命题，命题“P或Q的否定”称为P与Q的或非式，\\  
记作P \downarrow Q, \downarrow 称为或非联结词。P \downarrow Q为真当且仅当P，Q同时为假。即: \\  
P \downarrow Q = \lnot (P \lor Q)。$
 
$证明\lbrace \uparrow \rbrace 是完备集。\\  
\lnot P = P \uparrow P \\  
P \lor Q = (P \uparrow P) \uparrow (Q \uparrow Q) \\  
P \land Q = (P \uparrow Q) \uparrow (P \uparrow Q)$
 
$\lbrace \downarrow \rbrace也是完备集。$
 
$逻辑的一个重要功能是研究推理。固然，依靠等价关系可以进行推理。但是进行推理时，\\  
不必一定要依靠等价关系，只需是蕴涵关系就可以了。$ 
 $例如，若三角形等腰，则两底角相等，\\  
这个三角形等腰，所以，这个三角形两个底角相等。$ 
 $又如，若行列式两行成比例，则行列式值为0，\\  
这个行列式两行成比例，所以，这个行列式值为0。$ 
 $上面两个例子的推理关系涵义不同，但依据的推理规则相同，\\  
推理形式为:若P则Q；P，所以Q。$ 
 $推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，命题逻辑中用\\  
公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴涵关系。$
 
$定义2.3.5.设G，H是两个公式。称H是G的逻辑结果(或称G蕴涵H)，当且仅当对\\  
G，H的任意解释I，如果I满足G，则I也满足H，记作G \Rightarrow H。$ 
 $注意：符号\Rightarrow和符号=一样，它们都不是逻辑联结词，\\  
因此，G=H，G \Rightarrow H也都不是公式。\Rightarrow是一种部分序关系。$
 
$公式G蕴涵公式H的充要条件是：公式G \to H是恒真的。$ 
 $例如，(P \land Q) \Rightarrow P, (P \land Q) \Rightarrow Q$
 
$定义2.3.6.设G_1, \cdots, G_n, H是公式。称H是G_1, \cdots, G_n的逻辑结果\\  
(或称G_1, \cdots, G_n共同蕴涵H)，当且仅当公式G_1 \land \cdots \land G_n蕴涵H。$ 
 $公式H是G_1, \cdots, G_n的逻辑结果的充要条件是：公式((G_1 \land \cdots \land G_n) \to H)是恒真的。$ 
 $例如，P，P \to Q共同蕴涵Q。$
 
$定理2.3.1.如果H_1, \cdots, H_m, P共同蕴涵公式Q，\\  
则H_1, \cdots, H_m共同蕴涵公式P \to Q。$ 
 $证：因为(H_1 \land \cdots \land H_m \land P) \Rightarrow Q, \\  
所以公式(H_1 \land \cdots \land H_m \land P) \to Q是恒真的。\\  
利用下面的基本等价公式:\\  
P_1 \to (P_2 \to P_3) = (P_1 \land P_2) \to P_3 于是, \\  
(H_1 \land \cdots \land H_m \land P) \to Q = (H_1 \land \cdots \land H_m) \to (P \to Q)。\\  
故(H_1 \land \cdots \land H_m) \to (P \to Q) 是恒真的。\\  
所以 H_1, \cdots, H_m共同蕴涵P \to Q。$ 
 $例如，因为公式P \to Q,Q \to R, P 共同蕴涵R，\\  
所以P \to Q, Q \to R共同蕴涵P \to R。$
 
$定义2.3.7.设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公\\  
式的一个有限序列：G_1, \cdots, G_k其中，G_i或者属于S，或者属于某些G_j(j < i)\\  
的逻辑结果。并且G_k就是G。我们称公式G为此演绎的逻辑结果，或称从S演绎出\\  
G。有时也记为S \Rightarrow G。$ 
 $例如，设S = \lbrace P \lor Q, Q \to R, P \to M, \lnot M \rbrace, 则下面的公式序列\\  
\lnot M, P \to M, \lnot P, P \lor Q, Q, Q \to R, R \\  
就是从S推出R的一个演绎。$
 
$从演绎的定义知，演绎中仅仅使用了蕴涵的概念，也就是说，\\  
演绎是在蕴涵概念下进行的。下面给出的定理说明，演绎也是\\  
一种蕴涵，只不过换了一种形式。$
 
$引理：设G，H_1，H_2是公式。如果G蕴涵H_1, G蕴涵H_2,则G蕴涵H_1 \land H_2。$ 
 $证明：任取G，H_1,H_2的一个解释I。\\  
若I满足G，由假设知，I满足H_1, I满足H_2,故I满足H_1 \land H_2。\\  
由I的任意性，所以G \Rightarrow (H_1 \land H_2)。$
 
$定理2.3.2.设S是公式集合，G是一个公式。\\  
从S演绎出G的充要条件是G是S的逻辑结果。$ 
 $证：必要性，设从S演绎出G，令G_1, \cdots, G_k是这个演绎。\\  
对任意G_i(i = 1, 2, \cdots, k),往证G_i是S的逻辑结果。\\  
对I用归纳法。\\  
当i=1时，因G_1 \in S,显然G_1 \land \cdots \to G_1是恒真公式，\\  
故S \Rightarrow G_1, 即G_1是S的逻辑结果.\\  
设i < n时，命题成立。\\  
当i = n时，若G_n \in S,则S \Rightarrow G_n,归纳法完成。\\  
若G_n是某些G_j(j < n)的逻辑结果，不妨设(G_{j1} \land \cdots \land G_{jh}) \Rightarrow G_n \quad(1) \\  
其中j1, \cdots, jh都小于n。由归纳假设知，S \Rightarrow G_{jm}, m = 1, \cdots, h。\\  
由引理知：S \Rightarrow (G_{ji}, \land \cdots \land G_{jh}) \quad (2) \\  
根据(1),(2)式即蕴涵关系的传递性，得S \Rightarrow G_n，即G_n是S得逻辑结果，归纳完成。\\  
充分性，若G是S的逻辑结果，由演绎的定义知，\\  
G是如下演绎：G_1, \cdots, G_k, G的逻辑结果，其中G_1, \cdots, G_k是S中所有公式$
 
$定理2.3.3.设S是前提公式集合，G，H是两个公式。如果从S \cup \lbrace G \rbrace \\  
可演绎出H，则从G可演绎出G \to H。$ 
 $证：因为从S \cup \lbrace G \rbrace 可演绎出H，\\  
由定理2知，H是S \cup \lbrace G \rbrace 的逻辑结果。\\  
亦即(G_1 \land \cdots \land G_k \land G) \Rightarrow H \\  
其中G_1, \cdots, G_k是S中所有公式。\\  
由定理2.3.1知：(G_1 \land \cdots \land G_k) \Rightarrow (G \to H) \\  
即G \to H是S的逻辑结果，\\  
再由定理2.3.2知，从S可演绎出G \to H。$
 
$在命题逻辑中进行演绎，要不断地使用已知的蕴涵公式，过去我们知道的基本\\  
等价式当然可以当作两个蕴涵式使用，因为G = H的充要条件是(G \Rightarrow H)\\  
和(H \Rightarrow G)，下面我们在给出一个基本蕴涵式，以便在演绎时使用。$ 
 $基本蕴涵式：$ 
 $1. P \land Q \Rightarrow P$ 
 $2. P \land Q \Rightarrow Q$ 
 $3. P \Rightarrow P \lor Q$ 
 $4. Q \Rightarrow P \lor Q$ 
 $5. \lnot P \Rightarrow (P \to Q)$ 
 $6. Q \Rightarrow (P \to Q)$ 
 $7. \lnot (P \to Q) \Rightarrow P$ 
 $8. \lnot (P \to Q) \Rightarrow \lnot Q$ 
 $9. P, Q \Rightarrow P \land Q$ 
 $10. \lnot P, P \lor Q \Rightarrow Q$ 
 $11. P, P \to Q \Rightarrow Q$ 
 $12. \lnot Q, P \to Q \Rightarrow \lnot P$ 
 $13. P \to Q, Q \to R \Rightarrow P \to Q$ 
 $14. P \lor Q, P \to R, Q \to R \Rightarrow R$
 
$至此，给出两个公式G，H，证明G蕴涵H，我们有如下五种方法:$ 
 $1.真值表法；\\  
2.证G \to H是恒真公式; \\  
3.利用基本等价式即蕴涵式进行推导；\\  
4.任取解释I，若I满足G,往证I满足H；\\  
5.反证法，设结论假，往证前提假。$ 
 $若给出前提集合 S = \lbrace G_1, \cdots, G_k \rbrace, 公式G，证明S \Rightarrow G有如下两种方法:$ 
 $1.G_1 \land \cdots \land G_k \Rightarrow G \\  
 2. 形式演绎法：根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，\\  
在演绎过程中我们遵循以下三条规则：\\  
规则1：可随便使用前提。(根据演绎定义)\\  
规则2：可随便使用前面演绎出的某些公式的逻辑结果。(根据演绎的定义)\\  
规则3：如果需要演绎出的公式是P \to Q的形式，则我们可将P作为附加前提使用，\\  
而力图去演绎出Q。(根据定理2.3.3)$
 
$例2.3.1.证明 \lbrace (P \lor Q), (P \to R), (Q \to S) \rbrace \Rightarrow S \lor R$ 
 $证：\\  
1. P \lor Q  \quad 规则1 \\  
2. \lnot P \to Q \quad 规则2，根据1 \\  
3. Q \to S \quad 规则1 \\  
4. \lnot P \to S \quad 规则2， 根据2，3 \\  
5. \lnot S \to P \quad 规则2，根据4 \\  
6. P \to R \quad 规则1 \\  
7. \lnot S \to R \quad 规则2， 根据5， 6\\  
8. S \lor R \quad 规则2，根据7$
 
$例2.3.2.证明\lbrace P \to (Q \to S), \lnot R \lor P, Q \rbrace \Rightarrow R \to S$ 
 $证：\\  
1. \lnot R \lor P \quad 规则1 \\  
2. R \quad 规则3 \\  
3. P \quad 规则2，根据1，2\\  
4. P \to (Q \to S) \quad 规则1 \\  
5. Q \to S \quad 规则2， 根据3，4\\  
6. Q \quad 规则1 \\  
7. S \quad 规则2，根据5， 6 \\  
8. R \to S \quad 规则3，根据2，7$
 
$例2.3.3.若厂方拒绝加工资，则罢工不会停止，除非罢工超过一年并且工厂经理\\  
辞职。问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止？$ 
 $令\\  
P:厂方拒绝增加工资；\\  
Q:罢工停止；\\  
R:工厂经理辞职；\\  
S:罢工超过一年。\\  
于是，\\  
G_1:(P \land \lnot(R \land S)) \to \lnot Q \\  
G_2:P \\  
G_3: \lnot S \\  
H: \lnot Q$ 
 $我们要证明：H是\lbrace G_1, G_2, G_3 \rbrace逻辑结果。$ 
 $1. \lnot S \quad 规则1 \\  
2. \lnot S \lor \lnot R \quad 规则2，根据1 \\  
3. \lnot (R \land S) \quad 规则2，根据2 \\  
4. P \quad 规则1 \\  
5. P \land \lnot (R \land S) \quad 规则2，根据3，4 \\  
6. (P \land \lnot (R \land S)) \to \lnot Q \quad 规则1 \\  
7. \lnot Q \quad 规则2， 根据5，6 \\  
亦即，罢工不会停止。$

离散数学思维导图
 
 
大纲：
 
	预备知识
		1.集合论
			set
				表示方法
					大写字母表示
					枚举法(显示法)
					叙述法(隐式法)
					归纳法
					递归指定集合法
					文氏图解法
				几个特殊集合
					空集(绝对唯一）
					全集(相对唯一）
					无限集
						等势
							一一对应
								两个有限集合等势当且仅当它们的元素个数相同；
								可数集合可以和其可数的真子集等势.
						可数集合
							基数(阿列夫0)
								∈阿列夫1(开区间(0,1)的基数)
						不可数集合
							既不是有限集
							也不是可数集的集合
				重要定义
					集合A的元素个数: |A|(基数)
					集族(Power Set)
						集合作为元素构成
						幂集
							所有不同子集构成
					⊕：对称差运算
						
					补集
						
						相对补集A-B(差集)
					德摩根律
						
			重要题型
				
	数理逻辑
		命题逻辑
			联结词
				┐
					否定
				∧
					合取
				∨
					析取
				
					异或
						“P异或Q”称为P与Q的不可兼或
				→
					蕴涵
						P称为蕴涵式的前件，Q称为蕴涵式的后件
							若P，则Q
							P仅当Q
							只要P， 就Q
							只有Q，才P
							除非Q，才P
							除非Q，否则非P
							P是Q的充分条件
						P→Q为假当且仅当P为真且Q为假
				↔
					等价
						P当且仅当Q
				优先级：否定→合取→析取→蕴涵→等价
			命题公式分类
				永真公式(重言式)
					满足式(一定)
				永假公式(矛盾式)
				G在解释Ｉ下是真的:Ｉ满足G；  G在解释Ｉ下是假的:Ｉ弄假于G.
				公式G、H等价 ↔ 公式G↔H是永真公式
					G = H 不是命题公式， G↔H是命题公式
			范式
				定义
					命题变元或命题变元的否定称为文字
					有限个文字的析取称为析取式(也称为子句）
					有限个文字的合取称为合取式(也称为短语）
					P与┐P称为互补对
					包括单个
				有限个短语的析取式称为析取范式
				有限个子句的合取式称为合取范式
				主析取范式
					每一个短语都是极小项
					必须且只能包含使得公式真值为真的那些解释对应的极小项
				主合取范式
					每一个子句都是极大项
					必须且只能包含使得公式真值为假的那些解释对应的极大项
				求解方法
					等价式和蕴涵式
						(Ｇ→Ｈ) = (┐Ｇ∨Ｈ)
						(Ｇ↔Ｈ) = (Ｇ→Ｈ)∧(Ｈ→Ｇ)  = (┐Ｇ∨Ｈ)∧(┐Ｈ∨Ｇ)
					德▪摩根定律
						┐(┐Ｇ) =Ｇ；
						┐(Ｇ∨Ｈ) =┐Ｇ∧┐Ｈ；
						┐(Ｇ∧Ｈ) =┐Ｇ∨┐Ｈ。
					分配定律
						Ｇ∨(Ｈ∧Ｓ) = (Ｇ∨Ｈ)∧(Ｇ∨Ｓ)
						Ｇ∧(Ｈ∨Ｓ) = (Ｇ∧Ｈ)∨(Ｇ∧Ｓ)
				包括单个
				总结
					若单个的子句（短语）无 最外层括号，则是合取范式（析取范式）；
					析取范式、合取范式仅含联结词集{┐，∧，∨}；
					“┐”联结词仅出现在命题变元前.
			推理推论
				概念
					反映客观对象或现象的共同本质属性的思维形式
					任何概念都是内涵和外延的统一体。
					内涵
						概念的质
					外延
						概念的量
				
					若H是G1∧G2∧…∧Gn的逻辑结果
						则efficacious(有效的)
						
							Г={G1,G2,…,Gn}
					H是G的逻辑结果(或称G蕴涵H
						当且仅当G→Ｈ为永真公式
						G为前提
							Premise
						H为结论
							conclusion
				判断方法
					真值表技术
						对所有G1,G2,…,Gn都具有真值T的行(表示前提为真的行),如果在每一个这样的行中，H也具有真值T
						对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中，G1,G2,…,Gn中至少有一个公式的真值为F(前提也为假)
					推理定律
						
						
						
						
						
						
					演绎法
						规则P（称为前提引用规则）
						规则T（逻辑结果引用规则）
						规则CP（附加前提规则）
							
					反证法
						
		谓词逻辑
			解决“命题的结构和成分”有关的推理问题
			基本概念
				Universal Quantifier全称量词
					
				Existential Quantifier存在量词
					
				Individual个体词
					不能随意变更顺序
					取值范围：Individual Field 个体域(或论域)
						全总个体域(Universal Individual Field)
				P(x)
					x：个体词
					P：谓词
					P(x):命题函数
				Predicate谓词
					0元
						命题
					一元
						某一个个体的某种特性
					n元
						n个个体之间的关系
				项与原子公式
					项(Term)
						（1）任意的常量符号或任意的变量符号是项；
						（2）若f(x1, x2, …, xn)是n 元函数符号，t1,t2,…,tn是项，则f(t1, t2, …, tn)是项；
						（3）仅由有限次使用(1)，(2)产生的符号串才是项。
					原子公式(Atomic Formulae)
						 若P(x1,x2,…,xn)是n 元谓词，t1，t2，…，tn是项，则称P(t1,t2,…,tn)为原子谓词公式(Atomic Propositional Formulae)
				存在：合取
任意：蕴含
					x : Function Variable作用变量
					F(x) : Scope辖域
						
		自由主题
	树
		定义
			无向树
				连通而不含回路的无向图
				简称树(Tree)，常用T表示树。
			叶
				树中度数为1的结点
			分支点
				度数大于1的结点
				内部结点
			森林
				每个连通分支都是树的无向图
			生成树
				给定图G = <V, E>，若G的某个生成子图是树
				树枝
					生成树TG中的边
				弦
					G中不在TG中的边
				补
					TG的所有弦的集合称为生成树
				权
					T的每个树枝所赋权值之和
				最小生成树
					G中具有最小权的生成树
			有向树
				一个有向图，若略去所有有向边的方向所得到的无向图是一棵树
			有序树
				如果在根树中规定了每一层上结点的次序
			k元树
				若每个分支点至多有k个儿子
			k元完全树
				若每个分支点都恰有k个儿子
			k元有序完全树
				k元完全树T是有序的
			子树
				任一结点v及其所有后代导出的子图T’称为T的以v为根
			决策树
				有一棵根树，如果其每个分支点都会提出一个问题，从根开始，每回答一个问题，走相应的边，最后到达一个叶结点，即获得一个决策
		!算法
			Kruskal算法
				
			Prim算法
				
			哈夫曼算法
				
		定理
			树
				边数最多的无回路图
				边数最少的连通图
				无向图G = (n, m)中，
					    若m＜n-1，则G是不连通的
					    若m＞n-1，则G必含回路
	图论
		握手定理
			
			推论：图中度数为奇数的结点个数为偶数。
		同构
			
			
			必要条件
				（1）结点数目相同； 
				（2）边数相同； 
				（3）度数相同的结点数相同。
		
			边数最大值
		连通性
			连通图
				强连通图
					G中任何一对结点之间都是相互可达的
					它的可达性矩阵P的所有元素均为1；
				单向连通图
					若G中任何一对结点之间至少有一个结点到另一个结点是可达的
					它的可达性矩阵P及其转置矩阵PT经过布尔并运算后所得的矩阵P’= P∨PT中除主对角元外其余元素均为1
				(弱)连通图
					略去G中所有有向边的方向得无向图G’，如果无向图G’是连通图
					它的邻接矩阵A及其转置矩阵AT经布尔并运算所得的矩阵A’= A∨AT作为邻接矩阵而求得的可达性矩阵P’中所有元素均为1。
				若有向图G是强连通图，则它必是单向连通图；若有向图G是单向连通图，则它必是（弱）连通图。
			分支
				
		应用
			Floyd算法
				
				
			Dijkstra算法
		邻接矩阵与可达性矩阵
			可达性矩阵
				
			
			
	二元关系
		关系的基本概念 
			有序偶对(序偶)
				两个元素x,y按照一定的次序组成的二元组
				<x,y>
				其中称x为<x,y>的第一元素，y为<x,y>的第二元素
				成对出现、具有一定的顺序
			笛卡尔积(Descartes Product)
				集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}为集合A与B的笛卡尔积
				对有限集A,B，有|A×B|=|B×A|=|A|×|B|
				A×(B∪C)=(A×B)∪(A×C)
				
			关系(Relation)
				称A×B的任何子集 R 为从A到B的二元关系
				A＝B，则称R为A上的二元关系
				A称为R的前域，B称为R的后域
				
				当R=Φ时，称R为空关系(empty relation)；
				当R=A×B时，则称R为全关系(Total Relation)
				xRy
					<x,y>∈R
					x对y有关系R
				当集合A,B都是有限集时，A×B共有2^(|A|•|B|)个不同的子集，即从A到B的不同关系共有2^(|A|•|B|)个。
		关系的表示与运算
			集合表示法（枚举法和叙述法）
			关系图法
			关系矩阵
				关系矩阵是0-1矩阵，称为布尔矩阵
			R∪S={<x,y>|(xRy)∨(xSy)} (即<x,y>∈R∨<x,y>∈S)
			复合运算
				(RoS)oT = Ro(SoT)
				IAoR = RoIB = R
			逆运算
				 R-1＝{<b,a>|<a,b>∈R}
				(RoS)-1 = S-1oR-1
			幂运算
				设R是集合A上的关系，则R的n次幂，记为Rn，定义如下：
				R0＝IA＝{<a,a>|a∈A}；
				R1＝R；
				Rn+1＝RnoR＝RoRn
		关系的性质与闭包 
			假定其前域和后域相同
			
			
			
		特殊关系
			等价关系
				设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。
				事实上，对任意正整数n，整数集合Z的任意非空子集A上的关系，R={<x,y>|(x,y∈A)∧(n|(x-y))}，都是等价关系。 
				同余式
					上述R称为Z上以n为模的同余关系(Congruence Relation)，记xRy为x＝y(mod n)
					
					
				等价类
					
					
				商集
					
			次序关系
				拟序关系
					
				偏序关系
					
					哈斯图
						用小圆圈或点表示A中的元素，省掉关系图中所有的环；（因自反性)
						对任意x,y∈A，若x＜y，则将x画在y的下方，可省掉关系图中所有边的箭头；（因反对称性）
						对任意x,y∈A，若x＜y，且不存在z∈A，使得x＜z, z＜y，则x与y之间用一条线相连，否则无线相连。（因传递性）
					设<A,≤>是偏序集，B是A的任何一个子集。若存在元素a∈A，使得
						对任意x∈B，都有x≤a，则称a为B的上界；
						对任意x∈B，都有a≤x，则称a为B的下界；
						若元素a′∈A是B的上界，元素a∈A是B的任何一个上界，若均有a′≤a，则称a′为B的最小上界或上确界。记a′= SupB；
						若元素a'∈A是B的下界，元素a∈A是B的任何一个下界，若均有a≤a′，则称a′为B的最大下界或下确界。记a′= InfB。
				全序关系
					
					全序关系是偏序关系，反之则不然。
				良序关系
					

符号表
 
 
集合
 
设A,B两个集合有一种一一对应的关系ψ：A→B ， 则称A,B等势记做：A~B 。
 如果A=B ， 则A~B，反之不成立。
凡与自然集合N等势的集合称之为可数集合 ， 该集合的基数记为
 （阿列夫零）
开区间（0,1）称为不可数集合， 凡与开区间等势的集合称为不可数集合，称为阿列夫。
 
命题
 
 
一切没有判断内容的句子都不能作为命题，命题应该是一个陈述语句
 
 
设p为任意命题，非p称为p的否定式，记为﹁p。
 
 
p∧q 含义为 “p并且q”或“p与q” ； p∨q 含义为“p或q”，均为假才为假。
 
 
∧∨⊕ 相当于 or ， and ，xor
 
 
 
 
p↔q 为 p与q 的等价式。q ， p相�