离散数学

离散数学-必修课
Discrete mathematics- compulsory subjects

研究离散对象及其相互间关系的一门数学学科 ÿ研究离散结构的数学分支。

——辞海 ÿ离散数学是数学的几个分支的总称，以研究离 散量的结构和相互间的关系为主要目标，其研 究对象一般地是有限个或可数无穷个元素;因此 它充分描述了计算机科学离散性的特点。

内容包含：

数理逻辑、集合论、代数结构、图论、 组合学、数论等

​

应用部分:

图(Graphs) 树(Trees) 代数系统： 布尔代数(Boolean Algbra) 群（Group）

来两个题目吧

利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。

证明：{P→Q, R→S, P∨R}蕴涵Q∨S

(1) P∨R P

(2) ØR→P Q(1)

(3) P→Q P

(4) ØR→Q Q(2)(3)

(5) ØQ→R Q(4)

(6) R→S P

(7) ØQ→S Q(5)(6)

(8) Q∨S Q(7)

设A,B为任意集合，证明：(A-B)-C = A-(B∪C).

证明：(A-B)-C = (A∩~B)∩~C

​ = A∩(~B∩~C)

​ = A∩~(B∪C)

​ = A-(B∪C)

利用形式演绎法证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D。

\3. 证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D

(1) A D(附加)

(2) ØA∨B P

(3) B Q(1)(2)

(4) ØC→ØB P

(5) B→C Q(4)

(6) C Q(3)(5)

(7) C→D P

(8) D Q(6)(7)

(9) A→D D(1)(8)

所以 {ØA∨B, ØC→ØB, C→D}蕴涵A→D.

A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B .

证明：A－(A∩B)

= A∩~(A∩B)

＝A∩(~A∪~B)

＝(A∩~A)∪(A∩~B)

＝Æ∪(A∩~B)

＝(A∩~B)

＝A－B

而 (A∪B)－B

= (A∪B)∩~B

= (A∩~B)∪(B∩~B)

= (A∩~B)∪Æ

= A－B

所以：A－(A∩B) = (A∪B)－B.