离散数学课件

离散数学引入人有思维

研究思维的形式和规律

形式逻辑:以思维形式及其规律为主要研究对象，同时也涉及一些简单的逻辑方法的科学。概念、判断、推理是形式逻辑三大基本要素逻辑学辨证逻辑:研究人类辩证思维的科学

数理逻辑

第一章数理逻辑前言数理逻辑用数学方法研究推理的形式结构和推理规律的数学学科。主要研究内容：推理

着重于推理过程是否正确

着重于语句之间的关系主要研究方法：数学方法

引进一套符号体系的方法，所以数理逻辑又叫符号逻辑第一章数理逻辑前言

先看著名物理学家爱因斯坦出过的一道题：

一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”

第一章数理逻辑前言

请问这个人说得对吗？他是怎么推导出来的呢？要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程：

(1)什么是前提？有哪些前提？

(2)结论是什么？

(3)根据什么进行推理？

(4)怎么进行推理？

下面的第1,2,3节回答第一个问题。第6节回答第三、四个问题。第一部分命题逻辑1

命题符号化及其联结词2

命题公式及分类3

等值演算4

联结词全功能集5

对偶与范式6推理理论1.命题符号化及其联结词命题的定义命题分类命题的记法联结词命题的符号化简单命题复合命题命题的概念所谓命题，是具有真假意义的陈述句，也就是能够确定或分辨其真假的陈述句，且真与假必居其一。简言之，命题是非真即假的陈述句。例如中国是一个国家。作为命题的陈述句所表达的判断结果称为命题的真值。命题真值只有“真”和“假”两种，分别用“T”（或“1”）和“F”（或“0”）表示。真值为真的命题称为真命题，真值为假的命题称为假命题。真命题表达的判断正确，假命题表达的判断错误，任何命题的真值都是唯一的。命题的举例

判断下列句子是否是命题，并判断其真假?1）加拿大是一个国家。（√T）

2）北京是中国的首都。（√T）

3）这个语句是假的。（×）

4）1+101=110。（√？）

5）3+2≥10。（√？）

6）请你把门关上！（×）

7）你要出去吗？（×）

8）我喜欢踢足球。

（√？）

关于命题的注记命题一定是陈述句，但并非一切陈述句都是命题。那些‘自称谓’的陈述句可能产生自相矛盾的结论。例如：某人说:‘我正在说谎’；某些命题可能无法查明其真值，命题真假会因环境因条件因实际情况时间而异。例如：现在是上午；火星上有人.请注意:数理逻辑的任务不在于研究某个具体命题的真假问题，而在于它可以赋予真或假的可能性，特别是研究各命题规定其真值后它们之间的联系。命题的分类

例:

2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。全是命题。上述命题都是通过诸如“或”，“如果……，则……”等连词联结而成，这样命题，称为复合命题。相对地，不构成复合命题的命题称为简单命题。

命题的分类一般命题可分为两类：1）不能再分解为更简单命题的命题称为原子命题（简单命题）。2）原子命题常可通过一些命题联结词构成新命题，这种命题称为复合命题。明天下雪。明天下雨。原子命题明天下雪或明天下雨。复合命题命题的分类举例

将下列复合命题分成若干个原子命题：（1）天气炎热且正在下雨。

p：天气炎热；q：天正在下雨。（2）天正在下雨或湿度很高。

p：天正在下雨；q：天湿度很高。（3）如果你不看电影，那么我也不看电影。

p：你不看电影；q：我不看电影。（4）控制台打字机既可作为输入设备，又可作为输出设备。

p：控制台打字机可作为输入设备；q：控制台打字机可作为输出设备。

命题的记法通常用小写的带或不带下标的英文字母a、b、c、…p、q、r、…ai、bi、ci、…pi、qi、ri、…等表示简单命题明天下雪。p

明天下雨。q

设p：明天下雪；q：明天下雨；则：明天下雪或者下雨。p或者q。命题联结词

命题联结词又称为逻辑运算符，常用的有五种，它们是：否定词、合取词、析取词、蕴涵词和等价词。1否定词

¬设p表示命题，则‘p不真’是另一命题，记为¬

p，读为

‘非p’否定词可用右表定义，此表称为

¬

p的真值表p¬p01102合取词∧若p,q表示命题,则‘p并且q’也是命题,记为p∧q,读为‘p合取q’.p∧q的真值表如右表所示。由真值表可知

p∧q真,当且仅当p,q俱真pqp∧q0001101100013析取词∨若p,q表示命题,则‘p或者q’也是命题,记为p∨q,读为‘p析取q’.p∨q的真值表如右表所示。由真值表可知

p∨q真当且仅当p,q至少有一个真pqp∨q000110110111关于p∨q的说明“相容或”与“排斥或”

日常语言中“或”有这几种用法，例如：（1）小王是游泳冠军或者百米赛跑冠军；（2）小王现在在宿舍或者在图书馆里；（3）选小王或者小李中的一人当班长。（1）为“相容或”，（2）、（3）称为“排斥或”，但两者不同，（2）为不可能同时为真的排斥或，（3）为可能同时为真的排斥或。（1）（2）可表示为p∨q，（3）却不能。4蕴涵词→若p,q表示命题，则‘如果p，则q’也是命题，记为p→q,读为‘p蕴涵q’.p→q的真值表如右表所示。由真值表可知p→q为假,当且仅当p为假而q为真.只要p，就q;p仅当q;

