离散数学201023

《离散数学201023》由会员分享，可在线阅读，更多相关《离散数学201023（41页珍藏版）》请在金锄头文库上搜索。

1、*第三章 命题逻辑命题逻辑也称命题演算，或语句逻辑。研究内容：（1）研究以命题为基本单位构成的前提和结论之间的可推导关系（2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？1*命题逻辑的特征：在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止， 不再分析下去。不把一个简单命题再分 析为非命题的集合，不把谓词和量词等 非命题成份分析出来。 2*第三章 命题逻辑集合的表示方法2命题公式3命题范式4命题基本概念1命题联结词23*3.1 本章学习要求重点掌握一般掌握了解11、五种基本 联结词 2、24个基本 的等价公式 3 掌握求命题 范式的方法3联结词完

2、备集的理解和学习2公式的代入规则和替换规则4*3.2.1 命题定义3.2.1 具有确切真值的陈述句称为命题, 该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。3.2 命题与命题联结词5*（1）太阳是圆的； （2）成都是一个旅游城市； （3）北京是中国的首都； （4）这个语句是假的； （5）1110； （6）+y； （7）我喜欢踢足球； （8）3能被2整除； （9）地球外的星球上也有人； （10）中国是世界上人口最多的国家； （11）今天是晴天；例3.2.1 TTT/F非命题T/F F T/F T TT非命题6*例3.2.1（续） （12）

3、把门关上； （13）滚出去！ （14）你要出去吗？ （15）今天天气真好啊！非命题非命题非命题 非命题注意：一切没有判断内容的句子都不能作为命题，如命令 句、感叹句、疑问句、祈使句、二义性的陈述句等。 7*命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。结论：在数理逻辑中像字母“x”、“y”、“z”等字母总是 表示变量。约定：8*下列语句是否是命题？并判断其真值结果？（1）四川不是一个国家；（2）3既是素数又是奇数；（3）张谦是大学生或是运动员；（4）如果周末天气晴朗，则我们将到郊外旅游；（5）2+2=4当且仅当雪是白

4、的。例3.2.29*一般来说，命题可分两种类型：1) 原子命题(简单命题)：不能再分解为更为简单命题的命题。2) 复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或 者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类10*1) 今天天气很冷。2) 今天天气很冷并且刮风。3) 今天天气很冷并且刮风，但室内暖和。例3.2.3通常用大写的带或不带下标的英文字母、.P、Q、R、. Ai、Bi 、Ci、.Pi、Qi、Ri、.等表示命题11*3.2.2 命题联结词设命题P,Q表示任意两个命题,则最常见的命题联结词有：联接 词

5、记 号复合命 题读法 记法真值结 果3.析取 P或者QP与Q的析取PQPQ=1P=1或Q=12.合取 P并且QP与Q的合取PQPQ=1P=1且Q=11.否定 非PP的否定PP=1 P=04.蕴涵若P,则QP蕴涵QPQPQ=0 P=1,Q=05.等价 P当且仅当QP等价于QPQPQ=1P=1,Q=1 或P=0,Q=0 例如：命题P：2是素数；Q：北京是中国的首都12*总结P QPPQPQPQPQ 0 010011 0 110110 1 000100 1 10111113*说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结 ；2、联结词是两个句子真值之间的联结，而非句子的具

6、体含义的联结，两个句子 之间可以无任何地内在联系；14*符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。例3.2.415*例3.2.4 解 （1）设：四川是人口最多的省份。则命题（1）可表示为。（2）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；R：王超是一个体育成绩好的学生。则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了：教室的灯不亮可能是停电了则命题（3）可表示为。 16*

7、（4）设：周末天气晴朗；：学院将组织我们到石像湖春游。则命题（4）可表示为。（5）设：两个三角形全等；：三角形的三条边全部相等。 则命题（5）可表示为。例3.2.4 解(续)17*设命题P：明天上午七点下雨； Q：明天上午七点下雪；R：我将去学校。符号化下述语句：1) 如果明天上午七点不是雨夹雪，则我将去学校2) 如果明天上午七点不下雨并且不下雪，则我将去 学校3) 如果明天上午七点下雨或下雪，则我将不去学校4) 明天上午我将雨雪无阻一定去学校可符号化为：(PQR)(PQR)(PQR)(PQR)。或 (PQ)(PQ)(PQ)(PQ)R。例3.2.5可符号化为：(PQ)R。可符号化为:(PQ)R

8、。可符号化为:(PQ)R。18*说明3、联结词与自然语言之间的对应并非一一对应；联结词联结词自然语语言既又、不仅仅而且、虽虽然但 是、并且、和、与，等等；如P则则Q、只要P就Q、P仅仅当Q、只有 Q才P、除非Q否则则P，等等等价、当且仅仅当、充分必要、等等；相容（可兼）的或19*例设P:雪是白色的;Q:2+2=4。将下列命题符号化： （1）因为雪是白色的，所以2+2=4； PQ （2）如果2+2=4，则雪是白色的； QP （3）只有雪是白色的，才有2+2=4； QP （4）只有2+2=4，雪才是白色的； PQ （5）只要雪不是白色的，就有2+2=4； PQ （6）除非雪是白色的，否则2+24；

