离散数学知识点整理

离散数学一、逻辑和证明1.1 命题逻辑命题：是一个可以判断真假的陈述句。联接词：!\、V、一、f-。记住“P 仅当 q”意思是“如果 P，则 q”,即P-。记住“口除非卩”意思是“-P-q”。会考察条件语句翻译成汉语。构造真值表pqpAqpVqpfqpfpOq-pTTTTTTFFTFFTFFTFFTFTTFTTFFFFTTFT1.2 语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若 pq 无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。1.3 命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。证逻辑等价是通过 P 推导出 q,证永真式是通过 p 推导出 T。逻辑等价式pAToppVFop恒等律pAFoFpVToT支配律pApop幂等律-(-P)op双否律pAqoqAp交换律(pAq)AropA(qAr)结合律pV(qAr)o(pVq)A(pVr)pA(qVr)o(pAq)V(pAr)分配律-(pAq)o-pV-q-(pVq)o-pA-q德摩根律pV(pAq)opPA(pVq)op吸收律pA-poFpV-poT否定律条件命题等价式pfqo-pVqpfqo-qf-ppVqo-pfqpAqo-(pf-q)-(pfq)opA-q(pfq)A(pfr)opf(qAr)(p—r)人(q—r)o(pVq)fr(pfq)V(pfr)op—(qVr)(p—r)V(q—r)o(pAq)—r 双条件命题等价式•p^qo(p—q)A(q—p)p^qo-prqp^qo(pAq)V(-pA-q)-(p^q)oprq1.4 量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如 Dx>0P(x)。当论域中的元素可以一一列举，那么 VxP(x)就等价于P(xl)AP(x2)...AP(xn)。同理，3xP(x)就等价于 P(xl)VP(x2)...VP(xn)。两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如 Vx(P(x)AQ(x))和(VxP(x))A(VxQ(x))。量词表达式的否定：-VxP(x)o3x-P(x)，-3xP(x)oVx-P(x)。1.5 量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。1.6 推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。pp—q(pA(p—q))—q假言推理qp—qq—r((p—q)A(q—r))—(p—r)假言三段论p—r-qp—q(-qA(p—q))—-p取拒式-ppVq-p((pVq)A-p)—q析取三段论qpp—(pVq)附加律pVqpAq(pAq)—p化简律ppq(pAq)—(pAq)合取律pAqpVq-pVr(pVq)A(-pVr)—(qVr)消...