第一章：命题逻辑

1.1 命题符号化及联结词

[教学重点] 命题的概念和六个联结词的定义

[教学目的]1：使学生了解逻辑的框架，命题逻辑的基本要素是命题。 2：通过示例理解命题的概念。

3：通过示例理解合取、析取、异或、蕴涵、等价的含义，了解逻辑语言的精确性，为学习逻辑学打好基础。 4：学会命题符号化的方法。 [教学准备]

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

逻辑是解决推理方法的学科，中心是推理，基本要素是命题，称为命题逻辑。 数理逻辑则是用数学方法研究推理； 首先要理解命题是什么，然后了解怎样用数学方法描述命题，甚至逻辑推理。后者是命题符号化的问题。 板书：

第一章 命题基本概念 1.1 命题及其符号化 讲述： 首先讨论命题。 板书： 一 命题

A) 概念：

能判断真假的陈述句。 判断要点：

a 陈述句；b 或真或假，唯一真值； 讲述： 例：

(1) 地球是圆的； 真的陈述句，是命题 (2) 2+3=5； 真的陈述句，是命题 (3) 你知道命题逻辑吗？ 非陈述句，故非命题 (4) 3-x=5； 陈述句,但真假随x的变化而变化，非命题 (5) 请安静！ 非陈述句，故非命题 (6) 火星表面的温度是800?C； 现时不知真假的陈述句，但只能要么真要 么假，故是命题 (7) 明天是晴天； 尽管要到第二天才能得知其真假，但的确 是要么真要么假，故是命题 (8) 我正在说谎； 无法得知其真假，这是悖论

注意到(4)不是命题，后续章节中会提到，这被称为谓词，命题函数或命题变项。 板书：

B) 命题的真值表示： 真：1或T 假：0或F C) 分类：

a 简单命题，通常用p,q,r,…,等表示命题变项和命题常项； b 复合命题，由简单命题和联结词构成；

讲述：

简单命题可以简单地用单个字母表示，但复合命题还包含了联结词，多个命题变项由联结词联结起来成为复合命题。所以还需要考虑联结词的问题。 板书：

二 逻辑联结词 讲述： 首先最为简单的一种情况，就是日常语言中所说的“不”，这是对原有意思的的否定，所以称为否定式 板书：

1) 否定式和否定联结词：

命题p的非或否定，称为p的否定式，表示为?p；符号?即为否定联结词。用表格表示：

p ?p T F F T 讲述：

严格说，?p不是复合命题。 示例：p：今天天气好；?p：今天天气不好

p：2＋5 > 1； ?p： 2+5≤1；在此情形下，p为真，?p为假。

讲述： 问题：北京和上海都是中国的直辖市。显然这个句子可分成两个句子，中间由“和”、“且”之类的联结词联结。这类的联结词我们统称为“合取”。 板书：

2）合取式和合取联结词

p且q称为p,q的合取式，记为p?q；符号?即为合取联结词。

p q p∧q T T T T F F F T F F F F 逻辑“与”。 讲述： 相应的日常用语还有一些。 板书：

“既…又…”，“不但(仅)…而且…”，“虽然…但是…”。 讲述：

例：

1) p: 今天大太阳，q: 今天热，p∧q: 今天大太阳且热；

2) p: 今天上课有人迟到，q:2+5>1, p∧q: 今天上课有人迟到且2+5>1；

3)p: 李平聪明，q: 李平用功，p∧?q: 李平虽然聪明，但不用功； 讲述：

注意到2)中的结果，我们可以用逻辑联结词来联结两个日常生活中无关的命题。另外也要注意日常语言中的“和”，不一定都能用∧表示。

示例：“新闻和报纸不分家”，“我和你是同学”。 讲述： “或”也是非常常用的联结词。 例：

(1) 文文或华华今天出差。 (2) 他今天骑车或走路来上课。 讲述：

(1)一般情况下两个人可能同时去出差，即可以同时为真，是相容的，所以是“相容或”。 板书： 相容或 讲述：

(2)在这两种情况下，或者发生一种，或者都不发生(如他今天是乘公共车来上课的)，但不可能二者同时发生，即不可能二者同时为真，所以是“相斥或”。在自然语言中类似的“相斥或”是很多的，又如“刘苘或李兰是三班班长”。 板书： 相斥或 我们可以看到在日常语言中，“或”具有多义性，但我们用符号表示时，却必须避免这种歧义性。通常把相容或称为“析取”，而相斥或则称为“异或”。 板书：

