《[计算机软件及应用]数据结构- 命题逻辑》由会员分享，可在线阅读，更多相关《[计算机软件及应用]数据结构- 命题逻辑（183页珍藏版）》请在金锄头文库上搜索。
1、第第1章章 命题逻辑命题逻辑离散数学是以离散型变量为研究对象的一门科学。离散数学是以离散型变量为研究对象的一门科学。离散数学课程介绍离散数学各分支的根本概念、离散数学课程介绍离散数学各分支的根本概念、根本理论和根本方法、研究工具的根底课程。根本理论和根本方法、研究工具的根底课程。培养抽象思维能力、逻辑推理能力、归纳构造能培养抽象思维能力、逻辑推理能力、归纳构造能力力后续课程：数据结构、数据库系统、编译原理、后续课程：数据结构、数据库系统、编译原理、软件工程、计算机网络、人工智能、信息管理等软件工程、计算机网络、人工智能、信息管理等等。等。分四局部：数理逻辑、集合与关系、代数结构、分四局部：数理
2、逻辑、集合与关系、代数结构、图论图论第第1章章 命题逻辑命题逻辑数理逻辑是以数学的方法研究推理的形式结数理逻辑是以数学的方法研究推理的形式结构和规律的数学学科构和规律的数学学科曹雪芹是?红楼梦?的作者。=曹雪芹是小说家。小说家是文学家。数学方法：建立一套符号来描述和讨论问题，防止歧义性推理：就是研究前提和结论之间的关系和思维规律，亦即符号之间的关系第第1章章 命题逻辑命题逻辑第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类 1.3 等值演算等值演算 1.4 联结词全功能集联结词全功能集 1.5 对偶与范式对偶与范式 1.6 推理理论
3、推理理论*1.7 命题演算的自然推理形式系统命题演算的自然推理形式系统N 1.8 例题选解例题选解 习习 题题 一一第第1章章 命题逻辑命题逻辑1.1 命题符号化及联结词命题符号化及联结词 任何基于命题分析的逻辑称为命题逻辑。命题是研究思维规律的科学中的一项根本要素，它是一个判断的语言表达。命题:能唯一判断真假的陈述句。第第1章章 命题逻辑命题逻辑这种陈述句的判断只有两种可能，一种是正确的判断，一种是错误的判断。如果某个陈述句的判断为真与人们公认的客观事实相符，那么我们称其为一真命题，并说此命题的真值为真，否那么称为假命题，并说此命题的真值为假。第第1章章 命题逻辑命题逻辑【例1.1.1】下述
4、各句均为命题：14是偶数。2煤是白色的。3?几何原本?的作者是欧几里德。42190年人类将移居火星。5地球外也有生命存在。第第1章章 命题逻辑命题逻辑上述命题中1、3是真命题，2是假命题，其中的3可能有人说不出它的真假，但客观上能判断真假。4的结果目前谁也不知道，但到了时候那么真假可辨，即其真值是客观存在的，因而是命题。同样，5的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的开展，其真值是可以知道的，因而也是命题。第第1章章 命题逻辑命题逻辑【例1.1.2】以下语句不是命题：1你好吗？2好棒啊！3请勿吸烟。4x3。5我正在说谎。1、2、3均不是陈述句，因而不是命题。4是陈述句，
5、但它的真假取决于变量x的取值，例如取x为4时其值为真，取x为2时其值为假，即其真值不唯一，因此不是命题。5也是陈述句，但它是悖论，因而也不是命题。第第1章章 命题逻辑命题逻辑从上面讨论可以看出，判断一个语句是否是命题的关键是：(1)语句必须是陈述句。(2)陈述句必须具有唯一的真值。要注意两点：一个陈述句在客观上能判断真假，而不受人的知识范围的限制。一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。第第1章章 命题逻辑命题逻辑以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有“主语+谓语的形式，在数理逻辑中，我们将这种由简单句构成的
6、命题称为简单命题，或称为原子命题，用p、q、r、pi、qi、ri等符号表示亦可用其它小写的英文字母表示。如：p：4是偶数。q：煤是白的。r：?几何原本?的作者是欧几里德。第第1章章 命题逻辑命题逻辑【例1.1.3】以下命题不是简单命题：14是偶数且是2的倍数。2北京不是个小城市。3小王或小李考试得第一。4如果你努力，那么你能成功。5三角形是等边三角形，当且仅当三内角相等。第第1章章 命题逻辑命题逻辑上面的命题除3的真假需由具体情况客观判断外，余者的真值均为1。但是它们均不是简单命题，分别用了“且、“非、“或、“如果那么、“当且仅当等联结词。由命题和联结词构成的命题称为复合命题。构成复合命题的可
7、以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个根本的联结词。第第1章章 命题逻辑命题逻辑1.否认联结词设p为任一命题，复合命题“非pp的否认称为p的否认式，记作。为否认联结词。为真，当且仅当p为假。的真值亦可由表所示的称为“真值表的表格确定。由表可知：命题p为真，当且仅当为假。表1.1.1p0110第第1章章 命题逻辑命题逻辑【例1.1.4】(1)p：4是偶数。其真值为1。：4不是偶数。其真值为0。(2)q：这些都是学生。：这些不都是学生。第第1章章 命题逻辑命题逻辑注：否认联结词使用的原那么：将真命题变成假
8、命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的2，q的否认式就不能写成“这些都不是学生。事实上严格来讲，“不是不一定否认“是。如阿契贝难题：“本句是六字句与“本句不是六字句均是真命题。不过，一般地，自然语言中的“不、“无、“没有、“并非等词均可符号化为第第1章章 命题逻辑命题逻辑2.合取联结词“设p、q是任意两个命题，复合命题“p且qp与q称为p与q的合取式，记作：pq。“是合取联结词。pq为真，当且仅当p、q均为真。pq的真值表如表所示。表1.1.2p qpq000010100111第第1章章 命题逻辑命题逻辑【例1.1.5】(1)p：4是偶数。q：3是素数。
9、那么pq：4是偶数且3是素数。其真值为1。(2)r：煤是白的。那么pr：4是偶数且煤是白的。真值为0。第第1章章 命题逻辑命题逻辑3.析取联结词“设p、q是任意两个命题，复合命题“p或q称为p、q的析取式，记作：pq。“称为析取联结词。pq为假，当且仅当p、q同为假。表1.1.3p qpq000011101111第第1章章 命题逻辑命题逻辑【例1.1.6】(1)p：小王喜欢唱歌。q：小王喜欢跳舞。那么pq：小王喜欢唱歌或喜欢跳舞。(2)p：明天刮风。q：明天下雨。那么pq：明天刮风或者下雨。第第1章章 命题逻辑命题逻辑注“的逻辑关系是明确的。即p、q二命题中至少有一个为真那么析取式为真。因而，
10、自然语言中常用的联结词诸如：“或者或者、“可能可能等，都可以符号化为“。但日常语言中的“或是具有二义性的，用“或联结的命题有时是具有相容性的，如例中的二例，我们称之为可兼或。而有时又具有排斥性，称为不可兼或异或，如：1小李明天出差去上海或去广州。2刘昕这次考试可能是全班第一也可能是全班第二。第第1章章 命题逻辑命题逻辑4.蕴含联结词“设p、q是任意两个命题，复合命题“如果p，那么q称为p与q的蕴含式，记作：pq。P称为蕴含式的前件，q称为蕴含式的后件，称为蕴含联结词。pq为假，当且仅当p为真、q为假。表1.1.4p qp q001011100111第第1章章 命题逻辑命题逻辑【例1.1.7】(
11、1)p：天下雨了。q：路面湿了。那么pq：如果天下雨，那么路面湿。(2)r：三七二十一。那么pr：如果天下雨，那么三七二十一。第第1章章 命题逻辑命题逻辑注(1)逻辑中，前件p为假时，无论后件q是真是假，蕴含式pq的真值均为1。这与日常语言中的，特别是数学上常用的“真蕴含真不太一样。事实上并不矛盾，例如某人说：“如果张三能及格，那太阳从西边升起。说话者当然知道“张三能及格与“太阳从西边升起风马牛不相及，而一般人此时并没有说谎的必要，即这是真命题，它所要明确的是“张三能及格是假命题。第第1章章 命题逻辑命题逻辑2正如前面所说，数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结
12、词所联结的句子之间是有一定内在联系的，但在数理逻辑中，联结词所联结的命题可以毫无关系。如在日常语言中“如果那么所联结的句子之间表现的是一种因果关系，如例中的1。但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的，如例中的2。第第1章章 命题逻辑命题逻辑3pq的逻辑关系是：p是q的充分条件，q是p的必要条件。在日常语言中，特别是在数学语言中，q是p的必要条件还有许多不同的表达方式，如：“p仅当q仅当q，那么p、“只有q才p、“只要p就q、“除非q，否那么非p非p，除非q等，均可符号化成pq的形式。第第1章章 命题逻辑命题逻辑【例1.1.8】符号化以下命题：1只要天下雨，我就回家。2只
13、有天下雨，我才回家。3除非天下雨，否那么我不回家。4仅当天下雨，我才回家。解：设p：天下雨。q：我回家。那么1符号化为pq。2、3、4均符号化为qp或等价形式：第第1章章 命题逻辑命题逻辑5.等价联结词“设p、q是任意两个命题，复合命题“p当且仅当q称为p与q的等价式，记作：pq。“称为等价联结词。pq为真，当且仅当p、q真值相同。pq的真值表如表所示表1.1.5p qp q001010100111第第1章章 命题逻辑命题逻辑【例1.1.9】(1)p：2+2=4。q：5是素数。那么pq：2+2=4当且仅当5是素数。(2)p：A=B。q：二角是同位角。那么pq：A=B当且仅当二角是同位角。在1中
14、的p与q并无内在关系，但因二者均为真，所以pq的真值为1。在2中由于相等的两角不一定是同位角，所以真值为0。第第1章章 命题逻辑命题逻辑【例1.1.10】将以下自然语言形式化:1如果天不下雨并且不刮风，我就去书店。2小王边走边唱。3除非a能被2整除，否那么a不能被4整除。4此时，小纲要么在学习，要么在玩游戏。5如果天不下雨，我们去打篮球，除非班上有会。第第1章章 命题逻辑命题逻辑解1设p：今天天下雨，q：今天天刮风，r：我去书店。那么原命题符号化为：(2)设p：小王走路，q：小王唱歌。那么原命题符号化为：pq(3)设p：a能被2整除，q：a能被4整除。那么原命题符号化为：或第第1章章 命题逻辑
15、命题逻辑(4)设p：小刚在学习，q：小刚在玩游戏。那么原命题符号化为：或(5)设p：今天天下雨，q：我们去打篮球，r：今天班上有会。那么原命题符号化为：第第1章章 命题逻辑命题逻辑补充：补充：小明和小亮既是兄弟又是同学。PQ如果你和他不都是白痴，那么你俩都不会去干此傻事。无论你和他去不去，我去。第第1章章 命题逻辑命题逻辑1.2 命题公式及分类命题公式及分类 为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公式的演算推理规那么，以期由给定的公式推导出新的命题公式来。第第1章章 命题逻辑命题逻辑前面我们用p、q、r等符号表示确定的简单命题，通常此时称它们为命题常元。
16、而事实上，这些常元无论具体是怎样的简单命题，它们的真值均只可能是“1或“0。为了更广泛地应用命题演算，在研究时，我们只考虑命题的“真与“假，而不考虑它的具体涵义即只重“外延，不顾“内涵。譬如：当p是一个真命题时，p就是一个假命题，而不管此时p表示的是命题“三七二十一，还是命题“今天天下雨。这时的p实际上就是一个简单命题的抽象，就如同数学公式中的变量x一样，我们称其为命题变元。第第1章章 命题逻辑命题逻辑命题常元一个真值确定的命题命题变元一个真值尚未确定的命题，以p、q、r等表之。注意：命题变元不是命题，没有确定的真值，只有代以确定的命题，变成常元，才有真值第第1章章 命题逻辑命题逻辑命题公式由命题变元常元符、联结词和圆括号按一定逻辑关系联结起来的字符串。所谓按一定的逻辑关系，即字符串的构成要求合理，如p是个合理的构成，是命题，p不是合理的构成，就不是命题公式，同样pqr也不是合理的构成括号必须成对出现，因此也不是命题公式。合理的命题公式叫做合式公式亦称真值函数，记作：wffwff=Well-FormedFormulas。第第1章章 命题逻辑命题逻辑定义定义 合式公式的递归定义：合式公式
