1.5 离散数学.ppt

对偶式和对偶原理定义在仅含有联结词?, ∧,∨的命题公式 A中,将∨换成∧, ∧换成∨,若 A中含有 0或1,就将 0换成 1,1换成 0,所得命题公式称为 A的对偶式,记为 A *. 从定义不难看出, (A *) *还原成 A 定理设A和A *互为对偶式, p 1,p 2,…,p n是出现在 A和 A *中的全部命题变项,将 A和A *写成 n元函数形式, 则 (1) ?A(p 1,p 2,…,p n ) ?A *(?p 1, ?p 2,…, ?p n) (2) A(?p 1, ?p 2,…, ?p n ) ??A *(p 1,p 2,…,p n ) 定理(对偶原理) 设A,B为两个命题公式, 若 A ? B,则A *? B *. 例求 p ↑q, p ↓q的对偶式。解:因 p ↑ q ??( p ∧q)则: p ↑q的对偶式为?( p ∨q),即 p ↓q 同理: p ↓q的对偶式为 p ↑q 定理 设A和A*互为对偶式, p 1 ,p 2 , ,…p n是出现在A和A*中的全部命题变项,则: (1)?A (p 1 , p 2 , …p n ) ?A* (?p 1 , ?p 2 , …?p n) (2) A ( ?p 1 , ?p 2 , …?p n ) ??A* (p 1 , p 2 , …p n) 证明:由 p ∧ q ??(? p ∨?q) p ∨ q ??(? p ∧?q) 则: ?A (p 1 , p 2 , …p n ) ?A* (?p 1 , ?p 2 , …?p n) 同理: A ( ?p 1 , ?p 2 , …?p n ) ??A* (p 1 , p 2 , …p n) 定理 设p 1,p 2 , ,…p n是出现在 A和B中的命题变项,若 A ?B,则A*?B*(对偶原理)。证明: 由: A ?B 则: A( p 1,…p n ) ? B( p 1,…p n ) 是永真式故: A( ?p 1,…?p n ) ? B( ?p 1,…?p n)也是永真式即: A( ?p 1,…?p n ) ? B( ?p 1,…?p n) 由定理 ?A* (p 1 , p 2 , …p n ) ??B* (p 1 , p 2 , …p n) 即: A*?B*析取范式与合取范式给定一个命题公式,判断它是永真式、永假式、还是可满足式,这类问题称为判定问题。前面学过的判定方法: 真值表法、等值演算法,但以上方法不适合很多情形,必须将命题公式化为规范的形式: 主析取范式和主合取范式。文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, ?q, p ?? q, p?q?r, …简单合取式:有限个文字构成的合取式如p, ?q, p ?? q, p?q?r, …析取范式:由有限个简单合取式组成的析取式 A 1?A 2 ??? A r, 其中 A 1,A 2,?,A r是简单合取式合取范式:由有限个简单析取式组成的合取式 A 1?A 2 ??? A r, 其中 A 1,A 2,?,A r是简单析取式? p ∨( p ∧q ) ∨( p ∧? q ∧r)为析取范式? p ∧( p ∨q ) ∧( p ∨? q ∨r)为合取范式范式:析取范式与合取范式的总称公式 A的析取范式: 与A等值的析取范式公式 A的合取范式: 与A等值的合取范式说明: 单个文字既是简单析取式,又是简单合取式 p ?? q?r, ?p?q ?? r既是析取范式,: (1) 消去 A中的?, ?(若存在) (2) 否定联结词?的内移或消去 (3) 使用分配律?对?分配(析取范式) ?对?分配(合取范式) 公式的范式存在,但不惟一例求下列公式的析取范式与合取范式( 1) A =(p ?? q) ?? r解(p ?? q) ?? r?(?p ?? q) ?? r(消去?) ??p ?? q ?? r(结合律) 这既是 A的析取范式(由 3个简单合取式组成的析取式),又是 A的合取范式(由一个简单析取式组成的合取式) ( 2) B =(p ?? q)?r解(p ?? q)? r ?(?p ?? q)?r(消去第一个?) ??(?p ?? q)?r(消去第二个?) ?(p?q)?r(否定号内移——德?摩根律) 这一步已为析取范式(两个简单合取式构成) 继续: (p?q)?r?(p?r)?(q?r ) (?对?分配律) 这一步得到合取范式(由两个简单析取式构成)