当前位置: 首页 > news >正文

北京 网站 建设一键优化免费下载

北京 网站 建设,一键优化免费下载,网站建设的技术阶段,湖南建设局网站简单析取式与简单合取式 定义: 仅由有限个命题变项或其否定构成的析取式称为简单析取式。仅由有限个命题变项或其否定构成的合取式称为简单合取式。 例如: p p p、 p \lnot p p、 p ∨ q p\lor q p∨q、 p ∨ q p\lor\lnot q p∨q、 p ∨ q ∨ r \…
简单析取式与简单合取式

定义:
仅由有限个命题变项或其否定构成的析取式称为简单析取式。仅由有限个命题变项或其否定构成的合取式称为简单合取式

例如:
p p p ¬ p \lnot p ¬p p ∨ q p\lor q pq p ∨ ¬ q p\lor\lnot q p¬q ¬ p ∨ q ∨ r \lnot p\lor q\lor r ¬pqr等都是简单析取式;
p p p ¬ p \lnot p ¬p p ∧ q p\land q pq p ∧ ¬ q p\land\lnot q p¬q ¬ p ∧ q ∧ r \lnot p\land q\land r ¬pqr等都是简单合取式。

由以上定义可以得到两点结论:

  1. 一个简单析取式重言式,当且仅当它同时含有一个命题变项及其否定;
  2. 一个简单合取式矛盾式,当且仅当它同时含有一个命题变项及其否定。

例如:
简单析取式 p ∨ ¬ q ∨ q p\lor \lnot q\lor q p¬qq是重言式;简单合取式 p ∧ ¬ q ∧ q p\land\lnot q\land q p¬qq是矛盾式。

析取范式与合取范式

定义:
仅由有限个简单合取式构成的析取式称为析取范式;仅由有限个简单析取式构成的合取式称为合取范式

例如:
p ∨ q ∨ ¬ r p\lor q\lor\lnot r pq¬r ¬ p ∨ ¬ q ∨ r \lnot p\lor\lnot q\lor r ¬p¬qr ( p 1 ∧ ¬ q 1 ) ∨ ( ¬ p 1 ∧ p 2 ) ∨ ( p 1 ∧ p 2 ∧ p 3 ) (p_1\land\lnot q_1)\lor(\lnot p_1\land p_2)\lor(p_1\land p_2\land p_3) (p1¬q1)(¬p1p2)(p1p2p3)是析取范式;
p ∧ q ∧ ¬ r p\land q\land\lnot r pq¬r ¬ p ∧ ¬ q ∧ r \lnot p\land\lnot q\land r ¬p¬qr ( p 1 ∨ ¬ q 1 ) ∧ ( ¬ p 1 ∨ p 2 ) ∧ ( p 1 ∨ p 2 ∨ p 3 ) (p_1\lor\lnot q_1)\land(\lnot p_1\lor p_2)\land(p_1\lor p_2\lor p_3) (p1¬q1)(¬p1p2)(p1p2p3)是合取范式;

由以上定义可以得到两点结论:

  1. 一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式;
  2. 一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式。
范式存在定理与范式求解

范式存在定理:
任一命题公式都存在着不唯一的与之等值的析取范式和合取范式。

根据范式存在定理,可知任一命题公式都能通过等值演算求出与之等值的析取范式与合取范式。步骤如下:

  1. 消去 → \to ↔ \leftrightarrow
    p → q    ⟺    ¬ p ∨ q p\to q \iff\lnot p\lor q pq¬pq
    p ↔ q    ⟺    ( ¬ p ∨ q ) ∧ ( p ∨ ¬ q ) p\leftrightarrow q \iff (\lnot p\lor q)\land(p\lor \lnot q) pq(¬pq)(p¬q)
  2. 否定号的消去或内移:
    ¬ ¬ p    ⟺    q \lnot\lnot p\iff q ¬¬pq
    ¬ ( p ∧ q )    ⟺    ¬ p ∨ ¬ q \lnot(p\land q)\iff\lnot p\lor\lnot q ¬(pq)¬p¬q
    ¬ ( p ∨ q )    ⟺    ¬ p ∧ ¬ q \lnot(p\lor q)\iff\lnot p\land \lnot q ¬(pq)¬p¬q
  3. 使用分配率。对析取范式应使用 ∧ \land ∨ \lor 的分配率;对合取范式应使用 ∨ \lor ∧ \land 的分配率。

