离散数学——范式.ppt

4.3 范式 １.简单合取式与简单析取式 定义4.3.1 命题变元及命题变元的否定称为文字；有限个文字的析取式称为一个子句；有限个文字的合取式称为短语。 例：P,Q,R,?P, ?Q, ?R为文字； P∨Q,?P∨Q,P∨?Q为子句； P∧Q,P∧Q∧R,?P∧?R为短语. 析取范式 合取范式 (1)仅由有限个短语(简单合取式)构成的析取式称为析取范式; 设A＝A1∨A2∨…∨An, Ai(i＝1,2,…,n)为简单合取式,则A是析取范式,例如：(?P∧Q)∨(?P∧Q∧R)∨P (2)仅由有限个子句(简单析取式)构成的合取式称为合取范式. 设A＝A1∧A2∧…∧An, Ai(i＝1,2,…,n)为简单析取式,则A是合取范式.例如：(?P∨R)∧P∧(P∨Q∨R) P∧?Q∧R既是合取范式也是析取范式. 定理4.3.1 对于任何一命题公式，都存在与其等价的析取范式和合取范式。 求范式算法： ① 使用命题定律，消去公式中除?、?和?以外的所有联结词; 通常用(A→B?┐A∨B,A?B?(A→B)∧(B→A)) ② 使用?(?P)?P 和德·摩根律，将公式中出现的联结词?都移到命题变元之前； ③ 利用结合律、分配律等将公式化成析取范式或合取范式。 例1.14 求下面命题公式的合取范式和析取范式. ((p∨q) ? r) ? p 解 (1)求合取范式 ((p∨q ? r) ? p ?(? (p∨q)∨r)? p (消去第一个→) ? ? (?(p∨q)∨r)∨p (消去第二个→) ?((p∨q)∧ ?r)∨p (?消去) ?(p∨q∨p)∧(?r∨p), (∨对∧分配律) ?(p∨q)∧(?r∨p) (2)求析取范式 用∧对∨的分配律就可得到析取范式, 接上面倒数第三步 ?((p∨q)∧?r)∨p ?(p∧?r)∨(q∧? r)∨p (∧对∨分配律) 最后结果为原公式的析取范式.利用交换律和吸收律得p∨(q∧?r),也是原公式的析取范式,由此可见,与命题公式等价的析取范式也是不唯一的. 公式的主范式 范式基本解决了公式的判定问题。但由于范式不具有唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。 １.主析取范式 (1) 极小项的概念和性质 定义4.3.3 (教材P100)在含有n个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为极小项。 例如，两个命题变元P和Q，其构成的极小项有P?Q，P??Q，?P?Q和?P??Q； 而三个命题变元P、Q和R，其构成的极小项有P?Q?R，P?Q??R，P??Q?R，P??Q??R，?P?Q?R ，?P?Q??R，?P??Q?R，?P??Q??R。 可以证明，n个命题变元共形成2n个极小项。 如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个极小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个极小项的真值表。 3个命题变项，8个极小项对应情况如下： ? p∧?q∧?r —— 000 —— 0, 记作m0； ? p∧?q∧r ——001 —— 1, 记作m1； ? p∧ q∧?r ——010 —— 2, 记作m2； ? p∧ q∧r ——011 —— 3, 记作m3； p∧?q∧?r ——100 —— 4, 记作m4； p∧ ?q∧ r ——101 —— 5, 记作m5； p∧ q∧?r ——110 —— 6, 记作m6； p∧ q∧r —— 111 —— 7, 记作m7. 一般情况下,n个命题变项共产生2n个极小项,分别记为m0,m1,...m2n-1. 主析取范式定义与存在定理 定义:在给定公式的析取范式中，若其简单合取式都是极小项，则称该范式为主析取范式。（教材P101定义4.3.4） 定理:任意公式G都存在唯一的与之等价的主析取范式。 （教材P101定理4.3.4） 求主析取范式的步骤 (1)求A的析取范式A′； (2)若A’的某简单合取式B中不含命题变项pi或其否定? pi,则将B展成如下形式： B ? B∧1 ? B∧(pi∨?pi) ?(B∧pi)