第一章命题逻辑基本概念1

1.1命题及其符号化

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

［教学H的］1：使学生了解逻辑的框架，命题逻辑的基本要素是命题。

2：通过示例理解命题的概念。

3：通过示例理解合取、析取、异或、蕴涵、等价的含义，了解逻辑语言的精

确性，为学习逻辑学打好基础。

4：学会命题符号化的方法。

［教学准备］

［教学方法］讲述法

［课时安排］二课时。

［教学过程］

讲述：

逻辑是解决推理方法的学科，中心是推理，基本要素是命题，称为命题逻辑。

数理逻辑则是用数学方法研究推理；

首先要理解命题是什么，然后了解怎样用数学方法描述命题，甚至逻辑推理。后者式

命题符号化的问题。

板书：

第一章命题基本概念

1.1命题及其符号化

讲述：

首先讨论命题。

板书：

-命题

A）概念：

在二值逻辑中，命题是或真或假，而不会同时又真又假的陈述句。

判断要点：

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

讲述：

例：

(1)地球是圆的；真的陈述句，是命题

⑵2+3=5；真的陈述句，是命题

(3)你知道命题逻辑吗？非陈述句，故非命题

⑷3-x=5；陈述句，但真假随X的变化而变化，非命题

(5)请安静！非陈述句，故非命题

(6)火星表面的温度是800℃；现时不知真假的陈述句，但只能要么真要

么假，故是命题

⑺明天是晴天；尽管要到第二天才能得知其真假，但的确

是要么真要么假，故是命题

2

(8)我正在说谎；无法得知其真假，这是悖论

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

讲述：

类似一般的事物，也有不同的命题，分成不同的类型。

板书：

B)分类：

a简单命题，通常用p,q,r,…，等表示命题变项，命题常项用1(T),0(F)表示；

b复合命题，由简单命题和联结词构成；

讲述：

简单命题可以简单地用单个字母表示，但复合命题还包含了联结词，多个命题变项由

联结词联结起来成为复合命题。所以还需要考虑联结词的问题。

板书：

二逻辑联结词

讲述：

首先最为简单的一种情况，就是日常语言中所说的“不”，这是对原有意思的的否定,

所以称为否定式

板书：

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

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

Pf

TF

FT

讲述：

严格说，「p不是复合命题。

示例：p：今天天气好：「p：今天天气不好

P：2+5>1；[p：2+5W1；在此情形下，p为真,为假。

讲述：

问题：北京和上海都是中国的直辖市。显然这个句子可分成两个句子，中间由“和”、

“且”之类的联结词联结。这类的联结词我们统称为“合取”。

板书：

2)合取式和合取联结词

p且,称为p国的合取式，记为符号人即为合取联结词。

pqp'q

TTT

TFF

FTF

FFF

逻辑“与”。

讲述：

相应的日常用语还有一些。

板书：

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

讲述：

3

例：

Dp：今天大太阳，q:今天热，p/\q；今天大太阳且热；

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

讲述：

注意到2)中的结果，我们可以用逻辑联结词来联结两个日常生活中无关的命题。另外

也要注意日常语言中的“和”，不一定都能用人表示。

示例：“新闻和报纸不分家”。

讲述：

“或”也是非常常用的联结词。

例：

(1)文文或华华今天出差。

(2)他今天骑车或走路来上课。

(3)从理科2号楼到图书馆要3分钟或5分钟。

讲述：

(1)一般情况下两个人可能同时同以去出差，即可以同时为真，是相容的，所以是“相

容或”。

板书：

相容或

讲述：

(2)在这两种情况下，或者发生•种，或者都不发生(如他今天是乘公共车来上课的)，

但不可能二者同时发生，即不可能二者同时为真，所以是“相斥或”。在自然语言中类似的

“相斥或”是很多的，又如“刘荷或李兰是三班班长”。

板书：

相斥或

讲述：

(3)也是自然语言中的“或”，可能并不代表相容相斥，而表示一种大约的含义，即从

理科2号楼到图书馆大约要用3到5分钟的时间，又如：“他作了二三十道数学题”。

我们可以看到在日常语言中，“或”具有多义性，但我们用符号表示时，却必须避免

这种歧义性。通常把相容或称为“析取”，而相斥或则称为“异或”。

板书：

3)析取式和析取联结词

