四川大学计算机学院 离散数学(第4、5讲)

冯伟森Email：fws365@31一月2023离散数学计算机学院2023/1/31计算机学院2主要内容1、联结词的完备集2、范式

析取范式、合取范式、主析取（主合取）范式、极小项、极大项3、求主析取范式和主合取范式的方法

1）真值表法2）公式转换法

2023/1/31计算机学院31.4联结词的完备集前面我们已经介绍了最常见的6种逻辑联结词。它们都和自然语言中使用的联结词紧密相关，易于理解。不同联结词产生的真值表是互不相同的，根据对含两个命题变元的公式的解释方式看，共有2*2=4种不同的解释，因而公式的真值表相应有2*2*2*2=16种可能结果。对其中每一种真值表都应该存在相应的联结词。下面从真值表取值情况的角度定义几个新的联结词。2023/1/31计算机学院4下面是含两个命题变元的所有公式的真值表所能取得的情况：PQ1

2

3

4

567

8

9

10

11

12131415161

1100

10

0PQ1

2

3

4

567

8

9

10

11

12131415161

1100

10

01

0

1

1

101

1

1

0

0

000011

01

1

011

0

01

1

000101

0

1

0

110

1

0

1

0

101001

0

0

1110

0

1

0

1

11000Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTF2023/1/31计算机学院5PQP↑Q111001000111定义

1.14

设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：

2023/1/31计算机学院6PQP↓Q111001000001由真值表可以看出P↑Q～（P∧Q）,

即↑可由∧和～表示出来

P↓Q～（P∨Q），即↓可由∨和～表示出来2023/1/31计算机学院7

根据联结词↑和↓的定义，不难证明下面的等价式。①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q

～（～P∧～Q）P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q

～（～P∨～Q）P∧Q2023/1/31计算机学院8这些等价式告诉我们，

～，∨，∧可以由↑和↓单独表示出来，即↑和↓都可以单独表示出所有已知联结词，它们的这一性质使得在逻辑电路设计中只用一种门式电路元件就能实现任何电路功能，当然，元件的数量通常也显得更多。2023/1/31计算机学院9还有一个二元联结词“

”,称为条件否定，可以用下面的真值表定义：PQP

Q11100100

0

1

0

0显然，P

Q～(P→Q)2023/1/31计算机学院10至此我们定义了9个联结词，其中1个一元联结词，8个二元联结词。那么，还能不能定义出新的联结词呢？下面是含两个命题变元的所有公式的真值表所能取得的情况：2023/1/31计算机学院11Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTFP↑QP↓QQ

PP

QPQ1

2

3

4

567

8

9

10

11

12131415161

1100

10

01

0

1

1

101

1

1

0

0

000011

01

1

011

0

01

1

000101

0

1

0

110

1

0

1

0

101001

0

0

1110

0

1

0

1

110002023/1/31计算机学院12显然公式1是永真式，2代表矛盾式，3代表Ｐ∨Q，4代表Q→P,5代表P→Q，6代表P↑Q，7是P，8是Q，9代表PQ，10代表PQ，11代表～Q，12代表～P，13代表P↓Q，14代表Q

P,15代表P

Q，16代表P∧Q，可见，已定义的9个联结词就是全部可以定义的联结词。2023/1/31计算机学院13定义

1.15设S是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由S中的联结词实现，则称S是逻辑联结词的一个功能完备集；进一步，如果去掉S中的任何一个联结词后，至少有一个联结词的功能不能由S中剩余的联结词实现时，则称S是逻辑联结词的一个最小功能完备集。2023/1/31计算机学院14根据定义,我们知道{↑}、{↓}是最小的功能完备集，那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集，但是在实际应用中，普遍采用的功能完备集却是{～,∨,∧},这也是逻辑系统中最主要的3个常用联结词。2023/1/31计算机学院15习题一

8(1)（3）、9、10、

2023/1/31计算机学院161.5命题公式的范式表示

一个命题公式有无数多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也无法解决。要解决这个问题，我们引入范式(公式的标准型)的概念。范式——全名叫规范型式,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。问题：这样的标准形式存在吗？是否唯一？2023/1/31计算机学院17定义1.16命题变元或命题变元的否定称为句节。有限个句节的析取式称为子句；有限个句节的合取式称为短语。有限个短语的析取式称为析取范式；有限个子句的合取式称为合取范式。2023/1/31计算机学院18例1-5.1Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。Ｐ∨Ｑ∨～Ｒ是子句、析取范式、合取范式；～Ｐ∧Ｑ∧Ｒ是短语、析取范式、合取范式；（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。2023/1/31计算机学院19

句子（Ｐ∨Ｑ∨～Ｒ）仅是子句、合取范式，句子（～Ｐ∧Ｑ∧Ｒ）仅是短语、析取范式；句子Ｐ∨（Ｑ∨～Ｒ）、～（Ｑ∨Ｒ）既

不是析取范式也不是合取范式。但转换后：Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ上述两式的右端即是析取范式和合取范式。2023/1/31计算机学院20结论从上述定义和例子可以得出如下关系：单个的句节是一个子句、短语、析取范式、合取范式。单个的子句是合取范式、单个的短语是析取范式。若省略外层括号，单个的子句也是析取范式，单个的短语也是合取范式。析取范式、合取范式仅含联结词～

、∧、∨，且～仅出现在命题变元前。2023/1/31计算机学院21定理1.6任何命题公式都存在与之等价的合取范式与析取范式。证明：（1）利用等价公式中的等价式和蕴涵式将公式中的→、用联结词～

