命题逻辑-1.11.3.ppt

第一部分数理逻辑2020年5月16日星期六有一逻辑学家误入某部落，被拘于牢狱，酋长欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今加派两名战士负责解答你所提的任何问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。逻辑学家手指一门问身旁一名战士说：“这扇门是死亡门，他（指另一名战士）将回答‘是’，对吗？2020年5月16日星期六PQRSTTTFTFFTFTFFFFTTP：被问战士是诚实人。Q：被问战士的回答是“是”R：另一战士回答的是“是”S：这扇门是死亡门。S(P∧Q)∨(P∧Q)(P∨P)∧QQ(S的真值总与Q的真值相反)当被问人回答“是”时，此门是生门当被问人回答“否”时，此门是死门2020年5月16日星期六逻辑逻辑，是研究思维形式及思维规律的科学,也把它称为研究推理的科学，它分为：辨证逻辑——是研究人的思维中的辩证法。例如：用全面的和发展的观点观察事物；具体问题具体分析；实践是检查事物正误的唯一标准；等等。形式逻辑——是研究人的思维的形式和一般规律。在本学科，我们只关心形式逻辑。思维的形式结构包括了概念，判断和推理之间的结构和联系。形式逻辑主要研究推理。推理，就是由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。概念是思维的基本单位通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断由一个或几个判断推出另一判断的思维形式，就是推理2020年5月16日星期六推理推理分为以下几种：类比推理：由个别事实推出个别结论。如：地球上有空气、水，地球上有生物。火星上有空气、水。火星上有生物。归纳推理：由若干个别事实推出一般结论。如：铜能导电。铁能导电。锡能导电。铅能导电。……一切金属都导电。演绎推理：由一般规律推出个别事实。形式逻辑主要是研究演绎推理的。2020年5月16日星期六演绎推理演绎推理举例：例1：如果天下雨，则路上有水。(一般规律)天下雨了。(个别事实)推出结论：路上有水。(个别结论)例2：(大前提)：所有金属都导电。(一般规律)(小前提)：铜是金属。(个别事实)推出结论：铜能导电。(个别结论)不能仅停留在文字表面，否则无法与机器沟通。若停留在文字表面，如：下雨换成下雪；铜换成铁；机器该如何处理？2020年5月16日星期六数理逻辑数理逻辑是用数学的方法研究形式逻辑。所谓数学方法，主要是指引进一套符号体系的方法，因此数理逻辑又称为符号逻辑现代数理逻辑有四大分支：证明论、模型论、递归论、公理化集合论它们共同的基础——命题逻辑（Ls，命题演算）谓词逻辑（Lp，谓词演算）2020年5月16日星期六命题逻辑命题逻辑示例：如果天下雨，则路上有水。(一般规律)天下雨了。(个别事实)推出结论：路上有水。(个别结论)设P表示：天下雨。设Q表示：路上有水。设表示：如果…则…以上的推理过程表示为：前提1：PQ(如果天下雨，则路上有水。)前提2：P(天下雨了。)结论：Q(路上有水。)2020年5月16日星期六谓词逻辑谓词逻辑示例：(大前提)：所有金属都导电。(一般规律)(小前提)：铜是金属。(个别事实)推出结论：铜能导电。(个别结论)设M(x):x是金属；设C(x):x能导电。设x表示:所有的x；设a:表示铜.以上的推理过程表示为：大前提：(x)(M(x)C(x))(所有金属都导电。)小前提：M(a)(铜是金属。)结论：C(a)(铜能导电。)2020年5月16日星期六命题逻辑的应用PPQPP∧QQPPQQPPQQPPQQPP∨QQPPQQPPQQPP∨Q给后继课程：编译原理、人工智能、数字逻辑等提供必要的数学基础。第一章命题逻辑2020年5月16日星期六命题逻辑命题逻辑研究由命题为基础单位构成的前提和结论之间的可推导关系它是谓词逻辑的基础本章的主要内容：命题、联结词、命题公式等价式、蕴涵式范式、主范式推理理论2020年5月16日星期六第一节命题与联结词第一节命题与联结词一、命题的概念所谓命题(Proposition)：是指具有非真必假的陈述句。疑问句、感叹句、祈使句都不能判断其真假，故而都不是命题。命题仅有两种可能的真值（truthvalue）：真（true）（用T或1表示）假（false）（用F或0表示）因此，命题逻辑也称为二值逻辑陈述句二值逻辑2020年5月16日星期六命题命题的真假是具有客观性质的，而不是由人的主观决定的。命题是一个真或假的语句，但是不能既真又假。若一个命题的真值为真，称该命题为真命题；（用T或1表示）若一个命题的真值为假，称该命题为假命题；（用F或0表示）2020年5月16日星期六命题注意：命题有真假，并不意味着现在就能确定其为真还是为假，而是指它具有能够唯一确定的真假值这一性质。例如：地球外的星球上存在生物2020年5月16日星期六命题例1.1：判断下面的语句是否为命题？如果是命题，是真命题还是假命题？今天下雪。明天会刮风吗？x+y42是偶数，而3是奇数。陈胜起义那天，杭州下雨了。这真是太好了！假命题不是命题不是命题真命题是命题，未知真假不是命题2020年5月16日星期六命题你去哪里？给我一只笔。我正在说谎。1+1＝10金星的表面温度是800oC。本命题是假的。不是命题不是命题悖论，不是命题是命题，在二进制条件下是真命题，其他进制条件下是假命题假命题悖论，不是命题465oC～485oC2020年5月16日星期六悖论“悖论”（paradox）其字面意思为“荒谬的理论或自相矛盾的话”。从逻辑上看，悖论性的语句具有这样的特征：如果假定这个语句为真，那么会推出这个语句为假；反之，如果假定这个语句为假，又会推出这个语句为真。说它对也不是，不对也不是，真是左右为难。2020年5月16日星期六悖论悖论古已有之。一般认为，最早的悖论是古希腊的“说谎者悖论”。《新约全书·提多书》是这样记述的：克里特岛上的一个本地先知伊壁孟尼德（Epimenides）说：“克里特人总是撒谎，乃是恶兽，又馋又懒。”这个见证是真的。后来欧布里德（Eubulides）将他的话改进为：我正在说谎。2020年5月16日星期六悖论后来又发现了好几种“说谎者悖论”的变种，例如所谓“说谎者循环”：A说：“下面是句谎话。”B说：“上面是句真话。”“说谎者悖论”和“说谎者循环”是与自然语言的表达方式密切相关的悖论，涉及真假、定义、名称、意义等语义方面的概念，这类悖论被称为“语义学悖论”。2020年5月16日星期六悖论2020年5月16日星期六悖论语义学悖论的实例很多，“格列林（K.Grelling）-纳尔逊（L.Nelson）悖论”就饶有趣味，它与形容词的应用有关：将形容词分为两类，一类称为“自谓的”，即可对于它们自身成立、对自己为真的。例如，形容词“Polysyllabic（多音节的）”本身是多音节的；“English（英文的）”本身是英文的，它们都是自谓的。另一类称为“它谓的”，即对于它们自身不成立、对自己不真的。例如，形容词“Monosyllabic（单音节的）”是它谓的，因为这个词不是一个单音节词；“英文的”也是它谓的，因为这个词是中文的而不是英文的。问题来了：形容词“它谓的”是不是它谓的？2020年5月16日星期六悖论罗素（Russell）悖论——理发师悖论某村只有一个理发师，且该村的人都需要理发，理发师规定，一定给且只给村中不自己理发的人理发。试问：理发师给不给自己理发？芝诺（Zeno）悖论——龟兔赛跑乌龟与兔子赛跑，让乌龟在兔子前头1000米开始。假定兔子能够跑得比乌龟快10倍。比赛开始，当兔子跑了1000米时，乌龟仍前于他100米；当兔子跑了下一个100米时，乌龟依然前于他10米……所以，兔子永远追不上乌龟。2020年5月16日星期六命题命题应当是有客观真值的，但是命题的真值会因时、因地、因人而异。现在是21世纪。中国的首都是北京。今天这里下雨了。我是女性。从今天的角度上讲，这是真命题从上世纪的角度上讲，这是假命题目前讲，这是真命题如果从唐朝的角度讲，这是假命题对于有些地方而言，这是真命题对于有些地方而言，这是假命题对于我来讲，这是真命题对于男性来讲，这是假命题2020年5月16日星期六命题命题分为两类：如果一个陈述句，再也不能分解成更小的语句，由它构成的命题称为原子命题（或本原命题）。原子命题是命题逻辑的基本单位，用大写英文字母P,Q,R……或Pi,Qi,Ri表示例如：用P表示“今天是星期一”，记为P：今天是星期一2020年5月16日星期六命题由原子命题、命题联结词和圆括号组成复合命题。例如：P：明天下雨，Q：明天下雪可利用联结词“不”，“并且”，“或者”等分别构成新的命题：“明天不下雪”非Q“明天下雨并且明天下雪”P并且Q“明天下雨或者明天下雪”P或者Q2020年5月16日星期六命题联结词下面我们来讨论由已有命题产生新命题的方法，这些方法在1854年，曾由英国数学家乔治·布尔(1815-1864)在他的《TheLawsofThought》一书中讨论过。许多数学陈述都是组合一个或多个命题而来。称为复合命题的新命题，是由已有的命题用逻辑运算符组合而来的。复合命题的“真”或“假”只与所含的原子语句的真值有关，与他们的含义无关2020年5月16日星期六命题联结词二、命题联结词命题联结词就是命题演算中的运算符。也叫逻辑运算符，常用的有以下5个：否定词设P为命题，命题“非P”称为P的否定式复合命题，记做“P”。“”称为否定联结词。P为真，当且仅当P为假2020年5月16日星期六命题联结词否定词在学习命题公式之前，我们先来认识一下真值表：定义运算符的真值表，指明如何用运算对象的真值，来决定一个应用运算符的命题的真值。真值表左边列出运算对象的真值的所有组合，结果命题的真值列在最右边的一列。P的真值表为：P01P102020年5月16日星期六命题联结词否定词例1.2：P：4是质数，P表示什么？P：4不是质数（或者:4是质数，不是这样）Q：这些都是男同学，Q表示什么？Q：这些不都是男同学（或者：这些都是男同学，是错误的）不要翻译成：这些都不是男同学2020年5月16日星期六命题联结词合取词∧设P、Q是两个命题，命题“P并且Q”称为P和Q的合取式复合命题，记做“P∧Q”。也读作“P与Q”。“∧”称为合取联结词。P∧Q为真，当且仅当P和Q同时为真。P∧Q的真值表为：PQ00011011P∧Q0001合取是对称的，即给P和Q指派真值，P∧Q和Q∧P的真值相同2020年5月16日星期六命题联结词合取词∧例1.3：P：王华的成绩很好，Q：王华的品德很好P∧Q：王华的成绩很好，并且品德很好P：今天天晴，Q：三加三等于六，P∧Q表示什么？P∧Q：今天天晴，并且三加三等于六能将命题“汤姆和杰克是亲兄弟”符号化为“P∧Q”的形式吗？不能，这本身就是一个原子命题常把合取“与”用于具有某种关系的两个命题之间；但是，在逻辑学中，则不然，完全允许用两个相互无关系的原子命题，生成新的命题2020年5月16日星期六命题联结词析取词∨设P、Q是两个命题，命题“P或者Q”称为P和Q的析取式复合命题，记做“P∨Q”。“∨”称为析取联结词。P∨Q为假，当且仅当P和Q同时为假。P∨Q的真值表为：PQ00011011P∨Q01112020年5月16日星期六命题联结词析取词∨例1.4：P：今晚我写字，Q：今晚我看书，P∨Q表示什么？P∨Q：今晚我写字或者看书P：今年是闰年，Q：今年她生孩子，P∨Q表示什么？P∨Q：今年是闰年或者今年她生孩子2020年5月16日星期六命题联结词析取词∨通常语言中的“或者”有两种含义：可兼或如前面的例子“今晚我写字或看书”，不排除今晚“我”既看书又写字排斥或例如“人固有一死，或重于泰山，或轻于鸿毛”，其中的“或”表示非此即彼，不可兼得析取词∨表示的是可兼或（“排斥或”将用⊕表示）特例：他昨天做了二十或三十道题。此例中的“或”只表示了习题的近似数目，不能用联接词析取表