1第一章数理逻辑-命题逻辑

第二篇数理逻辑MathematicsLogic1数理逻辑逻辑学研究人的思维形式和规律的科学根据研究的对象和方法形式逻辑辩证逻辑数理逻辑用数学方法研究推理的规律和形式的科学推理：由一个或几个判断推出一个新判断的思维形式数学方法建立一套表意符号体系，对具体事物进行抽象的形式研究方法又称符号逻辑两种演算命题逻辑谓词逻辑2形式语言与自然语言数理逻辑需建立一套表意符号体系形式语言符号体系自然语言二义性Doubleclickthemouse,thenit’llrun.小王现在不方便接电话，他方便去了建立形式语言符号体系的目的消除二义性3主要内容第二章命题逻辑2.1命题的概念与表示2.2逻辑联结词2.3命题演算的合式公式2.4等价与蕴涵2.5功能完备集及其他联接词2.6对偶与范式2.7命题演算的推理理论第三章谓词逻辑3.1谓词的概念与表示3.2命题函数与量词3.3谓词演算的合式公式3.4变元的约束3.5谓词公式的解释3.6谓词演算的永真式3.7谓词演算的推理理论3.8自动推理证明41.1~1.5命题逻辑PropositionLogic52.1命题（Proposition）2.1.1命题断言一个陈述语句命题：具有确定真假含义的陈述句命题是一个非真即假(不可兼)的断言如果命题是真命题的真值（TruthValues）为真真命题大写字母“T”(1)表示如果命题是假命题的真值是假假命题大写字母“F”(0)表示6例:今天下雪3+3=62是偶数而3是奇数1+101=110明年的今天会下雨较大的偶数都可表为两个质数之和7例:x+y＞4真好啊!x=3你去哪里?0*x=0我正在说谎8原子命题(Primitiveproposition)由简单陈述句表示的判断命题逻辑规定：原子命题是不可再分的命题的表示常用大写英文字母（或带下标）表示P表示“雪是白的”Q表示“北京是中国的首都”命题变元（命题词）P表示任一命题时，P就称为命题变元（命题词）命题词不是命题命题指具体的陈述句，是有确定的真值命题变元的真值不定，只当将某个具体命题代入命题变元时，命题变元化为命题，方可确定其真值9复合命题(Compoundproposition)一个或几个简单命题用联结词联结所构成的命题例：“张三学英语和李四学日语”两个特殊的命题词命题常量T：永远表示真命题F：永远表示假命题T和F的两种含义命题常量命题的真值10数理逻辑不关心内容具体的陈述句的真值究竟为什么或在什么环境下是真还是假数理逻辑只关心形式命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系112.2逻辑联结词命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复合命题例：P:明天下雪,Q:明天下雨“明天不下雪”“非P”“明天下雪并且明天下雨”“P并且Q”“明天下雪或者明天下雨”“P或Q”12TFFT┐PP真值表（TruthTable)与自然语言中的“不”，“否”，“非”，“没有”，“未必”等类似1.否定词┐（～，negation）设P表示命题,那么“P不真”是另一命题,表示为┐P,叫做P的否定,读做“非P”。如果P是假,则┐P是真,反之亦然。13例(a)P:4是质数。┐P:4不是质数。(b)Q:这些都是男同学。┐Q:这些不都是男同学。14PQP∧Q000110110001例P:王华的成绩很好Q:王华的品德很好P∧Q:王华的成绩很好并且品德很好。2.合取词∧(Conjunction)如果P和Q是命题,那么“P并且Q”也是一命题,记为P∧Q,称为P和Q的合取,读做“P与Q”或“P并且Q”。15PQP∨Q0001101101113.析取词∨(disjunction)如果P和Q是命题,则“P或Q”也是一命题,记作P∨Q,称为P和Q的析取,读做“P或Q”。16可兼或排斥或X（R∨S）∧┐（R∧S）（R∧┐S）∨（┐R∧S）例(a)今晚我写字或看书P:今晚我写字,Q:今晚我看书。P∨Q(b)选小王或小李当班长R:选小王当班长，S:选小李当班长R∨S？17PQP→Q000110111101与自然语言中的“如果…则…”，“如果…那么…”，“只要…就…”等类似4.条件词→(蕴涵，蕴含，implication)如果P和Q是命题,那么“P蕴含Q”也是命题,记为P→Q,称为蕴含式,读做“如果P,那么Q”或“P则Q”。运算对象P叫做前提,假设或前件,而Q叫做结论或后件。18例(a)P:天不下雨,Q:草木枯黄。P→Q:如果天不下雨,那么草木枯黄。(b)R:G是正方形,S:G的四边相等。R→S:如果G是正方形,那么G的四边相等。(c)W:桔子是紫色的,V:大地是不平的。W→V:如果桔子是紫色的,那么大地是不平的。19因果关系引入→的目的是希望用来描述命题间的推理，表示因果关系使用P→Q能描述推理如果今天是星期二，那么明天是星期天如果今天是星期一，那么明天是星期天如果n3那么n29(n=4,n=2,n=-4)→与“如果…那么…”有一致的一面,同时也有与常识不一致的地方数理逻辑不关心具体命题，只关心推理的形式人为的规定，对P为F时P→Q的值另作规定也是可以的20蕴含式P→Q可以用多种方式陈述:;“若P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”;“P仅当Q”等。给定命题P→Q,我们把Q→P,┐P→┐Q,┐Q→┐P分别叫做命题P→Q的逆命题,反命题和逆反命题.21例令：P：天气好。Q：我去公园。1.如果天气好，我就去公园。2.只要天气好，我就去公园。3.天气好，我就去公园。4.仅当天气好，我才去公园。5.只有天气好，我才去公园。6.我去公园，仅当天气好。P→QP→QP→QQ→PQ→PQ→P22100100011011P↔QPQ5.双条件词↔（等值，Biconditional）如果P和Q是命题,那么“P等值于Q”也是命题,记为P↔Q,称为双条件式（等值式）,读做“P当且仅当Q”或“P等值于Q”。P↔Q也读做“P是Q的充要条件”。23联结词的注意事项要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义特别要注意“或”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。特别要注意“”的用法，它既表示“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件联结词的优先级顺序┐，∧,∨,→,↔24练习：填空已知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为()252.3命题演算的合式公式命题变元与命题常元命题常元命题有具体含义(真值)的例：“3是素数。”；T；F命题变元用大写的英字母如P、Q等表示任何命题真值指派解释将一个命题常元赋予命题变元的过程或者是直接赋给命题变元真值“T”或“F”的过程注意：命题变元本身不是命题，只有给它一个解释，才变成命题。26命题演算的合式公式(命题公式，wff，wellformedformulas)定义2.3.1：⑴单个命题变元是个合式公式。⑵若A是合式公式，则A是合式公式。⑶若A和B是合式公式，则(A∧B)，(A∨B)，(AB)和(AB)都是合式公式。⑷当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和圆括号的符号串是合式公式。此外，称逐次使用规则⑴，⑵，⑶的过程中所得到的命题公式为最后构成的命题公式的子公式。递归定义(1)——基本项，是递归的基础(2)(3)——递归项，是递推规则(4)——极小化，保证所构造集合的唯一性命题函数有n个命题变元的命题公式可用函数A(P1,P2,…,Pn)的形式表示其中P1,P2,…,Pn按字典顺序排列27例(a)(P→(P∨Q))解(i)P是命题公式根据条款(1)(ii)Q是命题公式根据条款(1)(iii)(P∨Q)是命题公式根据(i)(ii)和条款(2)(iv)(P→(P∨Q))是命题公式根据(i)(iii)和条款(2)28例下面的式子是否为合式公式：P∧Q，PR，P∨Q∧R修改(P∧Q)，(PR)，((P∨Q)∧R)29圆括号的省略规则最外层的圆括号可以省去符合联结词优先级顺序的,括号可省去相同的联结词,按从左至右次序计算时,括号可省去(┐((P∧┐Q)∨R)→((R∨P)∨Q))┐((P∧┐Q)∨R)→((R∨P)∨Q)┐(P∧┐Q∨R)→(R∨P∨Q)┐(P∧┐Q∨R)→R∨P∨Q30命题符号化用形式语言所表示的命题公式符号串来表示给定的命题例他既有理论知识又有实践经验P：他有理论知识Q：他有实践经验P∧Q如果明天不是雨夹雪则我去学校P：明天下雨Q：明天下雪R：我去学校┐(P∧Q)→R如果明天不下雨并且不下雪则我去学校┐P∧┐Q→R31如果明天下雨或下雪则我不去学校P∨Q→┐R明天,我将雨雪无阻一定去学校P∧Q∧R∨┐P∧Q∧R∨P∧┐Q∧R∨┐P∧┐Q∧R当且仅当明天不下雪并且不下雨时我才去学校┐P∧┐QRP∨Q┐R仅当明天不下雪并且不下雨时我才去学校R→┐P∧┐Q说小学生编不了程序,或说小学生用不了个人计算机,那是不对的P：小学生会编程序Q：小学生会用个人计算机┐(┐P∨┐Q)P∧Q32代入实例定义2.3.2设A和B是两个命题公式，如果将A中的某些命题变元用命题公式进行代换便可得到B，并且此种代换满足：（1）被代换的是命题变元（2）如果要代换某个命题变元，则要将该命题变元在A中的一切出现进行代换（3）代换必须同时独立进行此时称B是A的一个代换实例（代入实例）例A(P,Q)=P→QA(P,Q∧┐R)=P→Q∧┐RA(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))33真值指派（解释）定义2.3.3设A(P1,P2,…,Pn)是一个命题公式，P1,P2,…,Pn是出现于其中的全部命题变元。Pi有两种取值可能，P1,P2,…,Pn有2n种取值可能，P1,P2,…,Pn的任何一种取值称为对A(中变元)的一种真值指派（或解释），可记为I=(P1’,P2’,…,Pn’)，其中Pi’=0或1例A(P,Q,R)=P(RQ),真值指派(1,0,1)，(1,1,0)真值分别为F和T34真值表定义2.3.4设A(P1,P2,…,Pn)是一个命题公式，P1,P2,…,Pn是出现于其中的全部命题变元。如果有一张表列出了在P1,P2,…,Pn的所有2n种真值指派的每一种下，公式A对应的真值，则称此表为公式A的真值表例PQ(P∧(PQ))Q00101110111135重言式/矛盾式/可满足式定义2.3.5重言式（tautology）/矛盾式（contradiction）A(P1,P2,…,Pn)是含有命题变元P1,P2,…,Pn的命题公式，如不论对P1,P2,…,Pn作任何指派，都使得A(P1,P2,…,Pn)为真(假)，则称之为重言式(矛盾式),也称之为永真式(永假式)例：P∨P和P∧P偶然式不是永真式,也不是永假式例：P,P∧Q可满足式（satisfactableformula）非矛盾式P∨P，P∧Q36重言式的证明方法方法1：列真值表方法2：公式的等价变换，化简成“T”方法3：用公式的主析取范式证明(P∧(PQ))Q为重言式PQ(P∧(PQ))Q00011011TTTT37重言式的性质如果A是重言式，则A是矛盾式如果A是矛盾式，则A是重言式定理2.3.1如果A，B是重言式，则(