离散数学课件

离散数学

2/31Whatis

DiscreteMathematics?又称计算机数学是现代数学的重要分支计算机专业课程中的核心基础课程之一Mathematicsthatdealswithdiscreteobjectsandstructures绪论3/31WhatisDiscreteMathematics?离散数学是专门研究离散量的结构与相互间关系的数学理论与数学方法属于现代数学的一个分支，是计算机科学基础理论的核心课程，是计算机专业(CS、CE、SE)最重要的专业基础课之一旨在训练分析问题的能力介绍研究问题的方法论培养抽象思维和严密逻辑推理的能力4/31离散对象（DiscreteObjects）有限或可数个元素Separatedfromeachother(Oppositeofcontinuous)e.g.,integers,people,house,Continuousobjects:e.g.,realnumber离散结构（DiscreteStructures）Theabstractmathematicalstructuresusedtorepresentdiscreteobjectsandrelationshipsbetweentheobjectse.g.集合(sets),关系(relations),图(graphs)WhatisDiscreteMathematics?5/31离散性是计算机科学的显著特点也是研究自动控制、管理科学、电子工程等的重要工具Informationisstoredandmanipulatedbycomputersinadiscretefashion.0101101…Asastudentincomputersciencemajor,youneedtoknowthebasiclanguageandconceptualfoundationforallofthecomputerscience,i.e.,DiscreteMath!Discretemathconceptsarealsowidelyusedthroughoutmath,science,engineering,economics,biology,etc.,…Whystudy

DiscreteMathematics?6/31Gettrainingforrationalthought!离散数学是一门高度概括性、抽象性的科学研究一类问题的解决方法为一类问题建立统一的求解过程按照规定的程序步骤机械地进行下去为机械化提供可能Whystudy

DiscreteMathematics?7/31UsesofDiscreteMathinComputerScienceNetworkingDatabaseImageProcessingProgrammingLanguagesCompilers&InterpretersArtificialIntelligenceDigitalCircuit&CircuitDesignComputerArchitectureOperatingSystemsSecurity&Cryptography(密码学)AdvancedAlgorithms&DataStructuresGraphics&Animationlogistics(物流)SoftwareEngineering8/31Somequestions在举重比赛中，有两名副裁判，一名主裁判。当两名以上裁判（必须包括主裁判在内）认为运动员举杠铃合格，按电钮，才裁决合格。试设计该表决器的电路。设计一台自动售货机，它只能接受五毛和一元的硬币，当投入硬币总值超过一块五时，给出一根冰棍，并找回余额。9/31Somequestions印刷电路板需要多少层？哪些线路断开会导致整个电路不通？网络设计的可靠性怎么样？如果某些线路受损是否还能通讯？10/31Somequestions有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1比2高，7比5高”这样的比较结果，能否把士兵排好队呢？在设计一个组装工件的流水线时，我们知道零件2要在零件1之前装，零件5要在零件9之前装…，如何设计这个流水线呢？11/31软件工程的离散数学基础抽象与逐步求精

为了对付大型复杂的软件系统，须采用传统的“分解”方法。软件工程的分解是从横向和纵向(即空间和时间)两个方面进行的。

自顶向下逐层分解的过程，也是一个逐层抽象的过程。12/31软件工程的离散数学基础抽象

人类在认识复杂现象的过程中使用的最强有力的思维工具是抽象。人们在实践中认识到，在现实世界中一定事物、状态或过程之间总存在着某些相似的方面(共性)。把这些相似的方面集中和概括起来，暂时忽略它们之间的差异，这就是抽象。或者说，抽象就是抽出事物的本质特性而暂时不考虑它们的细节。13/31软件工程的离散数学基础抽象

由于人类思维能力的限制，如果每次面临的因素太多，是不可能做出精确思维的。处理复杂系统的惟一有效的方法是用层次的方式构造和分析它。一个复杂的动态系统首先可以用一些高级的抽象概念构造和理解，这些高级概念又可以用一些较低级的概念构造和理解，如此进行下去，直至最低层的具体元素。14/31软件工程的离散数学基础抽象

软件工程过程的每一步都是对软件解法的抽象层次的一次精化。在可行性研究阶段，软件作为系统的一个完整部件；在需求分析期间，软件解法是使用在问题环境内熟悉的方式描述的；当由总体设计向详细设计过渡时，抽象的程度也就随之减少了；最后，当源程序写出来以后，也就达到了抽象的最低层。15/31软件工程的离散数学基础抽象

随着软件开发工程的进展，在软件结构每一层中的模块，表示了对软件抽象层次的一次精化。软件结构顶层的模块，控制了系统的主要功能并影响全局；在软件结构底层的模块，完成对数据的一个具体处理，用自顶向下由抽象到具体的方式分配控制，简化了软件的设计和实现，提高了软件的可理解性和可测试性，使软件更容易维护。16/31软件工程的离散数学基础逐步求精

逐步求精是人类解决复杂问题时采用的基本方法，也是许多软件工程技术(例如，规格说明技术，设计和实现技术)的基础。可以把逐步求精定义为：“为了集中精力解决主要问题而尽量推迟对问题细节的考虑。”17/31软件工程的离散数学基础逐步求精

逐步求精能帮助软件工程师把精力集中在与当前开发阶段最相关的那些方面上，而忽略那些对整体解决方案来说虽然是必要的，然而目前还不需要考虑的细节，这些细节将留到以后再考虑。

