离散数学主析取及主合取范式

您所在的位置:网站首页 离散数学中真值是什么意思啊 离散数学主析取及主合取范式

离散数学主析取及主合取范式

2024-05-24 12:20| 来源: 网络整理| 查看: 265

本文为本人结合书本,网络资源的学习笔记,没有任何商业用途,如有任何错误,问题请广大网友指正和提出!

文章目录 概念一:析取范式与合取范式析取范式与合取范式求范式的步骤 二:主析取及主合取范式 解法等价公式真值表 注:

概念 一:析取范式与合取范式

百度百科

命题变项及其否定统称作文字。 仅由有限个文字构成的析取式称为简单析取式。 仅由有限个文字构成的合取式称为简单合取式。

例如,文字:p,┐q,r,q.

简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.

简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐r**.**

析取范式与合取范式

(1)由有限个简单合取式构成的析取式称为析取范式。

(2)由有限个简单析取式构成的合取式称为合取范式。

(3)析取范式与合取范式统称为范式。

例如,析取范式:**(**p┐∧q)∨r, ┐p∨q∨r, p∨┐q∨r.

合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∧┐q∧r.

求范式的步骤

1.消去联结词→、←、↔;

2.利用德·摩根律将否定符号┐直接移到各个命题变元之前;

3.利用分配律。

命题公式的析取范式与合取范式都不是唯一的。

二:主析取及主合取范式

主析取范式:

设命题公式A中含n个命题变项,如果A得析取范式中的简单合取式全是极小项,则称该析取范式为A的主析取范式。

若干个极小项的析取(并集)。

主合取范式:

设命题公式A中含n个命题变项,如果A得析取范式中的简单合析式全是极大项,则称该析取范式为A的主析取范式。

若干个极大项的合取(交集)。

极大项,极小项

极大项

包含全部数目的命题变元的析取表达式。

极小项

包含全部数目的命题变元的合取表达式。

所有极小项的析取为永真公式,所有极大项的合取为永假公式。

解法 等价公式

常用基本等价公式:

(G↔H)=(G→H)∧(H→G)=(¬G∨H)∧(¬H∨G); (G→H)=(¬G∨H);(蕴含式) G∨G=G,G∧G=G;(幂等律) G∨H=H∨G,G∧H=H∧G;(交换律) G∨(H∨S)=(G∨H)∨S,G∧(H∧S)=(G∧H)∧S;(结合律) G∨(G∧H)=G,G∧(G∨H)=G;(吸收律) G∨(H∧S)=(G∨H)∧(G∨S),G∧(H∨S)=(G∧H)∨(G∧S);(分配律) G∨0=G;G∧1=G;(同一律) G∧0=0,G∨1=1;(零律) ¬(G∨H)=¬G∧¬H,¬(G∧H)=¬G∨¬H(德摩根律)

例:(p∨(q∧r))→(p∧q∧r)

0.﹁(p∨(q∧r))∨(p∧q∧r)

1.(﹁p∧﹁(q∧r))∨(p∧q∧r)

2.(﹁p∧(﹁q∨﹁r))∨(p∧q∧r)

3.(﹁p∧﹁q)∨(﹁p∧﹁r)∨(p∧q∧r)

4.((﹁p∧﹁q)∧(r∨﹁r))∨((﹁p∧﹁r)∧(q∨﹁q))∨(p∧q∧r) 5.(﹁p∧﹁q∧r)∨(﹁p∧﹁q∧﹁r)∨(﹁p∧q∧﹁r)∨(p∧q∧r)

6.(﹁p∧﹁q∧﹁r)∨(﹁p∧﹁q∧r)∨(﹁p∧q∧﹁r)∨(p∧q∧r)

主析取范式m0∨m1∨m2∨m7

则可得出其主合取范式为M3∧M4∧M5∧M6

1.这里也用过主析取范式与主合取范式转换的相关知识,以及极大极小项的表示,本例m0–m7的表示,具体知识不详述。

2.使用公式转换法求主范式时,需要增加某一个命题变元,此时要注意正确加入该变 水真公式和永假公式,同时注意正确化简公式(如上述例子的3,4步的过渡)。

真值表

[直接给例子吧] 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

注:

“ = ”不是一个联结词,而是一种关系。而且具有以下三种性质:

1.自反性:即G=G 2.对称性:即若G=H,则H=G 3.传递性:即若G=H,H=S,则G=S


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3