离散-1-1-命题逻辑

《离散-1-1-命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学林昌龙华侨大学计算机学院1教材与参考资料教材：《离散数学》刘玉珍、刘咏梅编，武汉大学出版社参考资料：《离散数学》耿素云、屈婉玲、张立昂编，清华大学出版社《离散数学》朱一清编著，电子工业出版社《DiscreteMathematicalStructures》BernardKolman,FobertC.BusbyandSharonRoss著PrenticeHall出版社2目的、意义和要求IEEE(InstituteofElectricalandElectronicsEngineers)美国电气和电子工程师协会ACM(AssociationforComputingMachinery)美国计算机

2、协会Computingcurricula2001computerscience3目的、意义和要求研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学要求：内容：1-7章、8-10简介、11章作业：按时交、课后复习（概念、定理）4离散数学的构成数理逻辑集合论图论代数系统命题逻辑谓词逻辑集合关系图的基本概念几个特殊图代数系统的基本概念特殊代数系统离散数学函数图的连通性代数系统的同态与同构5主要内容：§1.1命题符号化基本概念命题联接词§1.2合式公式命题语言的字母表合式公式可归纳定义公式的代入实例6第一篇数理逻辑第一章命题

3、逻辑数理逻辑是用数学方法研究形式推理的一门学科命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析在计算机科学中的应用：软件、硬件设计符号化研究公式间的关系推导、演算7§1.1命题符号化1.基本概念命题：具有唯一真/假值的陈述句。T/1—真F/0—假（1）命题必须是一个完整的句子，包括用数学式子代表的语句。（2）所给的语句具有真假意义。一般只有陈述句才具有真假意义祈使句、疑问句、感叹句不具有真假意义（3）能判断出真假。将来某个时候能判断出真假也行两者必居其一且只居其一——二值逻辑8§1.1命题符号化1.基本概念命题：具有唯一真/假值的陈述句。T/1—真F/0—假例：

4、中国的首都在北京。雪是白色的。1+1=10《建国大业》里面有很多大腕。贾君鹏，你妈妈喊你回家吃饭。立正！你喜欢网络游戏吗？今天的天气真热！9§1.1命题符号化1.基本概念命题：具有唯一真/假值的陈述句。T/1—真F/0—假例：哥德巴赫猜想是正确的。牛鬼蛇神是存在的。x+y>3我正在说谎。本命题是假的。10§1.1命题符号化1.基本概念命题：具有唯一真/假值的陈述句。T/1—真F/0—假简单命题：若命题是一个简单的陈述句。复合命题：由简单命题通过“非”、“或”、“与”、“蕴含”、“等值”等命题联结词而组成。例：李红既学英语又学日语。你只有刻苦学习，才能取得好成绩。11否定词（┐）：┐P为真当且仅

5、当P的真值为假。例：P:中国的首都在北京。┐P:中国的首都不在北京。§1.1命题符号化2.联接词是不是简单命题？P┐P0110合取∧:P∧Q为真当且仅当P和Q的真值均为真。例：P:李红学英语。Q:李红学日语。P∧Q:李红学英语并且学日语。相当于汉语的“与”、“并且”PQP∧Q000010100111与自然语言不同：凡是命题均可联接。12§1.1命题符号化2.联接词合取的概念与自然语言中的“与”意义相似，但并不完全相同。例如P：我们去看电影。Q：房间里有十张桌子。上述命题的合取为P∧Q：我们去看电影与房间里有十张桌子。在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P

6、和Q的合取P∧Q来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，P∧Q的真值也必确定。13§1.1命题符号化2.联接词命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。P：今天下雨。Q：今天不下雨。（此时Q既是┐P）P∧Q：今天下雨与今天不下雨。P∧Q的真值为F。命题联结词“合取”也可以将若干个命题联结在一起。“合取”是一个二元运算。14§1.1命题符号化2.联接词注意，并非所有的“和”、“与”、“并且”均可用“∧”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“

7、∧”表示。练习：P：一个世纪是一百年。Q：4是偶数。写出P∧Q并确定其真值。15§1.1命题符号化2.联接词析取∨:P∨Q为假当且仅当P和Q的真值均为假。例：P:李红学英语。Q:李红学日语。P∨Q:李红学英语或者学日语。相当于汉语中两者可同时为真的“或”PQP∨Q000011101111并非所有的“或”可用“∨”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会