只有q才ppqp→q0001101111015等价词↔若p,q表示命题，则‘p当且仅当q’

也是命题,记为p↔q,读为‘p等价于q’.p↔q的真值表如右表所示.由真值表可知

p↔q为真,当且仅当p与q有相同的真值.pqp↔q000110111001五个逻辑运算符强弱顺序运算符结合力的强弱顺序约定为：

¬,∧,∨,→,↔；同级的联结词，按其出现的先后次序（从左到右）；若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。说明联结词联结的是句子，而不是单个的词语联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系联结词与自然语言之间的对应并非一一对应命题符号化—自然语言翻译为逻辑式符号化应注意以下几点：①确定句子是否为命题.不是就不必翻译.②确定句中连接词是否能对应于并且对应于哪一个命题连接词.③正确表示原子命题和选择命题连接词.④要按逻辑关系翻译而不能凭字面翻译.例如令：p:林芬做作业q:林芳做作业.则‘林芬和林芳同在做作业’可译为p∧q;但‘林芬和林芳是姐妹’不能译为p∧q，因为这是一个原子命题.命题符号化举例1

设命题p：明天上午七点下雨；

q：明天上午七点下雪；

r：我将去学校。符号化下列语句。

1）如果明天上午七点不是雨夹雪，则我将去学校。明天上午七点雨夹雪p∧q明天上午七点不是雨夹雪¬(p∧q)则我将去学校→r如果明天上午七点不是雨夹雪，则我将去学校。

¬(p∧q)→r命题符号化举例1

2）如果明天上午七点不下雨并且不下雪，则我将去学校。明天上午七点不下雨¬p

明天上午七点不下雪¬q明天上午七点不下雨并且不下雪¬p∧¬q则我将去学校→r如果明天上午七点不下雨并且不下雪，则我将去学校(¬p∧¬q)→r

3）如果明天上午七点下雨或下雪，则我将不去学校。明天上午七点下雨或下雪p∨q则我将不去学校→¬r如果明天上午七点下雨或下雪，则我将不去学校。(p∨q)→¬r命题符号化举例1

4）明天上午七点我将风雪无阻一定去学校。明天上午七点下雨并且下雪并且我一定去学校p∧q∧r明天上午七点不下雨并且下雪并且我一定去学校¬p∧q∧r明天上午七点下雨并且不下雪并且我一定去学校p∧¬q∧r明天上午七点不下雨并且不下雪并且我一定去学校¬p∧¬q∧r明天上午七点下雨并且下雪并且我一定去学校或者明天上午七点不下雨明天上午七点不下雨并且下雪并且我一定去学校或者明天上午七点下雨并且不下雪并且我一定去学校或者明天上午七点不下雨并且不下雪并且我一定去学校。

(p∧q∧r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(¬p∧¬q∧r)或（(p∧q)∨(¬p∧q)∨(p∧¬q)∨(¬p∧¬q))∧r小练习

将下列命题符号化,并给出各命题的真值:

(1)若3＋2＝4，则地球是静止不动的。

（2)若2＋2≠4，则3＋3≠6，反之亦然。

答案:

（1）p→q，其中，p：3＋2＝4，q：地球静止不动，真值为1。

（2）┐p↔┐q，其中，p：2＋2＝4，q：3＋3＝6，真值为1。

总结

1、掌握命题的定义

2、弄清命题和陈述句之间的关系

3、掌握并熟练运用5个基本的联结词对复合命题进行翻译2.命题公式及分类命题常元命题变元命题公式真值表命题公式分类永真式永假式可满足式命题公式命题常元一个特定的，具有确切真值的命题命题变元一个任意的，没有赋予具体内容的简单陈述句由下列递归规则生成的公式称为命题公式:(1)单个命题常元或变元是命题公式.(2)若A和B是命题公式，则（¬A）,（A∧B）,（A∨B）,（A→B）,（A↔B）是命题公式.(3)只有有限步应用(1)和(2)生成的公式(称为合式公式)才是命题公式.命题公式举例