3）析取式和析取联结词

p或者q称为p，q的析取式，记为p∨q；符号?即为析取联结词。

p q p∨q T T T T F T F T T F F F 逻辑“或” 讲述： “如果…则…”也是一类常见的联结词。这是有条件和结论的一类，称为“条件式”，也称为“蕴涵式”。 板书：

4）蕴涵式和蕴涵联结词

如果p则q称作p、q的蕴涵式，记为p?q。?为蕴涵联结词，p、q分别为蕴涵式的前件和后件。 讲述： 示例:

一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言？

父亲的可能情况有如下四种：

(1) 星期天天气好，带儿子去了动物园； (2) 星期天天气好，却没带儿子去动物园；

(3) 星期天天气不好，却带儿子去了动物园； (4) 星期天天气不好，也没带儿子去动物园。

显然，(1), (4)两种情况父亲都没有食言；(3)这种情况和父亲原来的话没有相抵触的地方，当然也不算食言；只有(2)这种情况，答应的事却没有做，应该算是食言了。(2)对应着“前件真后件假”的情况，使得蕴涵式为假，而其它三种情况都使得蕴涵式为真。 板书：

p q p?q T T T T F F F T T F F T 讲述：

这里注意到：在蕴涵式p?q中，p是q的充分条件，q是p的必要条件。这类的联结词还有： 板书：

p?q：“只要p就q”，“p仅当q”，“只有q才p”等 讲述：

蕴涵式的一个应用：数学归纳法

(1)证明P(n0)成立；(2)证明当k≥n0时P(k)?P(k+1)总是成立。

在(2)中，P(k)?P(k+1)总是成立，意味着P(k)?P(k+1)的真值为T，从而只可能是上述表中的第1, 2, 4种情形，而(1)中证明了前件为真，所以后件也一定为真。 讲述： 前面讲述描述了充分条件或必要条件的表示，现在我们可以表示充要条件了： “p是q的充要条件”，“p是q的充分条件”且“p是q的必要条件”，可以用蕴涵和合取两者描述。 板书：

p?q∧q?p 讲述：

这个表达式较为复杂，所以用一个联结词“等价”简单表示。自然语言中通常表述为“当且仅当” 板书：

5）等价式和等价联结词

p当且仅当q称作p、q的等价式，记为p?q。?称为等价联结词。

p p?q q T T F F T F T F T F F T 讲述：

以上介绍了五种常用的逻辑联结词以及与之相关的复合命题。这些联结词反映了复合命题及其支命题之间抽象的逻辑关系。复合命题的符号化一般可以根据上述定义进行，基本步骤如下： 板书： 符号化基本步骤：

1) 找出各个支命题，并逐个符号化； 2) 找出各个连接词，符号成相应联结词；

3) 用联结词将各支命题逐个联结起来； 示例：将下列命题符号化：

(1) 辱骂和恐吓决不是战斗；

(2) 李瑞和李珊是姐妹；

(3) 除非天气好，否则我是不会去公园的；

(5) 李明是计算机系的学生，他住在312室或313室． 讲述： 分析并符号化，强调在进行命题符号化以前，必须明确含义，删除歧义，这是命题翻译的关键之点。

(1) p：辱骂是战斗； q：恐吓是战斗。 符号化为?p∧?q。

(2) p：李瑞和李珊是姐妹。 符号化为p。

(3) p：今天天气好；

q：我去公园。 符号化为q?p。

(4) p：李明是计算机系的学生；

q：李明住在312室； r：李明住在313室。

因为李明不可能既住在312室又住在313室，符号化为p∧((q∧?r) ∨ (?q∧r))或者p∧(q ∨r)

讲述：

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

作业：

1.2 命题公式和真值赋值

[教学重点] 合式公式及层次，解释的含义，真值表的构成。

[教学目的]1：使学生了解合式公式和公式层次的定义，理解递归定义法的方法。 2：学会描述公式的形成过程。

3：理解解释的含义，领会公式分类的要点。

4：使学生了解并学会应用真值表的构成方法。

5：复习并进一步理解命题逻辑的基本概念。 [教学准备]