举例:求 ( ( p ∨ q ) → r ) → p ((p\lor q)\to r)\to p ((pq)r)p的合取范式和析取范式
解: ( ( p ∨ q ) → r ) → p = ¬ ( ¬ ( p ∨ q ) ∨ r ) ∨ p (消去 → ) = ( ( ¬ ¬ p ∨ ¬ ¬ q ) ∧ ¬ r ) ∨ p ( ¬ 内移) = ( ( p ∨ q ) ∧ ¬ r ) ∨ p ( ¬ 消去) = ( p ∨ q ) ∧ ( ¬ r ∨ p ) ( ∨ 对 ∧ 分配率,得合取范式) = ( p ∧ ¬ r ) ∨ ( q ∧ ¬ r ) ∨ p ( ∧ 对 ∨ 分配率,得析取范式) \begin{aligned} ((p\lor q)\to r)\to p& = \lnot(\lnot(p\lor q)\lor r)\lor p & \text{(消去$\to$)}\\ & = ((\lnot\lnot p\lor\lnot\lnot q)\land \lnot r)\lor p& \text{($\lnot$内移)}\\ & = ((p\lor q)\land \lnot r)\lor p & \text{($\lnot$消去)}\\ & = (p\lor q)\land(\lnot r\lor p) & \text{($\lor$对$\land$分配率,得合取范式)}\\ & = (p\land\lnot r)\lor(q\land\lnot r)\lor p & \text{($\land$对$\lor$分配率,得析取范式)} \end{aligned} ((pq)r)p=¬(¬(pq)r)p=((¬¬p¬¬q)¬r)p=((pq)¬r)p=(pq)(¬rp)=(p¬r)(q¬r)p(消去)内移)消去)(分配率,得合取范式)(分配率,得析取范式)

主析取范式与主合取范式

定义:
如果公式 A A A的析取范式中的简单合取式全是极小项,则称该析取范式为主析取范式;如果公式 A A A的合取范式中的简单析取式全是极大项,则称该合取范式为主合取范式

极小项与极大项

极小项定义:
在有 n n n个命题变项的简单合取式中,若每个命题变项及其否定有且仅有其中一个出现一次,则称这样的简单合取式为极小项。

通常极小项的命题变项用1表示,命题变项的否定用0表示,这就组成了一段二进制码,按二进制码的大小进行排序后用小写字母 m ( m i n i m u m ) m(minimum) m(minimum)加从0开始递增的脚标命名,例: m 0 m_0 m0 m 1 m_1 m1

例如:2个命题变项 p p p q q q可形成4个极小项;3个命题变项 r r r s s s t t t可形成8个极小项

极小项二进制码命名极小项二进制码命名
¬ p ∧ ¬ q \lnot p \land \lnot q ¬p¬q00 m 0 m_0 m0 ¬ r ∧ ¬ s ∧ ¬ t \lnot r\land \lnot s\land \lnot t ¬r¬s¬t000 m 0 m_0 m0
¬ p ∧ q \lnot p\land q ¬pq01 m 1 m_1 m1 ¬ r ∧ ¬ s ∧ t \lnot r\land \lnot s\land t ¬r¬st001 m 1 m_1 m1
p ∧ ¬ q p \land \lnot q p¬q10 m 2 m_2 m2 ¬ r ∧ s ∧ ¬ t \lnot r\land s\land \lnot t ¬rs¬t010 m 2 m_2 m2
p ∧ q p\land q pq11 m 3 m_3 m3 ¬ r ∧ s ∧ t \lnot r\land s\land t ¬rst011 m 3 m_3 m3
r ∧ ¬ s ∧ ¬ t r\land \lnot s\land \lnot t r¬s¬t100 m 4 m_4 m4
r ∧ ¬ s ∧ t r\land \lnot s\land t r¬st101 m 5 m_5 m5
r ∧ s ∧ ¬ t r\land s\land \lnot t rs¬t110 m 6 m_6 m6
r ∧ s ∧ t r\land s\land t rst111 m 7 m_7 m7

极大项定义:
在有 n n n个命题变项的简单析取式中,若每个命题变项及其否定有且仅有其中一个出现一次,则称这样的简单析取式为极大项。

通常极大项的命题变项用0表示,命题变项的否定用1表示,这就组成了一段二进制码,按二进制码的大小进行排序后用大写字母 m ( m a x i m u m ) m(maximum) m(maximum)加从0开始递增的脚标命名,例: M 0 M_0 M0 M 1 M_1 M1

例如:2个命题变项 p p p q q q可形成4个极大项;3个命题变项 r r r s s s t t t可形成8个极大项

极小项二进制码命名极小项二进制码命名
p ∧ q p \land q pq00 M 0 M_0 M0 r ∧ s ∧ t r\land s\land t rst000 M 0 M_0 M0
p ∧ ¬ q p\land \lnot q p¬q01 M 1 M_1 M1 r ∧ s ∧ ¬ t r\land s\land \lnot t rs¬t001 M 1 M_1 M1
¬ p ∧ q \lnot p \land q ¬pq10 M 2 M_2 M2 r ∧ ¬ s ∧ t r\land \lnot s\land t r¬st010 M 2 M_2 M2
¬ p ∧ ¬ q \lnot p\land\lnot q ¬p¬q11 M 3 M_3 M3 r ∧ ¬ s ∧ ¬ t r\land \lnot s\land\lnot t r¬s¬t011 M 3 M_3 M3
¬ r ∧ s ∧ t \lnot r\land s\land t ¬rst100 M 4 M_4 M4
¬ r ∧ s ∧ ¬ t \lnot r\land s\land \lnot t ¬rs¬t101 M 5 M_5 M5
¬ r ∧ ¬ s ∧ t \lnot r\land \lnot s\land t ¬r¬st110 M 6 M_6 M6
¬ r ∧ ¬ s ∧ ¬ t \lnot r\land \lnot s\land \lnot t ¬r¬s¬t111 M 7 M_7 M7

