数理逻辑总复习2012

1,第一章主要内容,命题、真值、简单命题与复合命题、命题符号化联结词,及复合命题符号化命题公式及层次公式的类型真值表及应用,2,第一章基本要求,深刻理解各联结词的逻辑关系,熟练地将命题符号化会求复合命题的真值深刻理解合式公式及重言式、矛盾式、可满足式等概念熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,3,第二章主要内容,等值式与等值演算基本等值式（16组，24个公式）主析取范式与主合取范式联结词完备集消解法,4,第二章基本要求,深刻理解等值式的概念牢记基本等值式的名称及它们的内容熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系,5,第二章基本要求,熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值会将公式等值地化成指定联结词完备集中的公式会用命题逻辑的概念及运算解决简单的应用问题掌握消解规则及其性质会用消解算法判断公式的可满足性,6,第三章主要内容,推理的形式结构判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律自然推理系统P构造推理证明的方法直接证明法附加前提证明法归谬法(反证法),7,第三章基本要求,理解并记住推理形式结构的两种形式：1.(A1A2Ak)B2.前提：A1,A2,Ak结论：B熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬法会解决实际中的简单推理问题,8,第四章主要内容,个体词、谓词、量词一阶逻辑命题符号化一阶语言L：项、原子公式、合式公式公式的解释量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释公式的类型永真式(逻辑有效式)、矛盾式(永假式)、可满足式,9,第四章基本要求,准确地将给定命题符号化理解一阶语言的概念深刻理解一阶语言的解释熟练地给出公式的解释记住闭式的性质并能应用它深刻理解永真式、矛盾式、可满足式的概念,会判断简单公式的类型,10,第五章主要内容,一阶逻辑等值式基本等值式，置换规则、换名规则、代替规则前束范式推理的形式结构自然推理系统NL推理定律、推理规则,11,第五章基本要求,深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们熟练正确地使用置换规则、换名规则、代替规则熟练地求出给定公式的前束范式深刻理解自然推理系统NL的定义，牢记NL中的各条推理规则，特别是注意使用、+、+、4条推理规则的条件能正确地给出有效推理的证明,12of8,练习1：符号化练习（红色为p，蓝色为q）,这个工作要求有C+或Java的开发经验。本饭店午餐免费赠送汤或沙拉。考试想要得高分，把这本习题集做完就够了。必须走500米才能登上香山山顶。只有你购买的手机没有超过一年，你的包修单才有效。在电脑上登陆必须有一个有效的口令。如果你经常玩电子游戏，你的视力会衰退，反之亦然。,pq,(pq)(pq),qp,qp,qp,pq,qp,13of8,练习1（续）,a)假如上午不下雨，我去看电影；否则就在家里读书或看报。p:上午下雨。q:我去看电影。r:我在家读书。s:我在家看报。b)我今天去打球，除非下雨。p:我今天去打球。q:今天下雨。c)仅当你走，我将留下。p:你走。q:我留下。,(pq)(p(rs),qp,qp,14,练习1（续）,符号化下列命题1）每一个人的外祖父都是他母亲的父亲.P(x):x是人，O(x,y):x是y的外祖父F(x,y):x是y的父亲，M(x,y):x是y的母亲2）不管白猫黑猫，抓住老鼠就是好猫.C(x):x是猫，W(x):x是白色的，B(x):x是黑色的G(x):x是好的，M(x):x是老鼠，K(x,y):x抓住y,xy(P(x)O(y,x)z(M(z,x)F(y,z),xy(C(x)(W(x)B(x)M(y)K(x,y)G(x),15,练习1（续）,3）在实数集中，任給一正实数，都存在大于该实数的实数。R(x):x是实数，G(x,y):x大于y，4）对平面上任意两点，有且仅有一条直线通过这两点。P(x):x是一个点；L(x):x是一条直线R(x,y,z):z通过x,y；E(x,y):x等于y.,x(R(x)G(x,0)y(R(y)G(y,x),xy(P(x)P(y)z(L(z)R(x,y,z)u(L(u)R(x,y,u)E(u,z),16,练习2：实际应用题,A,B,C,D四个人中要派两个人出差，按下述三个条件有几种派法？如何派。（1）若A去，则C和D中要去一人。（2）B和C不能都去。（3）C去则D要留下。,解：设a:A去出差。b:B去出差。c:C去出差。d:D去出差。按题意应有：a(cd)(cd),(bc),cd同时成立,17,练习2（续）,解：F=(a(cd)(cd)(bc)(cd)设B1=a(cd)(cd)a(cd)(cd)B2=(bc)(cd)(bc)(cd)(bc)(bd)c(cd)F=B1B2(abc)(abd)(ac)(acd)(cbd)(cbd)(cd)所以有三种派法：B和D,A和C,A和D,18,练习3：实际应用题,设有一个在Internet上下载新闻的程序，为避免程序产生死循环和重复下载同一条新闻条目，程序必须根据下述4个条件对给定的一个新闻条目判断是否执行下载任务：条件1：该新闻条目在程序的前一次执行中已下载，用命题符号e表示；条件2：该新闻条目在程序的本次执行中已下载，用命题符号n表示；条件3：该新闻条目是一个动态更新的新闻条目，用命题符号d表示；条件4：该新闻条目已过期，程序需要重新下载，用命题符号o表示。,19,练习3：实际应用题,执行下载任务的规划是：该新闻条目在程序的前一次执行中未下载，则不论其他条件如何，一定执行下载；如果是一条动态新闻，并且该新闻条目在程序的本次执行中没有下载，则执行下载，否则不执行下载；如果新闻条目在程序的前一次执行中已下载，并且该新闻条目在程序的本次执行中没有下载，则如果是一个过期的新闻条目，则执行下载，否则不执行下载。请根据上述条件，写出是否执行下载对应的主合取范式.,20,练习3（续）,e(dn)(eno)(ed)(en)(eno)(edn)(edo)(en)(eno)(edo)(en)(endo)(endo)(endo)(endo)(endo),21,练习4证明题,某厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止？,解：令p:厂方拒绝增加工资q:罢工停止r:工厂经理辞职s:罢工超过一年则，前提：(p(rs)q,p,s,22,练习4(续),解：(1)s前提引入(2)sr1)置换(3)(rs)2)置换(4)p前提引入(5)p(rs)3)4)合取引入(6)(p(rs)q前提引入(7)q5)6)假言推理所以罢工不会停止。,前提：(p(rs)q,p,s,23,练习5证明题,在一阶逻辑中推证下列结论的有效性：每个报考研究生的大学毕业生要么参加研究生入学考试，要么被推荐为免试生；每个报考研究生的大学毕业生当且仅当学习成绩优秀才被推荐为免试生；有些报考研究生的大学毕业生学习成绩优秀，但并非所有报考研究生的大学毕业生学习成绩都优秀。因此，有些报考研究生的大学毕业生要参加研究生入学考试。设P(x)：x是报考研究生的大学毕业生，Q(x)：x参加研究生入学考试，R(x)：x被推荐为免试生，S(x)：x学习成绩优秀。,24,练习5（续）,前提：x(P(x)Q(x)R(x),x(P(x)(S(x)R(x),x(P(x)S(x)x(P(x)S(x)结论：x(P(x)Q(x),25,练习5（续）,x(P(x)S(x)x(P(x)S(x)前提引入x(P(x)S(x)1)化简x(P(x)(S(x)R(x)前提引入P(x)(S(x)R(x)3)-P(x)(S(x)R(x)4)化简P(x)S(x)R(x)5)置换P(x)S(x)P(x)化简(P(x)S(x)R(x)(P(x)S(x)P(x)6)7)合取(P(x)S(x)(R(x)P(x)8)置换P(x)S(x)P(x)R(x)9)置换,26,练习5（续）,11)x(P(x)Q(x)R(x)前提引入12)P(x)Q(x)R(x)11)-13)P(x)R(x)Q(x)12)置换14)P(x)R(x)P(x)13)置换15)(P(