P或者g称为小g的析取式，记为pVq；符号v即为析取联结词。

pq

TTT

TFT

FTT

FFF

逻辑“或”

4)异或式和异或联结词

p或者(7中只能一个为真称为的异或式，记为pvq；符号v即为异或联结词。

Pqp斗q

TTF

TFT

4

FTIT

FF|F

讲述：

“如果…则…”也是一类常见的联结词。这是有条件和结论的一类，称为“条件式”,

也称为“蕴涵式”。

板书：

4)蕴涵式和蕴涵联结词

如果p则q称作p、q的蕴涵式，记为f为蕴涵联结词，p、q分别为蕴

涵式的前件和后件。

讲述：

示例:

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

食言？

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

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

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

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

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

显然，(1),(4)两种情况父亲都没有食言；(3)这种情况和父亲原来的话没有相抵触的地

方，当然也不算食言；只有(2)这种情况，答应的事却没有做，应该算是食言了。(2)对应着

“前件真后件假”的情况，使得蕴涵式为假，而其它三种情况都使得蕴涵式为真。

板书：

Pqprq

TTT

TFF

FTT

FFT

讲述：

这里注意到：在蕴涵式p-4中，。是夕的充分条件，夕是p的必要条件。这类的联结

词还有：

板书：

pf/"只要p就夕”，“p仅当“只有g才p”等

讲述：

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

(1)证明P(〃o)成立；(2)证明当时P(A)-P伏+1)总是成立。

在⑵中，P(k)-P(k+1)总、是成立,意味着P/)fP(%+l)的真值为T,从而只可能是表1.5

中的第1,2,4种情形，而(1)中证明了前件为真，所以后件也一定为真。

讲述：

前面讲述描述了充分条件或必要条件的表示，现在我们可以表示充要条件了：

“P是q的充要条件”，“p是q的充分条件”且“p是q的必要条件”，可以用蕴涵和

合取两者描述。

板书：

5

讲述：

这个表达式较为复杂，所以用一个联结词“等价”简单表示。

板书：

5)等价式和等价联结词

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

pqpaq

TTT

TFF

FTF

FFT

讲述：

以上介绍了六种常用的逻辑联结词以及与之相关的复合命题。这些联结词反映了复合

命题及其支命题之间抽象的逻辑关系。复合命题的符号化一般可以根据上述定义进行，基

本步骤如下：

板书：

符号化基本步骤：

1)找出各个支命题，并逐个符号化；

2)找出各个连接词，符号成相应联结词；

3)用联结词将各支命题逐个联结起来；

示例：将下列命题符号化：

(1)李明是计算机系的学生，他住在312室或313室.

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

(3)李瑞和李珊是姐妹。

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

讲述：

分析并符号化，强调在进行命题符号化以前，必须明确含义，删除歧义，这是命题翻

译的关键之点。

(1)P-.李明是计算机系的学生；

q：李明住在312室；

r：李明住在313室。

因为李明不可能既住在312室又住在313室，所以这里应该用*,而不用V,符号化

为pA(g-V-r)»

(2)p-.辱骂是战斗；

q：恐吓是战斗。

符号化为可八-ig。

(3)p：李瑞和李珊是姐妹。

符号化为p。

(4)p：今天天气好：

q：我去公园。

符号化为qfp。

作业：

习题1.1,1.2

6

1.2合式公式和真值赋值

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

［教学目的］1：使学生了解合式公式和公式层次的定义，理解递归定义法的方法。

2：学会描述公式的形成过程。

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

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

5：理解真值函数的含义，理解命题的多种形式的实质本质。

6：复习并进一步理解命题逻辑的基本概念。

［教学准备］

［教学方法］讲述法

［课时安排］二课时。

［教学过程］

讲述：

复习并示例：判断是否式命题，如果是，则符号化。

1)922+97+1；

2)x+5>6

3)理发师只给所有那些不给自己理发的人理发；

4)李兰现在在宿舍或在图书馆里；

5)蓝色和黄色可以调配成绿色；

6)如果晚上小王做完了做业并且没有其他事情，他就看电视或看电影。

问题：

在6)中获得一个长串的字符串，这里当然表示了一个命题，但是不是任何一个字符串

能表示一个命题呢？或者称为命题形式呢？

命题形式：各种复合命题的符号化表达式，即为此命题的命题形式，它给出的是复合

