离散数学第一章第一节.pptVIP

第一章 命题逻辑 数理逻辑是用一套数学符号系统来研究思维规律的学科。命题逻辑和谓词逻辑是数理逻辑中最基本的内容。 十九世纪中后期，德国数学家莱布尼兹、英国数学家布尔和逻辑学家怀海特、罗素为数理逻辑的产生和发展有突出贡献。 从二十世纪40年代起，数理逻辑成为计算机科学的重要基础理论之一。如布尔代数在计算机硬件设计中发挥了重大作用；形式语言的研究为建立计算机语言提供了基础。 第一章 目录 第一讲 命题和命题联结词 第二讲 命题公式和真值表 第三讲 蕴含式 第四讲 范式 第五讲 推理理论 第1-1讲 命题和命题联结词 1. 命题及其真值 2. 复合命题 3. 命题常量与命题变元 4. 命题联结词 5. 联结词的真值表定义 6. 本讲小结 7. 测试 8. 第1-1讲 作业 1、命题及其真值 思维的形式结构包括了概念、判断和推理之间的结构和联系。判断是对事物有肯定或否定的一种思维形式，而能够表达判断的语句叫陈述句。 命题是客观上能判明真假的陈述句。当命题为真时，称命题的真值为“真”；否则，说命题的真值为“假”。用T或1表示“真”，用F或0表示“假”。 例1 判断下列语句是不是命题 (1) 《红楼梦》的作者是曹雪芹。 (2) 沈阳市是吉林省省会。 (3) 外星人曾来过地球 例2 判断下列语句是不是命题: (1) 天多蓝啊! (2) 你去哪里？ (3) 帮帮我吧! (4) X+Y＞4。 (5) 本命题为假。 2、复合命题 无法继续分解的简单陈述句，称为简单命题或原子命题。(不包含任何“与、或、非”等联结词的命题) 由一个或几个简单命题通过联结词复合而成的命题，称为复合命题。 命题一般用大写英文字母表示。表示命题的符号叫命题标识符。 例如，用Ｐ表示“３是奇数”，记作 “Ｐ：３是奇数”。 3、命题常量和命题变元 如果一个命题标识符表示某个确定的命题，则称为命题常量。特别地，真命题(用T表示)和假命题(用F表示)是命题常量。 如果一个命题标识符表示不确定的命题，则称为命题变元。命题变元不是命题。在命题演算中，对命题变元指定相应的真值(真或假)，称为对命题变元的真值指派。 集合{T, F }是命题变元的值域。 4、命题联结词 否定联结词? 合取联结词∧ 析取联结词∨ 条件联结词? 双条件联结词? 定义1 否定联结词 设Ｐ为命题，复合命题非Ｐ，叫Ｐ的否定式，记作?Ｐ。记号?叫否定联结词。?Ｐ为真当且仅当Ｐ为假。 例如，设Ｐ：今天是星期一。 则?Ｐ：今天不是星期一。 定义2 合取联结词 设Ｐ，Ｑ 表示两个命题，复合命题“Ｐ且Ｑ”叫命题Ｐ与Ｑ的合取，记作Ｐ∧Ｑ。记号∧叫合取联结词。Ｐ∧Ｑ为真，当且仅当Ｐ，Ｑ同时为真。 例如，设Ｐ: 2是素数。 Ｑ: 2是偶数。R： 2是奇数。 则Ｐ∧Ｑ：2既是素数又是偶数。(真值为真) Ｐ∧R：2既是素数又是奇数。(真值为假) 定义3 析取联结词 设Ｐ，Ｑ为二命题，复合命题“Ｐ或Ｑ”称作Ｐ与Ｑ的析取，记作Ｐ∨Ｑ，∨叫析取联结词。Ｐ∨Ｑ为真，当且仅当Ｐ，Ｑ之中至少有一为真。 例如，设Ｐ：2是素数。Ｑ：2是偶数。 R： 2是奇数。 则Ｐ∨Ｑ：2是素数或2是偶数。(真值为真) Ｐ∨ R：2是素数或2是奇数。(真值为真) 定义4 条件联结词 设Ｐ，Ｑ是二命题，复合命题“如Ｐ，则Ｑ”称为Ｐ与Ｑ的条件命题，记作Ｐ→Ｑ, 其中Ｐ叫前件或前题，Ｑ叫后件或结论。Ｐ→Ｑ为真当且仅当Ｐ真和Ｑ假不同时成立。 例如，如果明天天晴就开运动会。 设Ｐ：明天天晴。Ｑ:明天开运动会。 则原命题表示为：Ｐ→Ｑ。 定义5 双条件联结词 设Ｐ,Ｑ为二命题，复合命题“Ｐ当且仅当Ｑ”称为Ｐ与Ｑ的双条件命题，记作Ｐ?Ｑ。?叫双条件联结词，也记作iff。Ｐ?Ｑ为真当且仅当Ｐ,Ｑ真值相同。 例如，2+2＝5当且仅当雪是黑的。 设Ｐ： 2+2＝5 。Ｑ：雪是黑的。 则原命题表示为：Ｐ?Ｑ。 5、 联结词的真值表定义 6、本讲小结 7、 练习 第一讲 作业 P8 3，4c，5bf，6bdgh * * 解：(1)是命题。其真值为“真”，因而是真命题。 (2)是命题。其真值为“假”，因而是假命题。 (3)的真实性目前还无法判明，但在客观上，是真是假，二者必居其一。因此它是命题。 解：(1)是感叹句；(2)是疑问句；(3)是祈使句。它们都不是命题。 (4) 真假要视Ｘ、Ｙ的值而定，因此这个语句无确定真值。它不是命题