判别下列符号串哪些是命题公式，哪些不是命题公式。（1）(¬(p∨q))；(命题公式)（2）(p→(¬(p∧q)))；(命题公式)（3）(p→q；(不是命题公式)（4）p∨q∨；(不是命题公式)（5）

rs→t

(不是命题公式)命题公式的赋值与真值表公式的赋值

设G是命题变元p1、p2、p3、…、pn是出现在公式G中的所有命题变元，指定p1、p2、p3、…、pn一组真值，则这组真值称为G的一个赋值\解释，常记为I。若指定的一组值使G的值为真，则称这组值为G的成真赋值；若指定的一组值使G的值为假，则称这组值为G的成假赋值；一般来说，若有n个命题变元，则应有2n个不同的解释。命题公式的赋值举例

给出下列命题公式的所有赋值

(1)

¬(p∨q)p、q两个命题变元，有22个不同的解释。

p=0,q=0;p=0,q=1;p=1,q=0;p=1,q=1.(2)(p→(¬(q∧r)))p、q、r三个命题变元，有23个不同的解释。

p=0,q=0,r=0;p=0,q=0,r=1;p=0,q=1,r=0;p=0,q=1,r=1;p=1,q=0,r=0;p=1,q=0,r=1;p=1,q=1,r=0;p=1,q=1,r=1;真值表

公式G在其所有可能的解释下所取真值的表，称为G的真值表。真值表的计算步骤1、根据公式中联结词和命题变元的个数画出表格，设联结词的个数为m个，命题变元的个数为n个，则表格的行数为2n＋1，列数为m＋n；2、找出公式中所有的命题变元及其所有不同的解释，放在表格前n列；3、按照联结词的运算次序依次完成剩下的表格。真值表举例1

设有公式：G＝(p∧q)→r

其中，p、q、r是G的所有命题变元，∧、→是G的所有命题联结词则其真值表如下pqrp∧q(p∧q)→r0000111111111111111111111000000000000000真值表举例11

列出公式：G＝┐(p∧┐q)的真值表。

公式G仅含两个命题变元，三个命题联结词所以真值表如下：pq┐qp∧┐q┐(p∧┐q)00000000001111111111命题公式的分类

设G是一个命题公式

1)重言式(永真式)

若G在它的各种赋值下取值均为真

例p∨(¬p)

2)矛盾式(永假式)

若G在它的各种赋值下取值均为假

例p∧(¬p)

3)可满足式若G至少存在一组赋值是成真赋值例q∨(¬p)

结论

从上述定义可知三种特殊公式之间的关系:1)G是永真式当且仅当¬G是永假式；

2)当G是永真式，则G一定是可满足式，反之则不然；

3)如果公式G在解释I下是真的，则称I满足G；如果G在解释I下是假的，则称I弄假于G。命题公式举例

列出下列公式的真值表，并验证其是否是永真式。

(1)(p→q)↔(¬p∨q)；

(1)的真值表如下：

永真式pq00011011¬p1100p→q1110¬p∨q1110(p→q)↔(¬p∨q)1111命题公式举例(续)

(2)p↔(r∧q)；

(2)的真值表如下:

pqrr∧qp↔(r∧q)0000100101010010111010000101001100011111可满足式3.等值演算

等值的定义等值演算真值表24个等值式置换定理等值判断等值

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式A↔B应为重言式。

等值

定义：若A↔B是重言式,则记为A

B,称为逻辑恒等式,读为‘A恒等于B’。

易见:A

B,当且仅当A,B真值表相同,故逻辑恒等式常用真值表来证明。等值判断举例

判断下列命题公式是否等值：

¬(p∨q)

¬p∧¬qpq¬p¬qp∨q¬(p∨q)¬p∧¬q000000000000000111111111111124个等值式

虽然用真值法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。24个等值式设A、B、C代表任意的命题公式：1、A

¬¬A（双重否定律）2、A

A∨A3、A

A∧A4、A∨B

B∨A5、A∧B

B∧A6、(A∨B)∨C

A∨(B∨C)7、(A∧B)∧C

A∧(B∧C)（等幂律）（交换律）（结合律）牢牢记住24个等值式8、A∨(B∧C)

(A∨B)∧(A∨C)9、A∧(B∨C)

(A∧B)∨(A∧C)10、¬(A∨B)

¬A∧¬B11、¬(A∧B)

¬A∨¬B12、A∨(A∧C)

A13、A∧(A∨C)

A14、A∨1

115、A∧0

0（分配律）（吸收律）（零律）（摩根律）24个等值式16、A∨0

A17、A∧1

A18、A∨¬A

1(排中律)19、A∧¬A

0(矛盾律)20、A→B

¬A∨B(蕴涵等值式)21、A↔B

(A→B)∧(B→A)(等价等值式)22、A→B

¬B→¬A(假言易位)23、A↔B

¬A↔¬B(等价否定等值式)24、(A→B)∧(B→A)

¬A

(归谬论)（同一律）24个等值式建议大家记住并使用它们的称谓,

例如:双否定律,等幂律,交换律,结合律,分配律,摩根律,吸收律,蕴涵表达式,等值表达式,零律,同一律,排中律,矛盾律,归谬律等等.用真值表证明分配律PQRA=P∧(Q∨R)B=(P∧Q)∨(P∧R)

000001010011100101110111

00000

01

000

0

1000

010

00

0

0000

1

101

1

11110

1

11

11等值演算

根据已知的等值式，推演出另外一些等值式的过程称为等值演算。

置换定理

定义：如果A是命题公式￠(A)的一部分，且A本身也是一个命题公式，则称A为公式￠(A)的子公式。

设A是命题公式￠(A)的子公式，若A

B，如果将￠(A)中的A用B来置换（不必每一处），所得到的公式￠(B)与公式￠(A)等价，即￠(A)

￠(B)

。这条规则之所以正确是由于对相应变元的任一种指派，A与B真值相同，故以B取代A后，￠(B)在相应指派下真值与￠(A)相同，所以￠(A)

￠(B)

。