[教学方法]讲述法 [课时安排]二课时。 [教学过程] 讲述： 复习并示例：判断是否式命题，如果是，则符号化。

1) 922+97+1； 2) x + 5 > 6

3) 理发师只给所有那些不给自己理发的人理发；（罗素悖论） 4) 李兰现在在宿舍或在图书馆里； 5) 蓝色和黄色可以调配成绿色；

6) 如果晚上小王做完了做业并且没有其他事情，他就看电视或看电影。 问题： 在6)中获得一个长串的字符串，这里当然表示了一个命题，但是不是任何一个字符串能表示一个命题呢？或者称为命题公式呢？

抽象地说，命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式。 板书 1.2合式公式及其解释 讲述： 首先自然先要了解什么公式。 板书：

一 合式公式

1) 合式公式：

(1) p, q, r, … ,1 , 0 是合式公式；

(2) 如果A是合式公式，则?A也是；

(3) 如果A和B是合式公式，则?p、p ? q、p ? q、p ? q、p ? q也是； (4) 有限次应用(1)-(3)构成的符号串才是合式公式。 讲述： 上述定义方法称为递归定义法（递归就是一个过程直接或间接地调用自己），递归法定义是离散数学中常用的方法。其中，（1）是递归定义的基础，直接规定简单的内容；（2）, （3）是递归定义的归纳，规定了是由简单到复杂的过程；（4）是递归定义的界限，规定了满足前述（1）~（3）条件的最小范围。（递归算法在计算机中容易实现，如C语言中的汉诺塔、n的阶乘、求两个数的最小公约数就是用递归的方法实现的）

板书：

递归定义法：递归基础、递归归纳、递归界限 讲述

在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼花缭乱，如((p?(q?r))?((p?q)?(r?s)))，共有6对括号，书写简单，可以省略括号 板书：

省略括号的约定：

(1) 公式最外层的括号可以省略；

(2) 规定联结词的运算优先级别由高到低是：?、?、?、?、?，若无括号，优先级高的先运算；

(3) 若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。 讲述：

按照上述约定，((p?(q?r))?((p?q)?(r?s)))省略了三对括号简化为p?(q?r) ?(p?q)?(r?s)。省略括号只是让公式书写简便，但并不能改变其复杂性。 示例

(1) (((p?q)∧(q?r)) ?(p∨r)) p、q是公式，(p?q)是公式；q、r是公式，(q?r)是公式；((p?q)∧(q?r))是公式；p、r是公式，(p∨r )是公式；(((p?q)∧(q?r)) ?(p∨r))是公式。 这样一个命题公式的形成过程简单表述为： p，q，(p?q)；q，r，(q?r)；((p?q)∧(q?r))；p，r，(p∨r)；(((p?q)∧(q?r)) ?(p∨r))。 (2) ((p∧q)?qr) p，q，(p∧q)；q，r，qr不是；((p∧q)?qr)不是。 讲述： 显然，有些公式的字符串很长，有些很短，甚至只有单个字母，这样公式的复杂性必然有所不同，为了描述这种复杂性，引入公式层次来描述。 板书：

二 合式公式的层次：

(1) 如果A是单个命题常项或命题变项p,q,r,s,…,0,1，则称A是0层公式； (2) 称A是n+1(n?0)层公式，是指A符合下列情况之一： (a) A=?B，B是n层公式；

(b) A=(B?C)，其中B、C分别是i层和j层公式，且n=max(i,j)； (c) A=(B?C)，其中B、C的层次同(b)； (d) A=(B?C) ，其中B、C的层次同(b)； (e) A=(B?C)，其中B、C的层次同(b)； 示例：

(1) (p?q)∨(r∧(p∨s)) (2) ?q?(p∨s)

(1) p, s是0层公式，p∨s是1层公式; r是0层公式, r∧(p∨s)是2层公式；p,q是0层公式，但p?q是1层公式；(p?q)∨(r∧(p∨s)) 是3层公式。公式层次是3。

(2) q是0层公式, ?q是1层公式；p, s是0层公式，p∨s是1层公式; ?(p∨s) 是2层公式；但?q?(p∨s)不是公式。 讲述：

一般来说，一个含有命题变项的命题公式，其真值是不确定的。只有给其每个命题变项都指定确定的真值，命题公式才会有确定的真值。

