离散 左孝凌 第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.1命题的基本概念在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。命题的概念包含了以下3个要素：⑴只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。⑵一个语句虽是陈述句,但不能判断真假不是命题。⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。

2、一个命题表达的判断结果称为命题的真值。命题的真值有“真”和“假”两种，分别用True、T、1(真)和False、F、0(假)来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值是惟一的。在命题逻辑中对命题不再细分，因而命题是数理逻辑中最基本的也是最小的研究单位。【例1.1】判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。解：⑴命题(F)，⑵命题(待定)，⑶不是命题(祈使句)，⑷命题(T)，⑸

3、命题(F)，⑹不是命题(疑问句),⑺命题(由上下文确定),⑻不是命题(悖论)。表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。如果命题变元表示原子命题时，该命题变元称为原子变元。在自然语言中，可以通过“如果…，那么…”，“

4、不但…，而且…”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。1.1.2命题联结词常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。1.否定联结词定义1.1.1设p为命题，则p的否定是一个复合命题，记作：¬p，读作“非p”或“p的否定”。定义为：若P为T，则¬p为F；若p为F，则¬p的真值为T。表1.1p¬p0110p和¬p的关系如表1.1所示，表1.1叫做否定联结词“¬”的真值表(下同)。联结词“¬”也可以看作逻辑运算，它是一元运算。【例1

5、.2】否定下列命题。p：王强是一名大学生。¬p：王强不是一名大学生。2.合取联结词定义1.1.2设p和q均为命题，则p和q的合取是一个复合命题，记作p∧q，读作“p与q”或“p合取q”。定义为：当且仅当p和q均为T时，p∧q的才为T。联结词“∧”的真值表如表1.2所示。联结词“∧”也可以看成逻辑运算，它是二元逻辑运算。表1.2pqp∧q000010100111【例1.3】设p：2008年将在北京举办奥运会。q：中国是世界四大文明古国之一。则p∧q：2008年将在北京举办奥运会并且中国是世界四大文明古国之一。3.析取联结词定义1.1.3设p和q

6、均为命题，则p和q的析取是一个复合命题，记作p∨q，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，p∨q才为F。联结词“∨”的真值表如表1.3所示。联结词“∨”也可以看成逻辑运算，它是二元逻辑运算。表1.3pqp∨q000011101111“∨”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。【例1.4】下列两个命题中的“或”，哪个是可兼或？哪个是不可兼或？⑴在电视上看这场杂技或在剧场里看这场杂技。(不可兼)⑵灯泡有故障或开关有故障。(可兼,“∨”是可兼或)4.条件联结词定义1.1.4设p和q

7、均为命题，其条件命题是个复合命题，记为：p→q。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，p→q才为F。p称为条件命题p→q的前件，q称为条件命题p→q的后件。联结词“→”真值表如表1.4所示。联结词“→”也可以看成逻辑运算，它是二元逻辑运算。表1.4pqp→q001011100111【例1.5】p：小王努力学习。q：小王学习成绩优秀。p→q：如果小王努力学习，那么他的学习成绩就优秀。联结词“→”与汉语中的“如果…，那么…”或“若…，则…”相似，但又是不相同的。5.双条件联结词定义1.1.5设p和q均为命题，其

8、复合命题p↔q称为双条件命题，读作：“p双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，p↔q为T。联结词“↔”的真值表如表1.5所示。联结词“