离散数学范式.ppt

§1.5范式 从前面的讨论可知,存在大量互不相同的命题公式，实 际上互为等价,因此,有必要引入命题公式的标准形式, 使得相互等价的命题公式具有相同的标准形式。这无 疑对判别两个命题公式是否等价以及判定命题公式的 类型是一种好方法,同时对命题公式的简化和推证也是 十分有益的. 命题公式的标准形式： （主）析取范式 （主）合取范式 对偶式和对偶原理 对偶式：将只含?∨∧（如有→ ?，则应该化去）联结词公式A中的联结词 ∨-------∧, ∧-------∨, 0 -------1, 1 ------- 0 得到的新公式A*称为A的对偶式。 例如：A = ?(p ∧ ?(? p∧q) ∨T) 1. 对偶式 2. 引理:?A(p1,p2,…,pn) ?A* (? p1,? p2,…,? pn) ?A *(p1,p2,…,pn) ?A (? p1,? p2,…,? pn) 证明: 因为 ┐(P?Q)?(┐P?┐Q) ┐(P?Q)?┐P?┐Q 所以┐A(P1 , P2 ,…,Pn )?A*（┐P1 , ┐P2 ,…, ┐Pn） 同理 ┐A*(P1 , P2 ,…,Pn )?A（┐P1 , ┐P2 ,…, ┐Pn） 3. 对偶原理 若A?B，则A * ? B * 证：设P1 , P2 ,…,Pn是出现于A和B中的所有原子变元. 因为 A(P1 , P2 ,…,Pn)?B(P1 , P2 ,…,Pn) 则 A(P1 , P2 ,…,Pn)?B(P1 , P2 ,…,Pn)永真. 故 A(┐P1 , ┐P2 ,…, ┐Pn)?B(┐P1 , ┐P2 ,…, ┐Pn) 永真. 由定理1.7.1得 ┐A*(P1 , P2 ,…,Pn)?┐B*(P1 , P2 ,…,Pn ) 因此 A*?B* . 显然：如果A是永真式，则A *是永假式。 1.简单合取式（基本积）: ∧ ∧… ∧ ,（ 为Pi或?Pi） 简单析取式（基本和）： ∨ ∨… ∨ 例如：求A=p∧(q→r)→s的析(合)取范式 解:A? p∧(?q∨r)→s 化掉→? ?? (p∧(?q∨r)) ∨ s 化掉→? ? ? p∨ ? (?q∨r)∨ s 否定深入 ? ? p∨ (q∧? r) ∨ s 否定深入 析取范式 ? ? p∨ s∨ (q∧? r) ? (? p∨ s∨ q)∧( ? p∨ s∨ ? r) 分配律 合取范式 1. 极小项： ∧ ∧… ∧ ,（ 为Pi或?Pi）中， 1) n个变元全部出现； 2) n个变元的位置有序； 2) Pi、?Pi不同时出现； 极大项： ∨ ∨… ∨ 例如,三个命题变元P,Q,R,极小项共有8个: 小项 编码 真值指派 小项的真值 ┐P?┐Q?┐R m000/m0 000 1 ┐P?┐Q?R m001/m1 001 1 ┐P?Q?┐R m010/m2 010 1 ┐P?Q?R m011/m3 011 1 P?┐Q?┐R m100/m4 100 1 P?┐Q?R m101/m5 101 1 P?Q?┐R m110/m6 110 1 P?Q?R m111/m7 111 1 n个命题变元最多可产生多少个极小（大）项？ 三个命题变元P,Q,R,极大项共有8个: 大项 编码 真值指派 大项的真值 P?Q?R M000/M0 000 0 P?Q?┐R M001/M1 001 0 P?┐Q?R M010/M2 010 0 P?┐Q?┐R M011/M3 011 0 ┐P?Q?R