离散数学命题逻辑

离散数学命题逻辑演示文稿第1页，共119页。（优选）离散数学命题逻辑第2页，共119页。0-2:AboutDiscreteMath.计算机本身的结构和它处理的对象都是离散型的，所以计算机科学与技术本质上是一门离散数学技术。“数字电路”、“编译原理”、“数据结构”、“操作系统”、“数据库系统”、“系统结构”、“容错判断”、“算法的分析与设计”、“逻辑程序设计”、“软件工程”、“人工智能”、“多媒体技术”、“计算机网络”、“信息管理”、“信号处理”、“模式识别”、“数据加密”、“机器定理证明”、“形式语言与自动机”等离散数学研究离散（变）量的结构及其相互关系，是计算机科学的理论基础。第3页，共119页。高等数学：从初等的思维方式带到基于工业革命的学科表达语言的富于创造性的思维方式离散数学：带入信息革命的学科的表达语言中去发展和创造具有时代特点的先进的思维方式。0-2:AboutDiscreteMath.第4页，共119页。0-2:AboutDiscreteMath.IntroductionThekindofproblemssolvedusingDiscretemath.include:Howcanalistofintegersbesortedsothattheintegersareinincreasingorder?Howmanystepsarerequiredtodosuchasorting?Howcanitbeprovedthatasortingalgorithmcorrectlysortsalist?Andsoon.第5页，共119页。学科特点Introduction

(1)知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。(2)方法性强：课程对抽象思维能力要求较高，通过学习能大大提高学习者的逻辑推理能力、抽象思维能力和形式思维能力。课程证明题多，方法灵活，在平时的学习中，要勤于思考，善于总结，多于练习。第6页，共119页。教材与教学参考书教材：耿素云、屈婉玲、张立昂，离散数学（第四版），清华大学出版社,2008.教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第三版），清华大学出版社，2008.

第7页，共119页。参考书目《离散数学》，左孝凌著，上海科技文献出版社；《DiscreteMathematicsandItsApplications》(英文FifthEdition),KennethH.Rosen著，机械工业出版社；第8页，共119页。考核方法1．平时成绩：占总成绩的50%

出勤，作业，听课情况，测验2．期末考试：占总成绩的50%。第9页，共119页。主要内容数理逻辑集合论代数结构图论组合分析初步形式语言和自动机初步第10页，共119页。数理逻辑

逻辑学是研究推理的科学利用计算的方法来代替人们思维中的逻辑推理过程莱布尼兹数理逻辑用数学方法研究推理的一门数学学科第11页，共119页。数理逻辑数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。------一套符号体系+一组规则第12页，共119页。数理逻辑部分第1章命题逻辑研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。第2章一阶逻辑数理逻辑第13页，共119页。第一章命题逻辑离散数学第14页，共119页。第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第15页，共119页。§1命题符号化及联结词

一、命题与真值二、命题分类：原子命题，复合命题三、命题常项与命题变项及其符号化四、联结词第16页，共119页。一、命题与真值

命题:具有唯一确定真假意义的陈述句命题的真值:判断的结果真值的取值:真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中判断结果不惟一确定的也不是命题第17页，共119页。

.真命题假命题疑问句感叹句祈使句不是命题（1）2是素数.（2）雪是黑色的.（3）2+3=5.（4）明年十月一日是晴天.（5）3能被2整除.（6）这朵花多好看呀!（7）明天下午有会吗?（8）请关上门!（9）x+y>5.（10）地球外的星球上也有人.真命题假命题第18页，共119页。二、命题分类：简单命题与复合命题简单命题（原子命题）：命题不能分成更简单的句子的命题，又称为命题常项（命题常元）。2是素数.雪是黑色的.2+3=5.明年十月一日是晴天.3能被2整除.第19页，共119页。二、命题分类：简单命题与复合命题复合命题：由简单命题用联结词联结而成的命题。3不是偶数;2是素数和偶数;林芳学过英语或日语;如果角A和角B是对顶角，则角A等于角B．第20页，共119页。三、命题常项与命题变项及其符号化1.命题变项（命题变元、命题函数）：真值可以变化的陈述句。如：x+y>5.

