《离散第二章 命题逻辑》由会员分享，可在线阅读，更多相关《离散第二章 命题逻辑（107页珍藏版）》请在金锄头文库上搜索。
1、1离散数学第二章第二章第二章第二章 命题逻辑命题逻辑命题逻辑命题逻辑2第2章 命题逻辑题逻辑2.1 命题逻辑基本概念2.2 命题逻辑等值演算2.3 范式2.4 推理3命题逻辑 基本概念一、命题一、命题一、命题一、命题定义：能判断真假而不是可真可假的陈述句，被称为命题。说明：命题的真值：作为命题所表达的判断只有两个结果： 正确和错误，此结果称为命题的真值。命题是正确的，称此命题的真值为真；命题是错误的 ，称此命题的真值为假。真值为真的命题称为真命题 ；真值为假的命题称为假命题。任何命题的真值都是唯一的。4命题逻辑 基本概念说明：其它类型的句子，如疑问句、祈使句、感叹 句均没有真假意义，因此，均不
2、是命题。在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别用T和F来表达。 命题是具有唯一真值的陈述 句。5命题逻辑 基本概念如何判断命题？1)首先判断其是否为陈述句2)其次判断其是否有唯一真值例1： 判断下列句子是否为命题，真值如何？（1）10是整数。（2）北京是我们祖国的首都。真命题 真命题 （3）雪是黑的。 （4）x大于y。（5）向右看齐！（6）你吃饭了吗？ 疑问句 非命题 祈使句 非命题 真值不唯一 非命题 假命题6命题逻辑 基本概念例1： 判断下列句子是否为命题，真值如何？（7）本命题是假的。（8）我正在说谎。悖论 非命题 悖论 非命题 （9）2006年元旦是晴天。
3、是命题 真假未定“他在说谎说谎 。”是命题还题还 是 悖论论？7命题与联结词三、原子命题（简单命题）三、原子命题（简单命题）三、原子命题（简单命题）三、原子命题（简单命题）不能被分解为更简单的命题的命题，称为原子命题。四、复合命题四、复合命题四、复合命题四、复合命题由若干个原子命题用命题联结词联结而成的命题称为复合命题。二、命题符号化二、命题符号化二、命题符号化二、命题符号化用小写字母 p，q，r，来表示命题。例2:p:10是整数。 q：北京是我们祖国的首都。 r:雪是黑的。 8命题与联结词例3：判断下列命题是否为复合命题，并将下列命题符号 化。 （1）5能被2整除。（2）2是素数当且仅当三角
4、形有三条边。原子命题 复合命题 （3）4是2的倍数或是3的倍数。复合命题（4）李明与王华是同学。原子命题（5）蓝色和黄色可以调配成绿色。原子命题（6）3不是偶数。复合命题（7）林芳学过英语或日语。复合命题课本24页例2.29命题与联结词命题联结词命题联结词命题联结词命题联结词 说明：否定 符号： pp0 11 0真值表：定义2.1：设p为命题，复合命题“非p”（或“p的否定”）称为p的否 定式，记作 p ，符号 称为否定联结词。规定 p为真当且仅当为 假。1)p是一元联结词 10命题与联结词真值表：合取 符号 定义2.2：设p，q为两个命题，复合命题“p并且q”（或 p与q）称为p 与q的合取
5、式，记作p q，符号 称为合取联结词。并规定p q为真当 且仅当p与q同时为真时为真。注意 ：P Q P Q0 0 00 1 01 0 01 1 1自然语言中的“既，又”，“不但，而且”，“虽然 ，但是”，“一面，一面”等联结词 可符号化为 。但不要见到“与”、“和”就符号化为合取11命题与联结词例4：将下列命题符号化。（1）吴颖既用功又聪明。（2）吴颖不仅用功而且聪明。（3）吴颖虽然聪明，但不用功。（4）张辉与王丽都是三好学生。（5）张辉与王丽是同学。p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学生。t:张辉与王丽是同学。p q p q r s p q t注意：若“和”、“
6、与”连接的是主语成分，则该陈述句为简单命 题。12命题与联结词真值表：析取 符号 定义2.3：设p，q为两命题，复合命题“p或q” 称为p与q的析取式，记 作p q ，符号 称为析取联结词。并规定p q为假当且仅当p与q同时为假。P Q P Q0 0 00 1 11 0 11 1 1注意：自然语言中的“或”具有二义性，用它做联结的命题有时具有 相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或。13命题与联结词例5：将下列命题符号化。（1）张明正在睡觉或游泳。（2）李强是位排球队员或是足球队员。（3）他昨晚做了二十或三十道题。（4）张静只能挑选202或203房间。或表示约数，不能用析取
7、p:张明正在睡觉。 q:张明正在游泳 p q 排斥或p:李强是位排球队员。 q:李强是位足球队员 p q 相容或p:张静挑选202房间。 q:张静挑选203房间 （ p q） （p q）排斥或14命题与联结词蕴含 符号： 定义2.4：设p，q为两命题，复合命题“如果p，则q” 称为p与q的蕴含式 ，记作p q ，并称p是蕴含式的前件，q为蕴含式的后件，符号 称为 蕴含联结词。并规定p q为假当且仅当p为真q为假。真值表：P Q P Q0 0 10 1 11 0 01 1 1p q的逻辑关系为q是p的必要条 件。15命题与联结词注意：1)在自然语言和数学中，有很多方式来描述蕴含，例如：“只 要p
8、，就q”，“因为p，所以q”，“p仅当q”，“只有q才p”，“除 非q才p”，“除非q，否则非p”，q是p的必要条件，因而所用 的联结词应符号化为 ，各种描述方式都应该符号化为p q 。2)在自然语言中，“如果p，则q”中的前件p与后件q往往具有某 种内在联系，而在数理逻辑中，p与q可以无任何内在联系。3)在数学或其它自然科学中，“如果p，则q”往往表达的是前件 p为真，后件q也为真的推理。但在数理逻辑中，作为一种规 定，当p为假时，无论q是真还是假，p q均为真，也就是说 ，只有p为真q为假这一种情况，使得复合命题p q为假。16命题与联结词例6：将下列命题符号化。（1）只要不下雨，我就骑自
9、行车上班。（2）只有不下雨，我才骑自行车上班。（3）若2+2=4，则太阳从东方升起。p:天下雨。 q:我骑自行车上班。 s:2+2=4。 t:太阳从东方升起r:太阳从西方升起。（4）若2+2 4，则太阳从东方升起。（5）若2+2=4，则太阳从西方升起。 （6）若2+2 4，则太阳从西方升起。p q q ps ts rs rs t17命题与联结词等价 符号： 定义2.5：设p，q为两命题，复合命题“p当且仅当q” 称为p与q的等价式 ，记作p q ，符号 称为等价联结词。并规定p q为真当且仅当p与q同时为真或同时为假。真值表：P Q P Q0 0 10 1 01 0 01 1 1p q的逻辑关
10、系为q与p的互为充分 必要条件。18命题与联结词例7：将下列命题符号化。（1）2+2=4当且仅当3是奇 数。（2）2+2=4当且仅当3不是奇数。p: 2+2=4。 q: 3是奇数。（3）2+2 4当且仅当3是奇数。 （4）2+2 4当且仅当3不是奇 数。p qp qp qp q19命题与联结词说说说说明：明：明：明： 1)由联结词集 中的一个联结词联结一个或两个 原子命题组成的复合命题是简单的复合命题，可以称他们为基本 的复合命题。2)多次使用联结词集中的联结词，可以组成更为复杂的复合命 题。求复杂复合命题的真值时，还要规定联结词的先后顺 序。将括号也算在内，这个顺序为 ， 对同一优先级的联结
11、词，先出现者先运算。3)我们只关心复合命题中命题之间的真值关系，而不关心命题 的内容。20命题与联结词例8：求下列复合命题的真值。（1） p q r 0 0 0 00 10 0 1 001 0 1 0 1000 1 1 1011 0 0 0101 0 1 01 1 1 1 0 00 01 1 100 121命题与联结词例9：求下列复合命题的真值。（2） p q r 0 0 0 01 10 0 1 111 0 1 0 1110 1 1 1001 0 0 0111 0 1 11 1 1 1 0 11 11 1 110 022命题公式及分类一、一、一、一、命题常项命题常项命题常项命题常项定义：简单命
12、题被称为命题常项。二、命题变项二、命题变项二、命题变项二、命题变项定义：真值可以变化的陈述句为命题变项或命题变元。可 以用p，q，r，表示命题变项。注意：命题变项不是命题。23命题公式（合式公式）命题公式（合式公式）命题公式（合式公式）命题公式（合式公式）定义2.6：（1）单个命题常项或变项p, q, r , , pi, qi, ri, ,0, 1是合式公式;（2）若A是合式公式，则（ A）也是合式公 式。（4）只有有限次地应用（1）（3）形成的符号串才是合式公式。合式公式也称为命题公式，并简称为公式。命题公式及分类（3）若A, B是合式公式，则（A B），（A B）， （A B），（A B）
13、也是合式公式。24例：根据上述定义，判定下面的符号串是不是命题公 式。(pq)p (q r)pqrpq rp r命题公式及分类25公式层次公式层次公式层次公式层次定义2.7：（1）若公式A是单个的命题变项，则称A为0层公式。（2）称A是n+1（n 0）层公式是指下面情况之一：（a）A= B，B是n层公式；命题公式及分类（b）A=B C, AB C, A=B C, A=B C中的一种 ， 其中B，C分别为i层和j层公式，并且n = max（i, j）；26例：求下列命题公式的层次。0层3层4层命题公式及分类2层4层2层27赋值（解释）赋值（解释）赋值（解释）赋值（解释）定义2.8：设A为一命题公
14、式， 是出现在公式A中 的所有命题变项，给 各指定一个真值 ，称为对A的一个赋值或解释，若指定的一 组值使A的真值为1，则称这组值为A的成真 赋值，若使A的真值为0，则称这组值为A的 成假赋值。注意：含n 个命题变项的公式含有 个不同的赋值。命题公式及分类28真值表真值表真值表真值表 定义2.9：将命题公式A在所有赋值下取值情况列成表，称作 A的真值表。构造真值表步骤构造真值表步骤构造真值表步骤构造真值表步骤（1）找出公式中所含的全体命题变项 （若无下脚标就 按字典顺序排列），列出 个赋值。赋值从0000开始，然后按二进 制加法依次写出各赋值，直到1111为止。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各个层次的真值，知道最后计算出公 式的真值。命题公式及分类29命题公式及其赋值例10：求下列公式的真值表。（1） p q r 0 0 0 11 10 0 1 101 0 1 0 1110 1 1 1011 0 0 0111 0 1 00 0 1 1 00111 1 100 01010111130例10：求下列公式的真值表。（2）