置换定理说明已知命题公式为p∧¬(p∨r)，根据德摩根律，可用¬p∧¬r置换命题公式中¬(p∨r)，则p∧¬(p∨r)变成p∧¬p∧¬r已知命题公式为(b∧c∧a)∨(b∧c∧¬a)，运用分配律，该公式变成(b∧c)∧(a∨¬a)运用排中律，该公式变成(b∧c)∧1运用同一律，该公式变成(b∧c)证明G=p∨¬((p∨¬q)∧q)是永真式。方法一：p∨¬((p∨¬q)∧q)

p∨¬((p∧q)∨(¬q∧q))（分配律）

p∨¬((p∧q)∨0)（矛盾律）

p∨¬(p∧q)（同一律）

p∨(¬p∨¬q)（摩根律）

(p∨¬p)∨¬q（结合律）

1∨¬q（排中律）

1（零律）等值演算举例1方法二：p∨¬((p∨¬q)∧q)

p∨¬(p∨¬q)∨¬q（摩根律）

(p∨¬q)∨¬(p∨¬q)（交换律）

T（排中律）等值演算举例1等值演算举例2试证(p∧(q∨r))∨(p∧¬q∧¬r)

p

证明:(p∧(q∨r)∨(p∧¬q∧¬r)

(p∧(q∨r))∨(p∧¬(q∨r))（摩根律）

p∧((q∨r))∨¬(q∨r))（分配律）

p∧T（排中律）

p（同一律）等值演算应用举例3甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好，甲说“不是我”，乙说“是丁”，丙是“是乙”，丁说“不是我”。四人的回答只有一人符合实际，问是只有一人成绩最好是谁。解：设a：甲的成绩最好；b：乙的成绩最好；c：丙的成绩最好；d：丁的成绩最好因为只有一个人的回答符合实际，故：(¬a∧¬d∧¬b∧d)∨(a∧d∧¬b∧d)∨(a∧¬d∧b∧d)∨(a∧¬d∧¬b∧¬d)T

(矛盾律,零律,等幂律)即(a∧¬b∧d)∨(a∧¬b∧¬d)T但

(a∧¬b∧d)∨(a∧¬b∧¬d)

((a∧¬b∧d)∧1)∨((a∧¬b∧¬d)∧1)

(同一律)((a∧¬b∧d)∧(c∨¬c))∨((a∧¬b∧¬d)∧(c∨¬c))

(排中律)(a∧¬b∧d∧c)∨(a∧¬b∧d∧¬c)∨(a∧¬b∧¬d∧c)∨(a∧¬b∧¬d∧¬c)(分配律)(1)甲、丙、丁三人成绩最好.(2)甲、丁成绩最好.(3)甲、丙成绩最好.(4)甲成绩最好只有一人成绩最好是甲成绩最好.等值演算举例4

将下列推理符号化，并判断推理是否正确。（1）若一个数为整数，则它为有理数；若一个数为有理数，则它为实数，有一个数为整数，所以它为实数。设p：一个数为整数；q：一个数为有理数；r：一个数为实数。故本题的推证为：

((p→q)∧(q→r)∧p)→r

((¬p∨q)∧(¬q∨r)∧p)→r(蕴涵等值式)

(p∧¬q)∨(q∧¬r)∨¬p∨r(蕴涵等值式,德摩根律)

(p∧¬q)∨¬p∨(q∧¬r)∨r(交换律)

(¬p∨¬q)∧(p∨¬p)∨(q∨r)∧(r∨¬r)(分配率)

(¬p∨¬q)∧1∨(q∨r)∧1(排中律)T(同一律,排中律,零律)((p→q)∧(q→r)∧p)→r为永真式，故本题推理成立．等值演算举例4（２）若一个数是实数，则它是复数，若一个数是虚数，则它也是复数，一个数既不是实数，也不是虚数，所以它不是复数。设r：一个数是实数；h：一个数是虚数；g：一个数是复数。本题的推证为：

(r→g)∧(h→g)∧(¬r∧¬h)→¬g

((¬r∨g)∧(¬h∨g)∧(¬r∧¬h))→¬g(蕴涵等值式)

¬((¬r∨g)∧(¬h∨g)∧(¬r∧¬h))∨¬g(蕴涵等值式)

(r∧¬g)∨(h∧¬g)∨(r∨h)∨¬g(德摩根律)

(r∧¬g)∨¬g∨(h∧¬g)∨h∨r(交换律)

¬g∨h∨r(吸收律)当g为T，h为F，r为F，(r→g)∧(h→g)∧(¬r∧¬h)→¬g为F，所以不是重言式，本题推理不成立。等值演算举例4小练习

证明下列等价式(采用等值演算法)

(1)a→(b→a)

¬a→(a→¬b)(2)¬(a→b)

a∧¬b总结1、掌握命题公式的定义

2、能熟练求出给定命题公式的真值表

3、等值演算和置换规则定义，24个等值式

4、掌握运用基本的等值式及置换定理进行等值演算的方法。

４．联结词全功能集联结词分类极小全功能集联结词全功能集常用三种联结词联结词记号复合命题读法记法真值结果异或∨P不可兼或QP异或QP∨QP∨Q=1

P=1，Q=0P=0，Q=1与非↑P和Q的与非P与非QP↑QP↑Q=0

P=1，Q=1或非↓P和Q的或非P或非QP↓QP↓Q=1

