离散数学 第二讲.pdf

2006 2 23电子工程学院 离散数学1 1 1 3 命题符号化命题符号化 1 1 2介绍的介绍的5种常用的联结词也可称为真值联结词 或逻辑联结词 在命题逻辑中 利用这些联结词可将 各种各样的复合命题符号化 基本的步骤如下 种常用的联结词也可称为真值联结词 或逻辑联结词 在命题逻辑中 利用这些联结词可将 各种各样的复合命题符号化 基本的步骤如下 找出各简单命题 将它们符号化 找出各简单命题 将它们符号化 使用合适的联结词 将简单命题逐个联结起来 组 成复合命题的符号化形式 使用合适的联结词 将简单命题逐个联结起来 组 成复合命题的符号化形式 1 1 命题符号化及联结词命题符号化及联结词 2006 2 23电子工程学院 离散数学2 例例1 12 将下列命题符号化 将下列命题符号化 1 小王是游泳冠军或百米赛跑冠军 小王是游泳冠军或百米赛跑冠军 2 小王现在在宿舍或在图书馆里 小王现在在宿舍或在图书馆里 3 选小王或小李中的一人做班长 解 根据以上步骤 上述命题可符号化为 选小王或小李中的一人做班长 解 根据以上步骤 上述命题可符号化为 1 p q 其中 其中 p 小王是游泳冠军 小王是游泳冠军 q 小王是百米赛跑 冠军 小王是百米赛跑 冠军 2 p q 其中 其中 p 小王在宿舍 小王在宿舍 q 小王在图书馆 这里 的 小王在图书馆 这里 的 或或 是排斥或 但因是排斥或 但因p与与q不能同时发生 所以仍然符号化为不能同时发生 所以仍然符号化为p q 3 p q q p 其中 其中 p 选小王做班长 选小王做班长 q 选小李 做班长 这里的 选小李 做班长 这里的 或或 是排斥或 因是排斥或 因p与与q可能同时发生 所以须 符号化为 可能同时发生 所以须 符号化为 p q q p 1 1 命题符号化及联结词命题符号化及联结词 2006 2 23电子工程学院 离散数学3 例例1 13 将下列命题符号化 将下列命题符号化 1 如果我上街 我就去书店看看 除非我很累 如果我上街 我就去书店看看 除非我很累 2 小王是电子工程学院的学生 他生于 小王是电子工程学院的学生 他生于1983年或年或1984年 他 是三好学生 解 上述命题可符号化为 年 他 是三好学生 解 上述命题可符号化为 1 r p q 其中 其中 p 我上街 我上街 q 我去书店看看 我去书店看看 r 我很累 该命题也可符号化为 我很累 该命题也可符号化为 p r q或或p r q 2 p q r s 其中 其中 p 小王是电子工程学院的学生 小王是电子工程学院的学生 q 他生于 他生于1983年 年 r 他生于 他生于1984年 年 s 他是三好生 他是三好生 1 1 命题符号化及联结词命题符号化及联结词 2006 2 23电子工程学院 离散数学4 5个联结词的优先级顺序为 个联结词的优先级顺序为 例例 我们写符号串 我们写符号串 p q r q s r 即为如下公式 即为如下公式 p q r q s r 1 1 命题符号化及联结词1 1 命题符号化及联结词 2006 2 23电子工程学院 离散数学5 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 1 2 1 命题公式 命题公式是由命题常项 命题变项 联结词 括号 等组成的符号串 但并不是由这些符号任意组成的符 号串都是命题公式 下面给出命题公式的严格定义 命题公式 命题公式是由命题常项 命题变项 联结词 括号 等组成的符号串 但并不是由这些符号任意组成的符 号串都是命题公式 下面给出命题公式的严格定义 定义定义1 6 1 单个命题常项或变项 单个命题常项或变项p q r pi qi ri 0 1是合式公式 是合式公式 2 若 若A是合式公式 则 是合式公式 则 A也是合式公式 也是合式公式 3 若 若A B是合式公式 则是合式公式 则A B A B A B A B也是合式公式 也是合式公式 4 只有有限次地应用 只有有限次地应用 1 3 组成的符号串才 是合式公式 我们将合式公式称为命题公式 或简称为公式 组成的符号串才 是合式公式 我们将合式公式称为命题公式 或简称为公式 2006 2 23电子工程学院 离散数学6 注意 注意 公式公式 p p q 等的括号可以省略 写成 等的括号可以省略 写成 p p q 整个公式的最外层括号可以省略 整个公式的最外层括号可以省略 p q r是公式 但是公式 但pq r不是公式 不是公式 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 2006 2 23电子工程学院 离散数学7 定义定义1 7 1 设 设A为单个命题 常项或变项 为单个命题 常项或变项 p q r pi qi ri 0 1 则称 则称A为为0层公式 层公式 2 称 称A是是n 1 n 0 层公式 若 层公式 若A符合下列情况之一 符合下列情况之一 A B B是是n层公式 层公式 A B C 其中 其中B C分别为分别为i层和层和j层公式 且层公式 且n max i j A B C 其中 其中B C 的层次同 的层次同 A B C 其中 其中B C 的层次同 的层次同 A B C 其中 其中B C 的层次同 的层次同 3 若 若A的最高层为的最高层为k 则 则A是是k层公式 层公式 例例1 2 2 p q p q r p q r s分别为分别为2 2 4 层命题公式 层命题公式 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 2006 2 23电子工程学院 离散数学8 1 2 2 解释 赋值 公式 解释 赋值 公式 p q r 若若p 电子院学生 电子院学生 q 2004级本科生 当级本科生 当r 学 习离散数学 学 习离散数学 p q r为真 当为真 当r 学习复变函数 学习复变函数 p q r为假 为假 定义定义1 8 设设A为命题公式 为命题公式 p1 pn是出现在是出现在A中的所 有命题变项 给 中的所 有命题变项 给p1 pn指定一组真值 称为对指定一组真值 称为对A的 一个赋值或解释 若指定的一组值使 的 一个赋值或解释 若指定的一组值使A的值为真 则 称这组值为 的值为真 则 称这组值为A的成真赋值 若指定的一组值使的成真赋值 若指定的一组值使A的值 为假 则称这组值为 的值 为假 则称这组值为A的成假赋值 的成假赋值 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 2006 2 23电子工程学院 离散数学9 定义定义 含含n n 1 个命题变项的命题公式 共有 个命题变项的命题公式 共有2n组 赋值 将命题公式 组 赋值 将命题公式A在所有赋值之下取值的情况列成 表 称为 在所有赋值之下取值的情况列成 表 称为A的真值表 构造真值表的步骤 的真值表 构造真值表的步骤 列出每个命题变项的所有可能的取值 按字典顺 序 列出每个命题变项的所有可能的取值 按字典顺 序 按命题公式的层次从低到高写出各个层次 按命题公式的层次从低到高写出各个层次 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 2006 2 23电子工程学院 离散数学10 例例1 7 1 求命题公式求命题公式p q r 的真值表 解 的真值表 解 注意 注意 p q r 在某些赋值下为真 在某些赋值下为假 在某些赋值下为真 在某些赋值下为假 1 1 0 0 1 1 0 0 q 1 0 1 0 1 0 1 0 r 1101 1111 0001 1111 0100 0110 0000 0110 p q r q r rp 2006 2 23电子工程学院 离散数学11 例例1 7 2 求命题公式求命题公式 p p q q 的真值表的真值表 解 解 注意 注意 p p q q 在各种赋值下均为真 在各种赋值下均为真 1 0 1 0 q 1111 1001 1010 1010 p p q qp p q p qp 2006 2 23电子工程学院 离散数学12 例例1 7 3 求命题公式 求命题公式 p q q 的真值表的真值表 解 解 注意 注意 p q q 在各种赋值下均为假 在各种赋值下均为假 00111 01001 00110 00100 p q q p q p qqp 2006 2 23电子工程学院 离散数学13 定义定义1 9 设设A为一个命题公式 为一个命题公式 1 若 若A在它的各种赋值下均为真 则称在它的各种赋值下均为真 则称A为重言式 或永真式 为重言式 或永真式 2 若 若A在它的各种赋值下均为假 则称在它的各种赋值下均为假 则称A为矛盾式 或永假式 为矛盾式 或永假式 3 若 若A至少存在一组赋值是成真赋值 则称至少存在一组赋值是成真赋值 则称A为可 满足式 显然 例 为可 满足式 显然 例1 7 2 真值表最后一列全为 真值表最后一列全为1 为永真 式 例 为永真 式 例1 7 3 真值表最后一列全为 真值表最后一列全为0 为永假式 例 为永假式 例 1 7 1 真值表最后一列即有 真值表最后一列即有0又有又有1 为可满足式 为可满足式 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 2006 2 23电子工程学院 离散数学14 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 1 3 等值演算等值演算 1 3 1 公式的等价 我们注意到这样一个 事实 公式的等价 我们注意到这样一个 事实 2个命题的所有真值个命题的所有真值 n个命题变量只能生成个命题变量只能生成 22n个真值不同的命题公 式 个真值不同的命题公 式 0或或111 0或或101 0或或110 0或或100 Aqp 2006 2 23电子工程学院 离散数学15 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 11011 00001 11110 11100 p q p q pqp 结论 结论 p q与与p q 应该等值 应该等值 2006 2 23电子工程学院 离散数学16 定义定义1 10 设设A B为两个命题公式 若等价式为两个命题公式 若等价式A B 是永真式 则称是永真式 则称A与与B等值 记为等值 记为A B 注意 注意 不是联结词 它只是不是联结词 它只是A与与B等值时的记号 等值时的记号 等值关系具有自反性 对称性和传递性 等值关系具有自反性 对称性和传递性 A与与B是否等值应判断是否等值应判断A B是否为永真式 是否为永真式 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 2006 2 23电子工程学院 离散数学17 1 p q 与 与 p q 解 则 解 则 p q 与 与 p q不等值不等值 0010011 1011001 1010110 1101100 p q p q p q q pqp 例例1 8 判断下列命题公式是否等值 判断下列命题公式是否等值 2006 2 23电子工程学院 离散数学18 解 则 解 则 p q p q 其实这正是 其实这正是德德 摩根律摩根律 0011001 0010110 1101100 p q p q p q q pqp 0010011 2 p q 与 与 p q 2006 2 23电子工程学院 离散数学19 1 A A 双重否定律 双重否定律 2 A A A 等幂律 等幂律 3 A A A 等幂律 等幂律 4 A B B A 交换律 交换律 5 A B A B 交换律 交换律 6 A B C A B C 结合律 结合律 7 A B C A B C 结合律 结合律 8 A B C A B A C 分配律 分配律 9 A B C A B A C 分配律 分配律 基本等值式 基本等值式 2006 2 23电子工程学院 离散数学20 证明 证明 证明 证明 9 9 A A B B C C A A B B A A C C 1 0 1 0 0 0 0 0 A C 0000000 0001100 0001010 0001110 1111011 1011101 0000001 A B A C A BA B C B CCBA 1111111 2006 2 23电子工程学院 离散数学21 10 A B A B 德 德 摩根律 摩根律 11 A B A B 德 德 摩根律 摩根律 12 A A B A 吸收律 吸收律 13 A A B A 吸收律 吸收律 14 A 0 0 零律 零律 15 A 1 1 零律 零律 16 A 0 A 同一律 同一律 17 A 1 A 同一律 同一律 基本等值式 基本等值式 2006 2 23电子工程学院 离散数学22 证明 证明 12 A A B A 1001 0010 0000 A A B A BBA 1111 2006 2 23电子工程学院 离散数学23 18 A A 1 排中律 排中律 19 A A 0 矛盾律 矛盾律 20 A B A B 蕴涵等值式 蕴涵等值式 21 A B A B B A 等价等值式 等价等值式 22 A B B A 假言易位 假言易位 23 A B A B 等价否定等值式 等价否定等值式 24 A B A B A 归谬论 其中 归谬论 其中 A B C代表任意的命题公式 因此每个公式都 是一个模式 请大家牢记以上 代表任意的命题公式 因此每个公式都 是一个模式 请大家牢记以上24种等值式 种等值式 基本等值式 基本等值式 2006 2 23电子工程学院 离散数学24 证明 证明 24 A B A B A 0 0 1 1 A 0 1 1 1 A B 1 0 1 0 B 0011 1100 1110 A B A B A B BA 0101 2006 2 23电子工程学院 离散数学25 1 3 2 等值演算等值演算 利用已知的等值式 推算出另外一些等值式的方 法即为等值演算 等值演算还将用到如下的置换规 则 利用已知的等值式 推算出另外一些等值式的方 法即为等值演算 等值演算还将用到如下的置换规 则 定理定理1 1 设 设 A 是含公式是含公式A的命题公式 的命题公式 B 是用公 式 是用公 式B置换了 置换了 A 中的中的A得到的命题公式 若得到的命题公式 若A B 则 则 A B 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 2006 2 23电子工程学院 离散数学26 例例1 9 验证等值式验证等值式 1 p q r p q r 证明 证明 p q r p q r 蕴涵等值式 蕴涵等值式 p q r 蕴涵等值式 蕴涵等值式 p q r 结合律 结合律 p q r 德 德 摩根律 摩根律 p q r 蕴涵等值式 蕴涵等值式 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 2006 2 23电子工程学院 离散数学27 例例1 9 2 验证等值式 验证等值式 p p q p q 证明 证明 p p 1 同一律 同一律 p q q 排中律 排中律 p q p q 分配律 分配律 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 2006 2 23电子工程学院 离散数学28 证明 证明 p q r p q r 蕴涵等值式 蕴涵等值式 p q r 蕴涵等值式 蕴涵等值式 r q p 结合律 结合律 r q p 蕴涵等值式 蕴涵等值式 r q p 蕴涵等值式 蕴涵等值式 例例1 10 1 验证 验证 p q r r q p 2006 2 23电子工程学院 离散数学29 p q p q r p q p r 解 原式解 原式 7层公式 层公式 p q p q r p q p r 德 德 摩根律 摩根律 p q p q r p q p r 双重否定律 德 双重否定律 德 摩根律 摩根律 p q p r p q p r 分配律 德 分配律 德 摩根律 摩根律 1 排中律 则 原式为 排中律 则 原式为永真式永真式 例例1 10 2 判断下列公式的类型 判断下列公式的类型 2006 2 23电子工程学院 离散数学30 例例1 11 用等值演算解决以下问题 用等值演算解决以下问题 A B C D四 人做百米竞赛 观众甲 乙 丙预报比赛的名次 为 甲 四 人做百米竞赛 观众甲 乙 丙预报比赛的名次 为 甲 C第一 第一 B第二 乙 第二 乙 C第二 第二 D第三 丙 第三 丙 A第二 第二 D第四 比赛结束后发现甲 乙 丙每人报告的情况都是各 对一半 试问实际名次如何 假设无并列名次的情 况 第四 比赛结束后发现甲 乙 丙每人报告的情况都是各 对一半 试问实际名次如何 假设无并列名次的情 况 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 2006 2 23电子工程学院 离散数学31 解 设解 设pi qi ri si分别表示分别表示A B C D四人却取得第四人却取得第 i 名 名 i 1 2 3 4 显然 显然pi qi ri si各有一个为真命题 由题意 以下三个命题均为真命题 各有一个为真命题 由题意 以下三个命题均为真命题 1 r1 q2 q2 r1 1 甲 甲 C第一 第一 B第二 第二 2 r2 s3 s3 r2 1 乙 乙 C第二 第二 D第三 第三 3 p2 s4 s4 p2 1 丙 丙 A第二 第二 D第四 第四 由由1 1 2 r1 q2 q2 r1 r2 s3 s3 r2 r1 q2 r2 s3 q2 r1 s3 r2 q2 r1 r2 s3 q2