命题及其简单命题之间真值关系的逻辑骨架。

实际上，只有那些称为“公式”的字符串才能表示命题。而一个公式还必须给定一个

解释，才能得知具体的含义。

板书

1.2合式公式及其解释

讲述：

首先自然先要了解什么公式。

板书：

一合式公式

命题形式必定是合式公式。

1)合式公式：

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

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

(3)如果A和B是合式公式，则由逻辑联结词联结A和B的符号串也是；

7

(4)有限次应用(1)-(3)构成的符号串才是合式公式。

讲述：

上述定义方法称为递归定义法，递归法定义是离散数学中常用的方法。其中，1)是递

归定义的基础，直接规定简单的内容；2),3)是递归定义的归纳，规定了是由简单到复杂的

过程；4)是递归定义的界限，规定了满足前述1)〜3)条件的最小范围。

板书：

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

讲述

在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼

花缭乱，如((pA(qvr))—((pvq)A(rvs))),共有6对括号，书写简单，可以省略括号

板书：

省略括号的约定：

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

(2)规定联结词的运算优先级别由高到低是：「、人、v、V,一、一，若无括号，优先

级高的先运算；

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

讲述：

按照上述约定,((pA(qvr))-»((pvq)A(rvs)))省略■了三对括号简化为pA(qvr)->(pvq)A(rvs)o

省略括号只是让公式书写简便，但并不能改变起复杂性。

示例

(1)((g-4)八(夕-r))-»(pVr))

p、g是公式，S—q)是公式；外,,是公式，(qf)是公式；((p->g)A(qf))是公式；p、

，是公式，(pVr)是公式；(((pfq)八(qfr))r))是公式。

这样一个命题公式的形成过程简单表述为：

p,q,(pfq);q,r,(«->厂)；((p->?)A(9->r));p,r,(pVr)；(((p-»q)A(qf))->(p

Vr))«

(2)((p八

p，q，(p八q);q，r,qr不是；((pAq)f")不是。

讲述：

显然，有些公式的字符串很长，有些很短，甚至只有单个字母，这样公式的复杂性必

然有所不同，为了描述这种复杂性，引入公式层次来描述。

板书：

二合式公式的层次：

(1)如果A是单个命题常项或命题变项p,q,r,s,...,0,1,则称A是0层公式；

(2)称A是n+l(n20)层公式，是指A符合下列情况之一：

(a)A=->B,B是n层公式；

(b)A=(AAB),其中B、C分别是i层和j层公式，且11=11^(q)；

(c)A=(AvB),其中B、C的层次同(b)；

(d)A=(AvB),其中B、C的层次同(b)；

(e)A=(A-B),其中B、C的层次同(b)；

(f)A=(AcB),其中B、C的层次同(b)；

(3)若A的最高层次为k,则称A是k层公式。

8

讲述:

叙述中出现的“=”即为通常意义上的等号。

上述两个定义中，不仅有p,q,r,s,…,0,1等，而且引入了大写的A、B、C等代表任意

的合式公式，不同于p,q,r,…，及联结词构成的表示某个具体的公式，两者是命题逻辑中不

同层次上的语言。

示例：

(l)(p^WA(pV5))(2)[4](pVs)

(l)p,s是0层公式，p\/s是1层公式;，是0层公式,rA(p\/s)是2层公式；是0层

公式，但是1层公式；(p^^)V(rA(pV5))是3层公式。公式层次是3。

(2)g是0层公式,是1层公式；p,s是0层公式，p\Js是1层公式;->(pVs)是2层

公式；但Vs)不是公式。

讲述：

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

项都指定确定的真值，命题形式才会有确定的真值。

给定一个真值，就是给命题变项一个赋值，相当于给定一个日常语言中某个具体的句

子，即给定一个解释。

板书：

三真值赋值

令A是命题形式，PI，P2,…Pn是出现在A中的所有命题变项，给PI，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,Oil,111,B成真

赋值为000,010,100，求N—B、B的成真赋值。

Z—B：000,001,010,100,101,110,111

Z—B：000,001,101,110

讲述：

上面是用具体的真值来指定，如果用另外的命题形式来指定，这时再不能称为赋值了，

这称为替换。

板书：

替换实例：用命题形式B1,B2,…Bn分别替换命题形式A中的命题变项必，P2,…Pn得到

的新的命题形式。

示例：

例如,pf(->p->q),以p—q替换p,以r替换q,则得到原式的一个替换实例为(p->q)f(->

(pfq)f)。

讲述：

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

9

只有成真赋值，或全是成假赋值，

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

板书：

命题形式的分类：

①重言式：值总是为真的命题形式。

讲述：

如果一个蕴涵式AfB是重言式，则记作A=B,表示由A可推导出B；同样如

果一个等价式A―B是重言式，则记作AoB,表示A和B等值。

注意：=和=不是逻辑联结词，它们表示的分别是逻辑推理和逻辑等值运算，下

面的章节将分别讨论。

板书：

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

③可满足式。

讲述：

从定义看来，重言式也是可满足式，不过还是将命题形式分成三类：重言式、矛盾式、

可满足式；即可满足式不包含重言式。这种分类主要是为了体现重言式的重要性，实际上

在命题逻辑中公理、定理都是重言式，在自然推理的过程中，一个正确的推理也必须是重

言式。

板书：

设A命题形式，则

(1)若A是重言式，则A的任何替换实例都是重言式；

(2)若A是矛盾式，则A的任何替换实例都是矛盾式；

示例：

例合式公式⑦八g)V-<p/\q)、仍八都是p7rp的一个替换实例，

