第2章 命题逻辑3.pptVIP

1.5 析取范式 与合取范式 定义1.5.1 将命题变元及其否定统称为文字。 简单析取式（基本和） 仅由有限个文字构成的析取式。 简单合取式（基本积） 仅由有限个文字构成的合取式。 例如， p、 q既是一个文字的简单析取式， 又是一个文字的简单合取式。 p∨ q、 p∨r均是有两个文字的简单析取式。 p∧q∧r、 p∧q∧ r均是有三个文字的简单合取式。 性质 (1) 一个文字既是简单析取式又是简单合取式。 (2) 一个简单析取式是重言式， 当且仅当它同时含有一个命题变元及其否定。 (3) 一个简单合取式是矛盾式， 当且仅当它同时含有一个命题变元及其否定。 例如， p∨q∨ p是重言式， p∧ q∧ q是矛盾式。 定义 1.5.2 析取范式 由有限个简单合取式构成的析取式。 合取范式 由有限个简单析取式构成的合取式。 【例1.5.1】 判断下列各式是析取范式还是合取范式。 （1） p （2） p∨ q （3） p∧q∧r （4） p∨（q∧ r）∨ r （5） p∧（p∨q）∧（p∨ q∨r）∧q 性质： (1) 一个文字既是一析取范式又是一合取范式。 (2) 一个析取范式为矛盾式， 当且仅当它的每个简单合取式是矛盾式。 (3) 一个合取范式为重言式， 当且仅当它的每个简单析取式是重言式。 例如： A=（ p∧p∧q）∨（p∧q∧ q）是矛盾式。 A=（ p∨p∨q）∧（p∨q∨ q）∧（q∨ r∨r） 是重言式。 定理1.5.1 任一命题公式都存在着与之等值的析取范式， 任一命题公式都存在着与之等值的合取范式。 证明 对于任一公式， 可用下面的方法构造出与其等值的范式： （1） 利用等值式 A B (A→B）∧（B→A） A→B A∨B 使公式中仅含联结词 、 ∧、 ∨。 （2） 利用德·摩根律和双重否定律  （A∨B） A∧ B （A∧B） A∨ B A A 将否定符移至命题变元符前，并去掉多余的否定符 【例1.5.2】 求公式 （（p∨q）→r）p的析取范式。 解 定义1.5.3 对于公式A： 极小项 包含A中所有命题变元或其否定一次且仅一次的简单合取式； 极大项 包含A中所有命题变元或其否定一次且仅一次的简单析取式。 注 极小项或极大项中各文字要求按角标顺序或字典顺序排列。 由真值表可看出： 对于p、 q的任一组赋值， 有且仅有一个极小项的真值为1， 即极小项之间是不等值的， 4个真值赋值与4个极小项值之间有一一对应关系。 我们用mi表示在十进制为i的赋值下真值为1的极小项。 定义1.5.4 对于公式A： 主析取范式 与A等值的由极小项构成的析取范式； 主合取范式 与A等值的由极大项构成的合取范式。 【例1.5.5】 求公式 （（p∨q）→r）p的主析取范式。 解 由例1.5.4已求得公式的析取范式， 在此基础上求主析取范式。 即： 【例1.5.6】 求（p→（p∨r））∧（q p）的主析取范式。 解 定理1.5.2 任何命题公式的主析取范式存在且唯一。 【例1.5.7】 用真值表法求上例公式 （p→（p∨r））∧（q p）的主析取范式。 解 构造公式的真值表如表1.5.2所示。 结论（主析取范式的用途）： (1) 重言式的主析取范式包含公式的全部2n个极小项。 (2)（规定）矛盾式的主析取范式为0。 (3) 二等值的公式必有相同的主析取范式（不计极小项的顺序）。 (4) 不列真值表， 由主析取范式可得公式的成真、 成假赋值。 (5) 仅由真值表， 可得公式的表达式（主析取范式形式）。 (6) 解决应用问题。 前两