P=0，Q=0异或的性质①P

Q

Q

P

交换律②P

(Q

R)

(P

Q)

R

结合律③P∧(Q

R)

(P∧Q)

(P∧R)分配律④(P

P)

F⑤T

P

¬P;F

P

P与非的性质①P

Q

Q

P

②P

P

¬P

左边

¬(P∧P)③(P

Q)

(P

Q)

P∧Q

左边

¬(P

Q)

¬(¬(P∧Q))④(P

P)

(Q

Q)

P∨Q

左边

(¬P)

(¬Q)

¬((¬P)∧(¬Q))或非的性质①P

Q

Q

P

②P

P

¬P

左边

¬(P∨P)③(P

Q)

(P

Q)

P∨Q

左边

¬(P

Q)

¬(¬(P∨Q))④(P

P)

(Q

Q)

P∧Q

左边

(¬P)

(¬Q)

¬((¬P)∨(¬Q))与非和或非使用举例证明:1)

¬(BC)

¬B

¬C2)¬(BC)

¬B

¬C证:1)

¬(BC)

¬

(¬(B∧C))

¬

(¬B∨¬C)

¬B

¬C2)¬(BC)

¬

(¬(B∨C))

¬

(¬B∧¬C)

¬B

¬C联结词分类冗余联结词在一个联结词的集合中，如果一个联结词可由集合中其他联结词定义独立联结词在一个联结词的集合中，如果一个联结词不可由集合中其他联结词定义联结词分类举例

找出联结词集{¬,∨,∧,→,↔}中的冗余联结词和独立联结词。

p→q

¬p∨qp↔q

(p→q)∧(q→p)

(¬p∨q)∧(¬q∨p)p∨q

¬¬(p∨q)

¬(¬p∧¬q)

∨,→,↔为冗余联结词;¬,∧为独立联结词。联结词极小全功能集设S是联结词集合，如果1、用S中的联结词表示的等价公式，可以表示任何命题公式，称S为全功能集；2、从S中删除任何一个联结词而得到的新联结词集合S1，至少存在一个命题公式不能用S1中的联结词表示的等价公式表示出来，称S为极小全功能集。极小全功能集举例由于：P→Q=¬P∨Q；

P↔Q=(¬P∨Q)∧(P∨¬Q)；

P∧Q=¬(¬P∨¬Q)。所以，{¬，∨}可以构成极小全功能集。同理，{¬，∧}可以构成极小全功能集。(2)由于:P∨Q=¬P→Q；

P↔Q=(P→Q)∧(Q→P)；

P∧Q=¬(¬P∨¬Q)=¬(P→¬Q)。所以，{¬，→}可以构成极小全功能集。极小全功能集举例(3)由于：¬P=¬(P∧P)=P↑P；

P∨Q=(P∧P)∨(Q∧Q)=¬(¬(P∧P)∧¬(Q∧Q))=¬((P↑P)∧(Q↑Q))=(P↑P)↑(Q↑Q)

所以，{↑}可以构成极小全功能集。同理，{↓}可以构成极小全功能集。5.对偶与范式简单析取式简单合取式析取范式合取范式极大项极小项主合取范式主析取范式

公式化归法真值表法对偶式在仅含联结词¬、∧、∨的命题公式A中，将∨换成∧，将∧换成∨，若A中含0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*。对偶式举例求出下列命题公式的对偶式（１）¬p∨q

¬p∧q（２）p∨¬q∧0p∧¬q∨1对偶定理

对偶定理

设A、B为仅含命题变元p1,…,pn

及¬、∧、∨的命题公式。若A

B，则A*

B*，反之亦真。简单析取式与简单合取式

简单析取式仅由有限个命题变项或其否定构成的析取式

简单合取式仅由有限个命题变项或其否定构成的合取式

注意:

单个命题变项或其否定是一个简单析取式、简单合取式析取范式与合取范式

析取范式:

仅由有限个简单合取式构成的析取式即形如A1∨A2∨…∨An，其中，Ai是由命题变元或命题变元的否定所组成的简单合取式例如：(p∧q)∨(¬p∧q)

合取范式:

仅由有限个简单析取式构成的合取式即形如A1∧A2∧…∧An，其中，Ai是由命题变元或命题变元的否定所组成的简单析取式例如：(p∨q)∧(¬p∨q)

注意:

单个简单析(合)取式是一个析取范式、合取范式求析取范式和合取范式的方法

求一个命题公式的与之等价的析取范式和合取范式，其步骤如下：

1）利用等价公式中的等价式和蕴涵式将公式中的→、↔用联结词¬、∧、∨来取代；

2）利用双重否定律、摩根定律将否定联结词¬移到各个命题变元的前端或消去；

3）利用分配律将公式化成其等价的析取范式和合取范式。如果是求析取范式用A∧(B∨C)

(A∧B)∨(A∧C)

如果是求合取范式用A∨(B∧C)

(A∨B)∧(A∨C)求析取范式和合取范式举例

求((p∨q)→r)→p析取范式和合取范式

((p∨q)→r)→p

(¬(p∨q)∨r)→p

¬(¬(p∨q)∨r)∨p

¬((¬p∧¬q)∨r)∨p

((¬¬p∨¬¬q)∧¬r)∨p