而是重言式，所以它们也是重言式。

板书：

1.3真值表和真值函数

四真值表

1)定义：命题形式在其命题变项取所有可能真值时对应的真值列成的表。

讲述：

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

下的公式所取得的值。

而一个赋值使得公式为真，就称为成真赋值，为假就是成假赋值，所以从真值表可以

直接获得一个命题公式的成真赋值、成假赋值。

板书：

2)构成方法：

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

10

②由低到高列出命题形式的各层次；

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

示例

例1.16构造合式公式(pv(p八q))(pVq)的真值表:

真值表：

pqp/\qpV(pAq)pVqTpVq)(pV(pAq))-TpVq)

0000011

0100101

1001100

1111100

讲述：上述真值表的构成方法中，如果公式层次比较高，则表的宽度将变得很宽，甚至无

法写下，因此可采用另一种形式，

板书：

②按照公式形成过程，标出各层对应的联结词所对应的真值；

③直至最后计算命题形式的值。

示例：

pq(pV(pAq))-»(pVq)

0000110

0100101

1010001

1111001

步骤②®③②®

板书：

五真值函数：

一个n元真值函数是指F：{0,1}"f{(),1},(n》l),即此函数以n个命题变项为变

元，其定义域和值域均由真、假两值构成。

讲述：

真值函数同样可以用真值表表示，这是真值函数在其命题变项所有可能取值下得到的值

列成的表。对于n个命题变项，可能的赋值有2n个。对于每个赋值，真值函数的取值

又有真、假两种可能。因此，对于n个命题变项来说，它们可以构成的不同的其值函数

有22"个。

示例:

11

如n=0,两个0元函数为0,l;n=l,有四个一元真值函数,n=2时有16个，下表中列出其中

的几个：

PqFGHRS

0000111

0100101

1001001

1101111

F：-.(p^q)Aq-•(Pvrp)A-.(qv-.q)

G:pv(qv->q)PA(qv-.q)

H:pfqTPvq)

R:p<->q

s：(pfq)Vp

复习并板书：

本章要点：

♦命题：或真或假的陈述句，不能又是真又是假；

♦复合命题：用联结词将若干个简单陈述句组合成的复合陈述句；

♦合取式：p/\Q,逻辑“与"，p、q同时为真，合取式才为真；

♦析取式：pVq,逻辑“或”，p、g同时为假，析取式才为真；

♦异或式：pWy,p、g不同时.异或式才为真；

♦蕴涵式：piq,前件p为真后件g为假时条件式才为假：

♦等价式：pcq,P、夕相同时等价式才为真，也称"同或"；

♦合式公式：递归定义参见定义1.7；

♦公式层次：递归定义参见定义1.8；

♦赋值：给合式公式中的所有命题变项指定一组真值，有成真赋值、成假赋值；

♦公式分类：重言式、矛盾式和可满足式；

♦替换实例：用多个命题公式分别处处替换命题公式A中对应命题变项所得新的命题公

式；

