离散数学CH02-命题逻辑.ppt

第2章: 命题逻辑 第3章：谓词逻辑 亚里士多德（Aristotle，B.C.384-B.C.322）：三段论 莱布尼茨（Gottfried Wilhelm von Leibniz， 1646-1716）：将推理还原为计算 布尔（George Boole 1815-1864）：形式符号和等式，布尔代数 弗雷格（Gottlob Frege，1848-1925）：一阶逻辑 罗素（Bertrand Russell，1872-1970）：逻辑主义 希尔伯特（David Hilbert，1862-1943）：形式主义 哥德尔（Kurt Godel, 1906-1978）：逻辑和形式方法不充分性 研究人的思维形式和规律的科学称为逻辑学。逻辑（Logics）研究的是有效的推理方法。 逻辑学包括：1.形式逻辑2.辨证逻辑3.数理逻辑 数理逻辑（Mathematical Logics）就是用数学化（符号化）的手段，研究有效的推理方法。所谓数学方法主要是指引进一套符号体系的方法。因此数理逻辑又称为符号逻辑。数理逻辑在逻辑设计、人工智能、语言理论、程序正确性证明等方面都有重要应用,是现代计算机技术的基础 。 2.1 命题及联结词 2.2 命题公式与翻译 2.3 真值表和等价公式 2.4 重言式 2.5 范式 2.6 全功能联结词集 2.7 对偶式与蕴含式 2.8 命题逻辑的推理理论 2.1.1 命题的基本概念 在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。 命题的概念包含了以下3个要素： ⑴只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。 ⑵一个语句虽是陈述句,但不能判断真假不是命题。 ⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。 2.1.1 命题的基本概念 命题的真值：判断的结果 真值的取值：真(True,T,1)与假(False,F,0) 真命题(真值为真的命题)与假命题(真值为假的命题) 任何命题的真值是惟一的 简单命题符号化 用小写英文字母 p, q, r, …, pi, qi, ri (i?1)表示简单命题。 用“1”表示真，用“0”表示假。例如，令 p：π是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1。 否定联结词的真值表 合取联结词的实例 例 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但是不用功. (4) 张辉与王丽都是三好生. 合取联结词的实例 令p:吴颖用功, q:吴颖聪明 (1)吴颖既用功又聪明. (2)吴颖不仅用功而且聪明. (3)吴颖虽然聪明，但不用功. (4)张辉与王丽都是三好生. 合取联结词的实例 p ：今天下雨 q：明天下雨 p ? q：今天下雨并且明天下雨 今天与明天都下雨 这两天都下雨 p ：我们唱歌 q：我们跳舞 p ? q：我们一边唱歌一边跳舞 合取联结词的实例 p ：他聪明 q：他用功 他既聪明又用功. p ? q 他虽然聪明，但不用功。 p ??q 他不仅聪明，而且用功。 p ? q 他不是不聪明，而是不用功。 ?(? p) ??q 合取联结词的实例 注意：不要一看到与、和等联结词就用?。 张辉与王丽是同学。 p:张辉与王丽是同学（简单命题） 注意：在数理逻辑中可以把两个没有内在联系的命题用联结词连接起来。 p：我去看电影 q：房间里有十张桌子 p ? q 在逻辑学中允许 析取联结词的真值表 析取联结词的实例 例 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1985 年或 1986 年. 析取联结词的实例 将下列命题符号化 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. 析取联结词的实例 (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1985 年或 1986 年. 单条件联结词的真值表 我将去旅游，仅当我有时间。 p: 我去旅游 q: 我有时间 p → q p: 不下雨 q: 我骑自行车上班 只要不下雨，我就骑自行车上班 p → q 只有不下雨，我才骑自行车上班。 q