Miller法则：一个人在任何时候都只能把注意力集中在(7±2)个知识块上。18/31软件工程的离散数学基础逐步求精

人类智力有局限性，我们只能在这个前提下尽我们的最大努力工作。可以把逐步求精看作是一项把一个时期内必须解决的种种问题按优先级排序的技术。逐步求精方法确保每个问题都将被解决，而且每个问题将在适当的时候被解决，但是，在任何时候一个人都不需要同时处理7个以上知识块。19/31软件工程的离散数学基础逐步求精

逐步求精最初是由Wirth提出的一种自顶向下的设计策略。Wirth本人对逐步求精曾做过如下概括说明：20/31软件工程的离散数学基础逐步求精“我们对付复杂问题的最重要的办法是抽象，因此，对一个复杂的问题不应该立刻用计算机指令、数字和逻辑符号来表示，而应该用较自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号(可能是自然语言)来表示。对抽象程序做进一步的分解，并进入下一个抽象层次，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。这时的程序可能是用某种高级语言或机器指令书写的。”21/31软件工程的离散数学基础逐步求精

求精实际上是细化过程。我们从在高抽象级别定义的功能陈述(或信息描述)开始，也就是说，该陈述仅仅概念性地描述了功能或信息，但是并没有提供功能的内部工作情况或信息的内部结构。求精要求设计者细化原始陈述，随着每个后续求精(即细化)步骤的完成而提供越来越多的细节。22/31软件工程的离散数学基础逐步求精

抽象与求精是一对互补的概念。抽象使得设计者能够说明过程与数据，同时却忽略低层细节。事实上，可以把抽象看作是一种通过忽略多余的细节同时强调有关的细节而实现逐步求精的方法。求精则帮助设计者在设计过程中逐步揭示出低层细节。这两个概念都有助于设计者在设计演化过程中创造出完整的设计模型。23/31离散数学的主要内容数理逻辑：研究推理的共性关系理论：研究关系的共性代数结构：研究运算的共性图论：数论：数理逻辑逻辑学研究人的思维形式和规律的科学根据研究的对象和方法形式逻辑辩证逻辑数理逻辑用数学方法研究推理的规律和形式的科学推理：由一个或几个判断推出一个新判断的思维形式数学方法建立一套表意符号体系，对具体事物进行抽象的形式研究方法又称符号逻辑两种演算命题逻辑谓词逻辑需要建立一套表意符号体系文法充分定义(well-defined)的形式语言符号体系自然语言有二义性Doubleclickthemouse,thenit’llrun.小王现在不方便接电话，他方便去了建立形式语言符号体系的目的消除二义性普适(高度概括)只关心推理过程的正确性,而不是推理的依据用数学方法研究推理的规律和形式主要内容命题与联结词命题公式重言式范式命题演算的推理理论谓词和量词谓词演算的永真公式谓词演算的推理规则命题逻辑谓词逻辑命题（Proposition）断言一个陈述语句命题命题是一个非真即假(不可兼)的断言如果命题是真命题的真值（TruthValues）为真真命题大写字母“T”(1)表示如果命题是假命题的真值是假假命题大写字母“F”(0)表示能够判断真假的陈述句有确定真假含义的陈述句例今天下雪。雪是黑的。3+3=6。明年的今天会下雨。较大的偶数都可表为两个质数之和。1+101=110。那个商店已经关门了。2是偶数而3是奇数。例(续)x+y＞4。x=3。0*x=0。真好啊！全体立正！你去哪里?我正在说谎。有确定的真假含义不等同于已知其真假含义较大的偶数都可表为两个质数之和。除地球外，别的星球上也存在生物。数理逻辑不关心内容具体的陈述句的真值究竟为什么或在什么环境下是真还是假数理逻辑只关心形式命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系原子命题(Primitiveproposition)由简单陈述句表示的判断命题逻辑规定：原子命题是不可再分的复合命题(Compoundproposition)一个或几个简单命题用联结词联结所构成的命题(复合陈述句)例：“如果天气好，我就去散步。”“2是偶数而3是奇数。”命题的表示常用大写英文字母(或带下标)表示原子命题P表示“雪是白的。”Q表示“北京是中国的首都。”表示命题的形式符号叫命题标识符表示原子命题的命题标识符叫命题词命题变元P表示任一命题时，P就称为命题变元命题词不是命题,是表示任意命题的位置标志命题指具体的陈述句，是有确定的真值命题变元的真值不定，只当将某个具体命题代入命题变元时(解释、真值指派)，命题变元成为命题，方可确定其真值两个特殊的命题词命题常量T：永远表示真命题F：永远表示假命题T和F的两种含义命题常量命题的真值逻辑联结词命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复合命题例：

P:明天下雪,Q:明天下雨。“明天不下雪。”“非P”“明天下雪并且明天下雨。”“P并且Q”“明天下雪或者明天下雨。”“P或Q”TFFT┐PP真值表（TruthTable)与自然语言中的“不”，“否”，“非”，“没有”，“未必”等表示否定的词类似1.否定词┐(～，negation)设P表示命题,那么“P不真”是一个复合命题,记为┐P,叫做P的否定,读做“非P”。如果P是假,则┐P是真,反之亦然。例(a)P:4是质数。

┐P:4不是质数。

(b)Q:这些都是男同学。

┐Q:这些不都是男同学。PQP∧Q000110110001例P:王华的成绩很好。

Q:王华的品德很好。