命题变项不是命题。2.命题常项（命题常元）：真值唯一确定的陈述句。如：2是偶数.

命题常项是命题。第21页，共119页。3.简单命题、命题变项的符号化简单命题符号化：p:2是素数;--命题常项q:雪是白的;--命题常项命题变项符号化：p:x+y>5;--命题变项（不是命题）命题的真值表示：1(T)表示真;0(F)表示假.第22页，共119页。四、联结词与复合命题

1.否定式与否定联结词“

”定义1设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作

p.符号

称作否定联结词

p

为真当且仅当p为假.例p：3是偶数。┐p：3不是偶数第23页，共119页。四、联结词与复合命题

(续)2.合取式与合取联结词“∧”

定义2

设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词p∧q为真当且仅当p与q同时为真合取联结词是逻辑“与”的意思。第24页，共119页。

例

将下列命题符号化.（1）李平既聪明又用功（2）李平虽然聪明,但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功（5）李文和李武是兄弟解：令p：李平用功，q：李平聪明，则（1）p∧q（2）p∧┐q（3）p∧q（4）（┐(┐p)∧┐q）（5）r:李文和李武是兄弟分清简单命题与复合命题不能见到“和”、“与”就用“∧”描述合取式的灵活性与多样性

第25页，共119页。四、联结词与复合命题

(续)

定义3

设p,q为命题，复合命题“p或q”称作p与q

的析取式，记作p∨q.∨称作析取联结词

p∨q为假当且仅当p与q同时为假.3.析取式与析取联结词“∨”第26页，共119页。四、联结词与复合命题

(续)例

将下列命题符号化

