math-chap1-1离散数学命题逻辑.ppt

庄伯金 bjzhuang@ * 基本等值规律(4) 蕴涵等值式 A→B??A∨B 等价等值式 A?B?(A→B)∧(B→A)? (?A∨B)∧(?B∨A) 假言易位 A→B??B→?A 等价否定等值式 A?B??A??B 归谬论 (A→B)∧(A→?B)??A 庄伯金 bjzhuang@ * 置换规则 设Φ(A)为含公式A的命题公式，Φ(B)为用公式B置换了A的命题公式，若A?B，则Φ(A)?Φ(B)。 利用等值规律及置换规则可以进行等值演算。 例 (p→q)→(?q→?p) ?(q→p)∧p (?p→q)→(q→?p) (p∨q) →r ?(p→(p∨q))∧r 庄伯金 bjzhuang@ * 联结词的完备集 问题：含n个命题变项的命题公式其真值表的可能性有多少种？ n元真值函数：F：{0,1}n→{0,1}为n元真值函数。 联结词完备集：设S是一个联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。 {?, ∧, ∨} {?, ∧} {?, ∨} {?, →} 庄伯金 bjzhuang@ * 对偶 对偶的定义：在仅含有?, ∧, ∨的命题公式A中，将∧换成∨， ∨换成∧，若A中含0或1，将0换成1，1换成0，所得的命题公式称为A的对偶式，记为A*。 定理：设A和A*互为对偶式， p1, p2, …, pn是出现在A和A*中的全部命题变项，若将A和A*写成n元函数形式，则： (1)?A(p1, p2, …, pn)?A*(?p1,?p2, …,?pn) (2) A(?p1,?p2, …,?pn)??A*(p1, p2, …, pn) 对偶原理：设A、B为两命题公式，若A?B，则A*?B*。 庄伯金 bjzhuang@ * 范式的概念 命题公式的规范表示方法 析取范式 合取范式 文字：命题变项及其否定式统称文字 简单析取式 仅有有限个文字构成的析取式 简单合取式 仅有有限个文字构成的合取式 定理： 一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式 庄伯金 bjzhuang@ * 析取范式 定义 由有限个简单合取式构成的析取式 例 p∨q (?p∧q)∨r 析取范式性质 析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式 庄伯金 bjzhuang@ * 合取范式 定义: 由有限个简单析取式构成的合取式 例 p∧q (p∨?q)∧r 合取范式性质 合取范式是重言式，当且仅当它的每个简单析取式是重言式 庄伯金 bjzhuang@ * 范式存在定理 定理：任一命题公式都存在与之等值的析取范式（合取范式）。 求范式的步骤 利用蕴涵等值式和等价等值式消去联结词→ 、?。 用双重否定律消去否定联结词，利用德.摩根律将否定联结词内移。 利用分配律求析取范式或合取范式。 例： (p→q)?r 范式的求解 例： (p→q)?r 庄伯金 bjzhuang@ * 庄伯金 bjzhuang@ * 极小项与极大项 极小项的定义 在含n个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 极大项的定义 在含n个命题变项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 n个命题变项共可形成2n个极小项和2n个极大项。 庄伯金 bjzhuang@ * 极小项的成真赋值 每个极小项仅有一个成真赋值 每个极小项的成真赋值均不相同 可以利用不同的成真赋值区别每个极小项，给予标记 二元极小项 取值 成真赋值 简记名称 ?p∧?q 1 00 m0 ?p∧q 1 01 m1 p∧?q 1 10 m2 p∧q 1 11 m3 庄伯金 bjzhuang@ * 极大项的成假赋值 每个极大项仅有一个成假赋值 每个极大项的成假赋值均不相同 可以利用不同的成假赋值区别每个极大项，给予标记 二元极大项 取值 成假赋值 简记名称 p∨q 0 00 M0 p∨?q 0 01 M1 ?p∨q 0 10 M2 ?p∨?q 0 11 M3 庄伯金 bjzhuang@ * 主析取范式与主合取范式 主析取范式的定义 若A的命题公式由若干个极小项进行析取构成，则称该析取范式为A的主析取范式 从主析取范式中很容易得到成真赋值 主合取范式的定义 若A的命题公式由若干个极大项进行合取构成，则称该合取范式为A的主合取范式 从主合取范式中很容易得到成假赋值 定理：任何命题公式都存在与之等值的主析取（合取）范式，且唯一。 庄伯金 bjzhuang@ * 主析取范式的求解方法(1) 用等值演算求得析取范式 依次扫描析取范式中的每个简单合取式B 若B为极小