离散数学知识点整理.doc

离散数学

逻辑和证明

1.1命题逻辑

命题：是一个可以判断真假的陈述句。

联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。

构造真值表

p

q

p∧q

p∨q

p→q

p?q

p⊙q

?p

T

T

T

T

T

T

F

F

T

F

F

T

F

F

T

F

F

T

F

T

T

F

T

T

F

F

F

F

T

T

F

T

1.2语句翻译

系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式

逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过p推导出q，证永真式是通过p推导出T。

逻辑等价式

p∧T?p

p∨F?p

恒等律

p∧F?F

p∨T?T

支配律

p∧p?p

幂等律

?(?P)?p

双否律

p∧q?q∧p

交换律

(p∧q)∧r?p∧(q∧r)

结合律

p∨(q∧r)?(p∨q)∧(p∨r)

p∧(q∨r)?(p∧q)∨(p∧r)

分配律

?(p∧q)??p∨?q

?(p∨q)??p∧?q

德摩根律

p∨(p∧q)?p

P∧(p∨q)?p

吸收律

p∧?p?F

p∨?p?T

否定律

条件命题等价式

p→q??p∨q

p→q??q→?p

p∨q??p→q

p∧q??(p→?q)

?(p→q)?p∧?q

(p→q)∧(p→r)?p→(q∧r)

(p→r)∧(q→r)?(p∨q)→r

(p→q)∨(p→r)?p→(q∨r)

(p→r)∨(q→r)?(p∧q)→r

双条件命题等价式

p?q?(p→q)∧(q→p)

p?q??p??q

p?q?(p∧q)∨(?p∧?q)

?(p?q)?p??q

1.4量词

谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x0P(x)。

当论域中的元素可以一一列举，则?(x)就等价于P(x1)∧P(x2)...∧P()。同理，?(x)就等价于P(x1)∨P(x2)...∨P()。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?(x))∧(?(x))。

量词表达式的否定：??(x)??x?P(x)，??(x)??x?P(x)。

1.5量词嵌套

我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则

一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。

推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。

p

p→q

(p∧(p→q))→q

假言推理

q

p→q

q→r

((p→q)∧(q→r))→(p→r)

假言三段论

p→r

?q

p→q

(?q∧(p→q))→?p

取拒式

?p

p∨q

?p

((p∨q)∧?p)→q

析取三段论

q

p

p→(p∨q)

附加律

p∨q

p∧q

(p∧q)→p

化简律

p

p

q

（p∧q）→（p∧q）

合取律

p∧q

p∨q

?p∨r

(p∨q)∧(?p∨r)→(q∨r)

消解律

q∨r

量化推理规则

?(x)

全称实例

P(c)

P(c)，任意c

全称引入

?P(x)

?(x)

存在实例

P(c)，对某个c

P(c)，对某个c

存在引入

?(x)

命题和量化命题的组合使用。

集合、函数、序列、和矩阵

2.1集合

∈说的是元素和集合的关系，?说的是集合和集合的关系。常见数集有{0,1,2,3...}，Z整数集，正整数集，Q有理数集，R实数集，正实数集，C复数集。

A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；

A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。

幂集：集合元素的所有可能组合，一定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。

笛卡尔积：A×B，结果是序偶，其中的一个子集叫一个关系。

带量词和集合符号如?x∈R（x20）是真的，则所有真值构成真值集。

集合恒等式

名称

(A∪B)∩B?

(A∩B)∪B

德摩根律

A∪(A∩B)

A∩(A∪B)

吸收律

2.3函数

考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。

一对一或者单射：B可能有多余的元素，但不