(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.第27页，共119页。解

令p:2是素数,q:3是素数,r:4是素数,s:6是素数,

则(1),(2),(3)均为相容或.

分别符号化为:p∨r,p∨q,r∨s,

它们的真值分别为1,1,0.

而(4)为排斥或.(4)令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为

(t∧

u)∨(

t∧u).

第28页，共119页。四、联结词与复合命题(续)

定义4

设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作p

q，并称p是蕴涵式的前件，q为蕴涵式的后件.

称作蕴涵联结词，

p

q为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“

”第29页，共119页。p

q的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q

只要p，就q

只有q,

才p

除非q，才p

除非q，否则非

p四、联结词与复合命题(续)第30页，共119页。自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。例如果3＋3＝6，则雪是黑的。如果3+36，则雪是黑的。第31页，共119页。例

设p:天冷，q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(7)如果天不冷，则小王不穿羽绒服.

注意：

p

q与

q

p

等值（真值相同）p

qp

qp

qq

p

q

pq

p第32页，共119页。四、联结词与复合命题(续)定义5

设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p

q.

称作等价联结词.p

q为真当且仅当p与q同时为真或同时为假.说明:(1)p

q的逻辑关系:p与q互为充分必要条件

5.等价式与等价联结词“

”第33页，共119页。例

将下列复合命题符号化并求其真值（1）2+2=4当且仅当3是奇数:p↔q1

（2）2+2≠4当且仅当3是奇数:┐p↔q0

（3）2+2=4当且仅当3不是奇数:p↔┐q0

（4）2+2≠4当且仅当3不是奇数:┐p↔┐

q1第34页，共119页。习题小王是游泳冠军或百米赛跑冠军:小王现在在宿舍或在图书馆:

(┐p∧q)∨(p∧┐q)或p∨q选小王或小李中的一人当班长:

(┐

p∧

q)∨(p∧

┐q)如果我上街，我就去书店看看，除非我很累:

┐r→(

p→q)王一乐是计算机系的学生，他生于1968年或1969年，他是三好学生:

p∧(

q∨r)

∧sp∨q第35页，共119页。联结词运算规则我们所学的5种基本联结词也称为逻辑运算符，其运算顺序为：┐，∧，∨，→，↔如果出现的基本联结词相同，又无括号时，则按从左到右的运算顺序；如果遇有括号时，不管出现的基本联结词如何，都先进行括号中的运算。第36页，共119页。真值表

p

p

T

F

F

T

pq

p∧q

TT

T

TF

F

FT

F

FF

F

pq

p∨q

TT

T

TF

T

FT

T

FF

F

pq

p

q

TT

T

TF

F

FT

T

FF

T

pq

pq

TT

T

TF

F

FT

F

FF

T第37页，共119页。第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第38页，共119页。§2命题公式及分类一、命题（合式）公式二、公式的赋值三、真值表四、命题的分类：重言式矛盾式可满足式第39页，共119页。一、命题（合式）公式

递归定义：（1）单个命题常项或变项p,q,r,...,pi,qi,ri,...,0,1是合式公式；（2）如果Ａ是合式公式，则┐Ａ是合式公式；（3）如果Ａ,B是合式公式，则(A∧B),(A∨B),(A→B),(A↔B)是合式公式；（4）只有有限次地应用(1)-(3)组成的符号串才是合式公式.命题（合式）公式：由命题常项、命题变项、联结词、括号等组成的符号串.1.定义第40页，共119页。(p∧q)

↔

r(┐p∧q)

↔

r(┐pq)

↔

r┐p∨→r

p∧

┐

q

↔rp

┐∧

q

↔r

√√××√×第41页，共119页。一、命题（合式）公式（续）2.层次

若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1(n≥0)层公式是指A符合下列情况之一：A=

┐B，B是n层公式；A=B∧C，其中B，C分别为i层公式和j层公式A=B∨C，其中B，C分别为i层公式和j层公式A=B→C，其中B，C分别为i层公式和j层公式A=

B↔C，其中B，C分别为i层公式和j层公式其中n=max(i,j);第42页，共119页。合式公式的层次(续)例如公式

p

p

p

q

(p

q)

r

((

p

q)

r)

(

r

s)0层1层2层3层4层第43页，共119页。二、公式的赋值

定义给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值

A=(

p∧q)→r

11

0

：A=0成假赋值

1

1

1，0

1

1，0

1

0

：A=1成真赋值第44页，共119页。三、真值表

真值表:公式A在所有赋值下的取值情况列成的表

例给出公式的真值表

A=(q

p)

q

p

的真值表

pq

q

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

1111第45页，共119页。例B=(

p

q)

q

的真值表

pq

p

p

q

(

p

q)

(

p

q)

q00011011

1100110100100000实例第46页，共119页。例C=(p

q)

r

的真值表

pqr

p

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

11101010第47页，共119页。四、公式的类型

定义设A为一个命题公式

(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式

A=(q

p)

q

p，B=(

p

q)

q，C=(p

q)

r第48页，共119页。第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第49页，共119页。§3等值演算

一、等值式二、基本等值式三、等值演算与置换规则四、应用举例第50页，共119页。一、等值式

定义若等价式A

B是重言式，则称A与B等值，记作A

B，并称A

B是等值式┐(pVq)与┐pV┐q┐(pVq)与┐p∧┐q注:不是逻辑联结词，表示对任意的赋值，A与B的值相同。↔是等价联结词，它与不能混为一谈。第51页，共119页。真值表法（1）pq┐p┐qpVq┐(pVq)┐pV┐q0011011011010110011011100100┐(pVq)与┐pV┐q不等值第52页，共119页。真值表法（2）pq┐p┐ppVq┐(pVq)┐p∧┐q0011011011010010011001100100┐(pVq)与┐p∧┐q等值第53页，共119页。二、基本等值式序号等值式定律1A

┐┐A双重否定2AAVA等幂律3A

A∧A4AVB

BVA交换律5A∧BB∧A6(AVB)VCAV(BVC)结合律7(A∧B)∧CA∧(B∧C)8AV(B∧C)(AVB)∧(AVC)分配律9A∧(BVC)(A∧B)V(A∧C)第54页，共119页。基本等值式（2）序号等值式定律10┐(AVB)

┐A∧┐B德.摩根律11┐(A∧B)

┐AV┐B12AV(A∧B)A吸收律13A∧(AVB)A14AV11零律15A∧0016AV0A同一律17A∧1A18AV┐A1排中律19A∧┐A0矛盾律第55页，共119页。基本等值式（3）序号等值式定律20A→B┐AVB蕴涵等值式(真值表)21A↔B(A→B)∧(B→A)等价等值式22A→B

┐B→┐A假言易位(逆否命题)23A↔B┐A↔

┐B等价否定等值式24(A→B)∧(A→┐B)┐A归缪论第56页，共119页。三、等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程置换规则：若A

B,则

(A)

(B)

等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则

第57页，共119页。四、应用举例——验证等值式验证下列等值式:p→(q→r)

(p∧q)→r（P10例1.9(1))

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)∨r┐p∨(┐q∨r)┐p∨(q→r)p→(q→r)第58页，共119页。验证等值式（续）验证下列等式:

