《离散-1-1-命题逻辑》由会员分享,可在线阅读,更多相关《离散-1-1-命题逻辑(26页珍藏版)》请在金锄头文库上搜索。
1、1,离 散 数 学,林昌龙 华侨大学计算机学院,2,教材与参考资料,教材: 离散数学 刘玉珍、刘咏梅编,武汉大学出版社 参考资料: 离散数学耿素云、屈婉玲、张立昂编,清华大学出版社 离散数学朱一清编著,电子工业出版社 Discrete Mathematical Structures Bernard Kolman, Fobert C. Busby and Sharon Ross 著 Prentice Hall出版社,3,目的、意义和要求,IEEE (Institute of Electrical and Electronics Engineers) 美国电气和电子工程师协会 ACM (Assoc
2、iation for Computing Machinery ) 美国计算机协会 Computing curricula 2001 computer science,4,目的、意义和要求,研究内容:离散量的结构及其相互间的关系。 意义:计算机科学的理论基础。 目的:打基础 必备的数学知识 培养抽象思维能力、逻辑推理能力 教学要求: 内容:1-7 章、8-10简介、11章 作业:按时交、课后复习(概念、定理),5,离散数学的构成,数理逻辑,集 合 论,图 论,代数系统,命题逻辑,谓词逻辑,集合,关系,图的基本概念,几个特殊图,代数系统的基本概念,特殊代数系统,离散数学,函数,图的连通性,代数系统
3、的同态与同构,6,主要内容:,1.1 命题符号化 基本概念 命题联接词 1.2 合式公式 命题语言的字母表 合式公式可归纳定义 公式的代入实例,7,第一篇 数理逻辑 第一章 命题逻辑,数理逻辑是用数学方法研究形式推理的一门学科 命题逻辑是数理逻辑的基本组成部分之一 推理的基本要素是命题 把命题作为基本单位来分析,在计算机科学中的应用:软件、硬件设计,符号化,研究公式间的关系,推导、演算,8,1.1 命题符号化 1. 基本概念,命题:具有唯一真/假值的陈述句。 T/1真 F/0假,(1)命题必须是一个完整的句子,包括用数学式子代表的语句。 (2)所给的语句具有真假意义。 一般只有陈述句才具有真假
4、意义 祈使句、疑问句、感叹句不具有真假意义 (3)能判断出真假。 将来某个时候能判断出真假也行,两者必居其一且只居其一 二值逻辑,9,1.1 命题符号化 1. 基本概念,命题:具有唯一真/假值的陈述句。 T/1真 F/0假,例:,中国的首都在北京。 雪是白色的。 1 + 1 = 10 建国大业里面有很多大腕。 贾君鹏,你妈妈喊你回家吃饭。 立正! 你喜欢网络游戏吗? 今天的天气真热!,10,1.1 命题符号化 1. 基本概念,命题:具有唯一真/假值的陈述句。 T/1真 F/0假,例:,哥德巴赫猜想是正确的。 牛鬼蛇神是存在的。 x + y 3 我正在说谎。 本命题是假的。,11,1.1 命题符
5、号化 1. 基本概念,命题:具有唯一真/假值的陈述句。 T/1真 F/0假,简单命题:若命题是一个简单的陈述句。 复合命题:由简单命题通过“非”、“或”、“与”、“蕴含”、“等值”等命题联结词而组成。 例:李红既学英语又学日语。 你只有刻苦学习,才能取得好成绩。,12,否定词():P为真当且仅当P的真值为假。 例: P : 中国的首都在北京。 P: 中国的首都不在北京。,1.1 命题符号化 2.联接词,是不是简单命题?,P,P,0,1,1,0,合取: PQ为真当且仅当P和Q的真值均为真。 例:P: 李红学英语。 Q: 李红学日语。 PQ: 李红学英语并且学日语。,相当于汉语的“与”、“并且”,
6、P Q,PQ,0 0,0,0 1,0,1 0,0,1 1,1,与自然语言不同:凡是命题均可联接。,13,1.1 命题符号化 2.联接词,合取的概念与自然语言中的“与”意义相似,但并不完全相同。例如 P:我们去看电影。 Q:房间里有十张桌子。 上述命题的合取为 PQ:我们去看电影与房间里有十张桌子。 在自然语言中,上述命题是没有意义的,因为P与Q没有内在联系,但作为数理逻辑中P和Q的合取PQ来说,它仍可成为一个新的命题,只要按照定义,在P、Q分别取真值后,PQ的真值也必确定。,14,1.1 命题符号化 2.联接词,命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时,其真值永为F。 P
7、:今天下雨。 Q:今天不下雨。(此时Q既是P) PQ:今天下雨与今天不下雨。 PQ的真值为F。 命题联结词“合取”也可以将若干个命题联结在一起。 “合取”是一个二元运算。,15,1.1 命题符号化 2.联接词,注意,并非所有的“和”、“与”、“并且”均可用“”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“”表示。 练习:P:一个世纪是一百年。 Q:4是偶数。 写出PQ并确定其真值。,16,1.1 命题符号化 2.联接词,析取: PQ为假当且仅当P和Q的真值均为假。 例:P: 李红学英语。 Q: 李红学日语。
8、 PQ: 李红学英语或者学日语。,相当于汉语中两者可同时为真的“或”,P Q,PQ,0 0,0,0 1,1,1 0,1,1 1,1,并非所有的“或”可用“”表示。例如,“我向东行或向西行。”该语句中的“或”称为“排斥或”,因为事实上一个人不会既向东行,又向西行。 析取“”指的是“可兼或”。例如,他可能是100米或400米赛跑的冠军。这里 P:他可能是100米赛跑的冠军。 Q:他可能是400米赛跑的冠军。 PQ:他可能是100米或400米赛跑的冠军。,17,1.1 命题符号化 2.联接词,还有一些汉语中的“或”字实际上不是命题联结词。例如,他昨天做了二十或三十道习题。这里的“或”字只表示了习题的
9、近似数目,不能用联结词“”表达。 练习:P:雪是黑的。 Q:4是偶数。 写出PQ并确定其真值。,18,1.1 命题符号化 2.联接词,蕴涵: PQ为假当且仅当P为真、Q为假。 例:P: 天晴。 Q: 我骑自行车上班。 PQ: 如果天晴,则我骑自行车上班。,P Q,PQ,0 0,1,0 1,1,1 0,0,1 1,1,例1 如果某动物为哺乳动物,则它必胎生。 例2 如果我得到这本小说,那么我今夜就读完它。 例3 如果雪是黑的,那么太阳从西方出。 上述三个例子都可用条件命题PQ表达。 在例1中,P:某动物为哺乳动物,Q:它必胎生。P的真值为T,Q的真值为T,PQ的真值为T。 在例2中,P:我得到这
10、本小说,Q:我今夜就读完它。P的真值为T,Q的真值为T,PQ的真值为T。如果P的真值为T,Q的真值为F,PQ的真值为F。如果P的真值为F,Q的真值为T,PQ的真值为T。 在例3中,P:雪是黑的,Q:太阳从西方出。P的真值为F,Q的真值为F,PQ的真值为T。,19,1.1 命题符号化 2.联接词,在自然语言中,“如果”与“那么”之间常常是有因果联系的,否则就没有意义,但对条件命题PQ来说,只要P、Q能够分别确定真值,PQ即成为命题。此外,自然语言中对“如果、则”这样的语句,当前提为假时,结论不管真假,这个语句的意义,往往无法判断。而在条件命题中,规定为“善意的推定”,即前提为F时,条件命题的真值
11、都取为T。,在数学上和有些逻辑学的书籍中,“若P则Q”亦可叫作P蕴含Q,而本书在条件命题中将避免使用“蕴含”一词,因为在以后将另外定义“蕴含”这个概念。 命题联结词“”亦可记作“ ”。,20,1.1 命题符号化 2.联接词,蕴涵 P Q,P Q,PQ,0 0,1,0 1,1,1 0,0,1 1,1,P是Q的充分条件。 Q当P。 Q是P的必要条件。 P仅当Q。 P除非Q。 只有Q,才P。,21,1.1 命题符号化 2.联接词,等价: PQ为真当且仅当P和Q的真值相同。 例:P: 两个圆的面积相等。 Q: 两个圆的半径相等。 PQ: 两个圆的面积相等当且仅当两个圆的半径相等。,P Q,PQ,0 0
12、,1,0 1,0,1 0,0,1 1,1,“P当且仅当Q”有两层含义: (1)P当Q; (2)P仅当Q 等价联结词又可以称为双蕴含连接词,例 当且仅当你走,我留下。 P:你走,Q:我留下。 命题可以表示为:P Q,22,1.1 命题符号化 2.联接词,分析找出 简单命题,用大写字母 表示简单命题,用联接词联接命题符号,例:符号化命题:如果我上街并且我不累,我就去书店看看。 简单命题:我上街 我累 我去书店看看,解 令 P: 我上街 Q: 我累 R: 我去书店看看 则可符号化为:(PQ)R,23,1.2 合式公式(1),1. 命题语言的字母表 : 命题常元:T, F (或 0,1) 命题变元:P
13、1, P2, , Pn 联接词:, 辅助符号:(, ) *:上的符号串,包括空串 2. 命题逻辑的合式公式可归纳定义如下: 命题常元或命题变元是合式公式; 若A,B是合式公式,则(A),(AB),(AB),(AB)和(AB)都是合式公式; 有限次地使用,所得到的符号串才是合式公式。 例:((PQ)P)R 子公式、真子公式,24,1.2 合式公式(2),3. 公式的代入实例:,所得到的公式称为A的代入实例。 例:(PQ)P,用PQ取代P,用PQ取代Q, (PQ)(PQ)(PQ)(同时取代) (PQ)Q)(PQ) (P(PQ)(PQ)(P(PQ) 注意上面“同时取代”和“逐步取代”的不同,先取代P,再取代Q,25,作业:P4 1,2, P7 3(1),26,发明计算机的目的 ? 计算机应用领域,信息、数据及其处理方法机器表示,现实世界,信息世界,机器世界,抽象表示,特点:处理各种各样 非连续数据 ,意义:,