离散数学笔记
无聊写的，懒得动笔。
我了个o((⊙﹏⊙))o. 老师连PPT都没发
常见的离散数学符号：
联结词： ¬ ∧ ∨ → ↔
推出：⇒
等值：⇔
△ × ≁
量词：∃ ∀
数学：
≠ ≥ ≤
集合关系
∪ ∩ ∈ ⊆ ⊂ ⊇ ⊃ Ø
第1章 命题逻辑的基本概念
1.1
命题是非真即假的陈述句,简单命题是最小的基本单位,其构成复合命题,悖论不是命题。
命题符号化，联结词也符号化。
¬：否定联结词
∧：合取联结词.规定p∧q为真当且仅当p与q同时为真
∨：析取联结词.规定p∨q为假当且仅当p与q同时为假
(或有两种：排斥或 相容或)
→：蕴涵联结词.p→q为假当且仅当p为真q为假。p为前件，q为后件。
注意点：
1.p→q：表示q是p的必要条件。
2.当p为假时，p→q必然为真
3.p→q为真仅表示p与q的取值关系为真，与其内在联系无关。
↔：等价联结词.规定p↔q为真当且仅当p与q同时为真或同时为假。
| p | q | ¬p | p∧q | p∨q | p→q | p↔q |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
ex：
p：北京比天津的人口多
q: 2+2=4
r：乌鸦是白色的
求下列符合命题的真值
先算简单命题真值：p:1 q:1 r:0
(1) ((¬p∧q)∨(p∧¬q))→r 左0右0 A：1
(2) (q∨r)→(p→¬r) 左1右1 A：1
(3) (¬p∨r)↔(p∧¬r) 左0右1 A：0
1.2 命题公式及其赋值
命题常项真值确定，命题变项是取值1或0的变元。
将命题变项用联结词和圆括号按照一定逻辑顺序联结起来的符号串称作合式公式
(1)单个命题变项是合式公式，并称为原子命题公式
(2)若A为合式公式，则¬A也为合式公式
(3)若A,B是合式公式，则 A∧B A∨B A→B A↔B 是合式公式
(4)有限次地应用(1)-(3)形成的符号串是合式公式
设A为任一命题公式
(1)若A在各种赋值下取值均为真，则称A为重言式或永真式
(2)若A在各种赋值下取值均为假，则称A为矛盾式或永假式
(3)若A不是矛盾式，则称A为可满式
好久不更新了，本来也随便写写。
并集：A与B的并集，记作：A∪B，它同时包含集合A或者集合B里面的元素：A∪B={x|xEA | xEB}
交集：A与B的交集，记作：A∩B，他包含A与B里面的公共元素：A∩B = {x| xEA & xEB}
如果两个集合不相交，他们的交集是空集。
A∪B = A + B - A∩B
补集：有两种：绝对补与相对补。
相对补：也叫做差集，记作A - B(意思是A集合里面减去包含在B里面的A元素)，即：A-B = A - A∩B
A - B = {x| xEA & x !E B}
绝对补：全集是E，有一个集合是A，那么A的补集是：A。A = E-A
所以有性质：(A) = A E = 空集 ~空集 = E A∩A = 空集 A∪~A = E
~(A ∩ B) = ~A ∪ ~B ~（A ∪ B）= ~A ∩ ~B
对称差：A与B对称差包括属于A的部分加上属于B的部分减去属于A与B的公共部分。
我们记作A@B
A@B = (A-B) ∪ (B-A) == A + B - A∩B
所以我们可以得到以下公式：A@B=B@A A@K=A A@A=K A@B=(A∩B)∪(B∩A) (A@B)@C=A@(B@C)
一、 真子集
真子集 :
描述 : A , B A , BA,B 两个集合 , 如果 A AA 集合 是 B BB 集合的子集 , 并且 A ≠ B A \not= BA
=B , 则称 A AA 是 B BB 的真子集 , B BB 真包含 A AA ;
记作 : A ⊂ B A \subset BA⊂B
符号化表示 : A ⊂ B A \subset BA⊂B ⇔ \Leftrightarrow⇔ A ⊆ B ∧ A ≠ B A \subseteq B \land A \not= BA⊆B∧A
=B
非真子集 :
描述 : A AA 集合 不是 B BB 集合的真子集 ;
记作 : A ⊄ B A \not\subset BA
⊂B
符号化表示 : A ⊄ B A \not\subset BA
⊂B ⇔ \Leftrightarrow⇔ ∃ x ( x ∈ A ∧ x ∉ B ) ∧ A ≠ B \exist x ( x \in A \land x \not\in B ) \land A \not= B∃x(x∈A∧x
∈B)∧A
=B
( 存在元素 x xx 是集合 A AA 的元素 , 不是集合 B BB 的元素 , 并且 A , B A , BA,B 不相等 , 则 A AA 不是 B BB 的真子集 )
真包含关系 性质 :
反自反性 : A ⊄ A A \not\subset AA
⊂A
反对称性 : 如果 A ⊂ B A \subset BA⊂B , 那么 B ⊄ A B \not\subset AB
⊂A
传递性 : 如果 A ⊂ B A \subset BA⊂B , 并且 B ⊂ C B \subset CB⊂C , 那么 A ⊂ C A \subset CA⊂C
二、 空集
空集描述 : 没有任何元素的集合 , 称为空集合 , 简称为 空集 ;
记作 : ∅ \varnothing∅
空集示例 : A = { x ∣ x 2 + 1 = 0 ∧ x ∈ R } A = { x | x^2 + 1 = 0 \land x \in R }A={x∣x
2
+1=0∧x∈R}
R RR 是实数集合 , 上述 x xx 明显无解 , 集合也为空集 ;
空集定理 : 空集是一切集合的子集 ;
空集推论 : 空集是唯一的 ;
三、 全集
全集 : 限定所讨论的集合 , 都是某个集合的子集 , 则称该集合为全集 , 记作 E EE ;
全集不唯一 : 全集只是相对于讨论问题的范畴 , 不唯一 , 不能讨论范畴之外的情况 ;
全集示例 : 讨论 [0, 1] 区间上的实数性质 , 取全集为 [0, 1] 上的所有实数 ;
( 讨论其它区间的数 , 也可以取其它的区间作为全集 )
四、 幂集
幂集描述 : A AA 是一个集合 , A AA 集合的全体子集组成的集合 称为 A AA 的幂集 ;
记作 : P ( A ) P(A)P(A)
符号化表述 : P ( A ) = { x ∣ x ⊆ A } P(A) = { x | x \subseteq A }P(A)={x∣x⊆A}
五、 集合元素个数
集合元素个数 :
0 00 元集 : ∅ \varnothing∅
1 11 元集 : 含有 1 11 个元素的集合 , 又称为 单元集 ;
2 22 元集 : 含有 2 22 个元素的集合 ;
n nn 元集 : 含有 n nn 个元素的集合 ; ( n ≥ 1 n \geq 1n≥1 )
有穷集 : ∣ A ∣ |A|∣A∣ 表示集合 A AA 中的元素个数 , 如果 A AA 集合中的元素个数是 有限数 时 , 那么称该 A AA 集合为有穷集 , 或 有限集 ;
幂集个数定理 : 集合 A AA 中的 元素个数 ∣ A ∣ = n |A| = n∣A∣=n , 则 A AA 的 幂集个数 ∣ P ( A ) ∣ = 2 n |P(A)| = 2^n∣P(A)∣=2 n
六、 求幂集步骤
求幂集步骤 : 求 集合 A AA 的幂集 , 需要按照顺序求 A AA 集合中 由低到高元的所有子集 , 再将这些子集组成集合 ;
低到高元的所有子集 : 0 00 元集 , 1 11 元集 , 2 22 元集 , ⋯ \cdots⋯ , n nn 元集 ;
集合 A = { a , b , c } A = { a, b , c }A={a,b,c}
0 00 元集 : ∅ \varnothing∅
1 11 元集 : { a } { a }{a} , { b } { b }{b} , { c } { c }{c}
2 22 元集 : { a , b } { a, b }{a,b} , { a , c } { a, c }{a,c} , { b , c } { b, c }{b,c}
3 33 元集 : { a , b , c } { a, b, c }{a,b,c}
集合 A AA 的幂集是 :
P ( A ) = { ∅ , { a } , { b } , { c } , { a , b } , { a , c } , { b , c } , { a , b , c } } P(A) = { \varnothing , { a } , { b } , { c } , { a, b } , { a, c } , { b, c } , { a, b, c } }P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}