p

(p∧q)∨(p∧┐q)（P10例1.9(2))

p

p∧1（同一律）

p∧(q∨┐q)（排中律）

(p∧q)∨(p∧┐q)（分配律）第59页，共119页。四、应用举例——判断公式类型

例3

用等值演算法判断下列公式的类型(1)q

(p

q)

解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德

摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.

第60页，共119页。例3(续)(2)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律）

1由最后一步可知，该式为重言式.第61页，共119页。例3(续)(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A

0A为重言式当且仅当A

1说明：演算步骤不惟一,应尽量使演算短些第62页，共119页。第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第63页，共119页。1.4联结词全功能集

一、联结词的扩展异或联结词∨与非联结词↑或非联结词↓二、真值函数三、联结词全功能集第64页，共119页。一、复合联结词

排斥或:p∨q

(p

q)

(

p

q)与非式:p

q(p

q)或非式:p

q(p

q)

第65页，共119页。二、真值函数

问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？

定义

称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1}n

{0,1}表示F是n元真值函数.

共有个n元真值函数.第66页，共119页。2元真值函数对应的真值表pq00011011

00000000000011110011001101010101

pq00011011

11111111000011110011001101010101

第67页，共119页。三、联结词的全功能集

定义

在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{

,

,

,

,

}中，

p

q

p

q,所以，

为冗余的联结词;类似地，

也是冗余的在{

,

,

}中，

p

q(p

q)，所以，

是冗余的联结词.第68页，共119页。全功能集，极小功能集若任一真值函数都可以用含某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集。若一联结词的全功能集中不含冗余的联结词，则称它为极小全功能集。

{┐,∧,V,↔,→}，{┐,∧,V,↔,→，↓，↑}，

{┐,∧,V}，{┐，V}，{┐,∧}，{↑}，{↓}

为全功能集。{┐,V}，{┐,∧}，{↑}，{↓}为极小全功能集。第69页，共119页。用{↓}表示下列命题公式：极小功能集例题1.p∧q

┐┐p∧┐┐q

┐(┐p∨┐q)

┐((p↓p)∨(q↓q

))

(p↓p)↓(q↓q)2.

p∨q

┐┐(p∨q)┐(p↓q)

(p↓q)↓(p↓q)p→q

┐p∨q

(p↓p)∨q

A∨q

(A↓q)↓(A↓q)

((p↓p)↓q)↓((p↓p)↓q)(p↓p)<=>A第70页，共119页。第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论第71页，共119页。§5对偶与范式

一、对偶式与对偶原理二、析取范式与合取范式三、主析取范式与主合取范式1.极小项和极大项2.求法3.用途第72页，共119页。一、对偶式和对偶原理定义在仅含有联结词

,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.p∧q

与

pVq是对偶式；┐(p∧q)

与┐(pVq)是对偶式。第73页，共119页。一、对偶式和对偶原理(续)定理

设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)

A(p1,p2,…,pn)

A*(

p1,

p2,…,

pn)(2)A(

p1,

p2,…,

pn)

A*(p1,p2,…,pn)例如:A(p,q,r)=p∧(┐qVr)┐A(p,q,r)=┐(p∧(┐qVr))┐pV(q∧┐r)A*(p,q,r)=pV(┐q∧r)A*(┐p,┐q,┐r)=┐pV(q∧┐r)┐A*(p,q,r)=┐(pV(┐q∧r))┐p∧(qV┐r)A(┐p,┐q,┐r)=┐p∧(qV┐r)第74页，共119页。对偶原理设A,B为两命题公式,若AB,则A*B*,其中A*,B*分别为A,B的对偶式.例如:(p∧q)V(┐pV(┐pVq))┐pVq(p∧q)V(┐pV(┐pVq))(p∧q)v(┐pvq)