给定一个真值，就是给命题变项一个赋值，相当于给定一个日常语言中某个具体的句子，即给定一个解释。 板书：

三 真值赋值

令A是一命题公式，p1,p2,…pn是出现在A中的所有命题变项，给p1,p2,…pn指定一组真值，称为对A的一个赋值或解释。

成真赋值：若指定的一组值使得A的值为真，称这组值为A的成真赋值； 成假赋值：若指定的一组值使得A的值为假，称这组值为A的成假赋值。 一个含有n个命题变项的命题公式，共有2n个赋值。 示例

例 已知A是含命题变项p,q,r的命题公式，其成真赋值为000,010,101，求?A的成真赋值和成假赋值。

?A的成真赋值为：001,011,100,110,111；成假赋值为：000,010,101。

例 已知A、B是含命题变项p,q,r的命题公式，A成真赋值为000, 011, 111，B成真赋值为000, 010, 100，求A?B、A?B的成真赋值。

A?B：000,001,010, 100,101,110,111 A?B：000,001,101,110 讲述： 上面是用具体的真值来指定，如果用另外的命题公式来指定，这时再不能称为赋值了，这称为替换。 板书：

替换实例：用命题形式B1,B2,…Bn分别替换命题形式A中的命题变项p1, p2,…pn得到的新的命题形式。 示例：

例如，p?(?p?q)，以p?q替换p，以r替换q，则得到原式的一个替换实例为(p?q)?(? (p?q )?r)。 讲述：

我们知道一个公式有多个赋值，一般来说既有成真赋值，又有成假赋值，但完全可能只有成真赋值，或全是成假赋值，

根据这种不同，我们将公式分成不同类型。 板书：

命题公式的分类：

① 重言式：值总是为真的命题公式。 讲述：

如果一个蕴涵式A?B是重言式，则记作A?B，表示由A可推导出B；同样如果一个等价式A?B是重言式，则记作A?B，表示A和B等值。

注意：?和?不是逻辑联结词，它们表示的分别是逻辑推理和逻辑等值运算，下面的章节将分别讨论。 板书：

② 矛盾式：值总是为假的命题公式。

③ 可满足式：至少存在一组赋值是成真赋值的命题公式。 讲述：

从定义看来，重言式也是可满足式，不过还是将命题公式分成三类：重言式、矛盾式、可满足式。这种分类主要是为了体现重言式的重要性，实际上在命题逻辑中公理、定理都

是重言式，在自然推理的过程中，一个正确的推理也必须是重言式。 板书：

设A是命题公式，则

(1) 若A是重言式，则A的任何替换实例都是重言式； (2) 若A是矛盾式，则A的任何替换实例都是矛盾式； 示例： 例 合式公式(p∧q)∨?(p∧q)、(p∧q?r)∨?(p∧q?r)都是p∨?p的一个替换实例，而p∨?p是重言式，所以它们也是重言式。 板书：

四 真值表

1) 定义：将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表 讲述：

所有命题变项取一组值，即是命题公式的一个赋值，所以真值表包含了所有赋值情况下的公式所取得的值。

而一个赋值使得公式为真，就称为成真赋值，为假就是成假赋值，所以从真值表可以直接获得一个命题公式的成真赋值、成假赋值。 板书：

2) 构造方法：

①找出给定命题公式中的所有命题变项，列出所有可能的取值：

p q T F T F r T T T T F F F F T F ②由低到高列出命题公式的各层次；

③计算各层次的的值，直至最后计算命题公式的值。

示例

例 1.16 构造合式公式(p∨ (p∧q)) ?? (p∨q)的真值表： 真值表： p q p∧q p∨ (p∧q) p∨q ?(p∨q) (p∨(p∧q)) ??(p∨q) 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0

讲述：上述真值表的构成方法中，如果公式层次比较高，则表的宽度将变得很宽，甚至无法写下，因此可采用另一种形式， 板书：

② 按照公式形成过程，标出各层对应的联结词所对应的真值； ③ 直至最后计算命题公式的值。 示例：

p q 0 0 0 1 1 0 1 1 步骤 (p ∨ (p∧q)) 0 0 0 0 1 0 1 1 ② ① ? ? 1 1 1 0 0 0 0 0 ③ ② (p∨q) 0 1 1 1 ①

讲述：

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

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 基本概念：

本文来源：https://www.bwwdw.com/article/vhwh.html