♦真值表：命题形式/在其所有可能的赋值下取得的值列成的表；

♦〃元真值函数：F:{0,1}0-{0,1}(«>1)»

作业：

习题1.82),4),6),8)

习题1.9H,S

习题1.41),3),5),7)

习题1.5

习题1.61),2)

习题1.7

12

2.1等值关系及联结词全功能集

［教学重点］等值关系及演算的规则

［教学目的］1：使学生了解等值算是逻辑理论的一个基本内容。

2：理解等值关系的含义，并理解等值式模式及其重要性。

3：理解并熟记等值演算的规则

4：理解全功能集的含义记应用。

［教学准备］

［教学方法］讲述法

［课时安排］二课时。

［教学过程］

讲述：

前面已经提到，等价式A-B为重言式，记为AoB,称为等值关系。并提到这是逻

辑理论的一个基本内容。

本章将主要讨论等值关系的有关内容，本节首先讨论了解什么等价关系，并详细阐述

等值演算的各种规则，然后再谈谈联结词的有关问题。

板书：

第二章命题逻辑等值演算

'等值关系

1概念：

如果两个逻辑形式对其中的命题变项的任何取值，都具有相同的值，则称它们是相

等的。另一种说法即为前面所提到的，A、B等值是指等价式A-B为重言式，记为AoB。

讲述：

两个命题形式是否等值可以通过真值表来判断或验证。下面给出一些常用的等值式,

其中很多正是通常所说的的布尔代数或逻辑代数的主要组成部分。

板书:

2各种等值关系模式：(只列出部分)

(1)双重否定律：A=「「A

(2)等幕律:(2a)Ao(AAA)(2b)Ao(AvA)

(3)交换律：(3a)(AAB)O(BAA)(3b)(AVB)O(BVA)

(4)结合律：(4a)((AAB)AC)»(AA(BAC))(4b)((AVB)VC)O(AV(BVC))

(5)分配律：(5a)(AV(BAC))O((AVB)A(AVC))(5b)(AA(BVC))<=>((AAB)V(AAC))

(6)德•摩根律:(6a)-I(AAB)(―iBv—iA)(6b)-i(AvB)<z>(―IBA-iA)

(7)吸收律：(7a)(AV(AAB))OA(7b)(AA(AVB))«A

(7c)(AV(-.AAB))«AVB(7d)(AA(->AVB))<=>AAB

(8)零律：(8a)(Avl)o1(8b)(AAO)O0

(9)同一律:(9a)(AvO)oA(9b)(AA1)<=>A

(10)排中律:(Av―iA)1

13

(11)矛盾式：(AMA)OO

(12)蕴涵等值式：(AfB)oJAvB)

(13)等价等值式：(AcB)o((A->B)A(BfA))

(14)假言易位：(A-B)o(「Bf「A)

(15)等价否定等值式：(A—B)o(「A>B)

(16)归谬律：((A—B)A(A-[B))o-1A

(17)香农定理：

(「尸(X],%2,X",1,0，人,v))OF,0,1,V,A))

示例：香农定理应用

对于公式…,p“,0,1,八，V)，完全可能省略了括号，这时应用香农定理时要

注意将省略的括号添加上，否则等值演算会出问题。

如：-.(pV^Ar)o->(/?V(^Ar))<=>但如果不将省略的括号添上，就演

算成显然该式是先运算而不是先运算结果不正确。

板书：

(18)对偶定理

对偶式：

公式A仅含有联结词「，A,V,则将A中的人，v,0,1分别换以v,A,1,0

后得到的公式为A的对偶式A*。

a)香农定理用对偶式表示即为：

(「E(X|,…,X“))O(尸*(7],72，…，))

b)如果AoB,则A*oB*。(对偶定理)

注意(17)(18)中的A、B、F均仅含有联结词「，A,V。

示例：类似香农定理应用，也要注意括号问题。

讲述：

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

板书：

3等值演算

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

板书：

(1)等值式模式

(2)重:言式替换规则

(3)置换规则

置换规则：设中是含有公式A的命题形式，3是用公式B置换①中的公式A(不一定是

每一处)而得到的命题形式，如果AoB,则①。中。

示例等值演算

例证明AfBVC=AA「BFC

讲述：

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

单的多。

证明：A->BvCo「Av(BvC)蕴涵等值式

14

=(-iAvB)vC结合律

