离散数学第二章知识点

命题逻辑等值演算

等值式

定理：设A，B两个命题公式（即前面的合式公式），若A，B构成的等价式A↔B

为重言式，则A与B是等值的，记作A⇔B(可以说该式子为等值式模式)

常用的16组等值式模式：

双重否定律：A⇔﹁﹁A

幂定律：A⇔A∧A，A⇔A∨A

交换律:A∨B⇔B∨A,A∧B⇔B∧A

结合律：(A∨B)∨C⇔A(B∨C)

(A∧B)∧C⇔A(B∧C)

分配律:A∨(B∧C)⇔(A∨B)∧(A∨C)

A∧(B∨C)⇔(A∧B)∨(A∧C)

德摩根律：﹁(A∨B)⇔﹁A∧﹁B

﹁(A∧B)⇔﹁A∨﹁B

吸收律：A∨(A∧B)⇔A，A∧(A∨B)⇔A

零律：A∨1⇔1,A∧0⇔0

同一律:A∨0⇔A,A∧1⇔1

排中律:A∨﹁A⇔1

矛盾律:A∧﹁A⇔0

蕴涵等值式: A→B⇔﹁A∨B

等价等值式: A↔B⇔(A→B)∧(B→A)

假言易位:A→B⇔﹁B→﹁A(这里可以用逆否命题的概念证明)

等价否定等值式:A↔B⇔﹁A↔﹁B(或写成﹁B↔﹁A，这里可以用逆否命题的概念证明)

归谬(miu)论：(A→B)∧(A→﹁B)⇔﹁A(此处可以通过蕴涵等值式，交换律以及结合律进行结合证明)

上述等值式模式可以通过真值表证明

等值式的验证

1. 等值演算法（即通过等值式模式对原式进行变形）

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

证明时可以从左边开始演算也可以从右边开始演算，无硬性要求，这里我们从右边开始演算。

(p→r)∧(q→r)

⇔(﹁p∨r)∧(﹁q∨r) //蕴涵等值式

⇔(﹁p∧﹁q)∨r //分配律

⇔﹁(p∨q)∨r //德摩根律

⇔(p∨q)→r //蕴涵等值式

2. 真值表法（我在第一章的最后有叙述，这里不再重述）

3. 观察法（也可称为带入法，此处适合用以证明两式不等值的情况） 关于等值演算法的补充：等值演算法可以用以证明公式的类型。

1. 当最后结果为1时为重言式（永真式）

2. 当最后结果为0时为矛盾式（永假式）

3. 当最后结果只能化成某个命题变项或公式时为可满足式

析取范式与合取范式

简单析取式：p,﹁p,p∨q,﹁p∨q,p∨﹁q,,﹁p∨﹁q,﹁p∨﹁q∨r等

（这里可以发现的是里面都只含有析取联结词，简单析取式结构就是由析取联结词和命题变项组成的一个公式）

简单合取式：p,﹁p,p∧q,﹁p∧q,p∧﹁q,,﹁p∧﹁q,﹁p∧﹁q∧r等

（这里可以发现的是里面都只含有合取联结词，简单合取式结构就是由合取联结词和命题变项组成的一个公式）

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

一些推论：

（1）一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式(意思大概就是除非它的每个命题变项全为0，或者说全为假时这个简单析取式为0或者说为假，否则这个简单析取式都是为1，或者说为真的)

（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式(意思大概就是除非它的每个命题变项全为1，或者说全为正时这个简单合取式为1或者说为真，否则这个简单析取式都是为0，或者说为假的)

析取范式：是由有限个简单合取式的析取构成的命题公式称作析取范式

这里我举个例：

A1∨A2∨A3∨...（这里面的Ai（i=1，2，3，4....）都是简单合取式）

合取范式：是由有限个简单析取式的合取构成的命题公式称作合取范式

这里我举个例：

A1∧A2∧A3∧...（这里面的Ai（i=1，2，3，4....）都是简单析取式）

一些推论：

（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

一些错误的析取范式和合取范式：

例如：

﹁﹁p，﹁（p∧q），﹁（p∨q）这里的错误是在一个范式外面加了个否定联结词，可以等同理解为没有完全化成范式即它是个半成品

我们来将它变成真正的范式：

﹁﹁p⇔p

﹁（p∧q）⇔﹁p∨﹁q

﹁（p∨q）⇔⇔﹁p∧﹁q

例如错误：p∧（q∨r）

p∨（q∧r）

这里的错误可以理解为没有化简

所以我们来将它化简以将它变成真正的范式：

p∧（q∨r）⇔（p∧q）∨（p∧r）

p∨（q∧r）⇔（p∨q）∧（p∨r）

一个重要的定律：任一个命题公式都存在于之等值的析取范式与合取范式。

关于将任一个命题公式变成公式范式的步骤：

（1）消去联结词→，↔。

（2）用双重否定律消去双重否定符，用德摩根律内移否定符。

（3）使用分配定律：求析取范式时使用∧对∨的分配律，求合取范式时使用使用∨对∧的分配律。

关于上面三个步骤是书本定义的一个固定的解法，实际上可以这三个步骤可以进行变化顺序，以加快解题的一个速度，具体变化需要结合题目进行分析。对于怕出现错误的可以照这三个步骤来。

我们现在用上面说的三个步骤来演示以个例题：

（p→q）↔r

求它的合取范式

⇔（﹁p∨q）↔r /消去→

⇔（（﹁p∨q）→r）∧（r→（﹁p∨q）） /消去↔

