离散数学部分概念和公式总结(考试专用).doc

离散数学部分概念和公式总结(考试专用).doc命题:称能判断真假的陈述句为命题。 命题公式:若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题

离散数学部分概念和公式总结(考试专用).doc 命题:称能判断真假的陈述句为命题。 命题公式:若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命 题变项，这样的复合命题形式称为命题公式。 命题的赋值:设A为一命题公式，p,p,…,p为出现在A中的所有命题变项。 给p,p,…,p指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A 的值为真，则称成真赋值。真值表:含n(n?1)个命题变项的命题公式，共有2^n 组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型:(1)若A在它的各种赋值下均取值为真，则称A为重言式或永 真式。 (2)若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 (3)若A至少存在一组赋值是成真赋值，则A是可满足式。主析取范式:设命 题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称 该析取范式为A的主析取范式。 主合取范式:设命题公式A中含n个命题变项，如果A得析取范式中的简单合 析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式:设A、B为两命题公式，若等价式A?B是重言式，则称A与B是 等值的，记作A<=>B。 约束变元和自由变元:在合式公式,xA和，xA中，称x为指导变项，称A为 相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自 由出现(自由变元)。一阶逻辑等值式:设A，B是一阶逻辑中任意的两公式，若 A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。