离散数学学习笔记1

小杨今天翻开尘封的离散数学书，感觉从来没有学过这门课一样，那好吧，虽然大一下学期学过，但是既然从来没有学过，就重头学习吧。

看了离散数学这本书的目录（清华大学出版 耿素云等等作者的），里面有树和图（图的概念貌似很多），看来上辈子和计算机是一家呢。

整理了一下第一章部分知识点，分享给大家。晚安。

数理逻辑：逻辑演算，证明论，公理集合论，递归论，模型论（看来还是一个很庞大的体系啊，离散数学第一章只涉及逻辑演算这点）

判断真假的陈述句——命题——具有唯一真值的陈述句

简单命题：不能再分解的命题

真值可以变化的简单的衬塑——命题变项/命题变远——不是命题

合取式 p∧q (和)

析取式 pvq (或)

蕴含式 如果p则q，p→q

p→q为假。当且仅当p为真且q为假

等价式 p当且仅当q p←→q

p←→q 为真，当且仅当p,q真值相同（可同真或同假）

若A（命题公式）在各种赋值取值均为真，则称A为重言式或永真式

若A（命题公式）在各种赋值取值均为假，则称A为矛盾式或永假式

若A（命题公式）至少你在一组赋值是成真赋值，则A是可满足式

n个命题变项只能生成2^(2^n)个真值不同的命题公式

真值表适合命题变量少的演算。

定义1.10.设A，B为两个命题公式，若等价式A←→B是重言式，则称A与B是等值的，记着≤=≥

例题1.4 将下列命题符号化(典型题)

（1）只有不下雨，我才骑自行车上班 等价于 如果下雨，我就不骑自行车上班 q→ ┒p

（2）除非天下大雨，否则他不乘公共汽车上班

q → p

例题1.6 将下列命题符号化(典型题)

（1）小王现在在宿舍或在图书馆里

p 小王在宿舍

q 小王在图书馆

p v q(小王在宿舍或在图书馆)

（2）如果我去上街了，我就去书店看看，除非我很累

p 我去上街

q 我去书店

r 我很累

┒r→(p→q) 等价于(┒r ∧ p)→ q (如果我不累，并且我上街，我就去书店看看)

注：“相容或”与"排斥或"区别

命题公式是由命题常项，命题变项，联接词，括号等组成的符号串

含n（n>=1）个命题变项的命题公式，共有2^n组赋值， 例 n=2时，11 10 01 00 2^2

24个重要的等值式

1. A等价于┒┒A ——双重否定律

2. A等价于AVA

3. A等价于A∧A ——等幂律

4. AVB等价于BVA

5. A∧B等价于B∧A ——交换律

6. （A V B）V C等价于AV（B V C）

7. （A∧B）∧ C 等价于A∧（B∧C） ——结合律

8. A V （B∧C）等价于（AVB）∧（AV C）

9. A∧（B V C）等价于（A∧B）V（A∧C） ——分配律

10.┒（AVB）等价于┒A∧B

11.┒（A∧B）等价于┒A V┒B ——德 摩根律

12. AV（A∧B）等价于A

13. A∧（A VB）等价于A ——吸收律

14. A V 1 等价于1

15. A∧0等价于0 ——零律

16. A V 0等价于A

17. A∧1 等价于A ——同一律

18. A V┒A等价于1 ——排中律

19. A∧┒A等价于0 ——矛盾律

20. A→B等价于┒A V B ——蕴涵等值式

21. A←→B等价于（A→B）∧（B→A） ——等价等值式

22. Ａ→Ｂ等价于┒Ｂ→┒Ａ ——假言易位

23.┒A←→┒B等价于┒B←→┒A ——等价否定等值式

24. （A→B）∧ （A→┒B）等价于┒A ——归谬论