P∧Q:王华的成绩很好并且品德很好。2.合取词∧(Conjunction)如果P和Q是命题,那么“P并且Q”是一个复合命题,记为P∧Q,称为P和Q的合取,读做“P与Q”或“P并且Q”。用法灵活与自然语言中表示并列、加强、转折等的词：“和”、“与”、“且”、“而且”、“并且”、“既…又…”、“不但…而且…”、“虽然…但是…”、“而”类似没有明显否定、选择、因果的表述也应该是合取PQP∨Q0001101101113.析取词∨(disjunction)如果P和Q是命题,则“P或Q”是一个复合命题,记作P∨Q,称为P和Q的析取,读做“P或Q”。大致与自然语言中表示选择的“或”,“或者”类似，但自然语言中的或具有二义性，用“或”联结的命题，有时具有相容性，有时具有排斥性可兼或(R∨S)∧┐(R∧S)(R∧┐S)∨(┐R∧S)例(a)今晚我写字或看书。

P:今晚我写字，Q:今晚我看书。

P∨Q

(b)选小王或小李当班长。

R:选小王当班长，S:选小李当班长。

R∨S？

排斥或或×PQP→Q000110111101与自然语言中表示因果的“若…则…”、“如果…则…”、“如果…那么…”、“只要…就…”等类似4.条件词→(蕴涵,蕴含,conditional)如果P和Q是命题,那么“P蕴含Q”是一个复合命题,记为P→Q,称为条件式,读做“如果P,那么Q”或“P则Q”。运算对象P叫做前提,假设或前件,而Q叫做结论或后件。例(a)P:天不下雨,Q:草木枯黄。P→Q:如果天不下雨,那么草木枯黄。(b)R:G是正方形,S:G的四边相等。R→S:如果G是正方形,那么G的四边相等。(c)W:桔子是紫色的,V:大地是平的。W→┐V:如果桔子是紫色的,那么大地是不平的。因果关系引入→的目的是希望用来描述命题间的推理，表示因果关系使用P→Q能描述推理如果n>3，那么n2>9。A是B的子集是指A的成员都是B的成员。→与“如果…那么…”有一致的一面,同时也有与常识不一致的地方如果今天是星期二，那么明天是星期天。如果今天是星期一，那么明天是星期天。

在自然语言中，条件和结论往往有某种内在联系，并且往往表示若条件成立则结论也成立这样的推理关系；

而在数理逻辑中，条件和结论不一定有内在联系，且若条件为假则条件式为真。数理逻辑不关心具体命题，只关心推理的形式人为的规定，对P为F时P→Q的值另作规定也是可以的应是人类思维共性的总结PQP→QTFF**TFTT条件式P→Q可以用多种方式陈述:

“P是Q的充分条件”“Q是P的必要条件”“Q每当P”“只有Q，才P”“P仅当Q”……

Q→P,┐P→┐Q,┐Q→┐P分别叫做P→Q的逆命题、反(否)命题和逆反(否)命题/

逆换式、反换式和逆反式。例令：P：天气好。Q：我去公园。1.如果天气好，我就去公园。2.只要天气好，我就去公园。3.天气好，我就去公园。4.仅当天气好，我才去公园。5.只有天气好，我才去公园。6.我去公园，仅当天气好。P→QP→QP→QQ→PQ→PQ→P100100011011P↔QPQ5.双条件词↔(等值，Biconditional)如果P和Q是命题,那么“P等值于Q”是一个复合命题,记为P↔Q,称为双条件式（等值式）,读做“P当且仅当Q”、“PiffQ”或“P等值于Q”。

P↔Q也读做“P的充要条件是Q”。有时“除非”也有互为因果的意义。联结词的注意事项熟练掌握这五个联结词在自然语言中所表示的含义(但要注意具体语言环境)以及它们的真值表的定义特别要注意“或”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”特别要注意“”的用法，它既表示“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件联结词的优先级顺序┐，∧,∨,→,↔练习：填空已知P∧Q为T，则P为()，Q为()已知P∨Q为F，则P为()，Q为()已知P为F，则P∧Q为()已知P为T，则P∨Q为()已知P∨Q为T，且P为F，则Q为()已知P

Q为F，则P为()，Q为()已知P为F，则P

Q为()已知Q为T，则P

Q为()已知

P

Q为F，则P为()，Q为()命题演算的合适公式命题变元与命题常元命题常元命题有具体含义(真值)的例：“3是素数。”；T；F命题变元用大写的英字母如P、Q等表示任何命题真值指派解释将一个命题常元赋予命题变元的过程或者是直接赋给命题变元真值“T”或“F”的过程注意：命题变元本身不是命题，只有给它一个解释，才变成命题。递归定义法如何定义自然数集N？可采用以下方式递归定义(1)1∈N；(2)若n∈N,则n+1∈N；(3)N是满足条件(1)和(2)的最小集合(换句话说，n∈N当且仅当能有限次应用(1)和(2)得到)。(1)——基本项，是递归的基础(2)——递归项，是递推规则(3)——极小化，保证所构造集合的唯一性是一个无限集合，但每个成员都是有限的命题公式命题公式(命题演算的合适公式,wff,wellformattedformula)定义：⑴单个命题词是个合适公式。⑵若A是合适公式，则(

A)是合适公式。⑶若A和B是合适公式，则(A∧B)，(A∨B)，(A

B)和(A

B)都是合适公式。⑷当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和圆括号的符号串是合适公式。 此外，称逐次使用规则⑴，⑵，⑶的过程中所得到的命题公式为最后构成的命题公式的子公式。(1)——基本项(2)(3)——递归项(4)——极小化例(P→(

(Q∨R)))解

