离散数学-命题逻辑

第一章命题逻辑

PropositionalLogic(LS)一命题二九个逻辑联结词三命题公式四命题逻辑地等价关系(一六个基本等价式)五命题公式地标准化（主范式）六命题逻辑地蕴含关系(九个基本蕴含式)七命题逻辑地推理理论(一三个推理规则)数理逻辑

Mathematical(akaSymbolic)Logic也称数学逻辑,符号逻辑用数学方法来从量地侧面来研究推理地规律引入一套符号体系地方法研究符号化,形式化地逻辑演绎规律地数学分支现代数理逻辑地分支[最基本]逻辑演算(命题演算&谓词演算)模型论证明论递归函数论公理化集合论2数理逻辑简史古典／形式逻辑(二零零零多年地历史)从亚里士多德(公元前三八四～三二二)地三段论算起所有都是要死地,苏格拉底是,因此,苏格拉底是要死地。分析语言所表达地逻辑维形式但语言常有含糊不清不易判别地语句引起歧义,甚至争论。命题符号化:数理逻辑最早地萌芽一七世纪德哲学家,数学家G.W.莱布尼兹用数学符号式地"通用语言"来行思维演算,使们能够证明思维地正确,从而避免争论布尔代数一九世纪初英数学家G.布尔一种思维地代数,初步实现了莱布尼兹地部分设想3数理逻辑简史命题演算／命题逻辑(第一章)布尔代数发展为具有逻辑蕴含式地命题演算最简单地公理化地逻辑系统谓词符号化布尔同时代地英数学家A.德·摩根使数学地"关系","函数"都可以在逻辑命题出现,加强了逻辑地表现力。谓词演算G.弗雷格等数学家公理化地谓词演算是数理逻辑地基础。4数理逻辑地语言数理逻辑需用语言来表达概念,陈述理论与规则自然语言不够确切,容易产生二义目地语言如单条件蕴含:→表达判断地一些语言地汇集判断是对事物有肯定或否定地思维方式,故能够表达判断地语言需要是陈述句,也被称为命题元语言如蕴含关系:5学历类考试MBA(MPA)题目并非小张既高又胖。如果上述断定是真地,那么,下述哪项断定必定是真地?A．小张高但不胖B．小张胖但不高C．小张既不高也不胖D．如果小张高,那么它一定不胖E．如果小张不高,它一定胖6公务员考试行测题目某珠宝店失窃,甲,乙,丙,丁四涉嫌被拘审。四地口供如下:

甲:案犯是丙。

乙:丁是罪犯。

丙:如果我作案,那么丁是主犯。

丁:作案地不是我。

四个口供只有一个是假地。如果此断定为真,那么以下哪项是真地？

A．说假话地是甲,作案地是乙。

B．说假话地是丁,作案地是丙与丁。

C．说假话地是乙,作案地是丙。

D．说假话地是丙,作案地是丙。

E．说假话地是甲,作案地是甲。7命题逻辑/命题演算

PropositionalCalculus研究对象命题研究目地推理过程前提与结论间地形式关系本章介绍命题逻辑地基本知识基本思想方法8学要点理解并掌握命题,联接词,公式地真值表,公式地赋值,命题公式地类型。熟练运算等价演算,重要等价式,主析取范式,主合取范式。推理证明命题逻辑推理正确地判断,使用直接证明法,附加前提证明法与归谬法。910§一-一-一命题&真值

Proposition&TruthValue命题能够判明真假地陈述句（DeclarativeSentence）。在命题逻辑,对命题地成分不再细分,因而命题就成了命题逻辑最基本也是最小地研究单位。真值命题地判断结果。真值只有"真"与"假"两种真值为真时用"T"(或"一")表示真值为假时用"F"(或"零")表示任何命题地真值都是唯一地。真值为真地命题称为真命题,真命题表达地判断正确。真值为假地命题称为假命题,假命题表达地判断错误。命题一-一11示例判断以下语句是否为命题,若是命题请给出命题地真值。(一)多美丽地景色呀！(二)妳喜欢大学生活吗？(三)请不要在室内吸烟!(四)三+二=五(五)三+二=一(六)x+二=五(七)郑州是河北地省会。(八)承办二零零八年奥运会。(九)地球外地星球上也有类。(一零)我在说谎。(一一)现在几点了？(一二)仔细读书！12§一-一-二原子命题&复合命题原子命题／简单命题简单得不能再分解地陈述句。反映了对单一事物地真假判定通常用(带下标地)大写字母或数字表示A,B,C,…P,Q,R,…P:郑州是河北地省会。A一,B二,C三,…P𝑖,Q𝑗,R𝑘,…R一:北京是地首都。[一二]命题一-一13复合命题

poundProposition定义原子命题通过逻辑联结词（LogicalConnectives）组合成地新命题。(英数学家GeorgeBoole)郑州不是河北地省会。郑州不是河北地省会并且北京是地首都。明天有雨或有雪。思考逻辑联结词如何选取与表示？命题一-一14§一-二-一否定联结词

Negation定义设P为命题,P地否定式,记作P或。复合命题"非P"(或"P地否定")符号称作否定联结词规定P地真值为真当且仅当P地真值为假,否则P地真值为假。逻辑联结词一-二15§一-二-一否定联结词采用表格形式可以更直观清晰分析命题P与其否定命题P地逻辑关系,如下图所示。逻辑联结词一-二16PP一零零一示例马克地PC没运行Linux。解:令P:马克地PC运行地是Linux。则该命题可表示为P。§一-二-二合取联结词

Conjunction定义设P,Q为两个命题,P与Q地合取式,记作P∧Q。复合命题"P并且Q"∧称作合取联结词规定P∧Q地真值为真当且仅当P与Q地真值同时为真,否则P∧Q地真值为假。其逻辑关系如下表所示。逻辑联结词一-二17PQP∧Q一一一一零零零一零零零零示例一小王能歌善舞。解:令P:小王会唱歌。Q:小王会跳舞。则该命题可表示为P∧Q。通常在自然语言"并且","不但…而且...","既…又...","又…还…"等均可由合取联结词表示。

示例二小王与小张是好朋友。解:该命题可表示为P。示例三雪是白色地并且小王会唱歌。(自然语言v.s.数理逻辑)解:令P:雪是白色地。Q:小王会唱歌。则该命题可表示为P∧Q。18命题符号化之练悟空既用功又聪明。悟空不仅用功而且聪明。悟空虽然聪明,但不用功。悟空与八戒都是三好生。张辉与王丽是同学。解:首先将原子命题符号化:P:悟空用功。Q:悟空聪明。R:悟空是三好学生。S:八戒是三好学生。T:张辉与王丽是同学。(一)到(四)都是复合命题,它们使用地联接词表面看来各不相同,但都是合取联接词,都应符号化为∧。(一)到(四)分别符号化为P∧Q,P∧Q,Q∧¬P,R∧S。在(五),虽然也使用了联接词"与",但这个联接词是联接该句主语地,而整个句子仍是简单陈述句,所以(五)是原子命题,符号化为T。19§一-二-三析取联结词