—।(AA—iB)vC德•摩根律

u>(AA「B)-C置换规则和蕴涵等值式

逻辑等值演算不仅仅停留在符号级,总要用来解决实际问题，如简化语句，确定•些

命题的真值等等，可以首先符号化命题，然后由已知条件列出这些命题应该满足的方程组,

从而达到要求。

例化简语句：“情况并非如此：如果他不来，那么我也不去”。

解：设p:他来，q：我去；上述语句符号化为

「(「pT「q)将词进行等值化简得

-!(->p-»-.q)=-i(-upv->q)

0r(Pv-.q)

<=>-ipAq

化简后语句为：“我去了，而他每来”。

例2.3小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张

是先进工作者，小赵也是；你不知道小李是先进工作者，问谁是先进工作者。

解：设p:小李是先进工作者；q:小张是先进工作者；

r你知道小李是先进工作者；s:小赵是先进工作者

贝II(pvq)A(p->r)人(q—s)八一>r=1

其中左边=(pvq)A(-,pvr)A(-,qvs)A->r

=(pvq)A(->qvs)A((->pvr)A-Ir)

<=>(pvq)A(->qvs)A(->PA->r)(吸收律)

=(-ipA(pvq))A(-.qvs)A->r

o(->pAq)A(->qvs)A->r

=->pA(qA(-.qvs))A->r

o-.pA(qAs)A->r

0->pAqAsA->r

o1

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

讲述：

从前面给出的等值式模式可以发现，常用的六种联结词不是相互独立的，在表示逻辑

关系时并不都是缺一不可的。其中有些联结词的逻辑功能可以用其它联结词代替，如：

A->B-iAVB,

46B=(4-B)A(8»)o(-v4V8)A(-.5VJ),

A¥B=(4八V(FAB)。

这里我们讨论联结词集合问题。我们把儿个联结词放在•起，称为一个联结词集合。

板书：

二联结词的全功能集

讲述：

正如前面所讲述的，在联结词集合中，•般•些联结词可以用另外的联结词来表示，

这就是说有冗余联结词和独立联结词之分。

联结词组成•个集合，如果一个联结词可由集合中的其它联结词定义，则称此联结词

15

为冗余联结词，否则称为独立联结词

板书：

1冗余联结词，独立联结词

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

讲述：

而个联结词集合称为全功能的是指任意真值函数仅用此集合中联结词的命题形式就

可以表示。如果全功能联结词集合不含冗余联结词则是极小全功能。

板书：

2全功能集及极小全功能集：

全功能集：任意真值函数仅用此集合中联结词的命题形式就可以表示

极小全功能集：不含冗余联结词的全功能集。

讲述

一个联结词集合到底是不是全功能集，甚至是否极小全功能集，必须通过证明，即通

过证明任何的真值函数都可用该集合中的联结词表示。

板书：

(1)任何真值函数都能表示；

(2)定理：如果一个全功能集&中的所有联结词都可由一个联结词集合S2定义，则

$2也是全功能集

示例：

｛r,A,V｝是全功能集，

｛「,A｝,｛「,V｝,｛f｝都是极小全功能集

讲述：

｛「，八｝,｛「，V｝都是极小全功能集，等价联结词定义蕴涵和合取两个联结词所描述的

一种命题，类似，也用一个联结词分别定义，

板书：

3新联结词

非联结词T

非联结词J

讲述：

由于=-1gAp)=pTp

p/\q<=>-•-,(/?A!?)<=>-<=>(pTq)T(pTq),

->q)0-1PT-1go(pfp)T(qfq)，

即八，v都可由T定义，因为｛「,八，V｝是全功能集，所以｛T｝也是全功能集。又由

于其中有且仅有-个联结词，故｛T｝是极小全功能集。

同理可证｛5｝也是极小全功能集，其中

—<p=->(pV/?)=p，p,

p\!q=->->(/?V^)==(pJq)J(P54)，

p[\q==仍Jp)J(q%)。

板书：

｛?｝>｛“都是极小全功能集。

讲述：

上述等值式都是成对出现的，有着对偶的特性，事实上正是对偶的，

16

4对偶式的扩展

A*(pi,p2,0,1,A,V,T,—O/(P1，P2,...,pn,1,0,V,A,4<,T)»示例：

示例

l)g/\q)T(ipA^Ar)2)(pJq)八(f/T-ig)

