- 1、本文档共59页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2.2 析取范式和合取范式 设Ai(i=1,2,…,s)为简单合取式,则A=A1∨A2∨…∨As为析取范式。例如,A1=p∧┐q,A2=┐q∧┐r,A3=p,则由A1,A2,A3构造的析取范式为A=A1∨A2∨A3=(p∧┐q)∨(┐q∧┐r)∨p 设Ai(i=1,2,…,s)为简单析取式,则A=A1∧A2∧…∧As为合取范式。例如,取A1=p∨q∨r,A2=┐p∨┐q,A3=r,则由A1,A2,A3组成的合取范式为A=A1∧A2∧A3=(p∨q∨r)∧(┐p∨┐q)∧r 说明 形如┐p∧q∧r的公式既是一个简单合取式构成的析取范式,又是由三个简单析取式构成的合取范式。 形如p∨┐q∨r的公式既是含三个简单合取式的析取范式,又是含一个简单析取式的合取范式。 析取范式和合取范式的性质 定理2.2 (1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 (2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 说明 研究范式的目的在于,将给定公式化成与之等值的析取范式或合取范式,进而将公式化成与之等值的主析取范式或主合取范式。 范式存在的讨论 在范式中不会出现联结词→与?,否则可使用等值式消除A→B ? ┐A∨BA?B ? (┐A∨B)∧(A∨┐B) 在范式中不会出现形如┐┐A,┐(A∧B),┐(A∨B)的公式:┐┐A ? A┐(A∧B) ? ┐A∨┐B ┐(A∨B)?┐A∧┐B 在析取范式中不会出现形如A∧(B∨C)的公式:A∧(B∨C) ? (A∧B)∨(A∧C) 在合取范式中不出现形A∨(B∧C)的公式:A∨(B∧C) ? (A∨B)∧(A∨C) 定理2.3 任一命题公式都存在着与之等值的析取范式与合取范式。 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。A→B ? ┐A∨BA?B ? (┐A∨B)∧(A∨┐B) (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。┐┐A ? A┐(A∧B) ? ┐A∨┐B┐(A∨B)?┐A∧┐B (3)利用分配律:利用∧对∨的分配律求析取范式, ∨对∧的分配律求合取范式。A∧(B∨C) ? (A∧B)∨(A∧C)A∨(B∧C) ? (A∨B)∧(A∨C) 例题 例题2.7 求下面公式的析取范式与合取范式: (p→q)? r (1) 求合取范式 (p→q)? r ? (┐p∨q) ? r ?????????????????? (消去→) ? ((┐p∨q)→r)∧(r→(┐p∨q)) ???(消去?) ? (┐(┐p∨q)∨r)∧(┐r∨┐p∨q)?(消去→) ? ((p∧┐q)∨r)∧(┐p∨q∨┐r)??? (否定号内移) ? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(∨对∧分配律) 解答 例题 (2) 求析取范式 (p→q)? r ? ((p∧┐q)∨r)∧(┐p∨q∨┐r) ? (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r) ∨(r∧┐p)∨(r∧q)∨(r∧┐r) ? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 说明 由此例可知,命题公式的析取范式不唯一。 同样,合取范式也是不唯一的。 范式的规范化形式 定义2.4 在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项和它的否定式不同时出现,而二者之一必出现且仅出现一次,且第i个命题变项或它的否定式出现在从左算起的第i位上(若命题变项无角标,就按字典顺序排列),称这样的简单合取式(简单析取式)为极小项(极大项)。 n个命题变项共可产生2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数i,就将所对应极小项记作mi 。 类似地,n个命题变项共可产生2n个极大项,每个极大项只有一个成假赋值,将其对应的十进制数i做极大项的角标,记作Mi。 表2.3 p,q形成的极小项与极大项 表2.4 p,q,r形成的极小项与极大项 范式的规范化形式 定理2.4 设mi与Mi是命题变项p1,p2,…,pn形成的极小项和极大项,则 ┐mi ? Mi, ┐Mi ? mi 定义2.5 设由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项),则称该析取范式(合取范式)为主析取范式(主合取范式)。 定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的。 定理2.5的证明 (只证主析取范式的存在和唯一性) (1)证明存在性。 设A是任一含n个命题变项的公式。 由定理2.3可知,存在与A等值的析取范式A′,即A?A′,若A′的某个简单合取式
您可能关注的文档
- 《高等数学》课件-第5章 定积分.PPT
- 《高等数学》课件-第5章 积分.PPT
- 《计算机基础》课件-第1章-计算机基础知识.pptx
- 《计算机基础》课件-第2章-计算机系统.pptx
- 《计算机基础》课件-第4章 电子表格系统Excel.pptx
- 《计算机基础》课件-第6章 数据库技术与Access.pptx
- 《近现代史纲要》课件-第2讲 中国人对国家出路的早期探索1 地主阶级洋务派的洋务运动.pptx
- 《近现代史纲要》课件-第3讲 中国人对国家出路的早期探索2 太平天国农民战争.pptx
- 《近现代史纲要》课件-第4讲 中国人对国家出路的早期探索3 资产阶级维新派的戊戌变法运动.ppt
- 《近现代史纲要》课件-第5讲 中国共产党的创立.ppt
- 2024-2025学年江苏省高邮市高三上学期10月调研英语试题及答案.docx
- 2024-2025学年湖北省襄阳市第五中学高三上学期9月月考化学试题及答案.docx
- 2024-2025学年湖南省师大附中高三上学期月考(二)物理试题及答案.docx
- 2024-2025学年湖北省襄阳市第五中学高三上学期9月月考英语试题及答案.pdf
- 2024-2025学年湖北省金太阳百校大联考高三上学期10月考英语试题及答案.docx
- 2024-2025学年湖北省武汉外国语学校高三上学期10月月考生物试题及答案.pdf
- 史上最全的网络安全试题及答案汇总.pdf
- 医疗卫生行业最全的信息化建设行业标准及政策.pdf
- 史上最全网络安全知识竞赛题库附答案.pdf
- 2023年至2024年大学英语四级真题及解析答案汇总.pdf
文档评论(0)