命题逻辑基本概念.ppt

1、第一章命题逻辑的基本概念，离散数学，A，2，本章中的主要内容命题，连接体词，复合命题命题公式，赋值，命题公式的分类本章与下一章的关系本章是对下一章的准备或前提，A，3，数学逻辑的概述，用数学方法研究思维规律的学问。数学逻辑通常也称为符号逻辑，因为它使用一系列符号来简洁地表达各种推理的逻辑关系。数学逻辑与计算机开发密切相关，为机器证明、自动编程、计算机辅助设计等计算机应用和理论研究提供了必要的理论依据。A，4，数学逻辑的发展初期，经典形式逻辑时期：亚里士多德的直接三段论理论早期逻辑代数时期(17世纪末)(1)资本主义生产力的大发展，自然科学的大发展，数学在理解自然和发展技术方面发挥了非常重要的作

2、用。(2)人们想用数学方法研究思想，把思维过程转换成数学计算。A，5，逻辑发展之前，(3)莱布尼茨(Leibniz，16461716)完成了三段式论述，提出了建立数学逻辑或理性微积分的想法：将推理的正确性归因于计算。通过这样的计算，人们的推理在推理过程中不依赖命题的意义内容，将推理的规则变为审美规则。用一种符号语言代替自然语言来说明微积分，以区分符号的形式及其意义。使计算在很大程度上取决于与符号的结合规则，而不管意义如何。A，6，在数学逻辑发展之前，(4)布尔(G.Boole，18151864)代数：将有关数学运算的研究的代数系统扩展到逻辑领域，布尔代数是一种代数系统和逻辑计算。A，7，抓住数

3、学逻辑框架的时期，弗雷格(G.Frege，18481925):概念语言算术正式语言组成的纯思维正式语言(1879)的出版标志着数学逻辑的基本部分命题演算和谓词演算的正式成立。钢琴(GiuseppePeano，18581932):用新方法提出的算术原理(1889)提出了自然算术的公理系统。A，8，数学逻辑的基础时期，罗素(BertrandRussell，18721970):数学原理(与white black合着，1910，1912，19113)是命题演算和由此，在类型论的基础上，以连续的定义和证明的方式引出了数学(主要是算术)的主要概念和定理。A，9，数学逻辑的基础期，逻辑计算的发展：gan c

4、en (G.Gentzen)的自然推理系统(NaturalDeductionSystem)，逻辑计算的元理论：公理的独立性、一致性和完整性多种非典型性逻辑的发展：刘易斯(Lewis，18831964)的模态逻辑包含了怪论和严格、一致的逻辑、卢卡什的多值逻辑等。A，10，1章命题逻辑，命题逻辑是将原子命题推论为基本单位的计算，其特点是，研究和考察逻辑的形式时，我们只分析其中包含的一个命题，即原子命题成分。通过这种分析可以揭示出一些重要的逻辑形式，与这种形式相关的逻辑规律属于命题逻辑。A，11，1.1命题和连接词，数学逻辑研究的中心问题是推理。推论的前提和结论都是表达判断的陈述。表达判断的陈述构成

5、了推理的基本单位。A，12，1.1命题及连接词，能判断非真非假的陈述语句称为命题。用命题的陈述表达的判断结果称为命题的真值。True值只取两个值：true和false。真值为真的命题称为真命题。真值为假的命题称为假命题。感叹号，疑问句，命令型不能说是命题。判断结果不唯一的陈述不是命题。陈述中的悖论不是命题。说明，A，13，4是小数。x大于y。足够大的偶数等于两个少数的和。今天是星期二。请不要吸烟！这朵花真漂亮！我在说谎。例1.1判断以下句子是否为命题。是，假命题是，真命题否，不确定的真值是，真值客观存在是，真值取决于情况。不，不是疑问句，不是命令型的，不是感叹词，而是悖论，A，14，一个陈述句

6、是否能区分真与假，我们是否知道那个真与假是两回事！例：小李去过长城。判断结果不唯一的陈述不是命题。陈述中的悖论不是命题。也就是说，要排除命题。例：这一页的这句话是假的。说明，A，15，命题和真值的编码，小写字母p，q，r，pi，qi，ri不能将命题分解为“1”，将谎言分解为“0”，分解为更简单的陈述语句。这种命题称为简单命题或原子命题。简单陈述是通过联接词实现的陈述，这种命题称为复合命题。A，16，示例1.2将以下陈述中的原子命题编码，指出其真值，然后编写此陈述。合理的数字是不对的。2是偶数小数。2或4是小数。如果2是小数，则3度是小数。2是小数，3万小数。p:是的，玻璃数q: 2是小数。R:

