离散数学命题逻辑讲解.ppt

An Introduction to Database Systenm 重庆文理学院计算机学院  数理逻辑 逻辑学是一门研究人的思维形式和规律的学科。 逻辑学可分为形式逻辑、辩证逻辑和数理逻辑三大类。 数理逻辑是数学的一个分支，它用数学的方法研究推理的过程。推理是从一种判断推出另一种判断的思维过程。 数理逻辑 数学方法： 采用一套符号、公式表示体系，使用已有的数学成果和方法，尤其是形式化的公理方法，对具体事物进行抽象的形式化研究。 数理逻辑的优点：表达简洁、推理方便、概括性好、易于分析。  第一章 命题逻辑 1.1 命题与连接词 1.2 命题公式及命题公式的翻译 1.3 等价公式及公式的分类 1.4 蕴含式与对偶式 1.5 其他连接词与最小连接词组 1.6 范式 1.7 公式的主范式 1.8 推理理论 1.1 命题与连接词 1.1.1 命题的概念 1.1.2 逻辑连接词 1.1.1 命题的概念 定义1.1.1 命题是具有真假意义的陈述句。 命题总是具有一个“值”，称为真值。真值只有“真”和“假”两种，“真”用符号T或1表示，“假”用符号F或0表示。 只有能够确定或能够分辨其真假的陈述句才能称为命题。一切没有判断内容的句子、无所谓是非的句子，如感叹句、疑问句、祈使句等不是命题。 1.1.1 命题的概念 例1.1.1 判断下列各语句是否为命题。 (1). 神州七号的成功发射是中国航天业的又一个壮举。 (2). 地震是地球各大板块相互挤压造成的。 (3). 北京举办了2008年奥林匹克运动会。 (4). 游客止步！ (5). 明天是否要下雨？ (6). 校园的景色真美！ (7). 如果功课不多，那么放学后我去打篮球。 (8). 我选修数学专业，或者我选修英语专业。 (9). x＋y＞5。 1.1.1 命题的概念 有两点需要注意： ■ 命题是可分辨真假的陈述句，但不一定必须知道它的真假。 ■ 悖论的陈述句不是命题，因为悖论往往产生自相矛盾的结论。 1.1.1 命题的概念 命题分为原子命题和复合命题两种类型。复合命题是由原子命题和连接词复合而成。判断一个命题是否为复合命题，其关键是连接词是否出现。若出现，则是复合命题；若不出现，则是原子命题。 一个原子命题通常用大写字母或带下标的大写字母表示，如P，Q，…或Pi ，Qi ，…。表示原子命题的符号称为命题标识符。一个命题标识符如果表示确定的命题，称为命题常量。如果命题标识符只表示命题的位置标志，称为命题变元。命题变元不能确定真值，只有当命题变元用一个特定命题取代时，命题变元才有真值。 例如：用P和Q分别表示原子命题“我是中国人”和“我为中国的进步感到骄傲”，那么复合命题“我是中国人而且我为中国的进步感到骄傲”，则可表示为“P而且Q”。自然语言中“而且”这样的连接词是可用逻辑符号表示的。 1.1 命题与连接词 1.1.1 命题的概念 1.1.2 逻辑连接词 1.1.2 逻辑连接词 自然语言中，常使用“或”、“与”、“如果…，那么…”等一些连接词。连接词是复合命题的重要组成部分，为了便于书写和推理，必须对连接词作出明确规定和符号化。 下面介绍常用的五种连接词： 1. 否定 2. 合取 3. 析取 4. 条件 5. 双条件 2. 合取 定义1.1.3 设P和Q是两个命题，由连接词∧将P、Q联接成复合命题，记作P∧Q ，读作“P和Q的合取 ”，或“P合取Q ”。 当且仅当P、Q同时为T 时， P∧Q为T。在其它情况下，P∧Q的真值为F。连接词∧的真值如表1.1.2所示。 表 1.1.2 连接词“∧”的真值表 连接词“∧” 表示自然语言中“而且”、“并且”、“既…，又…”等的逻辑抽象。 3. 析取 定义1.1.4 设P 和Q是两个命题，由连接词∨将P、Q 联接成复合命题，记作P∨Q ，读作“P 和Q的析取 ”，或“P 析取Q ”。 当且仅当P、Q同时为F 时， P∨Q为F。在其它情况下，P∨Q的真值为T。连接词∨的真值如表1.1.3所示。 表 1.1.3 连接词“∨”的