离散数学_第_1_章习题解答.pdf

第一章第一章 命题逻辑命题逻辑 习题与解答习题与解答 1 判断下列语句是否为命题 并讨论命题的真值 1 32 x 2 前进 3 如果2078 则三角形有四条边 4 请勿吸烟 5 你喜欢鲁迅的作品吗 6 如果太阳从西方升起 你就可以长生不老 7 如果太阳从东方升起 你就可以长生不老 解解 3 6 7 表达命题 其中 3 6 表达真命题 7 表达假命题 2 将下列命题符号化 1 逻辑不是枯燥无味的 2 我看见的既不是小张也不是老李 3 他生于1963年或1964年 4 只有不怕困难 才能战胜困难 5 只要上街 我就去书店 6 如果晚上做完了作业并且没有其它事情 小杨就看电视或听音乐 7 如果林芳在家里 那么他不是在做作业就是在看电视 8 三角形三条边相等是三个角相等的充分条件 9 我进城的必要条件是我有时间 10 他唱歌的充分必要条件是心情愉快 11 小王总是在图书馆看书 除非他病了或者图书馆不开门 解解 1 逻辑是枯燥无味的 p 逻辑不是枯燥无味的 符号化为p 2 我看见的是小张 p 我看见的是老李 q 我看见的既不是小张也不是老李 符号化为qp 3 年他生于 1963 p 年他生于 1964 q 他生于 1963 年或 1964 年 符号化为qp 4 害怕困难 p 战胜困难 q 只有不怕困难 才能战胜困难 符号化为pq 5 我上街 p 我去书店 q 只要上街 我就去书店 符号化为qp 2 6 小杨晚上做完了作业 p 小杨晚上没有其它事情 q 小杨晚上看电视 r 小杨晚上听音乐 s 如果晚上做完了作业并且没有其它事情 小杨就看电视或听音乐 符号化为srqp 7 林芳在家里 p 林芳在做作业 q 林芳在看电视 r 如果林芳在家里 那么他不是在做作业就是在看电视 符号化为rqp 8 三角形三条边相等 p 三角形三个角相等 q 三角形三条边相等是三个角相等的充分条件 符号化为qp 9 我进城 p 我有时间 q 我进城的必要条件是我有时间 符号化为qp 10 他唱歌 p 他心情愉快 q 他唱歌的充分必要条件是心情愉快 符号化为qp 11 图书馆开门小王病了 小王在图书馆看书 rqp 小王总是在图书馆看书 除非他病了或者图书馆不开门 符号化为prq 3 列出除 之外的所有二元联结词的真值表 解解 共有 16 个二元联结词 记除 之外的二元联结词为 1121 p q qp 1 qp 2 qp 3 qp 4 qp 5 qp 6 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 p q qp 7 qp 8 qp 9 qp 10 qp 11 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 4 求下列公式在真值赋值 0 0 1 1 4321 pppp下的值 1 321 ppp 2 4321321 ppppppp 3 4321321 ppppppp 4 4312 pppp 5 4231 pppp 6 421321 pppppp 7 4231 pppp 3 解解 记真值赋值 0 0 1 1 4321 pppp为 v 1 1 01 1 321 pppv 2 1 00 11 011 4321321 pppppppv 3 4321321 pppppppv 1 0 0 11 0 11 4 100 11 4312 ppppv 5 0 01 01 4231 ppppv 6 101 101 1 421321 ppppppv 7 0 01 01 4231 ppppv 5 用真值表判断以下公式是不是永真式 永假式 可满足式 1 rqprqrp 2 ppp 3 pqpqp 4 rpqprqp 5 rrqrpqp 6 qpp 7 pqpqp 解解 1 2 4 5 7 是永真式 6 是永假式 3 是非永真的可满足式 6 指出满足下列公式的所有真值赋值 1 rpqp 2 qprqp 3 rqrprp 4 rqp 解解 1 0 0 0 rqp 1 0 0 rqp 0 1 0 rqp 1 1 0 rqp 1 0 1 rqp 0 1 1 rqp 1 1 1 rqp 2 0 1 0 rqp 0 0 1 rqp 1 0 1 rqp 0 1 1 rqp 1 1 1 rqp 3 0 0 0 rqp 0 1 0 rqp 4 0 0 0 rqp 1 1 0 rqp 1 0 1 rqp 0 1 1 rqp 7 若公式 A 既不是永真式 也不是永假式 则 A 的每个替换实例一定既不是永真式 也不是永假式 对吗 解解 不对 若 A 是非永真的可满足式 则它的替换实例中既有永真式 也有永假式 也有非永真的可 满足式 8 用真值表证明以下等值式 1 2 3 4 4 9 用等值演算证明以下等值式 1 rpqrqp 2 rqprpqp 3 qrpqrqp 4 qpppqp 5 qrpqrqp 6 qpqp 解解 1 rpqrpqrqprqp 2 rqprqprpqprpqp 3 qrpqrpqrqpqrqp 4 1 qppqpppqppqp 5 qrpqrqpqrqp qrpqrp 6 qpqpqpqpqp 1 1 10 用等值演算证明以下公式是永真式 1 pqppq 2 sqrpsrqp 3 srqpsprpqp 4 rqrprqp 解解 1 pqppq 1 pppqppq 2 sqrpsrqp sqrpsrqp sqrsrpqp 1 sqrspq 3 srqpsprpqp srqpsprpqp 1 srqpsrqp 4 rqrprqp rqrprqp rqprqp 111 rqprrqpqp 11 用等值演算证明以下公式是永假式 1 pqppq 2 rprqqp 解解 1 pqppq 0 pppqppq 5 2 rprqqp rprqqp rprqqp rrqpqp 0 rqqp 12 找出与下列公式等值的尽可能简单的由 生成的公式 13 找出与下列公式等值的尽可能简单的由 生成的公式 1 prqp 2 qprqp 3 pqp 解解 1 prqp prqp pqprqp rqp rqp 2 qprqpqprqpqprqp 3 pqppqp 14 设 A 是由 生成的公式 证明 A 是永真式当且仅当每个命题变元在 A 中出现偶数次 证证 首先证明 若 A 是由 生成的仅出现一个命题变元 p 的公式 则 中出现奇数次在若 中出现偶数次在若 1 App Ap A 对 p 在 A 中的出现次数进行归纳 若 p 在 A 中出现 1 次 即 A 为 p 显然pA 若 p 在 A 中出现 2 次 即 A 为pp 显然1 A 设 p 在 A 中的出现 n 次 A 为CB p 在 B C 中的出现次数分别为 k 和 l 则lkn nk 且nl 若 n 为偶数 则 k 和 l 的奇偶性相同 B 和 C 等值于同一公式 1 A 若 n 为奇数 则 k 和 l 的奇偶性不同 B 和 C 中一个等值于 p 另一个是永真式 因此ppA 1 设在 A 中的出现的所有命题变元为 n pp 1 它们的出现次数分别为 n kk 1 因为 ABABBABA 并且 11 CBACBACBA 11CBACBACBA 所以 满足交换律和结合律 存在由 生成的公式 n BB 1 使得 n BBA 1 并且 i B 仅出现命题变元 i p 出现次数为 i k ni 1 若 n kk 1 全为偶数 则 111 1 n BBA 若 n kk 1 中有 m ll kk 1 是奇数 则 m lln ppBBA 1 1 显然 A 不是永真式 15 设 A 是由 生成的公式 证明 A 是永假式当且仅当每个命题变元在 A 中出现偶数次 证证 首先证明 若 A 是由 生成的仅出现一个命题变元 p 的公式 则 中出现奇数次在若 中出现偶数次在若 0 App Ap A 对 p 在 A 中的出现次数进行归纳 6 若 p 在 A 中出现 1 次 即 A 为 p 显然pA 若 p 在 A 中出现 2 次 即 A 为pp 显然0 A 设 p 在 A 中的出现 n 次 A 为CB p 在 B C 中的出现次数分别为 k 和 l 则lkn nk 且nl 若 n 为偶数 则 k 和 l 的奇偶性相同 B 和 C 等值于同一公式 0 A 若 n 为奇数 则 k 和 l 的奇偶性不同 B 和 C 中一个等值于 p 另一个是永假式 因此ppA 0 设在 A 中的出现的所有命题变元为 n pp 1 它们的出现次数分别为 n kk 1 因为 满足交换 律和结合律 所以存在由 生成的公式 n BB 1 使得 n BBA 1 并且 i B 仅出现命题 变元 i p 出现次数为 i k ni 1 若 n kk 1 全为偶数 则000 1 n BBA 若 n kk 1 中有 m ll kk 1 是奇数 则 m lln ppBBA 1 1 显然 A 不是永假式 16 北京 上海 天津 广州四市乒乓球队比赛 三个观众猜测比赛结果 甲说 天津第一 上海第二 乙说 天津第二 广州第三 丙说 北京第二 广州第四 比赛结果显示 每人猜对了一半 并且没有并列名次 问 实际名次怎样排列 解解 用字母表示命题如下 广州第四 广州第三 天津第二 天津第一 上海第二 北京第二 432 122 ssr rqp 由已知条件列出以下方程 甲猜对了一半 1 21 qr 乙猜对了一半 1 32 sr 丙猜对了一半 1 42 sp 每个城市只能得一个名次 0 21 rr 0 43 ss 没有并列名次 0 22 qp 0 22 rp 0 22 qr 解以上 8 个方程组成的方程组 000 1 221221222 qrrrqrrrr 将0 2 r代入1 32 sr得1 3 s 将1 3 s代入0 43 ss得0 4 s 将0 4 s代入1 42 sp得 1 2 p 将1 2 p代入0 22 qp得0 2 q 将0 2 q代入1 21 qr得1 1 r 因此 天津第一 北京第二 广州第三 上海第四 17 某勘探队取回一块矿样 三人判断如下 甲说 矿样不含铁 也不含铜 乙说 矿样不含铁 含锡 丙说 矿样不含锡 含铁 已经知道 这三人中有一个是专家 一个是老队员 一个是实习队员 化验结果表明 这块矿样 只含一种金属 专家的两个判断皆对 老队员的判断一对一错 实习队员的两个判断皆错 问 这三人的身分各是什么 解解 矿样含锡矿样含铜 矿样含铁 rqp 甲说的两句话为 p q 乙说的两句话为 p r 丙说的两句话为 r p 如果用一个公式表达出这三人中有一个是专家 一个是老队员 一个是实习队员 公式会非常复 7 杂 其实我们不必完全写出这样的公式 因为矿样只含一种金属 所以0 qp 0 rq 0 pr 甲是实习队员 即甲说的两句话都是错的 可表示为 qp 乙是实习队员 即乙说 的两句话都是错的 可表示为 rp 丙是实习队员 即丙说的两句话都是错的 可表示为 pr 甲 乙 丙三人中至少有一个是实习队员 可表示为 1 prrpqp 因为0 qp 所以1 prrp 即1 rp p 和r 中恰好有一个为 1 因此0 q 甲是老队员 即甲说的话一半对一半错 可表示为 qp 乙是老队员 即乙说的话一半对 一半错 可表示为 rp 丙是老队员 即丙说的话一半对一半错 可表示为 pr 甲 乙 丙三人中有奇数个老队员 可表示为 1 prrpqp 由教材上的等值式可得到 prrpqp pqrrpp 1 10pq pq 又知道0 q 所以1 p 因为0 pr 所以0 r 因此 甲说的话一半对一半错 甲是老队 员 乙说的话全错 乙是实习队员 丙说的话全对 丙是专家 18 先用等值演算证明下列等值式 再用对偶定理得出新等值式 1 pqpqp 2 qpqpqpqp 3 1 pqpq 解解 1 pqqpqpqpqpqp 由对偶定理得 pqpqp 2 qpqqpqpqpqp qpppqpp qpqp 由对偶定理得 qpqpqpqp 3 19 设 A 是由 1 0 生成的公式 A与 A 互为对偶式 1 若 A 是永真式 则 A是永假式 2 若 A 是永假式 则 A是永真式 证明证明 1 设 A 是永真式 则1 A 由对偶定理得0 A 因此 A是永假式 2 设 A 是永假式 则0 A 由对偶定理得1 A 因此 A是永真式 20 证明以下联结词集合是极小完全集 1 0 2 3 4 证明证明 8 1 00 ppp 因为 是完全集 所以 0 是完全集 任取由 0 生成的不 出现除命题变元 p 之外的命题变元的公式 A 令真值赋值 0 pv 则0 Av 而1 pv 因此 0 不能定义 所以 0 不是完全集 任取由 生成的仅出现命题变元 p 的公式 A 令真值赋值 1 pv 则1 Av 而0 pv 因此 不能定义 所以 不是完 全集 所以 是极小完全集 2 1ppppp 因为 是完全集 所以 是完全集 任取由 生成 的仅出现除命题变元 p 的公式 A 令真值赋值 0 pv 则0 Av 而1 pv 因此 不能定义 所以 不是完全集 不是完全集 所以 是极小完全集 3 1ppppp 因为 是完全集 所以 是完全集 任取由 生成的仅出现除命题变元 p 的公式 A 令真值赋值 0 pv 则0 Av 而1 pv 因 此 不能定义 所以 不是完全集 任取由 生成的仅出现命题变元 p 的 公式 A 令真值赋值 1 pv 则1 Av 而0 pv 因此 不能定义 所以 不是完全集 不是完全集 所以 是极小完全集 4 1ppppp 因为 是完全集 所以 是完全集 任取由 生成的仅出现除命题变元 p 的公式 A 令真值赋值 0 pv 则0 Av 而1 pv 因 此 不能定义 所以 不是完全集 任取由 生成的仅出现命题变元 p 的 公式 A 令真值赋值 1 pv 则1 Av 而0 pv 因此 不能定义 所以 不是完全集 不是完全集 所以 是极小完全集 21 证明以下联结词集合不是完全集 1 2 证明证明 1 任取由 生成的仅出现命题变元 p 的公式 A 令真值赋值 1 pv 则1 Av 而0 pv 因此 不能定义 所以 不是完全集 2 任取由 生成的仅出现命题变元 p 的公式 A 令真值赋值 0 pv 则0 Av 而 1 pv 因此 不能定义 所以 不是完全集 22 二元联结词 称为 与非 和 称为 或非 的真值表如下 p q qp qp 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 证明 1 是完全集 2 是完全集 3 若 是二元联结词且 是完全集 则 是 或 证明证明 1 ppp qpqpqpqpqp 因为 是完全集 所以 是完全集 9 2 ppp qpqpqpqpqp 因为 是完全集 所以 是完全集 3 若000 或111 则 不能由 定义 因此 100 且011 若0110 则 的真值表的最后一列有偶数个 1 真值表最后一列有奇数个 1 的 不能由 定义 所以 0110 若10110 则 是 若00110 则 是 23 三元联结词 的真值表如下 p q r rqp 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 证明 是极小完全集 证证 pqqqp 因为 是完全集 所以 是极小完全集 24 在下列公式中 哪些是析取范式 哪些是合取范式 p qp rqp rp pp rqqp 解解 p qp rp pp 是析取范式 p qp rqp rp pp 是合取范式 25 在下列公式中 哪些是关于 p q r 的主析取范式 哪些是关于 p q r 的主合取范式 rqp rqp rqprqp rqp rqpqpp 解解 rqp 是关于 p q r 的主析取范式 rqp 是关于 p q r 的主合取范式 26 是否有这样的公式 它既是主合取范式 又是主析取范式 如果有 举出一例 解解 有 p 既是关于 p 的主析取范式 又是关于 p 的主合取范式 27 求下列公式的主范式 进而判断其是否永真式 永假式 可满足式 1 rqp 2 rqp 3 qpqp 4 rqqpp 5 rqprqp 6 qpqp 解解 1 rqp rqp rqp rqp 的主合取范式是rqp 包含一个极大项 因此它是非永真的可满足式 10 2 rqp rqp rqp rqrp rqpprqqp rqprqprqp rqp 的主合取范式是 rqprqprqp 包含了三个极大项 因此它是非永真的可满足式 3 qpqp qpqpqp qpqp qpqp qp qpqp 的主合取范式为qp 包含了一个极大项 因此它是非永真的可满足 式 4 rqqpp rqqpp 1 rqqpp 的主合取范式为1 不包含任何极大项 因此它是永真式 5 rqprqp rqprqp rqrqprqrqppp rqprqp rqprqp 的主析取范式为 rqprqp 包含了两个极小 项 因此它是非永真的可满足式 6 qpqp qpqppqqp qpqpqpqp qpqp 的主合取范式为 qpqpqpqp 包含了所有的四 个极大项 因此它是永假式 28 用主范式证明下列等值式 1 qpqp prpp 2 rpqp rqp 解解 1 qpqp qpqp qpqp rrqprrqp rqprqprqprqp prpp prpp rpp p rrqqp rqprqprqprqp qpqp 和 prpp 等值于同一个关于 p q r 的主析取范式 rqprqprqprqp 因此 qpqp prpp 2 rpqp rpqp rqqprrqp rqprqprqprqp rqprqprqp rqp rqp rpqp rqqprrqp 11 rqprqprqprqp rqprqprqp rpqp 和rqp 的主合取范式相同 所以 rpqp rqp 29 判断以下关系是否成立 并说明理由 1 qp qp 2 qp pq 3 11 qp 22 qp 2121 qqpp 4 qp qppq 5 rqp rqprqp 解解 1 若真值赋值 v 使得1 pvqpv 则1 qv 所以qp qp 2 真值赋值 1 0 qpv 使得1 qvqpvqpv 但0 pv 所以 qp qp pq 3 若真值赋值 v 使得1 212211 ppvqpvqpv 则1 21 pvpv 因而 1 21 qvqv 1 21 qqv 所以 11 qp 22 qp 2121 qqpp 4 真值赋值 0 0 qpv 使得1 pqvqpv 但0 qpv 所以 qp qppq 5 真值赋值 0 1 0 rqpv 使得1 rqpvrqpv 但0 rqpv 所以 rqp