(i)P是命题公式根据条款(1)(ii)Q是命题公式根据条款(1)(iii)R是命题公式根据条款(1)(iv)(Q∨R)是命题公式根据(ii)(iii)和条款(3)(v)(

(Q∨R))是命题公式根据(iv)和条款(2)(vi)(P→(

(Q∨R)))是命题公式根据(i)(v)和条款(3)例下面的式子是否为合适公式：

P∧Q，PR，P∨Q∧R修改

(P∧Q)，((P)R)，((P∨Q)∧R)圆括号的省略规则最外层的圆括号可以省去符合联结词优先级顺序的,括号可省去相同的联结词,按从左至右次序计算时,括号可省去

(┐((P∧(┐Q))∨R)→((R∨P)∨Q))┐((P∧(┐Q))∨R)→((R∨P)∨Q)

┐(P∧┐Q∨R)→(R∨P∨Q)┐(P∧┐Q∨R)→R∨P∨Q命题符号化(翻译)用形式语言所表示的命题公式符号串来表示给定的命题命题词表示原子命题逻辑联结词联结例他既有理论知识又有实践经验。P：他有理论知识，Q：他有实践经验。

P∧Q如果明天不是雨夹雪则我去学校。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

仅当明天不下雪并且不下雨时我才去学校。

R→┐P∧┐Q说小学生编不了程序,或说小学生用不了个人计算机,那是不对的。P：小学生会编程序，Q：小学生会用个人计算机。 ┐(┐P∨┐Q)练习将下列命题符号化张三与李四是表兄弟。张三或李四都能做这件事。今晚我在家里看电视或去体育场看球赛。今天我上班，除非今天我病了。除非你努力，否则你不会成功。如果明天不下雨，我就进城，否则就在家读书或看报。真值指派(解释)命题公式不是命题——命题函数有n个命题变元的命题公式可用函数A(P1,P2,…,Pn)的形式表示其中P1,P2,…,Pn按字典顺序排列对应的真值指派可记为I=(P1’,P2’,…,Pn’)，其中Pi’=0或1例A(P,Q,R)=P(R

Q),真值指派(1,0,1)，(1,1,0)真值分别为F和T有n个命题变元的命题公式共有2n个不同的真值指派注意真值表设A(P1,P2,…,Pn)是一个wff，P1,P2,…,Pn是出现于其中的全部命题变元。如果有一张表列出了在P1,P2,…,Pn

的所有2n种真值指派的每一种下，公式A对应的真值，则称此表为公式A的真值表。按子公式列表按逻辑联结词列表重言式/矛盾式/可满足式重言式(tautology)/矛盾式(contradiction)A(P1,P2,…,Pn)是命题公式，P1,P2,…,

Pn是出现于其中的全部命题变元，如在P1,P2,…,

Pn的任何真值指派下，A(P1,P2,…,

Pn)的真值皆为真(假)，则称A为重言式(矛盾式),也称之为永真式

(永假式)例：P∨P和

P∧P偶然式不是永真式,也不是永假式例：P,P∧Q可满足式（satisfactableformula

）非矛盾式

P∨P，P∧Q重言式的性质重言式/矛盾式/可满足式是公式的性质(类别)性质对运算的封闭性(保持)偶数加(乘)偶数、可导函数之和(积)……如果A是重言式，则

A是矛盾式如果A是矛盾式，则

A是重言式如果A，B是重言式，则(A∧B)、(A∨B)、(A

B)和(A

B)也都是重言式如果A，B是矛盾式，则(A∧B)、(A∨B)是矛盾式如果A，B是矛盾式，则(A

B)和(A

B)是重言式思考：可满足式是什么情况？重言式的证明方法方法1：列真值表方法2：公式的等价变换，化简成“T”方法3：用公式的主析取范式证明(P∧(PQ))Q

为重言式PQ(P∧(PQ))Q00011011TTTT命题公式的等价与蕴含恒等式(等价式，

equivalent)设A:A(P1,P2,…,Pn),B:B(P1,P2,…,Pn)是两个命题公式,这里Pi(i=1,2,…,n)不一定在两公式中同时出现，如不论对P1,P2,…,Pn作何种指派，A和B恒有相同的真值，则称之为A与B等价(恒等、逻辑相等)，记作A

B，读做“A等价于B”或“A恒等于B”等价定理：A

B

当且仅当A

B是重言式注意：“

”与“

”不同：逻辑联结词：描述两个命题公式之间的关系若A与B是wff

，A

B是wff，A

B不是问题：由n个命题变元可构成多少个不等价的命题公式？常用逻辑恒等式

1双重否定律A

¬¬A2交换律A∨B

B∨AA∧B

B∧A3结合律(A∨B)∨C

A∨(B∨C)(A∧B)∧C

A∧(B∧C)4分配律A∧(B∨C)

(A∧B)∨(A∧C)A∨(B∧C)

(A∨B)∧(A∨C)5德摩根律¬(A∨B)

¬A∧¬B¬(A∧B)

¬A∨¬B6幂等律A∧A

A，A∨A

A7吸收律A∨(A∧B)

A，A∧(A∨B)

A8零元律A∨T

T，A∧F

F9同一律A∨F

A，A∧T

A10排中律A∨¬A

T11矛盾律A∧¬A

F12条件等价式A→B

¬A∨B13双条件等价式A↔B

(A→B)∧(B→A)14假言易位式A→B

¬B→¬A15双条件否定等价式A↔B

