离散数学部分概念和公式总结(考试专用)VIP免费

命题：称能判断真假的陈述句为命题。命题公式：若在复合命题中，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。约束变元和自由变元：在合式公式x A 和 x A 中，称 x 为指导变项，称 A 为相应量词的辖域，x 称为约束变元，x 的出现称为约束出现，A 中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设 A，B 是一阶逻辑中任意的两公式，若 A↔B 为逻辑有效式，则称 A 与 B 是等值的，记作 A<=>B，称 A<=>B 为等值式。前束范式：设 A 为一谓词公式，若 A 具有如下形式 Q1x1Q2x2Qk…xkB，称 A 为前束范式。集合的基本运算：并、 交、差、相对补和对称差运算。笛卡尔积：设 A 和 B 为集合，用 A 中元素为第一元素，用 B 中元素为第二元素构成有序对组成的集合称为 A 和 B 的笛卡尔积，记为 A×B。二元关系：如果一个集合 R 为空集或者它的元素都是有序对，则称集合 R 是一个二元关系。特殊关系：（1）、空关系：Φ （2）全域关系：EA={ | x∈A ∧ y∈A }= A×A（3） 恒等关系：IA={ | x∈A}（4） 小于等于关系：LA={| x, y∈A∧x≤y∈A },A  R（5） 整除关系： R ={| x，y∈ψ ∧ x  y} ,ψ 是集合族二元关系的运算：设 R 是二元关系，（...