⇔（﹁（﹁p∨q）∨r）∧（﹁r∨（﹁p∨q））/ 消去→

⇔（（p∧﹁q）∨r）∧（﹁r∨﹁p∨q）/否定符的内移，也就是使用德摩根律消去否定符

⇔（p∨r）∧（﹁q∨r）∧（﹁r∨﹁p∨q）/∨对∧的分配律

极小项：在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定形式按照下标从小到大或按照字典顺序排列，称这样的简单合取式为极小项，极小项记为mi（关于i的取值我在下面的表中给出）。

极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定形式按照下标从小到大或按照字典顺序排列，称这样的简单析取式为极大项，极大项记为Mi（关于i的取值我在下面的表中给出）。

一个推论：

当一个命题有n个变量时它的极小项和极大项的数量之和为2^n个。

极小项和极大项间的关系：

﹁mi⇔Mi

主析取范式：所有简单合取式都是极小项的析取范式。

主合取范式：所以简单析取式都是极大项的合取范式。

一个重要的定理：任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。

因为存在性的证明较简单我就不进行叙述

我对唯一性的证明进行一些简单叙述：

我们采用反证法：设存在两个不一样的主析取范式或主合取范式A，B

此时它们必有A⇔B（因为他们代表的是同一个命题公式），因为A与B的主析取或主合取范式不一样所以我们设A中有Mi而B中没有，也就是说此时A是假的而B是真的此时他们两个并不相等，故A⇔B矛盾，此时可证它具有唯一性。

关于将公式转换成为主析取范式或主合取范式的方法与命题公式变成公式范式法相同唯一需要注意的是它的简单析取式要写成极大项的形式，简单合取式要写出极小项形式。

主析取范式与主合取范式的运用

1. 求公式的成真赋值与成假赋值

//将公式化成主析取范式它包含的最小项就是它的成真赋值，不包含的就是成假赋值

将公式化成主合取范式它包含的最大项就是它的成假赋值，不包含的就是成真赋值

2. 判断公式的类型

设公式A中有n个命题变量

（1）A为重言式此时它的主析取范式包含了2^n个极小项

（2）A为矛盾式此时它的主析取范式不包括一个极小项

（3）A为可满足式此时A的主析取范式中至少含一个极小项。

3.判断两个命题公式是否等值。

即比较他们的极小项和最大项是否相同，相同时即为等值，不相同时为不等值。

联结词的完备集

n元真值函数F：{0，1}^n→{0,1} 这里的n是表示有n个变量，而{0,1}是指每个变量的取值范围。

n为1时我们称它为1元真值函数

n为2时我们称它为2元真值函数

以此类推

一些推论：n个命题变项共可构成（2^2）^n个不同的变量

关于n元真值函数我给出了两个最简单的真值函数表

这里我们可以发现的规律关于Fi（n）中的变量个数（即一列的个数为）2^n而i的取值范围为0~（2^2）^n

联结词完备集：设S是一个联结词集合，如果任何n（n>=1）元真值函数都可以由仅含S中的联结词构成的公式构成

一个重要定理： S={﹁，∧，∨} //这个定理在证明其他联结词是否为联结词完备集时使用。

发现：

1. 任何一个联结词完备集里面都含有﹁，此外任何一个联结词完备集都至少需要两个联结词（其中一个是﹁，另外的可以任意选择）

2. 当一个联结词集不是联结词完备集时，它的子集必然不是联结词完备集。

与非式：复合命题p与q的否定式，称作p，q的与非式，记作p↑q，即p↑q⇔

﹁（p∧q），符号↑称为与非联结词

或非式：复合命题p或q的否定式，称作p，q的或非式，记作p↓q，即p↓q⇔﹁（p∨q），符号↓称为或非联结词

这是我们会发现{↑}{↓}都是联结词完备集。因为这两个联结词完备集都相当与包含有两个联结词且其中一个联结词是﹁的联结词完备集。

可满足性问题与消解法

空简单析取式：称不含任何文字的简单析取式为空简单析取式，记作符号：入。

此时空简单析取是不可满足的（因为对任何赋值，空简单析取式中都没有文字为真也可以理解为空简单析取式就是成假赋值的）

当有一个空简单析取式的合取式就是矛盾式也就是不可满足的。

消解法的运用：

举例:

(﹁p∨q)∧(p∨q)∧（﹁q)

第一步，化成三个集合：S1（空集），S2（(﹁p∨q)，(p∨q)，（﹁q)）（它的每个元素都是合取式中的一个简单析取式），S3（空集）

第二步，将集合S1和S2中的元素互相消去

(﹁p∨q)∧(p∨q)得到q

(﹁p∨q)∧（﹁q)得到﹁p

(p∨q)∧（﹁q)得到p

此时发现没有得到符号：入（即空简单析取式）

且此时因为得到的命题变项是集合中没有的因此我将这些存储在集合S3中

并进入第二个循环。

此时令S1=S2，S2=S3.

此时令集合s1和集合S2中的元素互相消去

(﹁p∨q)∧p得到q

(p∨q)∧﹁p得到﹁q

此时你会发现q能与﹁q消去成为 （符号：入）

输出“no”，计算结束

关于消去过程中所需写的消去过程只需要写出可以消解化简的式子。

具体规范格式按照书本上即可，这里消解过程的原理： (﹁p∨q)∧(p∨q)∧（﹁q)∧（任一个原合取公式中的简单析取式）⇔ (﹁p∨q)∧(p∨q)∧（﹁q)//也就是等值式模式中吸收律