、∧、∨来取代；（2）利用德摩根定律将否定号┐移到各个命题变元的前端；（3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。2023/1/31计算机学院22例1-5.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S

（P∧（～Q∨R））→S～（P∧（～Q∨R））∨S～P∨～（～Q∨R）∨S（～P∨S）∨（Q∧～R）（～P∨S∨Q）∧（～P∨S∨～R）2023/1/31计算机学院23主析取范式一个公式的范式是不是唯一的呢？如

P∨（Q∧R）（P∨Q）∧（P∨R）

（（P∨Q）∧P）∨（（P∨Q）∧R）

（P∧P）∨（P∧Q)∨(P∧R）∨（Q∧R）由于范式不唯一，∴直接用范式判断命题间等价还是不方便。因此需要对公式进一步规范化，即求公式的主范式。析取范式也是析取范式2023/1/31计算机学院24定义1.17在n个变元的短语中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则称这种短语为极小项。由有限个极小项组成的析取式称为主析取范式。以下是由两个原子构成的极小项的真值表PQP∧QP∧～Q～P∧Q～P∧～Q1110001001000100100000012023/1/31计算机学院25由真值表可知：①任何两个命题公式（极小项）都不是相互等价的，并且只有一组真值指派，使得该公式的值为T。②2个命题变元有2²

=4种不同的组合（极小项）对于n个命题变元，共有2n个不同的极小项，记为。

极小项

公式成真赋值

名称

00

01

10

11

2023/1/31计算机学院262023/1/31计算机学院27主合取范式

定义1.17在n个变元的子句中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则这种子句称为极大项。由有限个极大项组成的合取式称为主合取范式。以下是由两个原子构成的极大项的真值表PQP∨QP∨～Q～P∨Q～P∨～Q1111101011010110110001112023/1/31计算机学院28由真值表可知：①任何两个极大项都不是相互等价的且只有一组真值指派使其值为F。②2个命题变元有2²=4种不同的组合（极大项）对于n个命题变元，共有2n个不同的极大项，记为。2023/1/31计算机学院29

极大项

公式成假赋值

名称

00

01

10

11

2023/1/31计算机学院30没有两个不同的极小项是等价的，且每个极小项只有一组真值指派，使该极小项的真值为真；没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假；极小项与极大项的性质2023/1/31计算机学院31mi=～Mi； Mi=～mi；i=0,1,2,…,2n-1Mi∨Mj=T； mi∧mj=F；i≠j；i,j∈{0,1,2,…,2n-1}2023/1/31计算机学院32极小项与极大项的性质（续）极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。当一个极大项在一种解释下取值0时，其余极大项在同一解释下取值1。PQP∨QP∨～Q～P∨Q～P∨～Q1111101011010110110001112023/1/31计算机学院33极小项取值1

“当且仅当”：如果极小项中出现的是原子本身，则原子赋值为1；如果出现的是原子的否定，则原子赋值为0。当一个极小项在一种解释下取值1时，其余极小项在同一解释下取值0。PQP∧QP∧～Q～P∧Q～P∧～Q111000100100010010000001范式存在定理2023/1/31计算机学院34定理1.7在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式，是该公式的主合取范式。定理1.8在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式，是该公式的主析取范式。2023/1/31计算机学院35利用真值表求主析（合）取范式例1-5.3设G=(P→Q)R，求出它的主析取范式和主合取范式。求主析（合）取范式的方法有：

1、真值表技术法

2、公式转换法

2023/1/31计算机学院36解：首先列出其真值表如下：PQRP→Q(P→Q)R0001000111010100111110001101001101011111例1-5.3（续）2023/1/31计算机学院371)、求公式的主析取范式PQR(P→Q）R000000110100011

1100

110101100111

1例1-5.3（续）～P∧～Ｑ∧Ｒ

极小项极小项极小项极小项～P∧Ｑ∧ＲP∧Ｑ∧～ＲP∧Ｑ∧Ｒ2023/1/31计算机学院38将极小项全部进行析取后，可得到相应的主析取范式：G=（Ｐ→Ｑ）Ｒ=（┐P∧┐Ｑ∧Ｒ）∨（┐P∧Ｑ∧Ｒ）∨（Ｐ∧┐Ｑ∧┐Ｒ）∨（Ｐ∧Ｑ∧Ｒ）例1-5.3（续）2023/1/31计算机学院392)、求公式的主合取范式PQR(P→Q)R00000011010001111001101011001111例1-5.3（续）极大项极大项极大项极大项P∨Ｑ∨Ｒ

P∨～Ｑ∨Ｒ～P∨Ｑ∨～Ｒ～P∨～Ｑ∨Ｒ2023/1/31计算机学院40将极大项全部进行合取后，可得到相应的主合取范式：G=（Ｐ→Ｑ）Ｒ=（P∨Ｑ∨Ｒ）∧（P∨～Ｑ∨Ｒ）∧（～Ｐ∨Ｑ∨～Ｒ）∧（～Ｐ∨～Ｑ∨Ｒ）例1-5.3（续）2023/1/31计算机学院41公式转换法（1）利用等价公式中的等价式和蕴涵式将公式中的→、用联结词～、∧、∨来取代；（2）利用德摩根定律将否定号～移到各个命题变元的前端；（3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。（4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。（5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。2023/1/31计算机学院42（6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元P，则可用公式：

（～Ｐ∨Ｐ）∧Q=Q将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项；（7）若合取范式的某一个子句中缺少该命题公式中所规定的命题变元P，则可用公式：

（～Ｐ∧Ｐ）∨Q=Q将