第一章：命题逻辑 (3)

1.3等值演算&1.4联结词全功能集

[教学重点] 等值关系及演算的规则

[教学目的]1：使学生了解等值演算是逻辑理论的一个基本内容。 2：理解等值关系的含义，并理解等值式模式及其重要性。 3：理解并熟记等值演算的规则 4：理解全功能集的含义并应用。 [教学准备]

[教学方法]讲述法 [课时安排]二课时 [教学过程] 讲述： 前面已经提到，等价式A?B为重言式，记为A?B，称为等值关系。并提到这是逻辑理论的一个基本内容。 本节将主要讨论等值关系的有关内容，阐述等值演算的各种规则，然后再谈谈联结词的有关问题。 板书：

1.3等值演算 讲述：

给定n个命题变项，按合式公式的形成规则可以形成无数多个命题公式。但这些无穷尽的命题公式中，有些具有相同的真值表。例如：n=2时，p?q 与?p?q的真值表相同。事实上，对于n个命题变项，可能的赋值有2n个。对于每个赋值，真值函数的取值又有真、假两种可能。因此，对于n个命题变项来说，只能生成22个真值不同的命题公式。 板书： 真值函数：

一个n元真值函数是指一个n（n≥1）维卡氏积{0，1}n 到{0，1}的函数，记为F：{0，1}n?{0，1}，(n≥1)，即此函数以n个命题变项为变元，其定义域和值域均由真、假两值构成。 示例：

n=1,有四个一元真值函数, n=2时有16个，如下图： p q A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 讲述：

A13可取的命题公式有 p?q 、?p?q、?(p??q)等，它们的真值相同，我们说这些公式是等值的。 一 等值关系 1 概念：

n 设A、B为两命题公式，若等价式A?B为重言式，记为A?B。 例如：p?q ??p?q??(p??q) 讲述：

两个命题公式是否等值可以通过真值表来判断或验证。下面给出一些常用的等值式，其中很多正是通常所说的的布尔代数或逻辑代数的主要组成部分。 板书：

2各种等值关系模式：（只列出部分） (1) 双重否定律：A ? ??A

(2) 等幂律： (2a) A ? (A?A) (2b) A ? (A?A) (3) 交换律： (3a) (A?B) ? (B?A) (3b) (A?B)?(B?A)

(4) 结合律： (4a) (A?B)?C?A?(B?C) (4b) (A?B)?C?A?(B?C) (5) 分配律： (5a) A?(B?C)?(A?B)?(A?C) (5b) A?(B?C)?(A?B)?(A?C) (6) 德?摩根律：(6a) ?(A?B) ? (?B??A) (6b) ?(A?B)?(?B??A) (7) 吸收律： (7a) (A?(A?B))?A (7b) (A?(A?B))?A (7c) (A?(?A?B))?A?B (7d) (A?(?A?B))?A?B (8) 零律： (8a) (A?1) ? 1 (8b) (A?0) ? 0 (9) 同一律： (9a) (A?0) ? A (9b) (A?1) ? A (10) 排中律： (A??A) ? 1 (11) 矛盾式： (A??A) ? 0 (12) 蕴涵等值式：(A?B) ? (?A?B) (13) 等价等值式：(A?B) ? ((A?B) ? (B?A)) (14) 假言易位： (A?B) ? (?B??A) (15) 等价否定等值式：(A?B) ? (?A??B) (16) 归谬律： ((A?B) ? (A??B)) ? ?A 讲述：

根据已知的等值式，可以推演出另外许多的等值式，这种推演过程称为等值演算。 板书： 3 等值演算

讲述：在等值演算时，除了要用到上面给出的等值式外，通常还用到一些重要的演算规则 板书：

(1) 等值式模式 (2) 重言式替换规则 (3) 置换规则

置换规则：设?(A)是含有命题公式A的命题公式，?(B)是用公式B置换?中的公式A(不一定是每一处)而得到的命题公式，如果A ? B，则?(A) ? ?(B)。 示例 等值演算

例 证明A?B?C?A??B?C 讲述：

证明的方法当然可以用真值表方法，但是直接应用等值式及替换和置换规则通常会简单的多。

证明：A?B?C ? ?A ? (B ? C) 蕴涵等值式 ? (?A ? B) ? C 结合律 ? ? (A ? ?B) ? C 德?摩根律 ? (A ? ?B) ? C 置换规则和蕴涵等值式

逻辑等值演算不仅仅停留在符号级，总要用来解决实际问题，如简化语句，确定一些命题的真值等等，可以首先符号化命题，然后由已知条件列出这些命题应该满足的方程组，从而达到要求。

例 化简语句：“情况并非如此：如果他不来，那么我也不去”。 解：设p:他来，q：我去；上述语句符号化为 ? (?p ? ?q) 将词进行等值化简得 ? (?p ? ?q) ? ? (??p ? ?q) ? ? (p ? ?q) ? ? p ? q 化简后语句为：“我去了，而他没来”。

例2.3 小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先进工作者，小赵也是；你不知道小李是先进工作者，问谁是先进工作者。

解：设p:小李是先进工作者； q: 小张是先进工作者; r你知道小李是先进工作者; s: 小赵是先进工作者 则 (p?q) ? (p?r) ?(q?s) ?? r ?1

其中左边 ? (p?q) ? (?p?r) ?(?q?s) ?? r ? (p?q) ? (?q?s) ?((?p?r) ?? r)

