导图社区 范式
离散数学-主析取范式和主合取范式的相关概念逻辑图
社区模板帮助中心，点此进入>>
英语词性
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
法理
刑法总则
【华政插班生】文学常识-先秦
【华政插班生】文学常识-秦汉
文学常识：魏晋南北朝
【华政插班生】文学常识-隋唐五代
民法分论
1.4-范式
范式的种类
析取范式
由有限个简单合取式组成的析取式
A1&A2&A3&A3,其中A1,A2,A3....,Ar是简单合取式
合取范式
由有限个简单析取式组成的合取式
A1|A2|A3|A4......,其中A1A2A3是简单析取式
例：
公式A的析取范式: 与A等值的析取范式
公式A的合取范式: 与A等值的合取范式
importance
从单个文字来看式子是由简单析取式组成的，从整体来看文字间是由合区符号链接的所以又是合取范式
主析取范式
由极小项构成的析取范式
(!p&!q&r) | (!p&q&r)==m1|m3==001|011二进制
主合取范式:
由极大项构成的合取范式
（p|q|!r) & (!p|Q|!r)==M1&M5==001&101二进制
任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是唯一的
范式的结构
定义
析取范式与合取范式的总称
项的组成
文字
命题变项及其否定的总称
简单析取式
有限个文字构成的析取式；p,!q,p|q,,p|!q....
简单合取式
有限个文字构成的合取式; p,q,!q,p&q,p&!q.....
注意：单个文字既是简单析取式，又是简单合取式
最小项与最大项
在含有n个命题变项的简单合取式（简单析取式）中，若每个命题均以文字的形式出现且仅出现一次，这样的简单合取式（简单析取式）为极小项（极大项）
性质
n个命题变项最多产生2^n个极小项或2^n个极大项
2n个极小项（极大项）均互不等值
在极小项和极大项中文字均按下标或字母顺序排列
用mi表示第i个极小项，其中i是该极小项成真赋值的十 进制表示.
用Mi表示第i个极大项，其中i是该极大项成 假赋值的十进制表示
mi(Mi)称为极小项(极大项)的名称
mi与Mi的关系：-mi==Mi,-Mi==mi
图例
子主题
一般mi表示成真赋值，Mi是成假赋值
与命题公式的联系
公式的范式存在，但不惟一
求解一个命题公式A的范式的过程
子主题 1
消去A中的->和<->（如果存在）
子主题 2
把否定连接词！内移到括号内或者消去
子主题 3
使用分配律
&对|分配得到(析取范式)
|对&分配（合取范式）
任何命题公式都存在着与之等值的析取范式
分支主题 5
例题
A==（p->!q）|!r==(!p|!q)|!r 蕴涵式==!p|!q|!r结合律
A既是析取范式也是合取范式
B==（p->！q)->r==!(p->!q)|r蕴涵式==!(!p|!q)|r蕴涵式==(p&q)|r德摩根律==r|p&r|q（分配律|对&分分配）==得到合取范式
求公式的主范式
A=（p->!q)->r
求主析取范式
A=!(p->!q)|r
=!(!p|!q)|r
=p&q|r
=(p&q)|(!r|r)
!r|r==1同一律
分配律(p&q&!r)|(p&q&r)
m6|m7
r|1|1==r
p|!p==1==q|!q同一律
r&(p|!p)&（q|!q）
（!p&!q&r）|（!p&q&r）|（p&!q&r）|（p&q&r）
m1|m3|m5|m7
将1，2合并
有p|p==p可得
m1|m3|m5|m7|m6
求A的主合取范式
分配律
(p|r)&(q|r)
(p|r)==p|(q&!q)|r=(p|r|q)&(p|q!|r)==M0&M2
(q|r)==q|（p&!p）|r==(p|q|r)&(!p|q|r)==M0&M4
(p|r|q)&(p|q|!r)&(p|q|r)&(p|!q|r)
M0&M2&M0&M4
M0&M2&M4
用等值演算法求公式的主范式的步骤
1.先求析取范式（合取范式）
2.将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析 取（极大项的合取）
2.1需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等.
3).极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序.
主范式的用途
与真值表相同
求公式的成真赋值和成假赋值
如A=（p->!q)->r
主析取式
成真赋值
主合取式
成假赋值
类似地，由主合取范式也可立即求出成 假赋值和成真赋值.
判断公式的类型
设A含n个命题变项，
A为重言式A的主析取范式含2n个极小项
A的主合取范式为1.
A为矛盾式 A的主析取范式为0
A的主合取范式含2n个极大项
A为非重言式的可满足式
A的主析取范式中至少含一个且不含全部极小项
A的主合取范式中至少含一个且不含全部极大项
判断两个公式是否等值
若A，B两个公式主析取范式或主合取范式
相同，A，B等值
不相同，A，B不等值
求解实际问题
解此问题的步骤为： ① 将简单命题符号化 ② 写出各复合命题 ③ 写出由②中复合命题组成的合取式 ④ 求③中所得公式的主析取范式