1)(pVq)1(-ipV^rVr)2)(pT4)VJpJrO

作业:

习题2.21)(1)(4)(5);2)(2)(3)(6)2.8

17

2.3范式

［教学重点］范式的定义和应用

［教学目的］1：使学生引入范式的意义。

2：理解合取范式和析取范式的概念。

3：熟练应用主合取方式和主析取方式的求法及互化

4：理解卡诺图及其在等值演算中应用。

［教学准备］

［教学方法］讲述法

［课时安排］二课时。

［教学过程］

讲述：

判断两个命题公式是否等值，前面已经介绍了真值表法和等值演算法。相比较而言，

等值演算法可能简单得多，特别是在命题变项数目较多的时候。然而有时想将•个命题形

式等值变换成另一个，却可能很难找到适当的过程。

一个有效的方法式将两个命题公式等值演算某种标准形式，然后在比较，这种标准就

称为范式。

板书：

2.3范式

1基本概念：

文字：命题变项及其否定的统称。

简单析取式：由有限个命题变项及其否定构成的析取式。

一个简单合取式是矛盾式，当且仅当其含有一个文字及其否定

简单合取式：由有限个命题变项及其否定构成的合取式.

一个简单析取式是重言式，当且仅当其含有一个文字及其否定

讲述：

示例例如pAq,p/\q/\->p,p/\q/\r/\s等都是简单合取式，pVq,p\Jp7pVr

等都是简单析取式。单个文字既可看作是简单合取式，也可看作是简单析取式。

板书：

2析取范式与合取范式

A定义

析取范式：简单合取式的析取

合取范式：简单析取式的合取

示例：

板书：

B性质

•个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式

C范式的获得

讲述：

18

任何一个命题形式都可以等值演算成合取范式和析取范式，

板书：

具体步骤：

1)利用等值式模式将其它联结词转化成A,V；

2)简化双重否定号，并利用香农定理将所有「写到文字里；

3)利用分配律，将4最终变成合取范式和析取范式。

示例

例通过等值演算将((pVg)-r)-p化成合取范式和析取范式。

解：((pVg)->r)=->(-1(/?Vq)Vr)Vp

=((pV^)A-nr)Vp

=V(q/\f)Vp(析取范式)

<=>((/?A->r)Vp)V(q八一>r)

opV(q/\f)(析取范式)

o(p'Vq)A(pY「r)。(合取范式)

板书

方法2:

1)连续利用展开定理，转化成「,八，V形成的公式

2)最后应用分配定理，将一个命题形式等值演算成范式形式。

示例：

讲述：

一个命题形式的析取范式不是唯一的，同样，合取范式也不是唯一的。这就给我们想通

过比较标准形式的异同判断命题形式是否等值的要求带来困难，因此不能将析取范式和合

取范式作为标准形式。

板书

1)主析取范式与主合取范式：

A极小项：

在含有〃个命题变项的简单合取式中，每个命题变项作为文字出现且仅出现一次。

主要性质：

(1)每个极小项的成真赋值仅有一个；

(2)两个不同的极小项的合取构成的命题形式为矛盾式；

(3)所有个极小项的析取构成的命题形式为重言式。

讲述：

为了书写方便，通常用m,表示某个极小项，下标i的规定如下：极小项的命题变项

按一定的次序排好后，下标i化为二进制后正是该极。这样每个师与其成真赋值建立了•

一对应的关系。

示例：

三个变量的极小项m7=pAqAr,m5=pA->q人r,

B主析取范式

极小项的析取

性质：

(1)如mi是主析取范式A的一个极小项，则mi的成真赋值一定是A的成真赋值；

(2)A、B是相同的n个命题变项的主析取范式，则AvB将包含A和B的所有极小项;

19

AAB将包含A和B的所有的公共极小项;

(3)「A包含主析取范式A的所有极小项之外的全部极小项。

表示：

(1)命题形式

(2)简写:

板书：

mivmjVmk

v(mj,mj,m。或》(m1,mj,mk)

(3)卡诺图法

示例讲述：

卡诺图的构成规律：

1)含有〃个命题变项，若〃是偶数，则斜线左右命题变项数目相同；若〃是奇数，斜

线左边命题变项的数目多一个；按照排列顺序，依次从外到里，从斜线左边到右边；

