复习-第一章-离散数学.ppt

2X+30明年爸爸就五十岁了！2是偶数或是奇数。只有2+2=6,3才能被2整除。长方体的体积等于底面积乘高。我正在说谎。在命题逻辑中复合命题符号化的基本步骤如下：⑴分析出各简单命题，将它们符号化；⑵使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示．若给命题公式A中的命题变元指派的一组值使公式A的值为真，则称这组值为A的成真赋值；若给命题公式A中的命题变元指派的一组值使公式A的值为假，则称这组值为A的成假赋值.练习：使用真值表判断命题公式的类型((p→q)→p)?p(p∧?p)?q1.3等值演算定义1.10设A和B是两个命题公式，p1，p2，…pn是所有出现在两个命题公式中的命题变元，如果对于p1，p2，…pn的任意一组赋值，A和B的真值都相同，则称公式A和B等值的，记作A?B.若A是命题公式，则A?A.若A，B是命题公式，且A?B，则一定有B?A.若A，B，C是命题公式，且A?B，B?C，则A?C.例1.9验证下列等值式⑴p→(q→r)?(p∧q)→r(p∧q)→r??(p∧q)∨r蕴涵等值式?(?p∨?q)∨r德．摩根等值式??p∨(?q∨r)结合律??p∨(q→r)蕴涵等值式?p→(q→r)蕴涵等值式例1.25：判断下列命题公式的类型⑴(p∧q)→(p∨q)⑶?(p→q)∧q⑷(p∧?p)?q⑸p→(p∨q)⑹(p∧?p)→((q∧?q)∧r)⑺((p→q)→p)?p⑻(p∧q)∨(p∧?q)⑼?(p∨q∨r)?(?p∧?q∧?r)?(p?q)?(p∨q)∧?(p∧q)证明:左边??(p?q)??((p→q)∧(q→p))(等价等值式)??(p→q)∨?(q→p)(德．摩根律)??(?p∨q)∨?(?q∨p)(蕴涵等值式)?(p∧?q)∨(q∧?p)(德．摩根律)右边?(p∨q)∧?(p∧q)?(p∨q)∧(?p∨?q)(德．摩根律)?(p∧?p)∨(p∧?q)∨(q∧?p)∨(q∧?p)(分配律)?(p∧?q)∨(q∧?p)(矛盾律)左边＝右边所以等值式成立1.4极小全功能集任何一个命题公式都可以由包含最小联结词组的命题公式等价代替，这个最小联结词组就称为极小全功能集．{?，∧｝、{?，∨｝、{↑｝、{↓｝是极小全功能集。对偶式的定义定义1.17在仅含有联结词?、∧和∨的命题公式A中，将∧换成∨，∨换成∧，若A中含有０或１，就将０换成１，１换成０，所得的命题公式称为A的对偶式，记作A*显然，A也是A*的对偶式，（A*）*＝A，可见对偶式是相互的。p∧q与p∨q，?(p∧q)与?(p∨q)?p∧(q∨r)与?p∨(q∧r)(p∨q)∨０与(p∧q)∧０１．简单合取式与简单析取式定义1.18在一公式中，仅由有限个命题变元及其否定构成的合取式，称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。在一公式中，仅由有限个命题变元及其否定构成的析取式，称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。常用A１，A2，…An表示n个简单析取式或n个简单合取式．例如，公式p，q，?p，?q，p?q，?p?q，p??q,?p??q和?p?q?p等都是简单合取式，而p，q，?p和?q为相应的简单合取式的合取项；公式p，q，?p，?q，p?q，?p?q，