¬A↔¬B16输出式A→(B→C)

A∧B→C公式等价的证明方法1：列真值表方法2：等价变换方法3：主范式例：证明：P→Q

¬P∨QTTFFTTTT11011000┐P∨QP

QQP永真蕴含式(implication)定义给定两个命题公式A和B，如果公式A

B是重言式，则称A重言(永真)蕴含B，或简单的说A蕴含B，记作A

B注意：“”不是联结词表示公式间的“永真蕴含”关系也可看成“推导”关系A

B可以理解成由A可推出B，即由A为真，可以推出B也为真蕴含式的证明方法真值表等价变换逻辑推证假定前件是真,若能推出后件是真,则此蕴含式是真假定后件是假,若能推出前件是假,则此蕴含式是真PQP→Q000110111101用真值表证明蕴含关系证明：(P∨Q)∧(P→R)∧(Q→R)

R111011101001110010100000(P∨Q)∧(P→R)∧(Q→R)→R(P∨Q)∧(P→R)∧(Q→R)RQP1110111011101010

方法1:设┐Q∧(P→Q)是真则┐Q,P→Q是真所以,Q是假,

P是假。因而┐P是真。故┐Q∧(P→Q)

┐P

方法2:设┐P是假,则P是真。以下分情况讨论。

(i)若Q为真,则┐Q是假,

所以┐Q∧(P→Q)是假

(ii)若Q是假,则P→Q是假所以┐Q∧(P→Q)是假故┐Q∧(P→Q)

P

例证明：┐Q∧(P→Q)

┐P考虑任一使┐Q∧(P→Q)为真的解释I，在I下：

┐QP→QTT严谨吗？

……公式怎么能是真？用逻辑推证方法证明蕴含关系引用联词定义逐步推演

例证明：(P→(Q→R))∧(┐S∨P)∧Q

S→R考虑任一使(P→(Q→R))∧(┐S∨P)∧Q为T的解释I，在I下：(P→(Q→R))(┐S∨P)QTTT怎么办？

输出式E19：P→(Q→R)

P∧Q→RP

Q

R

原题转变为证明：(P→(Q→R))∧(┐S∨P)∧Q∧S

RP→(Q→R)是永真式等同于P∧Q→R是永真式

考虑任一使(P→(Q→R))∧(┐S∨P)∧Q和S皆为T的解释I，在I下：(P→(Q→R))(┐S∨P)QSTTTT例证明：(P→(Q→R))∧(┐S∨P)∧Q

S→R

┐SFPTQ→RTRT这种证明方法叫附加前提证明法(CP规则)逻辑推证存在格式与过程不规范的问题永真蕴含式1附加律A

A∨B，B

A∨B2化简律A∧B

A，A∧B

B3假言推理A∧(A→B)

B4拒取式¬B∧(A→B)

¬A5析取三段论¬A∧(A∨B)

B，¬B∧(A∨B)

A6假言三段论(A→B)∧(B→C)

(A→C)7等价三段论(A↔B)∧(B↔C)

(A↔C)8构造性二难(A∨C)∧(A→B)∧(C→D)

B∨D(A∨¬A)∧(A→B)∧(¬A→B)

B9破坏性二难(¬B∨¬D)∧(A→B)∧(C→D)

(¬A∨¬C)等价和蕴含的性质等价关系的性质自反性任何命题公式A，有A

A对称性若A

B，则B

A传递性若A

B且B

C，则A

C蕴含关系的性质自反性任何命题公式A，有A

A反对称性若A

B且B

A，则A

B传递性若A

B且B

C，则A

C若A

B,A

C,则A

B∧C思考：若A

B，则┐A┐B？No！

┐B┐A证明若A

B,B

C则A

C

证明：A→B永真;B→C永真,所以

(A→B)∧(B→C)永真由公式I6得A→C永真,即A

C

若A

B,A

C,则A

B∧C

证明：A是真时,B和C都真,所以B∧C也真因此A→B∧C永真,则A

B∧C

由已知的等价式按照合理的规则逐步推演出新的等价式例证明：A∨B→C

(A→C)∧(B→C)

证：A∨B→C

(A→C)∧(B→C)等价变换┐(A∨B)∨C(┐A∨C)∧(┐B∨C)依据何在？

代入实例设A和B是两个命题公式，如果将A中的某些命题变元用命题公式进行代换便可得到B，并且此种代换满足：（1）被代换的是命题变元（2）如果要代换某个命题变元，则要将该命题变元在A中的一切出现进行代换（3）代换必须同时独立进行此时称B是A的一个代换实例（代入实例）例A(P,Q)=P→Q

A(P,Q∧┐R)=P→Q∧┐RA(P,Q,R,S)=(P→Q)∧R∧(S→(P→Q))

(P→Q)∧S∧(R→(P→Q))，(┐P→Q)∧┐R∧(┐S→(┐P→Q))

P∧R∧(S→P)，(┐P→Q)∧R∧(R→(P→Q))代入规则和替换规则简单地说，命题公式A(X1,X2,…,Xn)是A(P1,P2,…,Pn)的代入实例,只要Xi是命题公式(允许Xi=Pi

，i=1,2,…,n)。代入规则(RuleofSubstitution，代入定理)重言式的代入实例是重言式例(R∧Q)∨┐(R∧Q)(R∨Q)

∧┐(R∨Q)→(P∨Q→S∨Q)矛盾式的代入实例是矛盾式吗？YesP∨┐PP∧