? (p?q) ? (?q?s) ?(?p?? r) (吸收律) ? (?p? (p?q)) ? (?q?s) ?? r ? (?p? q) ? (?q?s) ?? r ? ?p? (q ? (?q?s)) ?? r ? ?p? (q ? s) ?? r ? ?p? q ? s ?? r ? 1

显然p=0,q=1,s=1,r=0；即小张和小赵是先进工作者。

讲述：

从前面给出的等值式模式可以发现，常用的六种联结词不是相互独立的，在表示逻辑关系时并不都是缺一不可的。其中有些联结词的逻辑功能可以用其它联结词代替，如: A?B ? ?A∨B， A?B ? (A?B) ∧ (B?A) ? (?A∨B) ∧ (?B∨A)， A∨B ? (A∧?B) ∨ (?A∧B)。

这里我们讨论联结词集合问题。我们把几个联结词放在一起，称为一个联结词集合。 板书：

二 联结词的全功能集 讲述：

正如前面所讲述的，在联结词集合中，一般一些联结词可以用另外的联结词来表示，这就是说有冗余联结词和独立联结词之分。

联结词组成一个集合，如果一个联结词可由集合中的其它联结词定义，则称此联结词为冗余联结词，否则称为独立联结词 板书： 1 冗余联结词，独立联结词

冗余联结词是可以由集合中的独立联结词来定义。

讲述：

而一个联结词集合称为全功能集的是指任意真值函数仅用此集合中联结词的命题公式就可以表示。如果全功能联结词集合不含冗余联结词则是极小全功能。 板书：

2 全功能集及极小全功能集： 全功能集：任意真值函数仅用此集合中联结词的命题公式就可以表示 极小全功能集：不含冗余联结词的全功能集。 讲述

一个联结词集合到底是不是全功能集，甚至是否极小全功能集，必须通过证明，即通过证明任何的真值函数都可用该集合中的联结词表示。 板书： （1）任何真值函数都能表示；

（2）定理：如果一个全功能集S1中的所有联结词都可由一个联结词集合S2定义，则S2也是全功能集 示例： {?, ∧, ∨}是全功能集, {?, ∧}, {?, ∨}, {?}都是极小全功能集 讲述：

{?, ∧}, {?, ∨}都是极小全功能集，等价联结词定义蕴涵和合取两个联结词所描述的一种命题，类似，也用一个联结词分别定义， 板书： 3 新联结词

异或联结词 ∨ :p∨q? (p∧?q) ∨(?p∧q) 与非联结词 ? :p?q?? (p∧q) 或非联结词 ? :p?q?? (p∨q) 讲述： 由于 ?p ? ?(p∧p) ? p?p

p∧q ? ??(p∧q) ? ?(p?q) ? (p?q) ? (p?q)， p∨q ? ?(?p∧?q) ? ?p??q ? (p?p) ? (q?q)，

即?, ∧, ∨都可由?定义，因为{?, ∧, ∨}是全功能集，所以{?}也是全功能集。又由于其中有且仅有一个联结词，故{?}是极小全功能集。 同理可证{?}也是极小全功能集，其中

?p ? ?(p∨p) ? p?p，

p∨q ? ??(p∨q) ? ?(p?q) ? (p?q) ? (p?q)， p∧q ? ?(?p∧?q) ? ?p??q ? (p?p) ? (q?q)。 板书：

{?}、{?}都是极小全功能集。 讲述：

最后，复习一下本节所讲述的内容。

作业：

1.5对偶与范式

[教学重点] 范式的定义和应用

[教学目的]1：理解对偶式和对偶原理的概念。 2：使学生引入范式的意义。

3：理解合取范式和析取范式的概念。 4：熟练应用主合取方式和主析取方式的求法及互化 [教学准备]

[教学方法]讲述法 [课时安排]二课时。 [教学过程] 讲述：

板书：

1．5 对偶与范式 一．对偶

1．对偶式：公式A仅含有联结词?，?，?，将A中的?，?，0，1分别换以?，?，1，0后得到的公式为A的对偶式A*。（对偶实质是一种关系，如朋友关系） 推论：（A*）*=A

2．定理1.2(广义De·Morgan定理)：A和A*互为对偶式，P1 ,P2,…, Pn 是出现在A和A*的全部的命题变项，若将A和A*写成n元函数形式，则 a）?A(P1,P2,?,Pn)?A*(?P1,?P2,?,?Pn)

*b）A(?P 1,?P2,?,?Pn)??A(P1,?P2,?,?Pn）3. 定理1.3（对偶原理）：如果A ? B，则A* ? B*。（可结合P9中等值式的内容）

示例：（1）A(p，q，r)= p?（? q?r），求? A(p，q，r)

答：A*(p，q，r)= p?（?q?r），? A(p，q，r)= ? p?（q??r）

讲述： 说明：（1）含有其他联结词的公式，需将其用等价式消去，然后再化为对偶式

（2）对偶原理不是说A与其对偶式A*等值，一般公式与其对偶式不是等值的。

判断两个命题公式是否等值，前面已经介绍了真值表法和等值演算法。相比较而言，等值演算法可能简单得多，特别是在命题变项数目较多的时候。然而有时想将一个命题公式等值变换成另一个，却可能很难找到适当的过程。

一个有效的方法是将两个命题公式等值演算成某种标准形式，然后再比较，这种标准就称为范式。 板书： 二．范式 1 基本概念：

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新幼儿教育第一章：命题逻辑 (3)全文阅读和word下载服务。