7、 2是偶数s: 3是小数。T: 4是小数、0110、非p。q和(和)r；q或t；如果是q，则为s；如果是q和s。A，17，例1.2的讨论，半形式化形式的数学逻辑研究方法的主要特征是符号化论述或推理的各种因素。是组织各种符号语言，而不是自然语言。正式语言：完全由符号组成的语言。符号化联接词，消除异议，严格定义。例：他是100米或400米赛跑的冠军。鱼香肉丝或锅塌肉，再加一碗汤。A，18，定义1.1否定，将p设置为命题，将复合命题“非p”(或“p的否定”)记录为p的否定，将符号记录为p，将符号称为否定联接词，仅在p为真且p为假时适用。例如：p:哈尔滨是个大城市。p:哈尔滨是个不大的城市。p:哈尔滨

8、不是大城市。A，19，将定义1.2的并集(conjunction)，p，q设置为2个命题，将复合命题“p和q”(或“p和q”)与p和q的组合，将它们记录为称为并集联接词的pq，p和q使用组合术语需要注意的两个事项：描述组合样式的灵活性和多样性。自然语言的“同时”、“不仅”、“但是”、“一方”等连接词都可以符号化。分辨简单命题和复合命题。在不查看“and”或“and”的情况下使用联接词。A，20，例1.3将以下命题符号化，吴颖都努力工作，聪明。吴英不仅努力工作，而且聪明。佑荣聪明，但不努力学习。张辉和王丽也是三个好学生。张辉和王丽是同学。p:吴颖辛苦。Q:吴颖很聪明。R:张辉是三个好学生。S:王

9、莉是三个好学生。T:张辉和王力是同学。(1)pq(2)pq(3)qp(4)rs(5)t，故障排除点：正确理解命题的含义。寻找原子命题，将其符号化。选择适当的联接器。a，21，联合案例，p:去看电影吧。问：房间里有10张桌子。问：我们去看电影了，房间里有10张桌子。在数学逻辑中，关心只是构成复合命题和复合命题的每个原子命题之间的真值关系，即抽象逻辑关系，不关心每个语句的具体内容。说明，A，22，将定义1.3提取(disjunction)，p，q设置为2命题，将复合命题“p”或“q”设置为p和q的提取，将它们记录为称为提取联接器的pq，仅当p和q都是假的情况下将pq设置为假的，在自然语言中“or”

10、有异议，与之相关的命题有时是兼容的，有时是排斥的，相应的联接词分别称为相容或排除或(反等)。说明，A，23，例1.4将以下命题符号化，张晓静喜欢唱歌或听音乐。张小静只能选择202或203房间。张小静是江西人还是安徽人。他昨天做了20或30个练习题。集p:张小静情歌，问：张小静想听音乐。兼容或符号选择“pq集t:张小静”为202房间，“u:张小静”为203房间。排除或符号化：(tu)设定r:张小静是江西人，s:张小静是安徽人。排除或编码：RS。(排除或连接的两个命题实际上不能同时为真)或编码：(rs)(rs)原子命题。or仅表示练习题的近似值。A，24，定义1.4隐含，p，q设置为2命题，复合命

11、题“如果是p，则q”是p和q的隐含，称为pq，p是隐含全项，q是隐含联接语，PP，说明，pq的逻辑关系表明q是p的必要条件。q对p有多个必要条件。因为p，q是p，所以qp仅在q是q的情况下，如果p不是q，则p，A，25，示例1.5用符号表示下一个命题，如果是3，36，则表示眼睛是白色的。3 36的话眼睛是白色的。3 36的话，眼睛不是白色的。3 36的话，眼睛不是白色的。解决方案：p: 3 36，p的true值为1。问：眼睛是白色的，q的真值也是1。Pqpqpqpq，1101，A，26，示例1.5编码下一个命题并表示其真值，下一个命题中的A是给定的正整数。(5)如果a可以分成4，那么a可以分成

12、2。(6)只有在a能被2整除的情况下，a才能被4整除。(7)如果a不能被2整除，那么a可以被4整除。(8)只要a不能被2整除，a就不能被4整除。(9)只有能把a除以2，才能把a除以4。(10)只有能把a除以4，才能把a除以2。解决方案：r: a可被4整除s: a可被2整除(5)到(9)的5个命题是a可被2整除，a可被4整除的必要条件，所以都被符号化为RS。True值被视为必要条件，即1 (10)除以4，a除以2，必须用Sr编码。a值不统一。true值未知。A，27，作为嵌入的附加说明，当p为假时，无论q为真还是假，pq均为真。也就是说，如果只有p真q是假的，那么复合命题pq就是假的。被称为实质