((p∨q)∧¬r)∨p

((p∨q)∧¬r)∨p

(p∨q∨p)∧(¬r∨p)合取范式

(p∧¬r)∨(q∧¬r)∨p析取范式极小项和极大项

设p1，p2，…，pn是n个命题变元，一个简单合取式(或简单析取式)如果恰好包含所有个n个命题变元或命题变元的否定，且排列顺序与p1，p2，…，pn的顺序一致，则称此简单合取式(或简单析取式)为一个极小项(或极大项)。

注：在极小(大)项中，任何命题变元pi和¬pi二者有且仅有一个出现。例如对两个命题变元p、q的情形

其极小项有：(¬p∧¬q)、(¬p∧q)、(p∧¬q)、(p∧q)

其极大项有：(p∨q)、(p∨¬q)、(¬p∨q)、(¬p∨¬q)问题：3个变元p、q、r的极小项和极大项？说明：对于n个命题变元．共有2n个不同的极小项和2n个不同的极大项，分别记为

m0、m1、…m2n-1和M0、M1、…M2n-1

。

¬p∧¬q∧¬r、¬p∧¬q∧r、¬p∧q∧¬r¬p∧q∧r、p∧¬q∧¬r、p∧¬q∧rp∧q∧rp∨q∨

r、p∨

q∨¬

r、p∨¬

q∨

rp∨¬

q∨

¬

r、¬

p∨

q∨

r、¬

p∨

q∨

¬r¬

p∨

¬

q∨

¬

r极小项、极大项的编码方式

对极小项，使其为“T”的那组解释为其对应的极小项的编码如¬p∧¬q，仅在p、q分别取真值0、0时才为真，所以可用m00(m0)来表示；如¬p∧q，仅在p、q分别取真值0、１时才为真，所以可用m0１(m１)来表示；如p∧¬q，仅在p、q分别取真值１、0时才为真，所以可用m１0(m２)来表示；如p∧q，仅在p、q分别取真值１、1时才为真，所以可用m11(m3)来表示；

极小项、极大项的编码方式

对极大项，使其为“F”的那组解释为其对应的极大项的编码如¬p∨¬q，仅在p、q分别取真值1、1时才为假，所以可用M11(M3)来表示；如¬p∨q，仅在p、q分别取真值１、０时才为假，所以可用M１０(M２)来表示；如p∨¬q，仅在p、q分别取真值０、1时才为假，所以可用M０1(M１)来表示；如p∨q，仅在p、q分别取真值０、０时才为假，所以可用M００(M０)来表示；主析取范式与主合取范式

主析取范式设命题公式A中含n个命题变元，如果A的析取范式中的简单合取式全是极小项

主合取范式设命题公式A中含n个命题变元，如果A的合取范式中的简单析取式全是极大项任何非永假(真)命题A都有主析(合)取范式

求主析(合)范式的两种常用方法:

①公式化归法

②真值表法主析(合)取范式公式化归法步骤

①把给定命题公式化成析(合)取范式

②若化成的析(合)取范式中的某个简单合(析)取式中不含命题变元，也不含该命题变元的否定，用同一律，排中律(矛盾律)，分配律等对该简单合(析)取式进行展开

③将重复出现的命题变元，矛盾式及重复出现的极小(大)项都消去

④将极小(大)项按由小到大的顺序排列，用

(

)表示。用公式化归法求A=(p→q)∧q的主析取范式解

A

(¬p∨q)∧q

(¬p∧q)∨(q∧q)分配律

(¬p∧q)∨(T∧q)等幂,同一律

(¬p∧q)∨((¬p∨p)∧q)排中律

(¬p∧q)∨(¬p∧q)∨(p∧q)分配律

(¬p∧q)∨(p∧q)

等幂律

m1∨

m3

(1,3)用公式化归法求A=(p→q)∧q的主合取范式解A

(¬p∨q)∧q

(¬p∨q)∧(F∨q)

(¬p∨q)∧((¬p∧p)∨q)

(¬p∨q)∧(¬p∨q)∧(p∨q)

(p∨q)∧(¬p∨q)

M0∧

M2

(0,2)主析(合)取范式真值表法步骤:①列出给定命题的真值表②从真值表中选出公式结果为真(假)的所有行,将选出的各行中值为“1”者还原成对应的原变量(对应的原变量的否定)，值为“0”者还原成对应的原变量的否定(对应的原变量)，所得到的合取式(析取式)为对应的极小项(极大项)③将这些极小项的析取(极大项的合取)即为给定公式的主析取范式(主合取范式)用真值表法求A=(p→q)∧q的主析取范式由下表得答案:A

(¬

p∧q)∨(p∧q)

pq¬p∧¬q¬p∧qp∧¬qp∧q

(p→q)∧q00011011100010010011001000000111

用真值表法求A=(p→q)∧q的主合取范式由下表得答案:A

(¬

p∨q)∧(p∨q)

pq¬p∨¬q¬p∨qp∨¬qp∨q

(p→q)∧q00011011111010110111101100011111主析取范式的应用11、判断两个命题公式是否等值由于任何命题公式的主析取范式都是唯一的，因而若AB，说明A与B有相同的主析取范式。反之若A、B有相同的主析取范式，必有AB。主析取范式的应用举例1