主范式存在定理:
任何命题公式都有唯一的主析取范式或主合取范式。

求解主范式的步骤:

  1. 求出析取范式或合取范式
  2. 扩展命题变项,将简单合取式(简单析取式)扩展为极小项(极大项)形式
  3. 合并重复项
  4. 求余项,求出主析取范式后余下的项就是主合取范式的组成项,求出主合取范式后余下的项就是主析取范式的组成项

例如:求 ( ( p ∨ q ) → r ) → p ((p\lor q)\to r)\to p ((pq)r)p的主析取范式与主合取范式主范式
解: ( ( p ∨ q ) → r ) → p = ( p ∧ ¬ r ) ∨ ( q ∧ ¬ r ) ∨ p 求出析取范式 = ( p ∧ ( ¬ q ∨ q ) ∧ ¬ r ) ∨ ( ( ¬ p ∨ p ) ∧ q ∧ ¬ r ) ∨ ( p ∧ ( ¬ q ∨ q ) ∧ ( ¬ r ∨ 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 ) 扩展命题变项 = m 4 ∨ m 6 ∨ m 2 ∨ m 6 ∨ m 4 ∨ m 5 ∨ m 6 ∨ m 7 = m 2 ∨ m 4 ∨ m 5 ∨ m 6 ∨ m 7 合并重复项,得出主析取范式 = M 0 ∧ M 1 ∧ M 3 求余项,得出主合取范式 \begin{aligned} ((p\lor q)\to r)\to p & = (p\land\lnot r)\lor(q\land\lnot r)\lor p & \text{求出析取范式}\\ & = (p\land(\lnot q \lor q)\land\lnot r)\lor((\lnot p \lor p)\land q\land\lnot r)\lor (p\land (\lnot q \lor q)\land (\lnot r \lor r))\\ & = (p\land\lnot q\land\lnot r)\lor(p\land q\land\lnot r)\lor(\lnot p \land q\land\lnot r)\lor(p \land q\land\lnot r)\lor\\&(p\land \lnot q\land \lnot r)\lor(p\land \lnot q\land r)\lor(p\land q\land \lnot r)\lor(p\land q\land r)& \text{扩展命题变项}\\ & = m_4\lor m_6\lor m_2\lor m_6\lor m_4\lor m_5\lor m_6\lor m_7\\ & = m_2\lor m_4\lor m_5\lor m_6\lor m_7& \text{合并重复项,得出主析取范式}\\ & = M_0\land M_1\land M_3& \text{求余项,得出主合取范式}\\ \end{aligned} ((pq)r)p=(p¬r)(q¬r)p=(p(¬qq)¬r)((¬pp)q¬r)(p(¬qq)(¬rr))=(p¬q¬r)(pq¬r)(¬pq¬r)(pq¬r)(p¬q¬r)(p¬qr)(pq¬r)(pqr)=m4m6m2m6m4m5m6m7=m2m4m5m6m7=M0M1M3求出析取范式扩展命题变项合并重复项,得出主析取范式求余项,得出主合取范式

http://www.shuangfujiaoyu.com/news/51447.html

相关文章:

  • 网站平台方案网站建设公司地址在哪
  • 做网站公司yuanmus如何做好线上推广
  • 常州辉煌网络网站制作域名大全查询
  • 合肥的网站建设温州seo教程
  • 传统网站布局站长seo工具
  • 安全的南昌网站制作灰色项目推广渠道
  • 合肥公司网站建设多少费用百度竞价排名利弊
  • 做网站UI工具神马快速排名优化工具
  • 丹东建设网官方网站seo是怎么优化
  • 建设银行湖北省分行 网站网络营销乐云seo
  • 工信部网站实名认证怎么做河南制作网站
  • 供应网站建设站长统计 站长统计
  • 百度网站建设目标线上宣传渠道
  • 手机wordpress的文章分类深圳防疫措施优化
  • 做网站是用什么语言做成的百度推广客户端登录
  • 网站建设 是否计入固定资产seo优化交流
  • 芜湖哪里有做网站的广东省白云区
  • 网站建设联盟网站制作的基本流程是什么
  • 成都网站设计是什么北京百度seo点击器
  • 分析影响网站排名的因素国内广告联盟平台
  • 手机网站存储登录信息英文外链seo兼职在哪里找
  • 做企业网站排名优化要多少钱seo基础优化包括哪些内容
  • 有没有做a的电影网站seo服务运用什么技术
  • 代理记账公司如何寻找客户求职seo
  • 网站设计联盟t和p在一起怎么做网站
  • 代理平台注册网站建设重庆做seo外包的
  • wordpress 多媒体尺寸seo排名培训
  • 博罗网站建设费用网站优化排名操作
  • 深圳企业倒闭网站优化+山东
  • 建设银行投诉处理网站代运营靠谱吗