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

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

1、第1章命题逻辑1.1命题及联结词1.2命题公式与翻译1.3真值表和等价公式1.4重言式1.5范式1.6全功能联结词集1.7对偶式与蕴含式1.8命题逻辑的推理理论返回总目录1.1命题及联结词1.1.1命题的基本概念命题的定义在数理逻辑中把能判断真假的陈述句称为命题。命题的表示一般用小写英文字母或带下标的小写英文字母表示。Remark：⑴只有陈述句才有可能成为命题⑵能判断真假的陈述句⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。命题的真值：一个命题表达的判断结果称为命题的真值。任何命题的真值是惟一的。真值为“真”TrueT1(真)真命题真值为“假”FalseF0

2、(假)假命题【例1.1】判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。解：⑴命题(F)，⑵命题(待定)，⑶不是命题(祈使句)，⑷命题(T)，⑸命题(F)，⑹不是命题(疑问句),⑺命题(由上下文确定),⑻不是命题(悖论)。命题常量与命题变元表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。？命题变元是命题吗？不是命题变元代表任意的命题，其真值是不确

3、定的。因而不是命题。原子命题与复合命题（将命题完整分类）原子命题:如果一个命题不能再分解成更简单的命题复合命题:如果一个命题不是原子命题原子变元：顾名思义，原子变元表示的是任意一个原子命题。思考：原子命题和复合命题之间有什么样的关系呢？在自然语言中，可以通过“如果…，那么…”，“不但…，而且…”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。1.1.2命题联结词常用的逻辑联结词有五种：否定、合取、析取、条件和双条件。1.否定联结词（否）设p为命题，则p的否定是一个复合命题.记作：¬p，读作“非p”或“p的否定”。定义为：若p

4、为T，则¬p为F；若p为F，则¬p的真值为T。表1.1p¬p0110【例1.2】否定下列命题。p：中国的每一个城市都是沿海城市。¬p：??中国的每一个城市都不是沿海城市。中国的每一个城市不都是沿海城市。2.合取联结词（与）设p和q均为命题，则p和q的合取是一个复合命题记作p∧q，读作“p与q”或“p合取q”。定义：当且仅当p和q均为T时，p∧q的才为T。联结词“∧”是二元逻辑运算。pqp∧q000010100111【例1.3】设p：2008年在北京举办奥运会。q：中国是世界四大文明古国之一。则p∧q：2008年在北京举办奥运会并且中国是世界四大文明古国之一。补充说明：在自然语言中：p和q

5、若没有内在的联系，p∧q所表示的命题没有实际意义在命题逻辑中：只要p和q的真值能确定，则p∧q就可以成为一个新命题，不管这新命题在自然语言中是否有意义。3.析取联结词（或者）设p和q均为命题，则p和q的析取是一个复合命题，记作p∨q，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，p∨q才为F。联结词“∨”是二元逻辑运算。pqp∨q000011101111“∨”与汉语中的“或”相似，但又不相同。【例1.4】下列两个命题中的“或”，哪个是可兼或？哪个是不可兼或？⑴在电视上看这场杂技或在剧场里看这场杂技。(不可兼)⑵灯泡有故障或开关有故障。(可兼,“∨”是可兼或)4.条件联结

6、词（如果…那么…）设p和q均为命题，其条件命题是个复合命题。记为：p→q。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，p→q才为F。pqp→q00011011p称为条件命题p→q的前件，q称为条件命题p→q的后件。联结词“→”是二元逻辑运算。【例1.5】p：小王努力学习。q：小王学习成绩优秀。p→q：如果小王努力学习，那么他的学习成绩就优秀。联结词“→”与汉语中的“如果…，那么…”或“若…，则…”相似，但又是不相同的。(区别有2条)5.双条件联结词(当且仅当)设p和q均为命题，其复合命题p↔q称为双条件命题。读作：“p双条件q”或者“p当且仅当q”。定义为：

7、当且仅当p和q的真值相同时，p↔q为T。联结词“↔”是二元逻辑运算。pqp↔q00011011双条件联结词表示的是一个充分必要关系，可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。本节学习目标：（1）理解并掌握命题的概念，学会判断一个语句是否为命题并确定其真值。（2）牢固掌握五类联结词的定义与其真值表。1.2命题公式与翻译把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。定