(pv(┐pvq))∧(qv(┐pvq))1∧(┐pvq)┐pVq对偶式(pvq)∧(┐p∧(┐p∧q))┐p∧q

(pvq)∧(┐p∧(┐p∧q))(pvq)∧(┐p∧q)(p∧(┐p∧q))v(q∧(┐p∧q))0v(┐p∧q)┐p∧q第75页，共119页。二、析取范式与合取范式

简单析取式:有限个命题变项及其否定构成的析取式…如p,

q,p

q,p

q

r,…简单合取式:有限个命题变项及其否定构成的合取式如p,

q,p

q,p

q

r,

析取范式:由有限个简单合取式组成的析取式A1

A2

Ar,其中A1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1

A2

Ar,其中A1,A2,,Ar是简单析取式第76页，共119页。二、析取范式与合取范式(续)范式:析取范式与合取范式的总称

公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式

p

q

r,

p

q

r

既是析取范式，又是合取范式

第77页，共119页。命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：

(1)消去A中的

,

（若存在）

(2)否定联结词

的内移或消去

(3)使用分配律

对

分配（析取范式）

对

分配（合取范式）公式的范式存在，但不惟一第78页，共119页。求公式的范式举例

例

求下列公式的析取范式与合取范式(1)A=(p

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）第79页，共119页。求公式的范式举例(续)(2)B=(p

q)

r第80页，共119页。三、主析取范式与主合取范式——极小项与极大项

定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项及其否定在其中出现且仅出现一次，而且第i（1

i

n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项

2n个极小项（极大项）均互不等值

mi极小项，i成真赋值.Mi极大项，i成假赋值

mi与Mi的关系:

mi

Mi,

Mi

mi

第81页，共119页。极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

第82页，共119页。

由p,q,r三个命题变项形成的极小项与极大项

极小项

极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

第83页，共119页。2.主析取范式与主合取范式

主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

A的主析取范式:与A等值的主析取范式

A的主合取范式:

与A等值的主合取范式.第84页，共119页。主析取范式与主合取范式(续)定理任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步骤：

(1)先求析取范式（合取范式）

(2)对命题中不含某个变项的采用

BB∧1(B∧p)∨(B∧┐p)BB∨0(B∨p)∧(B∨┐p)(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.

第85页，共119页。求公式的主范式例

求公式

A=(p

q)

r的主析取范式与主合取范式.(1)求主析取范式

(p

q)

r

(p

q)

r,（析取范式）

①

(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7,②第86页，共119页。求公式的主范式(续)

r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7

③②,③代入①并排序，得

(p

q)

r

m1

m3

m5

m6

m7（主析取范式）

第87页，共119页。主析取范式与主合取范式的关系存在

mi

Mi关系（单个）.所以A

m0

m1

m5

m7

∑(0,1,5,7)

M0

M1

M5

M7

(M0

M1

M5

M7)

(M2

M3

M4

M6)∏(2,3,4,6)

第88页，共119页。求公式的主范式(续)

(2)求A的主合取范式

(p

q)

r

(p

r)

(q

r),（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②第89页，共119页。求公式的主范式(续)

q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得

(p

q)

r

M0

M2

M4（主合取范式）

第90页，共119页。3.主范式的用途——与真值表相同

(1)求公式的成真赋值和成假赋值例如(p

q)

r

m1

m3

m5

m6

m7，其成真赋值为001,011,101,110,111，其余的赋值000,010,100为成假赋值.

类似地，由主合取范式也可立即求出成假赋值和成真赋值.第91页，共119页。主范式的用途(续)

(2)判断公式的类型

设A含n个命题变项，则

A为重言式

A的主析取范式含2n个极小项

A的主合取范式为1.A为矛盾式

A的主析取范式为0

A的主合取范式含2n个极大项A为非重言式的可满足式

A的主析取范式中至少含一个且不含全部极小项

A的主合取范式中至少含一个且不含全部极大项

第92页，共119页。主范式的用途(续)例

用主析取范式判断下述两个公式是否等值：⑴

p

(q

r)与

(p

q)

r⑵

p

(q

r)与

(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r=m0

m1

m2

m3

m4

m5

m7(p

q)

r=m1

m3

m4

m5

m7故⑴中的两公式等值，而⑵的不等值.

(3)判断两个公式是否等值说明：由公式A的主析取范式确定它的主合取范式，反之亦然.

用公式A的真值表求A的主范式.第93页，共119页。主范式的用途(续)

例

某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：

(1)若赵去，钱也去；

(2)李、周两人中至少有一人去；

(3)钱、孙两人中有一人去且仅去一人；

(4)孙、李两人同去或同不去；

(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？第94页，共119页。例(续)解此类问题的步骤为：①

将简单命题符号化②

写出各复合命题③

写出由②中复合命题组成的合取式

④

求③中所得公式的主析取范式

第95页，共119页。例(续)解

①

设p：派赵去，q：派钱去，r：派孙去，

s：派李去，u：派周去.②(1)(p

q)(2)(s

u)(3)((q

r)

(

q

r))(4)((r

s)

(

r

s))(5)(u

(p

q))③(1)~(5)构成的合取式为

A=(p

q)

(s

u)

((q

r)

(

q

r))

((r

s)

(

r

s))

(u

(p

q))第96页，共119页。例(续)④A

(

p

q

r

s

u)

(p

q

r

s

u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:

A

(

p

q)

((q

r)

(

q

r))

(s

u)

(

u

(p

q))

((r

s)

(

r

s))

（交换律)B1=(

p

q)

((q

r)

(

q

r))

((

p

q

r)

(

p

q

r)

(q

r))（分配律）第97页，共119页。例(续)第98页，共119页。1.6

命题逻辑的推理理论

推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法第99页，共119页。推理的形式结构—问题的引入

推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若AÈCÍBÈD，则AÍB且CÍD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.第100页，共119页。一、推理的形式结构定义若对于每组赋值，或者A1ÙA2Ù…Ù

Ak

均为假，或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,…,Ak

推B”的推理正确当且仅当A1ÙA2Ù…ÙAk®B为重言式.推理的形式结构:A1ÙA2Ù…ÙAk®B或前提：A1,A2,…,Ak

结论：B

若推理正确，则记作：A1ÙA2Ù…ÙAkÞB.第101页，共119页。二、判断推理是否正确的方法真值表法等值演算法判断推理是否正确主析取范式法构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1ÙA2Ù…ÙAk®B”.而在构造证明时，采用“前提:A1,A2,…,Ak,结论:B”.

第102页，共119页。推理定律——重言蕴涵式

第103页，共119页。构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课推理的形式结构为

前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

第104页，共119页。直接证明法(续)前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换第105页，共119页。构造证明——附加前提证明法

欲证明前提：A1,A2,…,Ak

结论：C®B等价地证明前提：A1,A2,…,Ak,C

结论：B

理由：(A1ÙA2Ù…ÙAk)®(C®B)

Û

Ø(A1ÙA2Ù…ÙAk)Ú(ØCÚB)

Û

Ø(A1ÙA2Ù…ÙAkÙC)ÚB

Û(A1ÙA2Ù…ÙAkÙC)®B第106页，共119页。附加前提证明法(续)

例构造下面推理的证明:2是素数或合数.若2是素数，则是无理数.

若是无理数，则4不是素数.所以，如果4是素数，则2是合数.

用附加前提证明法构造证明解设p：2是素数，q：2是合数，

r：是无理数，s：4是素数推理的形式结构前提：pÚq,p®r,r®Øs

结论：s®q第107页，共119页。附加前提证明法(续)前提：pÚq,p®r,

r®Øs

结论：s®q第108页，共119页。构造证明——归谬法（反证法）

欲证明前提：A1,A2,…,Ak

结论：B将ØB加入前提，若推出矛盾，则得证推理正确.理由: