离散数学(对偶和范式).ppt

文档介绍：该【离散数学(对偶和范式) 】是由【读书百遍】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【离散数学(对偶和范式) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
对偶与范式
对偶式与对偶原理
析取范式与合取范式
主析取范式与主合取范式
2
对偶式和对偶原理
定义 在仅具有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中具有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.
从定义不难看出，(A*)* 还原成A
显然，A也是A*的对偶式。可见A与A*互为对偶式。
3
对偶式和对偶原理
定理 设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)
(1)表明，公式A的否认等价于其命题变元否认的对偶式； (2)表明，命题变元否认的公式等价于对偶式之否认。
4
对偶式和对偶原理
定理（对偶原理）设A，B为两个命题公式，
若A  B，则A*  B*.
有了等值式、代入规则、替代规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为以便。
5
判定问题
真值表
等值演算
范式
6
析取范式与合取范式
文字:命题变项及其否认的总称
如 p, q
简单析取式:有限个文字构成的析取式
如 p, q, pq, pqr, …
简单合取式:有限个文字构成的合取式
如 p, q, pq, pqr, …
注意：一种命题变元或其否认既可以是简单合取式，也可是简单析取式，如p，q等。
7
析取范式与合取范式
定理： 简单合取式为永假式的充要条件是：它同步具有某个命题变元及其否认。
定理： 简单析取式为永真式的充要条件是：它同步具有某个命题变元及其否认。
8
析取范式与合取范式
简单析取式:有限个文字构成的析取式
如 p, q, pq, pqr, …
简单合取式:有限个文字构成的合取式
如 p, q, pq, pqr, …
析取范式:由有限个简单合取式构成的析取式
A1A2Ar, 其中A1,A2,,Ar是简单合取式
合取范式:由有限个简单析取式构成的合取式
A1A2Ar , 其中A1,A2,,Ar是简单析取式
9
析取范式与合取范式(续)
范式:析取范式与合取范式的总称 
公式A的析取范式: 与A等值的析取范式
公式A的合取范式: 与A等值的合取范式
阐明：
单个文字既是简单析取式，又是简单合取式
形如 pqr, pqr 的公式既是析取范式，
又是合取范式 (为何?)
10
命题公式的范式
定理 任何命题公式都存在着与之等值的析取范式
与合取范式.
求公式A的范式的环节：
(1) 消去A中的, （若存在）（消去公式中除、和以外公式中出现的所有联结词）
(2) 否认联结词的内移或消去（使用(P)P和德·摩根律）
(3) 使用分派律
对分派（析取范式）
对分派（合取范式）
公式的范式存在，但不惟一，这是它的局限性