┐P→Q替换规则(RuleofReplacement，置换定理)子公式定义：如果X是合适公式A的一部分且X本身也是合适公式，则称X为公式A的子公式例：A

Q→(P∨(P∧Q))，X

P∧Q替换规则定理：设X是合适公式A的子公式，若X

Y，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即A

B

例：Q→(P∨(P∧Q))

Q→P代入与替换的区别代入是对命题变元进行取代，替换对子公式代入必须取代该命题变元的一切出现，替换不用可用任意wff去代换命题变元，只能用与子公式等价的公式去替换代入实例一般不与原公式等价，替换后的公式必与原公式等价由已知的等价式按照合理的规则逐步推演出另外一些等价式的过程反复应用代入规则和替换规则每个常用逻辑恒等式都是一个模式，对应着无数个同型的等价式等价变换（等值演算）

E3：P∨Q

Q∨PA∧B┐A∧┐B∨

A∧B┐A∧┐B∨E16：P

Q

┐P∨Q由等价定理：例由代入定理：由等价定理：又如PQ

↔┐P∨Q是重言式(R∨Q)

P↔┐(R∨Q)∨P是重言式(R∨Q)

P

┐(R∨Q)∨P是重言式例(a)证明P∧┐Q∨Q

P∨Q

证明：P∧┐Q∨Q

Q∨P∧┐Q E3

(Q∨P)∧(Q∨┐Q) E7

(Q∨P)∧T E24和替换规则

Q∨P E12

P∨Q E3

(b)证明(P→Q)→(Q∨R)

P∨Q∨R证明：(P→Q)→(Q∨R)

(┐P∨Q)→(Q∨R)E16和替换规则

┐(┐P∨Q)∨(Q∨R)E16

P∧┐Q∨(Q∨R)E9、E1和替换规则

(P∧┐Q∨Q)∨RE5

P∨Q∨R例(a)和替换规则存在过程不规范的问题(c)试将语句“情况并非如此:如果他不来,那么我也不去”化简。 解：设P:他来, Q:我去 ┐(┐P→┐Q)

┐(P∨┐Q) E16和替换规则

┐P∧Q E9，E1和替换规则(d)找出P→(P↔Q)∨R的仅含∧和┐两种联结词的等价表达式。

P→(P↔Q)∨R

P→(P→Q)∧(Q→P)∨R

┐P∨(┐P∨Q)∧(┐Q∨P)∨R

(┐P∨┐P∨Q)∧(┐P∨┐Q∨P)∨R

(┐P∨Q)∧T∨R

┐

P∨Q∨R

┐(P∧┐Q∧┐R)(e)证明：(P∨Q)∧(P→R)∧(Q→R)R证：(P∨Q)∧(P→R)∧(Q→R)→R

(P∨Q)∧(┐P∨R)∧(┐Q∨R)→R

(P∨Q)∧(┐P∧┐Q∨R)→R

(P∨Q)∧R→R

T证：(P∨Q)∧(P→R)∧(Q→R)

(P∨Q)∧(┐P∨R)∧(┐Q∨R)

(P∨Q)∧(┐P∧┐Q∨R)

(P∨Q)∧R

R功能完备集及其他联结词联结词的扩充问题的提出：对n个命题变元P1…Pn来说,共可定义出多少个联结词?

在那么多联结词中有多少是相互独立的?4个新联结词：与非:P↑Q┐(P∧Q)或非:P↓Q┐(P∨Q)排斥或(异或):P⊕Q┐(P

Q)

P∧┐Q∨┐P∧Q蕴含否定(条件否定):P→Q┐(P→Q)

Q1：可定义多少个联结词？命题变元和命题联结词可以构成无限多个合适公式把所有的合适公式分类：将等值的公式视为同一类，对于该类合适公式，就可定义一个联结词与之对应一元联结词的个数一元联结词是联结一个命题变元的由一个命题变元P可构成4种不等价的命题公式相应的可定义出4个不同的一元联结词Pf1f2

f3f

40100110101

永假恒等否定永真二元联结词的个数二元联结词联结两个命题变元由两个命题变元P，Q可构成16种不等价的命题公式相应的可定义出16个不同的二元联结词n元联结词的个数对n个命题变元P1,…,Pn,每个Pi有2种取值,从而对P1…Pn来说共有2n种取值情形相应的可定义出22n个n元联结词

二元运算联结词的归约Q2：联结词是否都是独立的，或者说能否相互表示定义1.4-1

一个联结词集合,用其中联结词构成的式子足以把一切命题公式等价地表达出来,则这个联结词集合称为全功能的，相应的把这个集合称为联结词功能完备集完备集全体联结词的无限集合是完备的{

,∨,∧}是完备的联结词集合{

,∨}是联结词的完备集证明：已知{

,∨,∧}是全功能的，又P∧Q

(

P∨

Q)，因此∧可由{

,∨}表示，所以{

,∨}是全功能的{

,∧}是联结词的完备集{

,→}是完备集{↑}是完备集{↓}是完备集(独立的完备集){

,∧,∨,→,↔}是完备的不完备集{∨,∧,→,↔}{¬,↔}{∨,∧,→,↔}其任何子集都是不完备的{¬,↔}{∨,∧}其他联接词异或与非↑或非↓{↑}是完备集{↓}是完备集对偶原理交换律A∨B

B∨AA∧B

B∧A结合律(A∨B)∨C

A∨(B∨C)(A∧B)∧C

A∧(B∧C)分配律A∧(B∨C)

