离散数学-第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(假)假命题【例1.1】判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。解：⑴命题(F)，⑵命题(待定)，⑶不是命题(祈使句)，⑷命题(T)，⑸命题(F)，⑹不是命题(疑问句),⑺命题(由上下文确定),⑻不是命题(悖论)。命题常量与命题变元表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。？命题变元是命题吗？不是命题变元代表任意的命题，其真值是不确定的。因而不是命题。原子命题与复合命题（将命题完整分类）原子命题:如果一个命题不能再分解成更简单的命题复合命题:如果一个命题不是原子命题原子变元：顾名思义，原子变元表示的是任意一个原子命题。思考：原子命题和复合命题之间有什么样的关系呢？在自然语言中，可以通过“如果…，那么…”，“不但…，而且…”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。1.1.2命题联结词常用的逻辑联结词有五种：否定、合取、析取、条件和双条件。1.否定联结词（否）设p为命题，则p的否定是一个复合命题.记作：¬p，读作“非p”或“p的否定”。定义为：若p为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若没有内在的联系，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.条件联结词（如果…那么…）设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”。定义为：当且仅当p和q的真值相同时，p↔q为T。联结词“↔”是二元逻辑运算。pqp↔q00011011双条件联结词表示的是一个充分必要关系，可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。本节学习目标：（1）理解并掌握命题的概念，学会判断一个语句是否为命题并确定其真值。（2）牢固掌握五类联结词的定义与其真值表。1.2命题公式与翻译把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。定义1.2.1按下列规则构成的符号串称为命题演算的合式公式。（基础）⑴单个命题变元和常元是合式公式。（归纳）⑵如果A是合式公式，那么¬A是合式公式。（归纳）⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。（界限）⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。命题公式一般的用大写的英文字母A，B，C，…表示。为方便起见，对命题公式约定如下：⑴最外层括号可以省略。⑵规定联结词的优先级由高到低依次为¬，∧，∨，→，↔。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。？命题公式是命题吗？一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。用命题公式表示复合命题，常将这个过程称为命题的符号化。（翻译）命题的符号化可按如下步骤进行：⑴找出原子命题。⑵用小写的英文字母或带下标的小写的英文字母表示原子命题。⑶用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。从例1.7中可以看出：（1）具有否定意义的命题一定不是原子命题（2）对于不可兼或的表示，可用¬(p↔q)本小节学习目标：（1）了解命题公式的概念，掌握五类连接词的优先级（2）掌握如何将一个复合命题符号化？1.3真值表和等价公式1.3.1命题公式的真值表定义1.3.1设pl，p2，…，pn是出现在公式A中的全部命题变元，给pl，p2，…，pn各指定一个真值，称为对公式A的一个赋值或解释。若赋值使A的真值为T，则称这个赋值为A的成真赋值，若赋值使A的真值为F，则称这个赋值为A的成假赋值。定义1.3.2在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。构造真值表的几点注意：[1]先找出公式中所含的所有命题变元[2]第1行：命题变元；排列：由小到大；字典顺序[3]前n列：赋值；排列：从00…0到11…1递增如果公式A有n个命题变元，那么A的真值表应该有多少行？【例1.8】构造命题公式¬p∨q的真值表，并求成真赋值和成假赋值。解：表1.6pq¬p¬p∨q001011100110表1.7pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001【例1.9】构造命题公式(p∧q)∨(¬p∧¬q)的真值表，并求成真赋值和成假赋值。解：命题公式(p∧q)∨(¬p∧¬q)的真值表如表1.7所示。00，11是成真赋值，01，10是成假赋值。Remark：1.如果公式A有n个命题变元，那么A的真值表应该有多少行？2.什么叫做两个真值表相等？取决于真值表的最后一列是否相同。1.3.2命题公式的等价定义1.3.3设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B等价的或逻辑相等的，记为AB命题公式等价有下面的三条性质：⑴自反性，AA⑵对称性，若AB，则BA⑶传递性，若AB，BC，则AC所谓两个命题公式等价即为两个公式的真值表相同，所以我们可以用真值表来验证两个命题公式是否等价.【例1.12】根据等价的定义，用真值表证明p→(q→p)¬p→(p→¬q)证明：构造p→(q→p)和p→(p→q)的真值表表1.10pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。1.双重否定律A¬¬A2.交换律A∨BB∨A，A∧BB∧A3.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)4.分配律A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)5.德摩根律¬(A∨B)¬A∧¬B¬(A∧B)¬A∨¬B6.幂等律A∧AA，A∨AA7.吸收律A∨(A∧B)A，A∧(A∨B)A8.零律A∨11，A∧009.同一律A∨0A，A∧1A10.排中律A∨¬A111.矛盾律A∧¬A012.条件等价式A→B¬A∨B13.双条件等价式A↔B(A→B)∧(B→A)14.假言易位式A→B¬B→¬A15.双条件否定等价式A↔B¬A↔¬B定义1.3.4（子公式）如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。例如，Aq→(p∨(p∧q))，Xp∧q，则X是A的子公式。定理1.3.1（等价置换）设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB返回章目录本小节学习目标：1.能够写出任一命题公式的真值表。2.能熟练地应用命题定律来证明两个命题公式的等价。1.4重言式定义1.4.1设A是任一命题公式。⑴若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。⑵若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。⑶若A不是矛盾式，则称命题公式A为可满足的。Remark：1.任何重言式都是可满足的。2.重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。3.亦可以用等价演算法判断公式的类型。定理1.4.1任何两个重言式的合取或析取都是重言式。任何两个矛盾式的合取或析取都是矛盾式。定理1.4.2一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。【例1.19】由排中律知p∨¬p为重言式，以((p∨q)∧r)去置换其中的p，得公式((p∨q)∧r)∨¬((p∨q)∧r)，这是重言式。定理1.4.3设A、B为两个命题公式，AB当且仅当A↔B是重言式。证明：设AB，下证A↔B是重言式。因为AB，所以A，B具有相同的真值，由双条件联结词的定义知A↔B为真，所以A↔B为重言式。设A↔B为重言式，下证AB给A，B的任何赋值，因为A↔B为重言式，故A，B的真值相同，由命题公式等价的定义知AB1.5范式1.5.1析取范式与合取范式定义1.5.1(基本和)由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。定义1.5.2(基本积)由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。定义1.5.3(合取范式)由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。定义1.5.4(析取范式)由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。任何命题公式都可以化成与其等价的析取范式或合取范式。步骤如下：⑴消去联结词“→”和“↔”⑵消去“¬”(双重否定律)内移“¬”(德摩根律)⑶利用分配律，结合律将公式归约为合取范式和析取范式。【例1.21】求命题公式(p∨q)↔p的合取范式和析取范式。解：⑴求合取范式(p∨q)↔p((p∨q)→p)∧(p→(p∨q))(消去↔)(¬(p∨q)∨p)∧(¬p∨(p∨q))(消去→)((¬p∧¬q)∨p)∧(¬p∨(p∨