离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。联接词：∧、∨、→、、↔¬。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“¬p→q”。会考察条件语句翻译成汉语。构造真值表pqp∧qp∨qp→qpq↔p⊙q¬pTTTTTTFFTFFTFFTFFTFTTFTTFFFFTTFT1.2语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。证逻辑等价是通过p推导出q，证永真式是通过p推导出T。逻辑等价式p∧T⇔pp∨F⇔p恒等律p∧F⇔Fp∨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)⇔pP∧(p∨q)⇔p吸收律p∧¬p⇔Fp∨¬p⇔T否定律条件命题等价式p→q⇔¬p∨qp→q⇔¬q→¬pp∨q⇔¬p→qp∧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双条件命题等价式pq↔⇔(p→q)∧(q→p)pq↔⇔¬p¬q↔pq↔⇔(p∧q)∨(¬p∧¬q)¬(pq)↔⇔p¬q↔1.4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如∀x>0P(x)。当论域中的元素可以一一列举，那么∀xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，∃xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如∀x（P(x)∧Q(x))和(∀xP(x))∧(∀xQ(x))。量词表达式的否定：¬∀xP(x)⇔∃x¬P(x)，¬∃xP(x)⇔∀x¬P(x)。1.5量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。pp→q(p∧(p→q))→q假言推理qp→qq→r((p→q)∧(q→r))→(p→r)假言三段论p→r¬qp→q(¬q∧(p→q))→¬p取拒式¬pp∨q¬p((p∨q)∧¬p)→q析取三段论qpp→(p∨q)附加律p∨qp∧q(p∧q)→p化简律ppq（p∧q）→（p∧q）合取律p∧qp∨q¬p∨r(p∨q)∧(¬p∨r)→(q∨r)消解律q∨r量化推理规则∀xP(x)全称实例P(c)P(c)，任意c全称引入∀P(x)∃xP(x)存在实例P(c)，对某个cP(c)，对某个c存在引入∃xP(x)命题和量化命题的组合使用。二、集合、函数、序列、与矩阵2.1集合∈说的是元素与集合的关系，说的是集合与集合的关系。常见数集有⊆N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。A和B相等当仅当∀x(x∈A↔x∈B)；A是B的子集当仅当∀x(x∈A→x∈B)；A是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(xA∉∧x∈B)。幂集：集合元素的所有可能组合，肯定有何它自身。如的幂集就是∅∅{}∅，而{}∅的幂集是{∅，{}}∅。笛卡尔积：A×B，结果是序偶，其中的一个子集叫一个关系。带量词和集合符号如∀x∈R（x2>0）是真的，则所有真值构成真值集。集合恒等式名称(A∪B)'=A'∩B'(A∩B)'=A'∪B'德摩根律A∪(A∩B)=AA∩(A∪B)=A吸收律2.3函数考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。一对一或者单射：B可能有多余的元素，但不重复指向。映上或者满射：B中没有多余的元素，但可能重复指向。一一对应或者双射：符合上述两种情况的函数关系。反函数：如果是一一对应的就有反函数，否则没有。合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。2.4序列无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集...