求证p→q

¬p∨(p∧q)p→q

¬p∨q

¬p∧(¬q∨q)∨(¬p∨p)∧q(¬p∧¬q)∨(¬p∧q)∨(p∧q)

m0∨m1∨m3

¬p∨(p∧q)

¬p∧(¬q∨q)∨(p∧q)

(¬p∧¬q)∨(¬p∧q)∨(p∧q)

m0∨m1∨m3

主析取范式的应用2

2、判断命题公式的类别设Ａ含有n个命题变元的命题公式，

A为重言式当且仅当A的主析取范式中含全部2n个极小项；

A为矛盾式当且仅当A的主析取范式中不含极小项；

A为可满足式若A的主析取范式中至少含一个极小项；

主析取范式的应用举例２

利用主析取范式判断命题公式的类别（1）q∧(p∨¬q)(q∧p)∨(q∧¬q)

q∧p

3q∧(p∨¬q)为可满足式（2）p→(p∧(q→p))

¬p∨(p∧(¬q∨p))

(¬p∧(¬q∨q))∨((p∧¬q))∨(p∧(¬q∨q))

(¬p∧¬q)∨(¬p∧q)∨(p∧¬q)∨(p∧q)

(0,1,2,3)p→(p∧(q→p))为重言式主析取范式的应用33、求命题公式的成真和成假赋值主析取范式中出现的极小项编码的二进制表示为原公式的成真赋值，而主析取范式中没出现的极小项编码的二进制表示为原公式的成假赋值。因此只要知道一个命题公式A的主析取范式就可以求出A的真值表。主合取范式的应用

通过主合取范式也可以判断公式之间是否等价，判断公式类别（A为重言式当且仅当主合取范式不含任何极大项），求成假赋值（所含极大项的二进制表示）任何非永假(真)命题公式A的主析(合)取范式都是唯一的

证(反证法)设A有两个不同的主析取范式:A1和A2,则A1

A2.由于A1和A2不同,故有极小项m只出现在它们的一个当中.不妨令m在A1而不在A2中.取A1和A2的所有小项除m为成真外全为成假指派，于是对应这个指派,A1为真而A2为假,便与A1

A2矛盾。主析、合取范式的关系

只要求出了命题公式A的主析取范式，也就求出了主合取范式（反之亦然）。极小项与极大项之间的关系：

¬mi

Mi¬Mi

mi

主析范式求主合取范式的步骤

（1）求出A的主析范式中没有包含的极小项；（2）求出与（1）中极小项编码相同的极大项；（3）由以上极大项构成的合取式为A的主合取范式。例如：A中含3个命题变项，主析取范式为

A

m0∨m1∨m5∨m7

(0，1，5，7)

则主合取范式

AM2∧M3

∧M4

∧M6

(2，3，4，6)小练习

求(p→(q∧r))∧(¬p→(¬q∧¬r))的主合取范式和主析取范式

(1,2,3,4,5,6)主合取范式

(0,7)主析取范式总结

1、掌握对偶式的定义

2、掌握简单析取式,简单合取式,析取范式,合取范式,极大项,极小项,主析取范式,主合取范式的定义

3、掌握求析取范式,合取范式,主析取范式,主合取范式的方法

4、理解主析取范式,主合取范式的关系和相互互求的方法6.推理理论24个等值式推理规则推理理论两个技巧推理理论推理从前提推出结论的思维过程。前提已知的命题公式。结论从前提出发应用推理规则推出的命题公式。推理理论A1∧A2∧…∧Ak→B是永真式,称为A1

A2…Ak推出B,记为A1∧A2∧…∧Ak

B.易见:A1∧A2∧…∧Ak

B,当且仅当A为真时B必为真。推理定律(1)A(A∨B)；附加(2)(A∧B)A；化简(3)((A→B)∧A)B；假言推理(4)((A→B)∧¬B)¬A；拒取式(5)((A∨

B)∧¬A)B；析取三段式(6)((A→B)∧(B→C))(A→C)；假言三段式(7)((A↔B)∧(B↔C))(A↔C)；等价三段式(8)(A→B)∧(C→D)∧(A∨C)(B∨D)；构造性两难推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则：A→B，A︱=B(5)附加规则：A︱=A∨B(6)化简规则：A∧B︱=A(7)拒取式规则：A→B，¬B︱=¬

A推理规则(8)假言三段论规则：

A→B，B→C︱=A→C(9)析取三段论规则：A∨

B，¬B︱=A(10)构造性两难规则

A→B，C→D，A∨C︱=B∨D(11)合取引入规则：A，B︱=A∧B形式推理举例

(p∨q)∧(p

¬r)∧(s

t)∧(¬s

r)∧¬tq

步骤断言根据

.

1s

t

前提引入

2¬t前提引入

3¬s1,2拒取式

4

¬s

r

前提引入

5

r

3,4假言推理

6p

¬r

前提引入

7¬p5,6拒取式

8p∨q

前提引入

9q7,8析取三段论附加前提证明法

结论以蕴涵式的形式出现，即推理的形式为

(A1∧A2∧…∧An)→(A→B)

以A为附加前提引入，变推理形式为