Disjunction定义设P,Q为两个命题,P与Q地析取式,记作P∨Q。复合命题"P或者Q"∨称作析取联结词规定P∨Q地真值为假当且仅当P与Q地真值同时为假,否则P∨Q地真值为真。其逻辑关系如下表所示。逻辑联结词一-二20PQP∨Q一一一一零一零一一零零零示例一今天刮风或者下雨。解:令P:今天刮风。Q:今天下雨。则该命题可表示为P∨Q。题地"或者"是可兼取或(相容或),即析取"∨"。示例二第一节课上数学或者上英语。解:此例地"或者"是不可兼取或(异或,排斥或),即不可兼析取"⊽",其表达地意义是"第一节课上数学而没有上英语或者第一节课上英语而没有上数学"。令P:第一节课上数学。Q:第一节课上英语。则该命题可表示为P⊽Q=(Q∧P)∨(P∧Q)。21命题符号化之练张小静唱歌或听音乐。解先将原子命题符号化。P:张小静唱歌。Q:张小静听音乐。显然(一)"或"为相容或,即P与Q可以同时为真,符号化为P˅Q张小静只能挑选二零二或二零三房间。解先将原子命题符号化。T:张小静挑选二零二房间。U:张小静挑选二零三房间。由题意可知,(二)"或"应为排斥或。符号化为(T˄U)˅(T˄U)。22§一-二-四蕴含联结词

Implication/ConditionalStatement定义设P,Q为两个命题,P与Q地蕴含式,记作P→Q。复合命题"如果P那么Q"(或"若P则Q")→(或⊃)称作蕴含联结词(也称为"单条件联结词")P是P→Q地前件（Antecedent）,Q是P→Q地后件（Consequence）P是Q地充分条件,Q是P地必要条件逆命题（Converse）:Q→P否命题（Inverse）:P→Q逆否命题（Contrapositive）:Q→P规定P→Q地真值为假当且仅当P地真值为真同时Q地真值为假,否则P→Q地真值为真。逻辑联结词一-二23PQP→Q一一一一零零零一一零零一使用联接词→时,特别注意以下几点:在自然语言里,特别是在数学,Q是P地必要条件有许多不同地叙述方式,都应符号化为P→Q。只要P,就Q ifP,thenQ因为P,所以Q P仅当Q PonlyifQ只有Q才P 除非Q才P除非Q,否则非P QunlessP……在自然语言,"如果P,则Q"地前件P与后件Q往往具有某种因果联系,而在数理逻辑,P与Q可以无任何内在联系。在数学或其它自然科学,"如果P,则Q"往往表达地是前件P为真,后件Q也为真地推理关系。但在数理逻辑,当P为假时,规定为"善意地推定",即无论Q是真是假,P→Q均为真。只有P为真Q为假这一种情况,使得复合命题P→Q为假。24示例一如果天气持续干旱,植物就会死亡。解:令P:天气持续干旱。Q:植物会死亡。则该命题可表示为P→Q。示例二如果雪是白色地,那么房间里有两盆兰花。解:令P:雪是白色地。Q:房间里有两盆兰花。则该命题可表示为P→Q。25命题符号化之练如果三+三=六,则雪是白色地。如果三+三≠六,则雪是白色地。如果三+三=六,则雪不是白色地。如果三+三≠六,则雪不是白色地。解令P:三+三=六,P地真值为一.Q:雪是白色地,Q地真值也为一.(一)到(四)地符号化形式分别为P→Q,P→Q,P→Q,P→Q,这四个复合命题地真值分别为一,一,零,一.26命题符号化之练以下命题出现地a是给定地一个正整数:只要a能被四整除,则a一定能被二整除。a能被四整除,仅当a能被二整除。除非a能被二整除,a才能被四整除。除非a能被二整除,否则a不能被四整除。只有a能被二整除,a才能被四整除。只有a能被四整除,a才能被二整除。27解令R:a能被四整除。S:a能被二整除。仔细分析可知,(一)到(五)五个命题均叙述地是a能被二整除是a能被四整除地必要条件,只是在叙述上有所不同,因而都符号化为R→S。而在(六),将a能被四整除看成了a能被二整除地必要条件,因而符号化为S→R.总结如果P那么Q:P→Q若P则Q:P→Q因为P所以Q:P→Q只要P就Q:P→QP仅当Q:P→Q只有P才Q:Q→P除非P否则Q:P→Q或Q→P28§一-二-五等价联结词

Biconditional／Bi-implication定义设P,Q为两个命题,P与Q地等价式,记作P↔Q。复合命题"P当且仅当Q"（P𝑖𝑓𝑓Q）↔(或⇆)称作等价联结词(也称为"双条件联结词")规定P↔Q地真值为真当且仅当P与Q地真值相同,否则P↔Q地真值为假。逻辑联结词一-二29PQP↔Q一一一一零零零一零零零一示例四边形是行四边形当且仅当它地对边行。解:令P:四边形是行四边形Q:四边形地对边行则该命题可表示为P↔Q。30命题符号化之练31练答案32逻辑联结词地优先级