(A∧B)∨(A∧C)A∨(B∧C)

(A∨B)∧(A∨C)德摩根律¬(A∨B)

¬A∧¬B¬(A∧B)

¬A∨¬B幂等律A∧A

A，A∨A

A吸收律A∨(A∧B)

A，A∧(A∨B)

A零元律A∨T

T，A∧F

F同一律A∨F

A，A∧T

A排中律A∨¬A

T矛盾律A∧¬A

F关于¬、∧、∨联词的基本等价式均成对出现共轭联词共轭常量共轭量词()对偶式设有公式A,其中仅有联结词∧,∨,┐。在A中将∧,∨,T,F分别换以∨,∧,F,T得公式A*,则A*称为A的对偶(公)式。(A*)*?(A*)*

A例

(a)A=P∨F

，A*=？

A*=P∧T

(b)A=┐P∨Q∧R，A*=？

A*=┐P∧Q∨R

注意定理设A和A*是对偶式。P1,P2,…,Pn是出现于A和A*中的所有命题变元,于是

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)证明：反复地使用德-摩根定律A(P,Q)

P∨Q，A*(P,Q)

P∧Q

A(P,Q)

(P∨Q)A*(

P,

Q)

P∧

Q

A(P,Q)

A*(

P,

Q)推论:A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

因为

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

所以A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)即A(P1,P2,…,Pn)↔A*(

P1,

P2,…,

Pn)是重言式则A(

P1,

P2,…,

Pn)↔A*(P1,P2,…,Pn)是重言式所以A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)定理（对偶原理）若A

B,且A,B为命题变元P1,P2,…..,Pn及联结词∧,∨,

构成的公式,则A*

B*。 证明：因为A(P1,P2,…,Pn)

B(P1,P2,…,Pn)

故A(

P1,

P2,…,

Pn)

B(

P1,

P2,…,

Pn)

而A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

B(

P1,

P2,…,

Pn)

B*(P1,P2,…,Pn)

故A*(P1,P2,…,Pn)

B*(P1,P2,…,Pn)

所以A*(P1,P2,…,Pn)

B*(P1,

P2,…,

Pn)若A

B,且A,B为命题变元P1,P2,…..,Pn及联结词∧,∨,

构成的公式,则A*

B*成立吗？如果是，请证明；如果否，为什么？若A

B,且A,B为命题变元P1,P2,…..,Pn及联结词∧,∨,

构成的公式,则B*

A*等价变换存在过程不规范的问题初等数学中范式x2+xy+2y(x+y)应化成：x2+3xy+2y2或(x+y)(x+2y)x2+3yx+2y2(y+x)(x+2y)虽然等值，但不规范命题逻辑中，将公式化成主范式可使公式有唯一表示形式而：析取范式和合取范式范式就是命题公式形式的规范(标准化)形式范式中只含有联结词

、∨和∧基本积、基本和文字（因子）原子或原子的否定称为文字(基子句)例：P，

PP与

P称为互补对基本积文字的合取式（短语）P、

P、P∧Q、P∧Q∧R基本和文字的析取式（子句）P、

P、P∨Q、P∨Q∨R定理一个基本积是永假式,当且仅当它含有P,┐P形式的两个因子。 证明： 充分性：

P∧┐P是永假式,

而Q∧F

F,

所以含有P和┐P形式的两个因子时,此基本积是永假式

必要性：（反证法） 设基本积永假但不含P和┐P形式的两个因子,

则给这个基本积中不带否定符的命题变元指派真值T,

带有否定符的命题变元指派真值F,得基本积的真值是T,

与题设矛盾。 证毕。析取范式一个由基本积之和组成的公式,如果与给定的命题公式A等价,则称它是A的析取范式,记为

A

A1∨A2∨…∨An

,n≥1

这里A1,A2,…,An是基本积。任何一个命题公式都可求得它的析取范式一个命题公式的析取范式不是唯一的最简析取范式：运算符最少的析取范式合取范式一个由基本和之积组成的公式,如果与给定的命题公式A等价,则称它是A的合取范式,记为

A

A1∧A2∧…∧An

,n≥1

这里A1,A2,…,An是基本和任何一个命题公式都可求得它的合取范式一个命题公式的合取范式不是唯一的最简合取范式：运算符最少的合取范式析取范式与合取范式的求法⑴先用相应的公式去掉和。公式E16P

Q

P∨Q

公式E21PQ(P∧Q)∨(

P∧

Q)

公式E20PQ(P

Q)∧(Q

P)

再用E16PQ(P∨Q)∧(P∨

Q)⑵用公式的否定公式或摩根律将后移到命题变元之前。

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

摩根律

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q⑶用分配律、幂等律等公式进行整理，使之成为所要求的形式。

例(a)求P∧(P→Q)的析取范式。解P∧(P→Q)

P∧(┐P∨Q)

P∧┐P∨P∧Q

或：P∧(P→Q)

F∨P∧Q

P∧Q最简析取范式同时是个合取范式(b)求┐(P∨Q)↔(P∧Q)的最简析取范式。解┐(P∨Q)↔(P∧Q)

(┐(P∨Q)∧(P∧Q))∨((P∨Q)∧┐(P∧Q))

(┐P∧┐Q∧P∧Q)∨((P∨Q)∧(┐P∨┐Q))

┐P∧Q∨P∧┐Q

例(a)证明Q∨P∧┐Q∨┐P∧┐Q是永真式。解Q∨P∧┐Q∨┐P∧┐Q