13、的意义。例如：X5表示x2。(1)如果x=6 65，则为62。(2)如果x=3 35，则为32。(3)如果x=1 15，则为12。例：如果我有车的话，我会接你经常发生的错误，没有足够的条件和要求。A，28，定义1.5等价，将p，q设置为2命题，复合命题“p后只有q”等于p和q，称为等价联接词的pq，p和q都是真的或假的、和仅ifandonlyif pq的逻辑关系是p和q交互所必需的。(pq)(qp)与pq的逻辑关系完全匹配。A，29，示例1.6将以下命题符号化，讨论其真价是不合理的，只有加拿大在亚洲的情况下才有可能。2 35所需的充分条件是不合理的数字。两个圆a，b的面积相同，半径相同。反之亦

14、然。王小红心情幸福的时候，她唱歌；相反，她唱歌的时候，一定心情很好。p:是不合理的数字，问：加拿大位于亚洲。符号指定为pq，true值指定为0。P: 2 35，q:是不合理的数字。符号指定为pq，true值指定为1。A，30，示例1.6将以下命题符号化，讨论其真价是不合理的，只有加拿大在亚洲的情况下才有可能。2 35所需的充分条件是不合理的数字。两个圆a，b的面积相同，半径相同。反之亦然。王小红心情幸福的时候，她唱歌；相反，她唱歌的时候，一定心情很好。p:两个圆a，b的面积相等，q:两个圆a，b的半径相等。符号指定为pq，true值指定为1。设定p:王小红心情幸福，问：王小红歌。符号是pq，t

15、rue是上下文相关的。A、31、基本联接单词的说明、称为联接单词集。连接一个或两个原子命题的组合词集的复合命题是最简单的复合命题，可以称为基本复合命题。基本复合命题的真值可以通过多次使用下表：A，32，基本联接词的说明，以及联接词集中的联接词来构成更复杂的复合命题。求复杂复合命题的真值时，以上表为基础确定联接词的优先级，并计算括号。本书规定的联接语优先级是()、等)，首先出现在相同优先级的联接语上。A，33，例1.7，所以p:北京的人口比天津多。问：2 . 24 . r:乌鸦是白色的。求以下复合命题的真值。(1) (pq) (pq) r (2) (QR) (pr) (3) (pr)，解决方案：

16、p，q，r的真值分别为1，1，0，说明，A，34，1.2命题公式及其分配，简单命题是真实值唯一明确命题逻辑中最基本的研究单位，因此简单命题也称为命题上项或命题上院。(propositionconstant)声明true值可以更改的语句称为命题变量或命题参数(propositionvariable)。还使用p，q，r表示命题变形。p，q，r表示命题变量时，成为值为0或1的变项，因此命题变项不再是命题。这样，p，q，r既可以表示命题常项，也可以表示命题变项。在使用中，上下文必须确定该项是常量还是变体。命题变量用连接词和括号连接一定逻辑关系的符号行称为合式或命题公式。A，35，定义1.3联合公式(w

17、ff)，(1)单命题变量项是联合公式，称为原子命题公式。(2)如果a是合并公式，(a)也是合并公式。(3)如果a，b是合并公式，则(AB)，(AB)，(AB)也是合并公式。(4)在有限情况下，只有(1)(3)形式的符号字符串是合并公式。合式公式也称为命题公式或命题形式，简称公式。如果将a设定为关连公式，将b设定为a的一部分，将b设定为关连公式，则将b称为a的子公式。合并公式：WellFormedFormula，A，36，合并公式的说明，以及定义1.3提供的合并公式的方法称为归纳定义或递归定义。在定义中引入了A、B等符号，用于表示任意合并公式而不是特定公式，这与p、pq、(pq)r等特定公式不同。a、B等字符称为元语言符号。p、q等称为对象语言符号。对象语言是指用于说明研究对象的语言，而元语言是用于说明对象的语言，是不同级别的语言。例如，中国人学习英语时，英语是客体语言，用于学习英语的汉语是元语言。当公式(例如，A、37、联集公式的说明、(A)、(AB)单独出现时，可以保存方括号，将其写为A、AB等。在公式中，可以省略不影响运算顺序的括号。例如，公式(pq)(r)可以用pqr编写。合并公式范例：(pq)(qr)(pq)rp(q