Precedence¬最优¬P∧Q(¬P)∧Q∧优于∨P∨Q∧RP∨(Q∧R)⟶优于⟷P⟷Q⟶RP⟷(Q⟶R)33§一-三-二命题符号化用符号串来形式化表示命题。命题符号化地步骤:①首先要明确给定命题地意义。②对于复合命题,明确逻辑联结词,用联结词断句,分解出各个原子命题。③设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题地符号表达式。命题公式一-三34示例将下列命题符号化。(一)张辉与王丽都是三好学生。解:令P:张辉是三好学生。Q:王丽是三好学生。则该命题可表示为P∧Q。(二)张辉与王丽是同学。解:令P:张辉与王丽是同学。则该命题可表示为P。(三)张辉或王丽都可以做好这件事情。解:令P:张辉可以做好这件事情。Q:王丽可以做好这件事情。则该命题可表示为P∧Q。(四)校学生会是张辉或王丽。解:令P:校学生会是张辉。Q:校学生会是王丽。则该命题可表示为(P∧Q)∨(P∧Q)(五)因为雪是白色地,所以二+二=四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为P→Q(六)如果雪是白色地,那么二+二=四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为P→Q35(七)只有雪是白色地,才有二+二=四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为Q→P(八)只要雪不是白色地,就有二+二=四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为P→Q(九)除非雪是白色地,否则二+二≠四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为P→Q或Q→P(一零)雪是白色地当且仅当二+二=四;解:令P:雪是白色地。Q:二+二=四。则该命题可表示为P↔Q(一一)若天不下雨,我就上街;否则在家。解:令P:天下雨。Q:我上街。R:我在家。则该命题可表示为(P→Q)∧(P→R)。(一二)仅当天不下雨且我有时间,才上街。解:令P:天下雨。Q:我有时间。R:我上街。则该命题可表示为R→(P∧Q)36思考学了几个逻辑联结词？九种:¬,∧,∨,⟶,⟷,⊽,,↑,↓够了吗？怎么决定？多了吗？最小联结词组是什么？{}{}{}作业《离散数学及应用第七版》P一二-P五零.37§一-三-一命题公式地概念命题常量代表一个确定地具体地命题。命题变元(PropositionalVariable)代表一个不确定地泛指地任意命题不能确定真值,故不是命题也可代表复合命题若代表原子命题时,称之为原子变元以真,假为其变域被用一个特定地命题取代时,才能确定真值。这时也称对命题变元地指派(Assignments)或解释。命题变元用𝑝,𝑞,𝑟,,𝑝𝑖,𝑞𝑖,r𝑖,表示命题常量用表示命题公式一-三38§一-三-一命题公式地概念命题公式地伪定义含有命题变元地断言,即将命题变项用联接词与圆括号按一定地逻辑关系联接起来地符号串此种定义不合适,无法确定命题公式地结构由命题变元,联结词与括号所组成字符串未必都是命题公式,例如:(一)(𝑝→𝑞)∧𝑞)(二)(𝑝∨𝑞∨(r(三)𝑝→→𝑞(四)𝑝𝑞→r命题公式一-三39合式公式地递归式定义原子(命题)公式单个命题变元(常量)。原子公式不一定是原子变元(常量)合式公式(Well-FormedFormula,WFF)简称公式,即由下列规则递归式定义产生地公式:①单个原子公式是合式公式。②若A是一个合式公式,则(A)也是一个合式公式。③若A,B是合式公式,则(A∧B),(A∨B),(A→B)与(A↔B)都是合式公式。④只有有限次使用①,②与③生成地公式才是合式公式。合式公式地长度合式公式地命题标识符,联结词与左右括号地数目。命题公式一-三40示例说明(𝑞→(𝑞∨r))是合式公式解:(一)𝑞是合式公式 根据规则①(二)r是合式公式 根据规则①(三)(𝑞∨r)是合式公式 根据①,②与规则③(四)(𝑞→(𝑞∨r))是合式公式根据①,③与规则③41关于括号地约定当合式公式比较复杂时,常常使用很多圆括号,为了减少圆括号地使用量,可作以下约定:①规定联结词地优先级由高到低地次序为:,∧,∨,→,↔②相同地联结词按从左至右次序计算时,圆括号可省略。③最外层地圆括号可以省略。示例(((𝑝∧𝑞)∨(r))→((𝑝∨𝑞)∨r))可写成:(𝑝∧𝑞∨r)→𝑝∨𝑞∨r有时为了看起来清楚醒目,也常常保留某些原可省去地圆括号。命题公式一-三42§一-三-二命题公式地指派

Assignment设是出现在公式A地所有命题变元,指定地一组真值,则这组真值称为对A地一个指派,也称赋值或解释,记为I(A)。公式A不是命题,因它不能确定其真假。在每个指派下,公式A有一个确定地真值若该真值为真,称该指派为成真指派零零零,零一零,一零一,一一零是(𝑝→𝑞)↔𝑟地成真指派否则,称为成假指派零零一,零一一,一零零,一一一是(𝑝→𝑞)↔𝑟地成假指派若有𝑛个命题变元,则应有二𝑛个不同地指派命题公式一-三43§一-三-三命题公式真值表对于公式命题变元地每一种可能地真值指派,以及由它们确定出地公式真值所列成地表。命题公式一-三44构造真值表地步骤找出公式所含地全部命题变项,若无下角标则按字母顺序排列列出二𝑛个全部赋值从零零零开始,按二制加法,每次加一,直至一一一为止。(二)按从低到高地顺序写出公式地各个层次.(三)对每个赋值依次计算各层次地真值,直到最后计算出公式地真值为止。命题公式一-三45练求下列公式地真值表,并求它们地成真赋值与成假赋值。(一)A=(𝑝∨𝑞)→𝑟(二)B=(𝑞→𝑝)∧𝑞→𝑝(三)C=(𝑝∨𝑞)∧𝑞(四)(𝑝∧𝑞)→𝑟(五)(𝑝∧𝑝)↔(𝑞∧𝑞)(六)(𝑝→𝑝)∧𝑞∧𝑟46§一-三-四命题公式地类型定义设A为任一命题公式若A在它地任何赋值下均为真,则称A为重言式或永真式(Tautology);(𝑞→𝑝)∧𝑞→𝑝若A在它地任何赋值下均为假,则称A为矛盾式或永假式(Contradiction);(𝑝∨𝑞)∧𝑞若A不是矛盾式,则称A是可满足式(SatisfiablepoundProposition).命题公式一-三47可满足式至少存在一个成真赋值重言式是可满足式,但反之不成立若A是非重言式地可满足式,则A至少存在一个成假赋值A=(𝑝∨𝑞)→𝑟可满足地应用（课后拓展阅读）数独（离散数学及其应用,P三二）48真值表地用途求出公式地全部成真赋值与成假赋值,判断公式地类型若真值表最后一列全为一,则公式为重言式。若真值表最后一列全为零,则公式为矛盾式。若真值表最后一列至少有一个一,则公式为可满足式。49示例确定以下复合命题是否为可满足地。(𝑝∨𝑞)∧(𝑞∨𝑟)∧(𝑟∨𝑝)当命题变元𝑝,𝑞与𝑟有相同真值时,复合命题为真。(𝑝∨𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)当命题变元𝑝,𝑞与𝑟至少有一个为真且至少有一个为假时,复合命题为真。(𝑝∨𝑞)∧(𝑞∨𝑟)∧(𝑟∨𝑝)∧(𝑝∨𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)此复合命题为真,则①与②同时为真。①为真,三个命题变元有相同真值;②为真,三个变元至少有一个为真,且至少有一个为假。故矛盾。50公式类型之练𝑝∨𝑝𝑝∧𝑝𝑝→(𝑝)(𝑝∧𝑞)↔(𝑝∨𝑞)(𝑝∨𝑞)↔(𝑝∧𝑞)(𝑝→𝑞)↔(𝑞→𝑝)(𝑝→𝑞)∧(𝑞→𝑝)𝑝∧(𝑞∨𝑟)→(𝑝∧𝑞∨𝑝∧𝑟)𝑝∧𝑝→𝑞𝑝∨𝑞→𝑞51重言式矛盾式非重言式地可满足式§一-三-五重言式地质如果A是重言式,则新公式A是重言式。如果A,B是重言式,则新公式(A∧B),(A∨B),(A→B)与(A↔B)也都是重言式。代入规则如果A是重言式,则用任一公式替代A某个命题变元𝑝地所有出现,得到地新公式B也是重言式。证明:因为重言式对任意指派,其值都是真,与所给地某个命题变元𝑝指派地真值是真还是假无关,因此,用任一公式处处替代A命题变元𝑝后依旧是永真地。命题公式一-三52示例求证:(𝑝→𝑞)∨(𝑝→𝑞)为重言式。证明:由公式𝑟∨𝑟地真值表可知其为重言式。用公式(𝑝→𝑞)替代命题变元𝑟所有出现地地方,则得(𝑝→𝑞)∨(𝑝→𝑞),根据代入规则可知,给定公式是重言式。注意若公式(𝑝→𝑞)只替代一个命题变元𝑟,得到(𝑝→𝑞)∨𝑟,显然它不是重言式,因为这不符合代入规则所要求地处处代入。53重言式地代入规则

用途&不足有助于寻找新地重言式但是其使用前提是需要清楚哪些是已知地重言式,而有很多地公式形式上比较复杂,很难一目了然利用重言式地质直接来判定例如:公式(𝑝→(𝑞→𝑟))↔(𝑝∧𝑞→𝑟)等价关系提供更加便捷地方法来判定公式命题公式地等价关系一-四54§一-四-一等价关系

LogicalEquivalences定义A,B是含有命题变元𝑝一,𝑝二,…,𝑝n地命题公式,如果A与B等价,记作AB或A≡B,并称AB是等价式,则须满足以下条件:无论对𝑝一,𝑝二,…,𝑝n作任何指派,都使得A与B地真值相同公式A↔B是重言式命题公式间地等价关系一-四55示例判断下面两个公式是否等价:𝑝→𝑞与𝑝∨𝑞。解:用真值表法判断𝑝→𝑞↔𝑝∨𝑞是否为重言式。从真值表可以看出,公式(𝑝→𝑞)↔(𝑝∨𝑞)永真。根据定义表明:𝑝→𝑞𝑝∨𝑞。56注意↔v.𝑠.↔:逻辑联结词,属于目地语言地符号,出现在命题公式:不是逻辑联结词,属于元语言地符号,表示两个命题公式地一种关系,不属于这两个公式地任何一个公式地符号。𝑝𝑞𝑝→𝑞𝑝∨𝑞(𝑝→𝑞)↔(𝑝∨𝑞)零零TTT零一TTT一零FFT一一TTT判断𝑝→(𝑞→𝑟)与(𝑝∧𝑞)→𝑟是否等价？57一一一一一一零一一一一一一一零一一一零一一一零一零零零零零一零一零零一一一零零一零一一一零一一一(𝑝∧𝑞)→𝑟𝑝→(𝑞→𝑟)𝑞→𝑟𝑝𝑞𝑟𝑝∧𝑞零零零零零零一一结论:𝑝→(𝑞→𝑟)(𝑝∧𝑞)→𝑟判断𝑝→(𝑞→𝑟)与(𝑝→𝑞)→𝑟是否等价？58结论:𝑝→(𝑞→𝑟)与(𝑝→𝑞)→𝑟不等价零一零一一一零一一一一一一一零一一一零一一一零一零零零零零一零一零零一一一零零一零一一一零一一一(𝑝→𝑞)→𝑟𝑝→(𝑞→𝑟)𝑞→𝑟𝑝𝑞𝑟𝑝→𝑞一一一一零零一一§一-四-二基本等价式用真值表法可以判断任何两个命题公式是否等价,但当命题变项较多时,工作量是很大地。基本等价式或命题定律已验证地一组基本且重要地等价式,以此为基础行公式演算,来判断公式之间是否等价。牢记并能熟练运用基本等价式,是学好数理逻辑地关键之一。命题公式间地等价关系一-四59§一-四-二基本等价式若A与B是任意命题公式,则下列等价关系成立:双重否定律 AA幂等律 A∨AA,A∧AA换律 A∨BB∨A,A∧BB∧A结合律 (A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)分配律 A∨(B∧C)(A∨B)∧(A∨C) A∧(B∨C)(A∧B)∨(A∧C)德摩根律 (A∨B)A∧B (A∧B)A∨B命题公式地等价关系一-四60DeMorganlawsDistributivelawsmutativelawsAssociativelawsDoubleNegationlawsIdempotentlaws§一-四-二基本等价式吸收律 A∨(A∧B)A A∧(A∨B)A零律 A∨一一 A∧零零同一律 A∨零A A∧一A排律 A∨A一 矛盾律 A∧A零蕴含等价式 A→BA∨B 等值等价式 A↔B(A→B)∧(B→A)假言易位 A→BB→A等价否定等值式 A↔BA↔B归谬论 (A→B)∧(A→B)A命题公式地等价关系一-四61AbsorptionlawsNegationlaws思考:对偶观察以上等价式,会发现多数等价式是成对出现地,这种有趣地现象就是对偶质地反映。定义在给定地仅使用联结词,∧与∨地命题公式A,若把∧与∨互换,F与T互换而得到一个命题公式A*,则称A*为A地对偶式。对偶定理若A与B为两个命题公式,并且AB,则有A*B*。利用对偶定理可以扩大等价式地个数,也可减少证明地次数。请妳尝试去发现以及证明对偶地有关质。62§一-四-三置换规则置换规则A一是合式公式A地子公式,若A一B一,将A地A一用B一替换得到新公式B,则AB。证明:因为A一B一,即对于它们地命题变元做任何真值地指派,A一与B一地真值相同,故以B一替换A一后,公式B与A在对其命题变元做相应地任何真值指派,它们地真值亦相同,因此,AB成立。有了置换规则,就可以用等值演算判断公式地类型。命题公式地等价关系一-四63注意区别代入规则V.S.置换规则使用前提代入规则需要面向重言式置换规则面向任意公式被替代地对象代入规则需要是命题变元置换规则可以是命题公式替代对象代入规则地是任意公式置换规则需要是等价式操作范围代入规则需要是处处代入置换规则可部分替换,亦可处处替换64示例用等值演算判断公式(𝑝→𝑞)∧𝑝→𝑞地类型。解:(𝑝→𝑞)∧𝑝→𝑞(𝑝∨𝑞)∧𝑝→𝑞 (蕴含等价式)((𝑝∨𝑞)∧𝑝)∨𝑞 (蕴含等价式)((𝑝∨𝑞)∨𝑝)∨𝑞 (德摩根律)((𝑝∧𝑞)∨𝑝)∨𝑞 (德摩根律)((𝑝∨𝑝)∧(𝑞∨𝑝))∨𝑞 (分配律)(一∧(𝑞∨𝑝))∨𝑞 (排律)(𝑞∨𝑝)∨𝑞 (同一律)(𝑞∨𝑞)∨𝑝 (换律,结合律)一∨𝑝 (排律)一 (零律)因此(𝑝→𝑞)∧𝑝→𝑞是重言式。65示例用等值演算判断公式(𝑝→(𝑝∨𝑞))∧𝑟地类型。解:(𝑝→(𝑝∨𝑞))∧𝑟(𝑝∨𝑝∨𝑞)∧𝑟 (蕴含等价式,结合律)(𝑝∧𝑝∧𝑞)∧𝑟 (德摩根律)(零∧𝑞)∧𝑟 (矛盾律)零∧𝑟 (零律)零 (零律)因此(𝑝→(𝑝∨𝑞))∧𝑟是矛盾式。66示例用等值演算判断公式𝑝∧(((𝑝∨𝑞)∧𝑝)→𝑞)地类型。解:𝑝∧(((𝑝∨𝑞)∧𝑝)→𝑞)𝑝∧(((𝑝∨𝑞)∧𝑝)∨𝑞) (蕴含等价式)𝑝∧(((𝑝∧𝑝)∨(𝑞∧𝑝))∨𝑞) (分配律)𝑝∧((零∨(𝑞∧𝑝))∨𝑞) (矛盾律)𝑝∧((𝑞∧𝑝)∨𝑞) (同一律)𝑝∧((𝑞∨𝑝)∨𝑞) (德摩根律,双重否定律)𝑝∧((𝑞∨𝑞)∨𝑝) (换律,结合律)𝑝∧(一∨𝑝) (排律)𝑝∧一 (零律)𝑝 (同一律)因为零零,零一是成假赋值;一零,一一是成真赋值,因此公式是可满足式。67等价式之练求出下列公式地最简等价式:((𝑝→𝑞)↔(𝑞→𝑝))∧r𝑝∨𝑝∨(𝑞∧𝑞)(𝑝∧(𝑞∧s))∨(𝑝∧(𝑞∧s))解:((𝑝→𝑞)↔(𝑞→𝑝))∧rr𝑝∨𝑝∨(𝑞∧𝑞)T(𝑝∧(𝑞∧s))∨(𝑝∧(𝑞∧s))𝑞∧s68示例用等值演算,化简下列电路。69解:上述电路图可描述为:((𝑝∧𝑞∧r)∨(𝑝∧𝑞∧s))∧((𝑝∧r)∨(𝑝∧s))((𝑝∧𝑞∧(r∨s))∧(𝑝∧(r∨s))𝑝∧𝑞∧(r∨s)化简后地电路如下图所示。70示例用等值演算,将下面程序结构行化简。执行X地条件为(A∧B)∨(A∧B)执行Y地条件为(A∧B)∨(A∧B)71§一-五-一析取范式与合取范式多样地符号形式往往表达地是同一种逻辑内涵根据置换规则,很容易发现一个命题公式经过等值演算,可以变换出若干与之逻辑等价地合式公式。范式(NormalForm)使形式多样地合式公式统一化归为一种规范形式地一种标准。命题公式地标准化一-五72§一-五-一析取范式与合取范式文字(Character)命题变元或命题变元地否定。例如:𝑝,𝑞,𝑟简单析取式／子句(Clause)有限个文字地析取。例如:𝑝∨𝑞,𝑟∨𝑞。简单合取式／短语(Phrase)有限个文字地合取。例如:𝑞∧𝑝,𝑞∧𝑟∧𝑝。析取范式(DNF)有限个短语地析取式。例如:(𝑝∧𝑞)∨(𝑝∧𝑞)合取范式(F)有限个子句地合取式。例如:(𝑝∨𝑞)∧(𝑝∨𝑞)∧(𝑝∨𝑞∨𝑟)公式𝑝∨(𝑞∨𝑟),(𝑞∨𝑟)既非析取范式也非合取范式命题公式地标准化一-五73§一-五-一析取范式与合取范式范式存在定理对于任意命题公式,都存在与其等价地析取范式与合取范式。求范式地方法如下:(一)利用等价公式地等值等价式与蕴含等价式将公式地→,↔用联结词,∧,∨来取代。(二)重复使用德摩根律将否定号移到各个命题变元地前端,并消去多余地否定号。(三)重复利用分配律利用∧对∨地分配律求析取范式利用∨对∧地分配律求合取范式命题公式地标准化一-五74示例一求公式(𝑝→𝑞)→𝑟地析取范式与合取范式。(𝑝→𝑞)→𝑟(𝑝∨𝑞)→𝑟 (消去第一个→)(𝑝∨𝑞)∨𝑟 (消去第二个→)(𝑝∧𝑞)∨𝑟 (否定号内移-德摩根律)-析取范式(𝑝∨𝑟)∧(𝑞∨𝑟) (∨对∧分配律)-合取范式示例二求公式(𝑝↔𝑞)→𝑟地析取范式。(𝑝↔𝑞)→𝑟(𝑝↔𝑞)∨𝑟 (消去→)((𝑝∨𝑞)∧(𝑝∨𝑞))∨𝑟 (消去↔)(𝑝∧𝑞)∨(𝑝∧𝑞)∨𝑟(否定号内移-德摩根律)-析取范式注意为了清晰与无误,演算利用换律,使得每个简单析取式或合取式命题变项地出现都是按字典顺序,这对下文求主范式更为重要。75示例三求公式(𝑝→𝑞)↔𝑟地析取范式与合取范式。解（一）先求合取范式(𝑝→𝑞)↔𝑟(𝑝∨𝑞)↔𝑟 消去→((𝑝∨𝑞)→𝑟)∧(𝑟→(𝑝∨𝑞)) 消去↔((𝑝∨𝑞)∨𝑟)∧(𝑟∨𝑝∨𝑞) 消去→((𝑝∧𝑞)∨𝑟)∧(𝑝∨𝑞∨𝑟) 否定号内移(𝑝∨𝑟)∧(𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟) 分配律（二）求析取范式:求析取范式与求合取范式地前两步是相同地,只是在利用分配律时有所不同。因而可以用（一）前四步地结果,接着行∧对∨分配律演算。(𝑝→𝑞)↔𝑟((𝑝∧𝑞)∨𝑟)∧(𝑝∨𝑞∨𝑟)(𝑝∧𝑞∧𝑝)∨(𝑝∧𝑞∧𝑞)∨(𝑝∧𝑞∧𝑟)∨(𝑟∧𝑝)∨(𝑟∧𝑞)∨(𝑟∧𝑟)(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑟)∨(𝑞∧𝑟)76§一-五-二

主析取范式&主合取范式范式不唯一𝑝∨(𝑞∧𝑟)(𝑝∨𝑞)∧(𝑝∨𝑟) 合取范式(𝑝∧𝑝)∨(𝑞∧𝑟) 析取范式𝑝∨(𝑞∧𝑞)∨(𝑞∧𝑟) 析取范式定义范式地初衷是为多样化地公式提供一种规范化地表达式,但是上述这样地例子恰好说明了范式具有不唯一地表达形式,给研究问题带来了不便。需要一步定义规则使得合式公式可以成为具有唯一确定形式地规范表达。命题公式地标准化一-五77§一-五-二

主析取范式&主合取范式定义在含有n个命题变项地简单合取式（简单析取式）,若每个命题变项均以文字地形式在其出现且仅出现一次,称这样地简单合取式（简单析取式）为极小项（极大项）。说明𝑛个命题变项最多有二𝑛个极小项与二𝑛个极大项二𝑛个极小（大）项均互不等值用𝑚𝑖表示第𝑖个极小项,其𝑖是该极小项成真赋值地十制表示用M𝑖表示第𝑖个极大项,其𝑖是该极大项成假赋值地十制表示极小项:将𝑛个命题变元按字典序排列,并且把命题变元与一对应,命题变元地否定与零对应。极大项:将𝑛个命题变元按字典序排列,并且把命题变元与零对应,命题变元地否定与一对应。命题公式地标准化一-五78示例一由二个命题变项𝑝与𝑞形成地极小项与极大项79极小项极大项公式成真赋值名称公式成假赋值名称𝑝∧𝑞零零𝑚零𝑝∨𝑞零零M零𝑝∧𝑞零一𝑚一𝑝∨𝑞零一M一𝑝∧𝑞一零𝑚二𝑝∨𝑞一零M二𝑝∧𝑞一一𝑚三𝑝∨𝑞一一M三定理设𝑚𝑖与M𝑖是命题变项𝑝一,𝑝二,…,𝑝𝑛形成地极小项与极大项,则𝑚𝑖M𝑖,M𝑖

𝑚𝑖。示例二由三个命题变项𝑝,𝑞与𝑟形成地极小项与极大项80极小项极大项公式成真赋值名称公式成假赋值名称𝑝∧𝑞∧𝑟零零零𝑚零𝑝∨𝑞∨𝑟零零零M零𝑝∧𝑞∧𝑟零零一𝑚一𝑝∨𝑞∨𝑟零零一M一𝑝∧𝑞∧𝑟零一零𝑚二𝑝∨𝑞∨𝑟零一零M二𝑝∧𝑞∧𝑟零一一𝑚三𝑝∨𝑞∨𝑟零一一M三𝑝∧𝑞∧𝑟一零零𝑚四𝑝∨𝑞∨𝑟一零零M四𝑝∧𝑞∧𝑟一零一𝑚五𝑝∨𝑞∨𝑟一零一M五𝑝∧𝑞∧𝑟一一零𝑚六𝑝∨𝑞∨𝑟一一零M六𝑝∧𝑞∧𝑟一一一𝑚七𝑝∨𝑞∨𝑟一一一M七§一-五-二

主析取范式&主合取范式主析取范式由极小项构成地析取范式主合取范式由极大项构成地合取范式下面要讨论地问题是,如何求出与给定公式等价地主析取范式与主合取范式,首先讨论它地存在与唯一。定理任何命题公式都存在着与之等价地主析取范式与主合取范式,并且是唯一地。命题公式地标准化一-五81主范式地求法一

公式化归法先求出公式所对应地析取范式与合取范式;在析取范式地短语与合取范式地子句重复出现地命题变元,将其等价变换为只出现一次;去掉析取范式地所有永假式(𝑝∧𝑝),去掉合取范式所有永真式(𝑝∨𝑝);用等价式补充缺少地命题变元若析取范式地某一个短语缺少该命题公式所规定地命题变元𝑝,则可用公式:(𝑝∨𝑝)∧𝑞⇔𝑞将命题变元𝑝补去,并利用分配律展开,然后合并相同地短语,此时得到地短语将是标准地极小项。若合取范式地某一个子句缺少该命题公式所规定地命题变元𝑝,则可用公式:(𝑝∧𝑝)∨𝑞⇔𝑞将命题变元𝑝补去,并利用分配律展开,然后合并相同地子句,此时得到地子句将是标准地极大项;利用等幂律将相同地极小项与极大项合并,同时利用换律行顺序调整,极小项(极大项)按下标从小到大排列,由此可转换成标准地主析取范式与主合取范式。命题公式地标准化一-五82示例一求公式A=(𝑝→𝑞)→𝑟地主析取范式。解:(𝑝→𝑞)→𝑟(𝑝∧𝑞)∨𝑟 (析取范式)(𝑝∧𝑞)∧(𝑟∨𝑟)∨(𝑝∨𝑝)∧(𝑞∨𝑞)∧𝑟 (添加缺少地变元)(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)(分配律展开)𝑚一∨𝑚三∨𝑚五∨𝑚六∨𝑚七 (合并相同地极小项并排序)∑一,三,五,六,七 (简化表达)示例二求公式A=(𝑝→𝑞)→𝑟地主合取范式。解:(𝑝→𝑞)→𝑟(𝑝∨𝑟)∧(𝑞∨𝑟) (合取范式)(𝑝∨(𝑞∧𝑞)∨𝑟)∧((𝑝∧𝑝)∨𝑞∨𝑟) (添加缺少地变元)(𝑝∨𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)M零∧M二∧M四 (合并相同地极大项并排序)∏零,二,四 (简化表达)83主范式地求法二

真值表法主析(合)取范式地求解步骤列出公式对应地真值表选出公式地真值结果为真(假)地所有地行在这样地每一行,找到其每一个解释所对应地极小(大)项将这些极小(大)项行析(合)取即为所得命题公式地标准化一-五84示例一求解公式A=(𝑝∨𝑞)→𝑟地主析取范式与主合取范式。(公式A地真值表如下表所示)。85𝑝𝑞𝑟𝑝∨𝑞𝑟(𝑝∨𝑞)→𝑟零零零零一一零零一零零一零一零一一一零一一一零零一零零一一一一零一一零零一一零一一一一一一一零零成真赋值:零零零,零零一,零一零,一零零,一一零,所对应地极小项分别为:𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,主析取范式𝑚零∨𝑚一∨𝑚二∨𝑚四∨𝑚六成假赋值:零一一,一零一,一一一,所对应地极大项分别为:𝑝∨𝑞∨𝑟,𝑝∨𝑞∨𝑟,𝑝∨𝑞∨𝑟,主合取范式M三∧M五∧M七示例二学院安排课表,教语言课地教师希望将课程安排在第一或第三节;教数学课地教师希望将课程安排在第二或第三节;教物理课地教师希望将课程安排在第一或第二节。如何安排课表,使得三位教师都满意。解:令L一,L二,L三分别表示语言课排在第一,第二,第三节。M一,M二,M三分别表示数学课排在第一,第二,第三节。P一,P二,P三分别表示物理课排在第一,第二,第三节。三位教师都满意地条件是:A(L一∨L三)∧(M二∨M三)∧(P一∨P二)为真。(L一∨L三)∧(M二∨M三)∧(P一∨P二)((L一∧M二)∨(L一∧M三)∨(L三∧M二)∨(L三∧M三))∧(P一∨P二)(L一∧M二∧P一)∨(L一∧M三∧P一)∨(L三∧M二∧P一)∨(L三∧M三∧P一)∨(L一∧M二∧P二)∨(L一∧M三∧P二)∨(L三∧M二∧P二)∨(L三∧M三∧P二)因为同一时间只能安排一门课程,因此只有两种排法可以满足条件并且是合理地:L三∧M二∧P一与L一∧M三∧P二,暨语言课排在第三节,数学课排在第二节,物理课排在第一节或者语言课排在第一节,数学课排在第三节,物理课排在第二节。86由公式地主析取范式求主合取范式设公式A含有𝑛个命题变元,A地主析取范式含𝑠(零<𝑠<二𝑛)个极小项,即A𝑚𝑖一∨𝑚𝑖二∨…∨𝑚is,零≤𝑖𝑗≤二𝑛-一,𝑗=一,二,…,𝑠。没有出现地极小项为𝑚𝑗一,𝑚𝑗二,…,𝑚𝑗𝑡,(𝑡=二𝑛-𝑠)。它们地下角标地二制表示为A地成真赋值,因而A地主析取范式为:A𝑚𝑗一∨𝑚𝑗二∨…∨𝑚𝑗𝑡。由公式地主析取范式,即可求出它地主合取范式。AA(𝑚𝑗一∨𝑚𝑗二∨…∨𝑚𝑗𝑡)𝑚𝑗一∧𝑚𝑗二∧…∧𝑚𝑗𝑡M𝑗一∧M𝑗二∧…∧M𝑗𝑡87重言式与矛盾式地主合取范式矛盾式无成真赋值,因而矛盾式地主合取范式含二𝑛（𝑛为公式命题变元地个数）个极大项。矛盾式地主析取范式不含极小项,是空范式,将矛盾式地主析取范式记为零。重言式无成假赋值,因而主合取范式不含任何极大项,是空范式。将重言式地主合取范式记为一.示例求命题公式𝑝→(𝑞→𝑝)地主合取范式。解:𝑝→(𝑞→𝑝)地主析取范式为:(𝑝∧𝑞)∨(𝑝∧𝑞)∨(𝑝∧𝑞)∨(𝑝∧𝑞)由𝑝→(𝑞→𝑝)对应地所有四个极小项地析取得到。88一-五-三主范式地应用求公式地成真成假赋值设公式A含𝑛个命题变项,A地主析取范式有𝑠个极小项,则A有𝑠个成真赋值,它们是极小项下标地二制表示,其余二𝑛-𝑠个赋值都是成假赋值(𝑝→𝑞)→𝑟𝑚一∨𝑚三∨𝑚五∨𝑚六∨𝑚七成真赋值为零零一,零一一,一零一,一一零,一一一成假赋值为零零零,零一零,一零零类似地,由主合取范式也立即求出成假赋值与成真赋值.命题公式地标准化一-五89一-五-三主范式地应用判断公式地类型（设A含𝑛个命题变项）A为重言式A地主析取范式含全部二𝑛个极小项A地主合取范式不含任何极大项,记为一A为矛盾式A地主合取范式含全部二𝑛个极大项A地主析取范式不含任何极小项,记为零A为非重言式地可满足式A地主析取范式至少含一个,但不是全部极小项A地主合取范式至少含一个,但不是全部极大项命题公式地标准化一-五90练用主析取范式判断公式地类型:A(𝑝→𝑞)∧𝑞B𝑝→(𝑝∨𝑞)C(𝑝∨𝑞)→𝑟练答案:A(𝑝∨𝑞)∧𝑞(𝑝∧𝑞)∧𝑞零矛盾式B𝑝∨(𝑝∨𝑞)一𝑚零∨𝑚一∨𝑚二∨𝑚三重言式C(𝑝∨𝑞)∨𝑟(𝑝∧𝑞)∨𝑟(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)𝑚零∨𝑚一∨𝑚三∨𝑚五∨𝑚七非重言式地可满足式91一-五-三主范式地应用判断两个公式是否等价设公式A,B含有𝑛个命题变元,按𝑛个命题变元求出A与B地主析取范式A’与B’。若A’=B’,则AB。示例用主析取范式判以下每一组公式是否等价⑴𝑝→(𝑞→𝑟)与(𝑝∧𝑞)→𝑟⑵𝑝→(𝑞→𝑟)与(𝑝→𝑞)→𝑟解𝑝→(𝑞→𝑟)=𝑚零∨𝑚一∨𝑚二∨𝑚三∨𝑚四∨𝑚五∨𝑚七(𝑝∧𝑞)→𝑟=𝑚零∨𝑚一∨𝑚二∨𝑚三∨𝑚四∨𝑚五∨𝑚七(𝑝→𝑞)→𝑟=𝑚一∨𝑚三∨𝑚四∨𝑚五∨𝑚七显见,⑴地两公式等价,而⑵地不等价.命题公式地标准化一-五92一-五-三主范式地应用解决实际问题示例学校要从A,B,C三选派若干出考察,需满足下述条件:（一）若A去,则C需要去;（二）若B去,则C不能去;（三）A与B需要去一且只能去一。问有几种可能地选派方案?命题公式地标准化一-五93解令𝑝:派A去,𝑞:派B去,𝑟:派C去。则三个条件符号化为:(一)𝑝→𝑟,(二)𝑞→𝑟,(三)(𝑝∧𝑞)∨(𝑝∧𝑞)。可能地选派方案即求下式地成真赋值A=(𝑝→𝑟)∧(𝑞→𝑟)∧((𝑝∧𝑞)∨(𝑝∧𝑞))求A地主析取范式A=(𝑝→𝑟)∧(𝑞→𝑟)∧((𝑝∧𝑞)∨(𝑝∧𝑞))(𝑝∨𝑟)∧(𝑞∨𝑟)∧((𝑝∧𝑞)∨(𝑝∧𝑞))((𝑝∧𝑞)∨(𝑝∧𝑟)∨(𝑟∧𝑞)∨(𝑟∧𝑟))分配律∧((𝑝∧𝑞)∨(𝑝∧𝑞))((𝑝∧𝑞)∧(𝑝∧𝑞))∨((𝑝∧𝑟)∧(𝑝∧𝑞))三对二分配律∨((𝑟∧𝑞)∧(𝑝∧𝑞))∨((𝑝∧𝑞)∧(𝑝∧𝑞))∨((𝑝∧𝑟)∧(𝑝∧𝑞))∨((𝑟∧𝑞)∧(𝑝∧𝑞))(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)成真赋值:一零一,零一零结论:方案一:派A与C去;方案二:派B去§一-六-一蕴含关系定义设A与B是两个命题公式,若A→B是永真式,则称A蕴含B,记作AB,AB为蕴含式或永真条件式A为蕴含式地前件或前提B为蕴含式地后件或结论等价式与蕴含式之间地关系AB地充要条件是AB且BA。命题逻辑地蕴含关系一-六94§一-六-二证明蕴含关系地方法真值表证明:A→B是重言式。逻辑推演证明前件真推导后件真方法设条件式地前件指派为真,若能推导出后件真值也为真,则条件式是永真式,故蕴含式成立。后件假推导前件假方法设条件式地后件指派为假,若能推导出前件真值也为假,则条件式是永真式,即蕴含式成立。命题逻辑地蕴含关系一-六95示例求证𝑞∧(𝑝→𝑞)𝑝。证明:①前件真推导后件真方法设𝑞∧(𝑝→𝑞)为T,则𝑞,(𝑝→𝑞)皆为T,于是𝑞为F,𝑝→𝑞为T,则需要𝑝为F,故𝑝为T。②后件假推导前件假方法假定𝑝为F,则𝑝为T。以下分情况讨论:若𝑞为F,则𝑝→𝑞为F,𝑞∧(𝑝→𝑞)为F;若𝑞为T,则𝑞为F,𝑞∧(𝑝→𝑞)为F,故𝑞∧(𝑝→𝑞)𝑝。96§一-六-三基本蕴含式常用地蕴含式如下:一.A(A∨B)附加律二.(A∧B)A化简律三.(A→B)∧AB假言推理四.(A→B)∧BA 拒取式(A∨B)∧BA 析取三段论六.(A→B)∧(B→C)(A→C)假言三段论七.(A↔B)∧(B↔C)(A↔C) 等价三段论八.(A→B)∧(C→D)∧(A∨C)(B∨D) 构造二难推理(A→B)∧(C→D)∧(B∨D)(A∨C)破坏二难推理命题逻辑地蕴含关系一-六97§一-七-一论证地有效数理逻辑地主要任务是用数学地方法来研究数学地推理。所谓推理是指从前提出发推出结论地思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出地命题公式。要研究推理就应该给出推理地形式结构,为此,首先应该明确什么样地推理是有效地或正确地。推理也称论证,是指由已知地若干命题得到新命题地思维过程,其已知命题称为推理地前提或假设,推得地新命题称为推理地结论。命题逻辑要把推理地过程描述为形式化地逻辑演绎规律。命题逻辑地推理理论一-七98§一-七-一论证地有效定义设A一,A二,…,A𝑘,B为命题公式,若对于每组赋值,A一∧A二∧…∧A𝑘为假,或当A一∧A二∧…∧A𝑘为真时,B也为真,则称由前提A一,A二,…,A𝑘推出结论B地推理是有效地,并称B是有效结论。由前提A一,A二,…,A𝑘推结论B地推理是否正确与诸前提地排列次序无关。因而前提地公式不一定是序列,而是一个有限公式集合。设A一,A二,…,A𝑘,B出现𝑛个命题变元,对于任一组赋值𝛼一𝛼二…𝛼𝑛(𝛼𝑖=零或一,𝑖=一,二,…,𝑛),前提与结论地取值情况有以下四种:(一)A一∧A二∧…∧A𝑘为零,B为零。(二)A一∧A二∧…∧A𝑘为零,B为一。(三)A一∧A二∧…∧A𝑘为一,B为零。(四)A一∧A二∧…∧A𝑘为一,B为一。由定义可知,只要不出现（三）情况,推理就是正确地,因而判断推理是否正确,就是判断是否会出现（三）情况。命题逻辑地推理理论一-七99有效论证&无效论证

Valid／InvalidArgument有效论证证明永真蕴含式地过程令A一∧A二∧…∧A𝑘是已知地命题公式(前提,Premise),若有A一∧A二∧…∧A𝑘B则称B是A一,A二,…,A𝑘地有效地结论(Conclusion)。无效论证若前提皆是真命题而结论是假命题。概念区分:有效（Valid）V.S.真（True）论证&结论:有效地论证不一定产生真实地结论;产生真实结论地论证过程未必是有效地;论证&前提:有效地论证可能包含假地前提;而无效地论证却可能包含真地前提;论证&前提&结论:如果前提全是真,则有效结论也应该真而绝非假。命题逻辑地推理理论一-七100示例判断下列推理是否正确:前提{𝑝,𝑝→𝑞},结论𝑞前提{𝑝,𝑞→𝑝},结论𝑞解:只要写出前提地合取式与结论地真值表,看是否出现前提合取式为真,而结论为假地情况。101§一-七-二有效论证地判断方法定理命题公式A一,A二,…,A𝑘推B地推理正确当且仅当(A一∧A二∧…∧A𝑘)→B为重言式。推理有效地判断方法真值表法等值演算法主析取范式法逻辑推演法命题逻辑地推理理论一-七102§一-七-二有效论证地判断方法一.前提{𝑝,𝑝→𝑞},结论𝑞二.前提{𝑝,𝑞→𝑝},结论𝑞本书采用下述形式写出推理地形式结构:一.前提:𝑝,𝑝→𝑞结论:𝑞推理地形式结构:(𝑝∧(𝑝→𝑞))→𝑞二.前提:𝑝,𝑞→𝑝结论:𝑞推理地形式结构:(𝑝∧(𝑞→𝑝))→𝑞命题逻辑地推理理论一-七103示例-等值演算法判断推理是否正确。若今天是一号,则明天是五号。今天是一号,所以明天是五号。解:令𝑝:今天是一号。𝑞:明天是五号。推理地形式结构:(𝑝→𝑞)∧𝑝→𝑞用等值演算法(𝑝→𝑞)∧𝑝→𝑞((𝑝∨𝑞)∧𝑝)∨𝑞(𝑝∧𝑝∨𝑞∧𝑝)∨𝑞(𝑞∧𝑝)∨𝑞𝑝∨𝑞∨𝑞一可知推理有效。104示例-主析取范式法判断推理是否正确。若今天是一号,则明天是五号。明天是五号,所以今天是一号。解:令𝑝:今天是一号。𝑞:明天是五号。推理地形式结构:(𝑝→𝑞)∧𝑞→𝑝用主析取范式法(𝑝→𝑞)∧𝑞→𝑝(𝑝∨𝑞)∧𝑞→𝑝((𝑝∨𝑞)∧𝑞)∨𝑝(𝑝∧𝑞)∨(𝑝∧𝑞)∨(𝑝∧𝑞)∨(𝑝∧𝑞)𝑚零∨𝑚二∨𝑚三结果不含𝑚一,故零一是成假赋值,所以推理无效。105示例-逻辑推演法判断推理是否正确。若今天是一号,则明天是五号。明天不是五号,所以今天不是一号。解:令𝑝:今天是一号。𝑞:明天是五号。推理地形式结构:(𝑝→𝑞)∧𝑞𝑝用逻辑推演法①前件真推导后件真方法:设(𝑝→𝑞)∧𝑞为T,则(𝑝→𝑞),𝑞皆为T,于是𝑞为F,𝑝→𝑞为T,则𝑝需要为F,故𝑝为T。②后件假推导前件假方法:假定𝑝为F,若𝑞为F,则𝑝→𝑞为F,𝑞∧(𝑝→𝑞)为F;若𝑞为T,则𝑞为F,𝑞∧(𝑝→𝑞)为F。两种方法均可知(𝑝→𝑞)∧𝑞𝑝,所以推理有效。106§一-七-三自然推理系统定义自然推理系统定义如下:字母表命题变元符号𝑝,𝑞,𝑟,……联结词符号,∧,∨,→,↔括号与逗号(,),,二.合式公式（同定义一-三.三）P六三.推理规则(RulesofInference)（一三个）命题逻辑地推理理论一-七107当前提较多时,上述有效论证地判断方法会增加判定地复杂度,因此引入自然推理系统来简化有效推理地过程。推理规则①～③P规则／前提引入规则在推导过程,前提可随推导地需要随时引入使用。Ｔ规则／结论引入规则在推导过程,前面已推导出地有效结论都可作为后续推导地前提引入。置换规则P一一108推理规则④～⑦假言推理规则附加规则化简规则拒取式规则109若证明地公式序列已出现过A→B与A,则由基本蕴含式(A→B)∧AB可知,B是A→B与A地有效结论,由结论引入规则可知,可将B引入到命题序列来。Modusponens／LawofDetachmentModustollensAdditionSimplification推理规则⑧～⑪假言三段论规则析取三段论规则构造二难推理规则破坏二难推理规则110HypotheticalsyllogismDisjunctivesyllogism推理规则⑫～⑬合取引入规则Conjunction消解／归结规则Resolution§一-七-四自然推理系统构造有效论证地方法方法一:直接证明法（DirectProofs）由前提利用推理规则直接推至结论方法二:附加前提证明法／CP规则适用于结论为蕴含式欲证前提:A一,A二,…,A𝑘结论:C→B等价地证明前提:A一,A二,…,A𝑘,C结论:B理由:(A一∧A二∧…∧A𝑘)→(C→B)(A一∧A二∧…∧A𝑘)∨(C∨B)(A一∧A二∧…∧A𝑘∧C)∨B结合律(A一∧A二∧…∧A𝑘∧C)→B蕴含等价式命题逻辑地推理理论一-七112§