Q∨(P∨┐P)∧┐Q

(Q∨P∨┐P)∧(Q∨┐Q)

Q∨P∨┐P

T，(Q∨┐Q)

T

所以(Q∨P∨┐P)∧(Q∨┐Q)

T(b)求┐(P∨Q)↔(P∧Q)的最简合取范式。

解┐(P∨Q)↔(P∧Q)

(┐(P∨Q)→(P∧Q))∧

((P∧Q)→┐(P∨Q))

((P∨Q)∨(P∧Q))∧(┐(P∧Q)∨┐(P∨Q))

(P∨Q)∧((┐P∨┐Q)∨(┐P∧┐Q))

(P∨Q)∧(┐P∨┐Q)主析取范式和主合取范式极小项在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫关于这n个变元的极小项。设P1,P2,…,Pn是n个命题变元，则称

P1’∧P2’

∧…∧Pn’

为关于P1,P2,…,Pn的极小项，其中Pi’

为Pi或┐Pi极小项(续)P∧Q、P∧Q、P∧Q、P∧Q？文字的出现顺序与变元符号的字典顺序一致n个变元可构成2n个不同的极小项命题变元看成1,命题变元的否定看成0,那么每一极小项对应一个二进制数,因而也对应一个十进制数把对应的十进制数当作足标,用mi表示这一项m0

┐P∧┐Q∧┐R——000——0m1

┐P∧┐Q∧R——001——1m2

┐P∧Q∧┐R——010——2m3

┐P∧Q∧R——011——3m4

P∧┐Q∧┐R——100——4m5

P∧┐Q∧R——101——5m6

P∧Q∧┐R——110——6m7

P∧Q∧R——111——7一般地，对P1,…,Pn而言，2n个极小项为：三个变元八个小项的真值表PQRm0m1m2m3m4m5m6m70

000010

100111001011101111000000001000000001000000001000000001000000001000000001000000001m0

┐P∧┐Q∧┐Rm1

┐P∧┐Q∧Rm7

P∧Q∧R极小项的性质合取式每个极小项mk只在与其下标对应的真值指派下为T，其余都为Fmi∧

mj

F，i≠j∨mi

T（0≤i≤2n-1）一个由极小项之和组成的公式,如果与给定的命题公式A等价,则称它是A的主析取范式。小项应以下标递增次序排列设G=(P

Q)

(

P

R)

(Q

R)PQRG0

00000110

10001111000101011011111┐P∧┐Q∧R┐P∧Q∧RP∧Q∧┐RP∧Q∧R∨∨∨

m1∨m3∨m6∨m7∑(1，3，6，7)定理每一个不为永假的命题公式A(P1,P2,…,Pn)必与一个由P1,P2,…,Pn所产生的主析取范式等价。且在A的真值表中，使A为T的指派所对应的诸小项之析取，即为A的主析取范式。永真公式的主析取范式包含所有2n个极小项永假公式的主析取范式是一空公式，用F表示证明：存在性：由上页主析取范式的构造过程可证唯一性：设有两个不同的主析取范式B和C都与A等价由于B和C不同，即必存在极小项mi在B中但不在C中，或在C中但不在B中，不妨设其在B中但不在C中。则在i对应的真值指派下，mi为T，即B为T，而C为F与B和C都是A的主析取范式矛盾唯一性得证唯一用等价变换求主析取范式先用相应的公式去掉和用公式的否定公式或摩根律将后移到命题变元之前用分配律、幂等律等公式进行整理，使之成为析取范式A1∨A2∨...∨An

为使每个Ai都变成极小项，对缺少变元的Ai补全变元，比如缺变元R，就用∧联结永真式(R∨

R)形式补R消去重复的极小项，并将极小项按下标由小到大的次序排列规范(甚至可以机器完成)例求G=

(R

P)

(Q

(P

R))主析取范式G

(R

P)

(Q

(P

R))

(

R

P)

(Q

P)

(Q

R)

(

P

R)

(Q

P)

(Q

R)

((

P

R)

(

Q

Q))

((Q

P)

(

R

R))

( (Q

R)

(

P

P))

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R) ∑(1，3，6，7)利用主范式证明两公式等价例证明：┐P∨Q和P→((P→Q)∧┐(┐Q∨┐P))二式等价。

证┐P∨Q

┐P∧(Q∨┐Q)∨Q∧(P∨┐P)

┐P∧Q∨┐P∧┐Q∨P∧Q

P→((P→Q)∧┐(┐Q∨┐P))

┐P∨((┐P∨Q)∧(Q∧P))

┐P∨(┐P∧Q∧P)∨(Q∧Q∧P)

┐P∨P∧Q

┐P∧(Q∨┐Q)∨P∧Q

┐P∧Q∨┐P∧┐Q∨P∧Q所以,二式逻辑等价。极大项在n个变元的基本和中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本和叫关于这n个变元的极大项。关于P,Q：P∨Q、P∨Q、P∨Q、P∨Q文字的出现顺序与变元符号的字典顺序一致n个变元可构成2n个不同的极大项命题变元看成0,命题变元的否定看成1,那么每一极大项对应一个二进制数,因而也对应一个十进制数把对应的十进制数当作足标,用Mi表示这一项M0

P∨Q∨R——000——0M1

P∨Q∨┐R——001——1M2

P∨┐Q∨R——010——2M3

P∨┐Q∨┐R——011——3M4

┐

P∨Q∨R——100——4M5

┐

P∨Q∨┐R——101——5M6

┐

P∨┐Q