离散数学范式 离散数学析取范式

一般的教材不直接介绍范式的概念,以下属于个人理解.我觉得范式可以理解为一类结构特殊一点的合式公式或干脆称之为命题公式,说它特殊是因为它的组成部分,除了命题变项p,q,r,.外,其中的联结词组成一个联结词完备集,比如{否定,合取,析取},由此可以构造出析取范式或合取范式.这类范式可以很容易判断是永真式、永假式还是可满足式子,讨论范式的目的就是研究命题公式的简化,从而可以对命题公式进行分类.

一个个命题公式称为合取范式仅当具有形式 : A1∧A2..An (n≥1) 其中An 都是由命题变元或其否定组成的析取式. 这里A1,A2,..,An称为析取项(或简单析取式), n可取1,n=1时,Ak化为单个来变元或单个变元否自定,也即单个变元或单个变元否定均可看成析取项(简单析取式知),同理单个变元或单个变元否定也均可看成合取项(简单合取式). 如 P∧(P∨┐Q∨R)∧(道┐p∨Q),P∧Q∧(P∨┐Q)均是合取范式. P∨(P∧┐Q∧R)∨(┐p∧Q),P∨Q∨(P∧┐Q)均是析取范式

简而言之,主合取范式,就是若干个(只有1个也可以)极大项的合取(交集). 主析取范式,就是若干个(只有1个也可以)极小项的析取(并集). 如何按步骤求命题公式的主合取范式与主析取范式 http://jingyan.baidu/article/1612d5005ed288e20f1eee6e.html

只要看式子中连接每一项的连接词是∧还是∨,连接词是∧则式子为合取范式,为∨是析取范式.例如:(A∨B∨C)∧(┐A∨┐B∨┐C)∧(A∨┐B∨C)是合取范.

求主范式的过程如下:(p∧q)∨(p∧r) ⇔(p∧q∧(¬r∨r))∨(p∧(¬q∨q)∧r) 补项 ⇔((p∧q∧¬r)∨(p∧q∧r))∨(p∧(¬q∨q)∧r) 分配律2 ⇔(p∧q∧¬r)∨(p∧q∧r)∨(p∧(.

∀xF(x)→∃y(G(x,y)∧H(x,y)) (用换名规则) ∀uF(u)→∃y(G(x,y)∧H(x,y)) ┐∀uF(u)∨∃y(G(x,y)∧H(x,y)) ∃u┐F(u)∨∃y(G(x,y)∧H(x,y)) ∃u∃y(┐F(u)∨(G(x,y)∧H(x,y))) ∃u.

用P'表示非P,原式=PR+SR+P'=PR+SR+P'(R+R')=PR+P'R+SR+P'R'=(P+P')R+SR+P'R'=R+SR+P'R'=R+P'R'.可以吗?

前者p→q,是蕴含式 后者p↔q,是等值表达式 两者不一样:p↔q ⇔ (p→q)∧(q→p)

主析取范式是由极小项之和构成的,命题公式化简出来的主析取范式中包含的极小项,其下标对应的指派得到的命题公式的真值应该为1.主合取范式由极大项之积构成,命题公式等价的主合取范式中包含的极大项,其对应下标应该是使对应的指派得到命题公式的真值为0.所以,假设有三个命题変元,极小项和极大项的下标分别是0--7,如果一个命题変元的主析取范式表示为m1或m3或m5,它的主合取范式应该是m0且m2且m4且m6且m7.也就是说下标是极小项下标集合的补集.