2)命题变项的赋值，位于最外层的总是从上往下、从左到右依次为0,1；位于里层的，

则按照其相邻外层的相邻两个赋值0,1,从上往下、从左到右依次扩展为0,1,1,0。

讲述:

卡诺图可用表示主析取范式，也可以用于化简命题形式的表达式:

板书：

用于化简表达式：利用卡诺图化简，将相邻的“1”合并。

相邻：

(1)任何水平和垂直方向上几何相邻的单元；

(2)图形两端的单元；

(3)关于对称轴对称的单元；

示例：

化简V(0,1,4,5,6,11,12,14,16,20,22,28,30,31)

板书：

唯一性

任何一个命题形式都存在一个且唯一一个主析取范式或

主合取范式

讲述：

任何一个命题形式可以等值演算成合取范式和析取范式。

板书：

演算步骤:

20

(1)等值演算变换成析取范式，不妨设S2V...VS„(«>1)»

(2)不是极小项的简单合取式，如不含有p的文字，则等值演算：

BQ/\1<=>5,A(pV-i/j)■»V(S,A->p),

其所缺少的命题变项重复上述过程，直到所有简单合取式都是极小项为止。

(3)将所有相同的极小项合并。

板书：

C主合取范式

板书：

极大项

对比极小项讲述：极大项定义，性质

在含有〃个命题变项的简单析取式中，每个命题变项作为文字出现且仅出现一次。

性质：

1)每个极大项的成假赋值有且仅有一个；

2)两个不同的极大项的析取构成的命题形式为重言式；

3)所有极大项的合取构成的命题形式为矛盾式。

简单表示：

三个变量的极大项M7=->pv-.qv-1r,M5=-ipvqv->r,

板书

主合取范式：极大项的合取

对比主析取范式讲述：

性质，表示，唯一性，演算过程

板书：

表示：

MiAMjAMk

人(i,j,k)或n(i,j,k)

唯一性

演算过程

讲述：

我们已经讨论了两个主范式，在演算过程中，为了方便，可以以任何一种范式作为基

础，实际上两种范式是相通的。

板书：

D两种主范式的互换

和M之间的关系：

M,0—i/n,,m*。一>Mg

主范式关系：

主析取范式不包含的极小项标号正是其主合取范式所包含的极大项标号。

A(i|,ji,=A(i2,)2,k2,...)(ii#i2,小刊2,k|^k2,...)

示例：

m2Vm4Vm5Vm6Vm7

0MoAMiAM3

21

讲述：

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

复习讲述，板书：

本章要点：

♦等值：两个命题形式具有相等的值，或等价式为重言式；

♦等值式模式：常用的等值式；

♦等值演算：由已知等值式推演新的等值式的过程；

♦等值演算常用规则定理：等值式模式、替换规则、置换规则、香农定理、对偶定理、展

开定理；

♦与非联结词色命题P与4的否定；

♦或非联结词L命题p或4的否定；

♦对偶式：仅含有联结词「，A,和J的命题公式，将其中的八，V,U,0,1分别换以V,

0后得到的公式称为原式的对偶式；

♦联结词全功能集：任何真值函数都可仅用其中的联结词表示；

♦冗余联结词：可用其它联结词定义的联结词；

♦极小全功能集：不含冗余联结词的全功能集；

♦文字：命题变项及其否定；

♦简单合取式：有限个文字的合取式；

♦极小项：每个命题变项形成的文字出现且仅出现一次的简单合取式；

♦简单析取式：有限个文字的析取式;；

♦极大项：每个命题变项形成的文字出现且仅出现一次的简单析取式；

♦范式：有限个简单析取式的合取为合取范式，有限个简单合取式的析取为析取范式；

♦主范式：极小项的合取范式为主合取范式，极大项的析取范式为主析取范式。

♦获得主范式方法：等值演算法，真值表获得成真赋值法、卡诺图法。

♦范式特性：范式的多样性和主范式的唯一性；

♦卡诺图：参见图2.1；

作业：

习题2.10(2)(3)

习题2.12

22

第三章命题逻辑自然推理

［教学重点］推理系统及证明的构造，归缪法、CP规则

［教学目的］1:使学生理解推理的含义。

2：了解推理系统，理解并识记各推理规则。

3：熟练掌握自然推理系统P