《x本科数理逻辑-命题3-1》由会员分享，可在线阅读，更多相关《x本科数理逻辑-命题3-1（30页珍藏版）》请在金锄头文库上搜索。
1、 1、课程意义：离散数学是现代数学的一个分支随计算机的发展而出现的分支研究方法与以实数连续性为基础的微积分形成鲜明对 照2.目的 （1）为后继课程的内容作必要的数学准备：数据结构、数字逻辑（数字电路）、操作系统、编译原理的等 （2）培养抽象思维的逻辑推理能力-这是创新能力的主要基础-提高认识能力、处理问题的概括能力，解决问题的能力均可表现为以数字”0” 和 ”1” 为特征的离散现象引 言现实中的离散现象：电路的开和关、通和断磁介质的正负向电压的高电平和低电平 信息技术中的计算机软件（代码集合）硬件（数字电路）均是以离散现象所表示的系统 所有的信息专业均将其作为重要专业基础课 3、 主要内容 学
2、习的主要内容：1）数理逻辑 （命题逻辑）1,2,3章(一阶逻辑) 4，5章2）集合论 6，7，8，9 章3）代数结构 10、11章4）图论 14，15，16 章 参考书：离散数学及其应用 傅彦编 电子出版社（应用-通俗）离散数学 左孝凌等编 上海科技文献出版社（经典）4、 学习方法 （1）概念的基本术语，领会准确清晰 （2）定理的条件结论明确 （3）演绎、推理要求严谨 （4）听课认真 、作业自己完成、有问题及时问。 （5）期末考试 （考勤、作业30，期末考试成绩70） 答疑时间：周一下午3点6点 地点：二层219房间第一部分 数理逻辑 逻辑学：研究人的思维形式规律的科学根据研究的对象和方法分为
3、三类1.辩证逻辑-认识论（马克思主义）2.形式逻辑- 研究人的思维逻辑的形式和规律（古希 腊-亚里斯多德）3.数理逻辑-采用数学方法来研究形式逻辑中的推理 规律（符号逻辑） 数理逻辑： 1.形式逻辑：思维的形式结构-包括了概念，判断和推理之间的结构和联系 2.在数理逻辑中的表示：（1）概念：是思维的基本单位(事物的性质属性）（2）判断：对事物是否具有的属性进行肯定或者否定用字母表示事物之间的关系用运算定义用运算符号（连接词）表示（3）推理：有一个或多个判断推出另一判断的思维形式（4）符号逻辑：引入一套符号体系的方法来从量的方向研究思维规律 主要的内容：命题逻辑、谓词逻辑、证明论，模型论，递归函
4、数轮，公理化集合论等我们仅学习其中的命题逻辑，谓词逻辑是其中最基本的部分 例、 判断下列句子是否为命题(1) 太阳是圆的；(2) 北京是中国的首都；(3) x + y 0 ；(4) 充分大的偶数可表示为两个素数之和(哥德巴赫猜想)；(5) 2100年元旦是晴天；(6) 你是要出去吗? 第一章 命题逻辑基本概念一、命题1、命题定义：具有真假意义的陈述句被称为命题注1、必须是陈述句（感叹句、疑问句、祈使句均不是命题）注2、有确定的真假值真假意义必须二者必居其一（悖论）(7) (7) 请把门关上；请把门关上； (8) (8) 今天的天气真好啊今天的天气真好啊! ! (9) 1+1=10 (9) 1+
5、1=10 ； （1010）火星上有生物；）火星上有生物； （1111） 这个语句是假的；这个语句是假的；2 2、命题的、命题的真值真值命题若为真，称命题的命题若为真，称命题的真值为真真值为真（可记为（可记为 1 1 或或 T T）命题若为假，称命题的命题若为假，称命题的真值为假真值为假（可记为（可记为 0 0 或或 F F）3. 3. 命题的符号化命题的符号化 命题的实质是具有真值将命题的实质抽象出来(内容隐去）用字母表示一个具体的命题对于内容不相关的问题均可以进行讨论（只要具有真值）例：2既是偶数又是素数；如果周末天气晴朗，则我们到郊外去旅游；雪是白的当且仅当 1+13； 4. 4. 简单命
6、题与复合命题简单命题与复合命题若命题不能分解为更简单的陈述句，称为原子（简单）命题注：复合命题要能分解为若干具体的简单命题的组合 李丽和王丽是同学；5. 5. 命题变元命题变元用一个字母表示一个具体命题（具有真值）称为命题常 元用一个字母表示一个抽象的命题（无确定的真值）称为 命题变元。例 P: 我是老师 0（f,F）, 1（t,T） 也称为常元当p没有特指为一个命题时，p为命题变元。6. 命题变元的赋值（命题变元的值域）称为对命题变元赋予真值。注：命题变元不是命题只有对其进行赋值才为一个具体命题转运算例: 判断下例是否为复合命题1、张辉与王丽都是三好生 2、张辉与王丽是同乡 3、8是偶数的充
7、要条件是8能被3 整除 4、他是山东人或东北人 5、除非雪是黑的，否则2+24 6、王超和王非是兄弟二.命题的运算复合命题-是利用自然语言的一些连词将若干简单命题复合构 成连词-要将其定义（抽象）为数理逻辑中的运算符号抽象要有严格的定义-只有严格的定义运算的运算律，性 质才能使在此上的演绎、演算得以正确进 行注：由于自然语言的广义性一定要把握定义的实质（不能仅从字面上进行套用）先定义五种最常用的运算运算的符号称为联接词1、否定联接词定义：设P为命题，规定“P是不对的” 称为对P的否 定记为： P规定： P为真当且仅当P为假 如 p: 6是素数 p: 6 不是素数 注： iP是一个命题，其真值由
8、P 的真值确定ii）自然语言中的否定中的逻辑关系例 P: 所有自然数均为偶数P: 对全称的否定，只要个别不成立对个别的否定，要对全称进行否定 逻辑上有效如 p: 他不会范错误 P: 所以的人都会范错误 iii）从运算的角度看否定联接词为一元运算（仅对一个命题起作用）2、合取联接词定义：设p,q为二命题，复合命题“p并且q”( 或“p与q”)称为p与q的合取式记作pq， 称作合取联结词。规定pq为真，当且仅当p与q同时为真 。注：i pq为一个复合命题，由二个命题 p,q复合构成的命题 ii合取在逻辑中表现为俩个事件同时发生注意自然语言中的连词的词义来判别是否属于此种现象我与小张去游泳 连词 “
9、与”我与小张是老乡（这里的“与”并没有两个事件同时发生，它是一个简单命题。 ） 连词： 即 又 、不仅 而且 、“和” 等均具有合取的意义例 将下列命题符号化(1)吴颖既用功又聪明(2)吴颖不仅用功而且聪明p：吴颖用功 q：吴颖聪明（1）、(2) 均可表示为 p q(3)吴颖虽然聪明，但不用功p q(4)张辉和王丽都是三好生r：张辉是三好生 s：王丽是三好生r s(5)张辉和王丽是同学t：张辉和王丽是同学iii由于仅讨论真值问题，那么对风马牛不相及的 命题也可以进行合取P：6时素数 Q：今天刮风在这里是有意义的，关键只要具有真 值 、真值表将命题变元的所有赋值与其复合命题所得的真值用表格形式给
10、出（运算表）要注意赋值的次序（按二进制的大小进行）联接词 非()的真值表联接词合取（ ）的真值表 4、析取联接词定义：设，为命题，称“或”为、的的析取，记作规定：为假，当且仅当、同时为假1）析取是自然语言连词“或”的抽象“或”在自然语言中有二重含义：“可兼或”- 二个判断可同时为真（相容或）小张喜欢唱歌或喜欢跳舞“排斥或”- 二个判断不能同时为真（异或、不可兼或）小张住在203房间或303房间 联接词所定义的“或”抽象的是那种？2）从定义可得其真值表 析取联结词“ ”抽象的是可兼或 例 将下列命题符号化(1)张晓静爱唱歌或爱听音乐p:张晓静爱唱歌 q:张晓静爱听音乐相容或：可用表示为 p q
11、(2)张静是大学生或是运动员p:张静是大学生 q:张静是运动员相容或：可用表示为 p q (2)张晓静是江西人或安徽人排斥或：可表示为（ p q） （ p q） (3)张晓静只能挑选202或203房间排斥或 5蕴涵联结词 “” ）定义：设，为命题，称“如果，则”为、的蕴涵式（条件命题），记作 Q规定： Q真值为假，当且仅当P为真时Q为假，并称P为 Q的前提（前件），Q为 Q 的结论（后件）2）蕴涵联接词“”的真值表注意：条件命题的真值与条件命题中的结论的真值是不同的概念从直值表中可以分析出：i 当前件为假，不论后件如何，则 Q一定为真即：前提不成立，结论不论真假， Q为真命题ii后件为真，不论
12、前件真假， Q为真命题 iii Q 的真值 仅在 “p为真q为假”时为假（其余情况均为真） 当 Q 的真值为假时：Q为假，则P一定为真 P为真， Q一定为假 当 Q的真值为真P为真，Q一定为真 P为假时， Q可任意 以上的结论对今后的推理将起到非常重要的作用，对条件命 题的理解，将贯穿于我们这五章的主要内容 3）自然语言中将该命题的前件和后件的其他叙述为：p q p是q 的充分条件 q是p的必要条件前件是后件的充分条件，后件是前件的必要条件 而对于充分条件和必要条件的叙述又有各种的表达方式：如果 p 则 q 只有 q 则 p只要 p 就 q p 仅当 q若 p 就 q 除非 q 则 p 关键是
13、对此类命题的符号化 双条件例 将下列命题符号化，并指出各复合命题的真值：(1)如果3+3 = 6，则雪是白色的(2)若3+3 6，则雪是白色的(3)只要3+3 = 6，则雪不是白色的(4)3+36是雪不是白色的充分条件雪不是白色的是3+36的必要条件令p：3+3= 6 （p 的真值为1） q：雪是白色的（q的真值为1）两个命题虽无逻辑上的内在联系，但可用蕴涵式表 示（1）表示为p q（2）表示为 p q （3）表示为 p q （4）表示为 p q 真值为 1 1 0 1 以下命题中出现的a是给定的一个正整数：令 r：a能被4整除 s: a能被2整除 (5)只要a能被4整除，则a一定能被2整除(
14、6)a被4整除，仅当a能被2整除(7)除非a能被2整除，a才能被4整除(8)除非a能被2整除，否则a不能被4整除(9)只有a能被2整除，a才能被4整除(10)只要a能被2整除，a才能被4整除(5)到(9)五个命题均叙述的是a能被2整除是a能被4整除的必要条件 ，只是在叙述上有所不同，因而都符号化为 r s是否存在真值？不论a为何整数从逻辑关系可知：不会出现前件真后件假的情况故前五个命题均为真（10）所表示的是s是r的充分条件（即 s r ）那么结果就不能确定（只能由a的具体值确定来得到）6.等价式 (双条件命题) 1）定义：P，q为命题，称复合命题“P当且仅当 q”为P、q的等价式（双条件命题
15、）记为P q。规定： P q真值为真，当且仅当P，q同 时为真或同时为假。例6：将下列命题符号化，并求命题的真值：(1)蓝色和黄色可以调配成绿色；(2)蓝色和黄色都是常用的颜色；(3)王小红虽然没上过大学，但她自学成才；(4)2是偶素数(5)李冰选学英语或法语 (6)李和平是山西人或陕西人；(7)只要4是偶数，则5也是偶数；(8)除非4是奇数，否则5不是奇数；(9)经一事，长一智，并且不经一事，不长一智；(10)经一事，长一智，并且不长一智，不经一事 ；(11) 235当且仅当19不是素数6五个连接词将原子命题连接为复合命题，可以将连接词 看成对原子命题的运算符1）通过连接词得到的复合命题的真值仅与原子命题的真 值有关（与其内容、含义均无关）2）作为运算律来说，、 均满足交换律和结合律 ，而 不满足交换律和结合律3）作为运算来说，五个连