(A1∧A2∧…∧An∧A)→B附加前提证明法例(p

(qr))∧(¬s∨p)∧q(sr)步骤断言根据

.

1

¬s∨p

前提引入

2s

附加前提引入

3p

1,2析取三段论

4

p

(qr)

前提引入

5

qr

3,4假言推理

6

q

前提引入

7

r

5,6假言推理

反证法基础(归谬定理):若

H1∧…∧Hn有成真指派,且

H1∧…∧Hn∧¬CR∧¬R,则

H1∧…∧HnC.证:H1∧…∧Hn∧¬CR∧¬R(

F)表明H1∧…∧Hn∧¬C为永假(矛盾式),即对任何使H1∧…∧Hn

为真的指派必使¬C为假,即C为真.H1∧…∧Hn

C.证明(p

(¬(r∧s)

¬q)∧p∧¬s

¬q

步骤断言根据

.

1p

(¬(r∧s)

¬q)

前提引入

2

p

前提引入

3¬(r∧s)

¬q

1,2假言推理

4

¬(¬q)

否定结论引入

5q4置换

6

(r∧s)

3,5拒取式

7¬s前提引入

8s6化简

9

(s∧¬s)

7,8合取

小练习

证明¬

(p∧¬q)、¬q∨r、¬r

¬p

步骤断言根据.1¬r

前提引入

2

¬q∨r

前提引入

3¬q

1,2析取三段论

4

¬

(p∧¬q)

前提引入

5

¬p∨q

摩根律

6

¬p

3,5析取三段论

总结

1、掌握前提,结论,推理的定义

2、掌握推理定律和推理规则

3、掌握进行推理的方法第二部分一阶逻辑1

一阶逻辑基本概念2一阶逻辑合式公式及解释1.一阶逻辑的基本概念

个体词谓词一阶逻辑命题符号化联结词量词谓词的基本概念与表示例如有句子

张华是一个电子科技大学的学生；王南是一个电子科技大学的学生；

李华是一个电子科技大学的学生；则在命题中必须要用三个命题P、Q、R来表示，但是它们都具有一个共同的特征：“…是一个电子科技大学的学生”因此若将句子分解成：“主语+谓语”用P表示“是一个大学生”，P后紧跟“某某人”。则上述句子可以写为：P(张红);P(王南);P(李华)。一般地，P(x)：x是个大学生P：谓词x：个体词P(x)命题函数个体词\谓词

在句子中，可以独立存在的客体称为个体词刻化客体的性质或客体之间的关系即谓词个体常量,个体变量,个体域表示具体或特定的个体词称为个体常量用带或不带下标的小写英文字母a,b,…,a1,a2,…表示；表示抽象或泛指的个体词称为个体变量用带或不带下标的小写英文字母x,y,…,x1,y2,…表示。个体词的取值范围称为个体域或论域，常用D表示。而宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域。谓词常量,谓词变量表示具体或特定的谓词称为谓词常量用带或不带下标的大写英文字母F,G,H…,表示；表示抽象或泛指的谓词称为谓词变量用带或不带下标的大写英文字母F,G,H…表示。F,G,H…等表示谓词常量还是谓词变量由上下文而定。例找出下列句子中的个体词和谓词1)成都是一个省会城市。P(成都)2)离散数学是计算机基础课程。P(离散数学)3)X是一个游泳健将。P(X)2)人是聪明的。P(人)个体常量个体变量n元谓词、0元谓词谓词中所含有的个体词数称为元数。含n个个体词的谓词称为n元谓词，记为P(x1,…,xn)。定义域：个体变量x1,…,xn的个体域

值域：P(x1,…,xn)∈{0，1}。不带个体变项的谓词称为0元谓词命题0元谓词符号化设有如下命题：P：上海是一个现代化的城市；Q：甲是乙的父亲。R：3介于2和5之间。T：李兰和高翔是同班同学。设有如下谓词变项：C(x)：x是一个现代化的城市；F(x,y)：x是y的父亲；B(x,y,z)：x介于y和z之间；S(x,y)：x与y是同班。设：a:上海；b:甲；c:乙：d:3；e:2；f:5；g:李兰；h:高翔。则上述命题又可表示为：P：C(a)Q：F(b,c)R:B(d,e,f)T:S(g,h)n元谓词举例设谓词S(x)：x是大学生。D：某大学班级中的学生，则S(x)是永真式。D：某中学里班级中的学生，则S(x)是永假式。D：x是所有的中国人，则这些人中有的是大学生，有的不是大学生，那么对有些人来讲，S(x)为真，对另外一些人来讲S(x)为假。说明：一个n元谓词中的个体变元在不同的个体域中取不同的值决定其是否成为命题和其真值。几个结论1)谓词中个体词的顺序十分重要，不能随意变更。2)一元谓词用以描述一个个体的某种特征或性质，而n元谓词则用以描述n个个体之间的关系。3)0元谓词(不含个体词)实际上就是一般命题。4)具体命题的谓词表示形式和n元谓词是不同的，前者是有真值的，而后者不是命题，它的真值不确定。量词在有的命题中，除了有个体词和谓词外，还需要表示数量的词，称为量词。量词有两种：(1)全称量词，对应“所有的”、“一切的”、