9、 P Q或QP （7）雪是白色的当且仅当2+2=4； P Q20*3.3 命题公式、解释与真值表定义3.3.1 一个特定的命题是一个常值命题，它不是 具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变 量命题，常称它为命题变量(或命题变元)，该命题变 量无具体的真值，它的变域是集合T，F(或0，1)注意(1)复合命题为命题变元的“函数”,其函数值仍为“真 “或“假”值。(2)真值函数或命题公式，没有确切真值。真值函数21*3.3.1 命题公式 定义3.3.2 (命题公式)命题演算的合式公式命题演算的合式公式WffWff（ Well formed

10、formula Well formed formula ）, ,又称为命题公式又称为命题公式, ,可可 按如下规则生成按如下规则生成: :1. 命题变元本身是一个公式；2. 如G是公式，则(G)也是公式；3. 如G，H是公式，则(GH)、(GH)、(GH)、 (GH)也是公式；4. 仅由有限步使用规则1-3后产生的结果。该公式 常用符号G、H、等表示。22*符号串：(P(QR)(Q(SR)； (PQ)； (P(PQ)； (PQ)(RQ)(PR)。 等都是命题公式。例3.3.1例3.3.2符号串：(PQ)Q)； (PQ；(PQ(R； PQ。等都不是合法的命题公式。23*为了不使句子产生混淆，作如

11、下约定，命题联结词之优先级如下：1. 否定合取析取蕴涵等价2. 同级的联结词，按其出现的先后次序(从左 到右)3. 若运算要求与优先次序不一致时，可使用 括号；同级符号相邻时，也可使用括号。 括号中的运算为最优先级。约 定24*例3.3.3 试用符号形式写出下列命题：（1）虽然今天天气晴朗，老陈还是不来；（2）除非你陪伴我或代我叫车子，否则我将不出去；（3）停机的原因在于语法错误或者程序错误；（4）若a和b是偶数，则a+b是偶数；（5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。 25*例3.3.3 解 （1）P：今天天气晴朗,Q：老陈要来,则有：PQ；（2）P：你陪伴我； Q：你

12、代我叫车子；R：我出去 。则有：RPQ或PQR；（3）P：停机的原因在于语法错误，Q：停机的原因 在于程序错误，则有：PQ；（4）P：a是偶数；Q：b是偶数，R：a+b是偶数，则 有：PQR；（5）P：我们要做到身体好,Q：我们要做到学习好, R ：我们要做到工作好，S：我们要为祖国四化建设而奋 斗，则有：PQR S。 26*公式(P(QR)(Q(SR)可表示如下：(P(QR)(Q(SR)P(QR) Q(SR)P QR Q SRQ R S RS例3.3.427*定义3.3.3 设P1、P2、Pn是出现在公式G中的所有 命题变元，指定P1、P2、Pn一组真值，则这组真 值称为G的一个解释,常记为

13、。一般来说，若有个命题变元，则应有2n个不同的解释。如果公式G在解释下是真的，则称满足G；如 果G在解释下是假的，则称弄假G。定义3.3.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。3.3.2 公式的解释与真值表28*例3.3.5求下面公式的真值表：(P(PQ)R)Q其中，、是的所有命题变元。P Q R PPQ(PQ)R P(PQ)R)G0 0 0 10 0 11 0 0 1 10 0 11 0 1 0 1 1 0 1 1 0 1 1 1 1 1 11 1 0 0 0 1 0 001 0 1 0 1 1 11 1 1 0 0 0 0 01 1 1 1 0 0 0 0129

14、*例3.3.5（续） P Q R(P(PQ)R)Q 0 0 010 0 11 0 1 01 0 1 11 1 0 00 1 0 11 1 1 01 1 1 1 1进一步化简为：30*例3.3.6P Q() ()() ( Q) 0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表：1 ()；2()；3 () (Q)。31*从这三个真值表可以看到一个非常有趣的 事实： 公式G1对所有可能的解释具有“真”值 公式G3对所有可能的解释均具有“假”值 公式G2则具有“真”和“假”值结论32*定义3.3.51. 公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。2. 公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。3. 公式G称为可满足的，如果它不是永假的。33*从上述定义可知三种特殊公式之间的关系 ：1) 永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。2) 永真式一定是可满足式,可满足式不一定是永真式3) 可满足式的否定不一定为不可满足式(即为矛盾式)结论34*例3.3.7 写出下列公式的真值表，并验证其公式是重 言式、矛盾式、可满足公式。（1）G1=()()；（2）G2=(Q)(Q)(Q)；（3）G3=(PQ)Q。