5360人阅读
主析取范式与主合取范式
定义&&& 设A为恰含命题变元p1,&,pn的公式。公式A'称为A的主析（合）取范式（majordisjunctive（conjunctive）normal form），如果A'是A的析（合）取范式，并且其每个合（析）取子句中p1,&,pn均恰出现一次。
据定义，例1.21中公式┐p&┐(p&q)的主析取范式是(p&q)&(p&┐q)，而其主合取范式则应是(p&q)&(p&┐q)。
&&& &例1 &求公式(p&q)&r的主析取范式及主合取范式。
&&& (p&q)&r
&&&& (p&q&(r&┐r))&((p&┐p)&(q&┐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)&(p&┐q&r)&(┐p&q&r)&(┐p&┐q&r)
&&& 此即所求的主析取范式。另外
(p&r)&(q&r)
(p&(q&┐q)&r)&((p&┐p)&q&r)
(p&q&r)&(p&┐q&r)&(p&q&r)&(┐p&q&r)
(p&q&r)&(p&┐q&r)&(┐p&q&r)
最后一式即为所求的主合取范式。
**** 我们总结一下利用等价推演求公式的主析（合）取范式的方法步骤：
第一步：求出该公式的析（合）取范式；
第二步：简化各子句.除去范式中所有恒假（真）的合（析）取子句，即化掉含有互补文字对的合（析）取子句；将合（析）取子句中同一命题变元的多个出现合并为一个；
第三步：对析（合）取范式中合（析）取子句不是每一变元都出现的，利用pp&tp&(q&┐q)或pp&fp& (q&┐q)把未出现的变元补进来，并用分配律将其展开，最后得到给定公式的主析（合）取范式。
现在我们要讨论指派与两种范式之间的联系。
很明白，要使主析取范式取值1，只要使其一个合取子句取值1，从而须使这一子句中的每个文字都取值1，即令正文字中命题变元取值1，而令负文字中命题变元取值0。换言之，由主析取范式的一个合取子句可确定一个弄真原公式的指派；反之，亦可由弄真原公式的一个指派确定其主析取范式中的一个合取子句。弄真公式的指派与主析取范式的合取子句是一一对应的。例如，例1.23中公式的主析取范式有五个合取子句，它们分别对应于5个弄真公式的指派：
&&&&&&& p&q&r&&&&&&&&&&&&&&& 1,1,1
&&&&&&&&&&& p&q&┐r&&&&&&&&&&&&& 1,1,0
&& &&&&&&&&&p&┐q&r&&&&&&&&&&&&& 1,0,1
&&&&&&&&&&& ┐p&q&r&&&&&&&&&&&&& 0,1,1
&&&&&&&&&&& ┐p&┐q&r&&&&&&&&&&& 0,0,1
&&& 类似地，要使主合取范式取值0，只要使其一个析取子句取值0，从而须使析取子句中的每一文字取值0，即令正文字中命题变元取值0，而令负文字中命题变元取值1。换言之，由主合取范式的一个析取子句可确定一个弄假原公式的指派；反之，亦可由弄假原公式的一个指派确定其主合取范式中的一个析取子句。弄假公式的指派与主合取范式的析取子句是一一对应的，只是对应方式刚好相反，正文字对应0，负文字都对应1。例如，例1.23中公式的三个析取子句，如下对应于三个弄假指派：
p&q&r&&&&&&&&&&&&&&& 0,0,0
&&&&&&&&&&& p&┐q&r&&&&&&&&&&&&& 0,1,0
&&&&&&&&&&& ┐p&q&r&&&&&&&&&&&&& 1,0,0
&&& 由以上分析，我们可以进一步得到下述结论：
&&& （1）每公式的主析取范式和主合取范式都是唯一确定的，因为任一公式的弄真指派及弄假指派是完全确定的。
&&& （2）永真式，例如p&┐p，没有主合取范式，因为它没有弄假指派。永真式只有主析取范式，它包含所有可能的合取子句（p&┐p的主析取范式为其自身），因为一切指派均弄真它。为讨论方便，约定永真式的主合取范式为t。
&&& （3）永假式，例如p&┐p，没有主析取范式，因为它没有弄真指派。永假式只有主合取范式，它包含所有可能的析取子句（p&┐p的主合取范式为自身），因为一切指派均弄假它。为讨论方便，约定永假式的主析取范式为f。
（4）n个命题变元的主析取范式及主合取范式都有 个，因为不同的合取子句及析取子句都是 个，而两种主范式都是从 个子句中取若干个（0,1,&, 个）子句组成的（取0个子句组成t或f）。我们知道 + + & + = 。从真值表的角度看也是如此。一张真值表（确定了弄真指派和弄假指派）恰对应一个主析（合）取范式。因此，n个变元的真值表有多少种，便相应地有多少n个变元的主析（合）取范式。事实上，n个变元的真值表必有 行，对应于 个可能的指派，而最后一列的每一行有0，1两个可能的值，因而这一列可能的取值状况有 种，从而生成 张不同的真值表。
（5）由于每一公式均有主析（合）取范式，因此，无限多的含n个变元的公式可以分作 （有限）个类，这一类公式都逻辑等价于它们共同的主析（合）取范式。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：97425次
积分：1275
积分：1275
排名：第16981名
原创：11篇
转载：79篇
评论：27条
(1)(8)(12)(28)(9)(18)(1)(9)(4)0m∨1m∨3m∨5m∨7m.这与用等值演算法所求结果完全一致的. 命题公式的主..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
主析取范式与主合取范式
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口提问回答都赚钱
> 问题详情
求(P→(Q∧R))∧(￢P→(￢Q∧￢R))的主析取及主合取范式．
悬赏：0&&答案豆&&&&提问人：匿名网友&&&&提问收益：0.00答案豆&&&&&&
求(P→(Q∧R))∧(￢P→(￢Q∧￢R))的主析取及主合取范式．
发布时间：&&截止时间：
网友回答&(共0条)
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&2.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&5.00元收益
你可能喜欢的
[] [] [] [] [] [] [] [] [] [] [] []
请先输入下方的验证码查看最佳答案您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
2014年电大离散数学期末考试试题(有几套带答案).doc14页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：75 &&
你可能关注的文档：
··········
··········
离散数学试题A卷及答案）
一、证明题（10分）
1P∧Q∧R∨Q∧R∨P∧RR
　　证明: 左端P∧Q∧R∨Q∨P∧RP∧Q∧R∨Q∨P∧R
　　　　　　P∨Q∧R∨Q∨P∧RP∨Q∨Q∨P∧R
　　　　　　P∨Q∨P∨Q∧RT∧R置换R
2xAxBx xAxxBx
　　证明 ：xAxBxxAx∨BxxAx∨xBxxAx∨xBxxAxxBx
二、求命题公式P∨Q∧RP∧Q∧R的主析取范式和主合取范式（10分）
　　证明：P∨Q∧RP∧Q∧RP∨Q∧R∨P∧Q∧R
　　　　　　（P∧Q∨R）∨P∧Q∧R
　　　　　　P∧Q∨P∧R∨P∧Q∧R
　　　　　　P∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧R
　　　　　　m0∨m1∨m2∨m7
　　　　　　M3∨M4∨M5∨M6
三、推理证明题（10分）
C∨D, C∨D E, EA∧B, A∧BR∨SR∨S
　　证明：1 C∨DE
　　2 EA∧B
　　3 C∨DA∧B
　　4 A∧BR∨S
　　5 C∨DR∨S
　　6 C∨D
　　7 R∨S
2 xPxQy∧Rx，xPxQy∧xPx∧Rx
　　证明（1）xPx
　　3xPxQy∧Rx
　　4PaQy∧Ra
　　5Qy∧Ra
　　9Pa∧Ra
　　10xPx∧Rx
　　11Qy∧xPx∧Rx
四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍
设，，…，为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，，，…，这m＋1个整数中至少存在两个数和，它们被m除所得余数相同，因此和的差是m的整数倍。
五、已知A、B、C是三个集合，证明A-B∪CA-B∩A-C （15分）
∵x A-（B∪C） x A∧x（B∪C） x A∧（xB∧xC） （x A∧xB）∧（x A∧xC） x（A-B）∧x（A-C） x（A-B）∩（A-C）∴A-（B∪C）（A-B）∩（A-C）
六、已知R、S是N上的关系，其定义如下：Rx,y| x,yN∧yx2，Sx,y| x,yN∧yx+1。求R-1、R*S、S*R、R1,2、S[1,2]（10分）
　　解：R-1y,x| x,yN∧yx2，R*Sx,y| x,yN∧yx2+1，S*Rx,y| x,yN∧y（x+1）2，
七、若f:A→B和
正在加载中，请稍后...离散数学的主析取范式和主合取范式应该怎样求 求具体的方法 一看到这样的题就卡住_作业帮
拍照搜题，秒出答案
离散数学的主析取范式和主合取范式应该怎样求 求具体的方法 一看到这样的题就卡住
离散数学的主析取范式和主合取范式应该怎样求 求具体的方法 一看到这样的题就卡住
理论基础：主合取范式:若干个极大项的合取.主析取范式:若干个极小项的析取.合取：同真取真,其余取假,就相当于集合中的取交集；析取：有真取真,同假取假,就相当于集合中的取并集.定理：（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定.（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定.定义：（1）由有限个简单合取式构成的析取式称为析取范式.（2）由有限个简单析取式构成的合取式称为合取范式.（3）析取范式与合取范式统称为范式.&举例说吧：例1, 求公式(p∧q)∨r的主析取范式及主合取范式.主析取范式:(p∧q)∨r&==&(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐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)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r主合取范式：(p∧q)∨r&==&(p∨r)∧(q∨r)&==&(p∨(q∧┐q)∨r)∧((p∧┐p)∨q∨r)&==&(p∨q∨r)∧(p∨┐q∨r)∧(p∨q∨r)∧(┐p∨q∨r)&==&(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r从上面的例子你不难看出两者之间的关系吧!就是一个主析取范式转化为主合取范式就是取其主析取范式内不存在的最小项的标号的最大项进行析取,反过来求也是一样的!例2,文字：p,┐q,r,q.简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.&亲手总结,望采纳!