离散数学第1章-命题逻辑.ppt

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

1、重庆文理学院计算机学院离散数学2010年9月.离散数学第一篇数理逻辑.数理逻辑逻辑学是一门研究人的思维形式和规律的学科。逻辑学可分为形式逻辑、辩证逻辑和数理逻辑三大类。数理逻辑是数学的一个分支，它用数学的方法研究推理的过程。推理是从一种判断推出另一种判断的思维过程。.数理逻辑数学方法：采用一套符号、公式表示体系，使用已有的数学成果和方法，尤其是形式化的公理方法，对具体事物进行抽象的形式化研究。数理逻辑的优点：表达简洁、推理方便、概括性好、易于分析。.离散数学第一章命题逻辑.第一章命题逻辑1.1命题与连接词1.2命题公式及命题公式的翻译1.

2、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).

3、神州七号的成功发射是中国航天业的又一个壮举。(2).地震是地球各大板块相互挤压造成的。(3).北京举办了2008年奥林匹克运动会。(4).游客止步！(5).明天是否要下雨？(6).校园的景色真美！(7).如果功课不多，那么放学后我去打篮球。(8).我选修数学专业，或者我选修英语专业。(9).x＋y＞5。.1.1.1命题的概念有两点需要注意：■命题是可分辨真假的陈述句，但不一定必须知道它的真假。■悖论的陈述句不是命题，因为悖论往往产生自相矛盾的结论。..1.1.1命题的概念命题分为原子命题和复合命题两种类型。复合命题是由原子命题和连接词复合

4、而成。判断一个命题是否为复合命题，其关键是连接词是否出现。若出现，则是复合命题；若不出现，则是原子命题。一个原子命题通常用大写字母或带下标的大写字母表示，如P，Q，…或Pi，Qi，…。表示原子命题的符号称为命题标识符。一个命题标识符如果表示确定的命题，称为命题常量。如果命题标识符只表示命题的位置标志，称为命题变元。命题变元不能确定真值，只有当命题变元用一个特定命题取代时，命题变元才有真值。例如：用P和Q分别表示原子命题“我是中国人”和“我为中国的进步感到骄傲”，那么复合命题“我是中国人而且我为中国的进步感到骄傲”，则可表示为“P而且Q”。

5、自然语言中“而且”这样的连接词是可用逻辑符号表示的。.1.1命题与连接词1.1.1命题的概念1.1.2逻辑连接词.1.1.2逻辑连接词自然语言中，常使用“或”、“与”、“如果…，那么…”等一些连接词。连接词是复合命题的重要组成部分，为了便于书写和推理，必须对连接词作出明确规定和符号化。下面介绍常用的五种连接词：1.否定2.合取3.析取4.条件5.双条件.1.否定定义1.1.2设P是一个命题，P的否定是一个新的命题，记作¬P，读作“非P”。连接词“¬”表示命题的否定。若P为T，则¬P为F；若P为F，则¬P为T。命题P与其否定¬P的关系如表1

6、.1.1所示。表1.1.1连接词“¬”的真值表连接词“¬”表示自然语言中“非”、“不”、“没有”的逻辑抽象。.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

7、和Q的析取”，或“P析取Q”。当且仅当P、Q同时为F时，P∨Q为F。在其它情况下，P∨Q的真值为T。连接词∨的真值如表1.1.3所示。表1.1.3连接词“∨”的真值表连接词“∨”表示自然语言中“或”、“或者”等逻辑抽象。在自然语言中的“或”是多义的，可表示“排斥或”，也可表示“可兼或”。析取连接词表示的是“可兼或”。.3.析取“排斥或”也是一种连接词，用表示。连接词的真值如表1.1.4所示。.4.条件定义1.1.5设P和Q是两个命题，由连接词→将P、Q联接成复合命题，记作P→Q，读作“如果P，那么Q”，或“若P则Q”。在P→Q中，P称为前

8、件，Q称为后件。当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，否则P→Q的真值为T。连接词→的真值如表1.1.5所示。表1.1.5连接词“→”的真值表.4.条件在自然语言中，“如果…