离散数学(左孝凌)课后习题解答(详细).doc

离散数学 习题 1 1 1 下列句子中 哪些是命题 哪些不是命题 如果是命题 指出它的真值 中国有四大发明 计算机有空吗 不存在最大素数 21 3 5 老王是山东人或河北人 2 与 3 都是偶数 小李在宿舍里 这朵玫瑰花多美丽呀 请勿随地吐痰 圆的面积等于半径的平方乘以 只有 6 是偶数 3 才能是 2 的倍数 雪是黑色的当且仅当太阳从东方升起 如果天下大雨 他就乘班车上班 解 是命题 其中 是真命题 是假命题 的真值目前无法确定 不是命题 2 将下列复合命题分成若干原子命题 李辛与李末是兄弟 因为天气冷 所以我穿了羽绒服 天正在下雨或湿度很高 刘英与李进上山 王强与刘威都学过法语 如果你不看电影 那么我也不看电影 我既不看电视也不外出 我在睡觉 除非天下大雨 否则他不乘班车上班 解 本命题为原子命题 p 天气冷 q 我穿羽绒服 p 天在下雨 q 湿度很高 p 刘英上山 q 李进上山 p 王强学过法语 q 刘威学过法语 p 你看电影 q 我看电影 p 我看电视 q 我外出 r 我睡觉 p 天下大雨 q 他乘班车上班 3 将下列命题符号化 他一面吃饭 一面听音乐 3 是素数或 2 是素数 若地球上没有树木 则人类不能生存 8 是偶数的充分必要条件是 8 能被 3 整除 停机的原因在于语法错误或程序错误 四边形 ABCD 是平行四边形当且仅当它的对边平行 如果 a 和 b 是偶数 则 a b 是偶数 解 p 他吃饭 q 他听音乐 原命题符号化为 p q p 3 是素数 q 2 是素数 原命题符号化为 p q p 地球上有树木 q 人类能生存 原命题符号化为 p q p 8 是偶数 q 8 能被 3 整除 原命题符号化为 p q p 停机 q 语法错误 r 程序错误 原命题符号化为 q r p p 四边形 ABCD 是平行四边形 q 四边形 ABCD 的对边平行 原命题符号化 为 p q p a 是偶数 q b 是偶数 r a b 是偶数 原命题符号化为 p q r 4 将下列命题符号化 并指出各复合命题的真值 如果 3 3 6 则雪是白的 如果 3 3 6 则雪是白的 如果 3 3 6 则雪不是白的 如果 3 3 6 则雪不是白的 是无理数当且仅当加拿大位于亚洲 3 2 3 5 的充要条件是 是无理数 假定是 10 进制 3 若两圆 O1 O 2 的面积相等 则它们的半径相等 反之亦然 当王小红心情愉快时 她就唱歌 反之 当她唱歌时 一定心情愉快 解 设 p 3 3 6 q 雪是白的 原命题符号化为 p q 该命题是真命题 原命题符号化为 p q 该命题是真命题 原命题符号化为 p q 该命题是假命题 原命题符号化为 p q 该命题是真命题 p 是无理数 q 加拿大位于亚洲 原命题符号化为 p q 该命题是假命3 题 p 2 3 5 q 是无理数 原命题符号化为 p q 该命题是真命题 p 两圆 O1 O2 的面积相等 q 两圆 O1 O2 的半径相等 原命题符号化为 p q 该命题是真命题 p 王小红心情愉快 q 王小红唱歌 原命题符号化为 p q 该命题是真命 题 习题 1 2 1 判断下列公式哪些是合式公式 哪些不是合式公式 p q r p q r p q r s p q rs p q r q p q r 解 是合式公式 不是合式公式 2 设 p 天下雪 q 我将进城 r 我有时间 将下列命题符号化 天没有下雪 我也没有进城 如果我有时间 我将进城 如果天不下雪而我又有时间的话 我将进城 解 p q r q p r q 3 设 p q r 所表示的命题与上题相同 试把下列公式译成自然语言 r q r q q r p q r r q 解 我有时间并且我将进城 我没有时间并且我也没有进城 我进城 当且仅当我有时间并且天不下雪 如果我有时间 那么我将进城 反之亦然 4 试把原子命题表示为 p q r 等 将下列命题符号化 或者你没有给我写信 或者它在途中丢失了 如果张三和李四都不去 他就去 我们不能既划船又跑步 如果你来了 那末他唱不唱歌将看你是否伴奏而定 解 p 你给我写信 q 信在途中丢失 原命题符号化为 p q p q p 张三去 q 李四去 r 他去 原命题符号化为 p q r p 我们划船 q 我们跑步 原命题符号化为 p q p 你来了 q 他唱歌 r 你伴奏 原命题符号化为 p q r 5 用符号形式写出下列命题 假如上午不下雨 我去看电影 否则就在家里读书或看报 我今天进城 除非下雨 仅当你走 我将留下 解 p 上午下雨 q 我去看电影 r 我在家读书 s 我在家看报 原命题符 号化为 p q p r s p 我今天进城 q 天下雨 原命题符号化为 q p p 你走 q 我留下 原命题符号化为 q p 习题 1 3 1 设 A B C 是任意命题公式 证明 A A 若 A B 则 B A 若 A B B C 则 A C 证明 由双条件的定义可知 A A 是一个永真式 由等价式的定义可知 A A 成立 因为 A B 由等价的定义可知 A B 是一个永真式 再由双条件的定义可知 B A 也是一个永真式 所以 B A 成立 对 A B C 的任一赋值 因为 A B 则 A B 是永真式 即 A 与 B 具有相同的 真值 又因为 B C 则 B C 是永真式 即 B 与 C 也具有相同的真值 所以 A 与 C 也 具有相同的真值 即 A C 成立 2 设 A B C 是任意命题公式 若 A C B C A B 一定成立吗 若 A C B C A B 一定成立吗 若 A B A B 一定成立吗 解 不一定有 A B 若 A 为真 B 为假 C 为真 则 A C B C 成立 但 A B 不成立 不一定有 A B 若 A 为真 B 为假 C 为假 则 A C B C 成立 但 A B 不 成立 一定有 A B 3 构造下列命题公式的真值表 并求成真赋值和成假赋值 q p q p p q r p q q p p q r q r p p q r q r 解 q p q p 的真值表如表 1 24 所示 表 1 24 p q p q q p q q p q p 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 使得公式 q p q p 成真的赋值是 00 10 11 使得公式 q p q p 成假的 赋值是 01 p q r 的真值表如表 1 25 所示 表 1 25 p q r q r p q r 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 使得公式 p q r 成真的赋值是 000 001 010 011 101 110 111 使得公式 p q r 成假的赋值是 100 p q q p 的真值表如表 1 26 所示 表 1 26 p q p q q p p q q p 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 所有的赋值均使得公式 p q q p 成真 即 p q q p 是一个永真式 p q r q r 的真值表如表 1 27 所示 表 1 27 p q r q p q r q p q r q p q r q r 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 使得公式 p q r q r 成真的赋值是 000 001 010 011 101 110 111 使得公式 p q r q r 成假的赋值是 100 p p q r q r 的真值表如表 1 28 所示 使得公式 p p q r q r 成真的赋值是 000 001 010 011 101 110 111 使得公式 p p q r q r 成假的赋 值是 100 4 用真值表证明下列等价式 p q p q 证明 证明 p q p q 的真值表如表 1 29 所示 表 1 29 p q p q p q q p q 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 由上表可见 p q 和 p q 的真值表完全相同 所以 p q p q p q q p 证明 证明 p q q p 的真值表如表 1 30 所示 表 1 30 表 1 28 p q r p q p p q p p q r q r p p q r q r 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 p q p q p q q p 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 由上表可见 p q 和 q p 的真值表完全相同 所以 p q q p p q p q 证明 证明 p q 和 p q 的真值表如表 1 31 所示 表 1 31 p q p q p q q p q 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 由上表可见 p q 和 p q 的真值表完全相同 所以 p q p q p q r p q r 证明 证明 p q r 和 p q r 的真值表如表 1 32 所示 表 1 32 p q r q r p q r p q p q r 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 由上表可见 p q r 和 p q r 的真值表完全相同 所以 p q r p q r p q p p p q 证明 证明 p q p 和 p p q 的真值表如表 1 33 所示 表 1 33 p q q p p q p p q p q p p q 0 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 由上表可见 p q p 和 p p q 的真值表完全相同 且都是永真式 所以 p q p p p q p q p q p q 证明 证明 p q 和 p q p q 的真值表如表 1 34 所示 表 1 34 p q p q p q p q p q p q p q p q 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 由上表可见 p q 和 p q p q 的真值表完全相同 所以 p q p q p q p q p q p q 证明 证明 p q 和 p q p q 的真值表如表 1 35 所示 表 1 35 p q p q p q p q p q p q p q 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 由上表可见 p q 和 p q p q 的真值表完全相同 所以 p q p q p q p q r p q r 证明 证明 p q r 和 p q r 的真值表如表 1 36 所示 表 1 36 p q r q r p q r q p q p q r 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 由上表可见 p q r 和 p q r 的真值表完全相同 所以 p q r p q r 5 用等价演算证明习题 4 中的等价式 p q p q 条件等价式 p q 德 摩根律 q p q p 条件等价式 q p 双重否定律 p q 交换律 p q 条件等价式 p q p q q p 双条件等价式 p q q p 条件等价式 p q q p 德 摩根律 p q q p q p 分配律 p q q p 分配律 p q q p 交换律 p q q p 条件等价式 p q 双条件等价式 p q r p q r 条件等价式 p q r 结合律 p q r 德 摩根律 p q r 条件等价式 p q p p q p 条件等价式 T p p q p p q 条件等价式 T 所以 p q p p p q p q p q p q 例 1 17 p q p q 德 摩根律 p q p q 德 摩根律 所以 p q p q p q p q p q q p 双条件等价式 p q q p 条件等价式 p q p q 德 摩根律 p q r p q r 条件等价式 p q r 结合律 p q r 德 摩根律 p q r 条件等价式 6 试用真值表证明下列命题定律 结合律 p q r p q r p q r p q r 证明 证明结合律的真值表如表 1 37 和表 1 38 所示 表 1 37 p q r p q p q r q r p q r 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 表 1 38 p q r p q p q r q r p q r 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 由真值表可知结合律成立 分配律 p q r p q p r p q r p q p r 证明 证明合取对析取的分配律的真值表如表 1 39 所示 析取对合取的的分配律的 真值表如表 1 40 所示 表 1 39 p q r q r p q r p q p r p q p r 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 表 1 40 p q r q r p q r p q p r p q p r 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 由真值表可知分配律成立 假言易位式 p q q p 证明 证明假言易位式的真值表如表 1 41 所示 表 1 41 p q p q q p q p 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 由真值表可知假言易位律成立 双条件否定等价式 p q p q 证明 证明双条件否定的真值表如表 1 42 所示 表 1 42 p q p q p q p q 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 由真值表可知双条件否定等价式成立 习题 1 4 1 用真值表或等价演算判断下列命题公式的类型 p q q p q q 条件等价式 p q q 德 摩根律 q 可满足式 吸收律 p q q p q q 条件等价式 p q q 德 摩根律 F 永假式 结合律 矛盾律 p q p q p q p q 条件等价式 p p q p q 分配律 q p q 同一律 矛盾律 q p q 条件等价式 q p q 德 摩根律 T 永真式 零律 排中律 p q q p q q 条件等价式 q 可满足式 吸收律 p q q p p q p q 假言易位式 T 永真式 p q q r p r p q q r p r 条件等价式 p q q r p r 德 摩根律 p q p q r p r r 分配律 p q p q r 同一律 排中律 零律 p q r p p q r q 分配律 T 永真式 p p q p p q 条件等价式 T 永真式 p p q r p p q r 条件等价式 T 永真式 2 用真值表证明下列命题公式是重言式 p p q q p p q q 的真值表如表 1 43 所示 由表 1 43 可以看出 p p q q 是重言式 表 1 43 p q p q p p q p p q q 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 q p q p q p q p 的真值表如表 1 44 所示 由表 1 44 可以看出 q p q p 是重言式 表 1 44 p q p q q q p q p q p q p 0 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 p p q q p p q q 的真值表如表 1 45 所示 由表 1 45 可以看出 p p q q 是重 言式 表 1 45 p q p q p p p q p p q q 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 p q q r p r p q q r p r 的真值表如表 1 46 所示 由表 1 46 可以看出 p q q r p r 是重言式 表 1 46 p q r p q q r p q q r p r p q q r p r 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 p q p r q r r p q p r q r r 的真值表如表 1 47 所示 由表 1 47 可以看出 p q p r q r r 是重言式 表 1 47 p q r p q p r q r p q p r q r p q p r q r r 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 p q r s p r q s p q r s p r q s 的真值表如表 1 48 所示 由表 1 48 可以看出 p q r s p r q s 是重言式 表 1 48 p q r s p q r s p q r s p r q s p r q s 原公式 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 p q q r p r p q q r p r 的真值表如表 1 49 所示 由表 1 49 可以看出 p q q r p r 是重言式 表 1 49 p q r p q q r p q q r p r p q q r p r 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 3 用等价演算证明题 2 中的命题公式是重言式 p p q q p p q q p p q q p p p q q p q q T q p q p q p q p q p q p q p q p p q p q p q p q T p p q q p q q p q q p q q T p q q r p r p q q r p r p q q r p r p q p q r p r r p q p q r p q r p p q r q T p q p r q r r p q p r q r r p q p q r r p q r r p q r r p q r r T p q r s p r q s p q r s p r q s p q r s p r q s p q r s p r q p r s p q r s p r q p q r s p r s r s p r q p p r q q r s p r s p p r s q r s T r s p q r s r s p q r s p q r s r p q r s s T p q q r p r p q q p q r r q p r p q q p q r r q p r p r p q p r r q q r q p p r p q r q r r q q p p r q r q r p q r r q q p p r T p q r r q q p p r p q r r q q p p r p q r q p p r r q p q r p q r q r p q r p q r T 4 证明下列等价式 p r q r p r q r p q r p q r p q r p q p q p q p q p q q p F p p p q p p q p p p q F p q p q 习题 1 5 1 求下列命题公式的析取范式 p q r p q r p q r p q r p q r p q r p q r p p q p p q p p p q p q p q q r p q q r q p r p q r t p q r t p q r p q t 2 求下列命题公式的合取范式 p q p q p q q p q r q p q q q r q p q r p q p q p q p p q q p p q p p q q q p q p q p q p q p q p q p q p q r p q r p q r p q r 3 求下列命题公式的主析取范式 并求命题公式的成真赋值 p q p r 作 p q p r 的真值表 如表 1 50 所示 表 1 50 p q r p q p r p q p r 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 由真值表可知 原式 p q r p q r p q r 主析取范式 5 6 7 使得命题公式 p q p r 成真的赋值是 101 110 111 p q p r p q p r p q p r p q p p q r 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 2 3 4 5 6 7 使得命题公式 p q p r 成真的赋值是 001 010 011 100 101 110 111 p q p q 作 p q p q 的真值表 如表 1 51 所示 表 1 51 p q p q p q p q p q p q 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 由真值表可知 原式 p q p q p q 主析取范式 1 2 3 使得命题公式 p q p q 成真的赋值是 01 10 11 p q p q p q p q p q p q p q p q p q p p q q p q p q p q p q 主析取范式 0 2 3 使得命题公式 p q p q 成真的赋值是 00 10 11 p q r p q r p q r p q r p q p r p q p r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 主析取范式 使得命题公式 p q r p q r 成真的赋值是 000 111 4 求下列命题公式的主合取范式 并求命题公式的成假赋值 p q r p q r p q r p q r p r p r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 0 2 4 5 6 使得命题公式 p q r 成假的赋值是 000 010 100 101 110 p q p q 作 p q p q 的真值表 如表 1 52 所示 表 1 52 p q p q p q q p q p q p q 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 1 由真值表可知 原式 p q p q 0 1 使得命题公式 p q p q 成假的赋值是 00 01 p q p r p q p r p q p r p q p p q r p q r 0 使得命题公式 p q p r 成假的赋值是 000 p q p p q p p q p F 0 1 2 3 使得命题公式 p q p 成假的赋值是 00 01 10 11 p q r r p q r r p q r 4 使得命题公式 p q r r 成假的赋值是 100 5 求下列命题公式的主析取范式 再用主析取范式求出主合取范式 p q q r p q q r p q q p q r p q p r q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 主析取范式 0 1 3 7 2 4 5 6 p q r p q r p q r p q r 主合取范式 p q r p q r p q r p q r p r p r p q r p q r p q r 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 5 6 7 0 2 4 p q r p q r p q r 主合取范式 6 求下列命题公式的主合取范式 再用主合取范式求出主析取范式 p q r p q q p r p q q p r p q r p q r q p r q p r p r p r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 主合取范式 0 2 3 4 5 6 1 7 p q r p q r 主析取范式 p q q p q q p q q T 无主合取范式 0 1 2 3 p q p q p q p q 7 用主析取范式判断下列命题公式是否等价 p q r 和 q p r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 主析取范式 0 1 2 3 4 5 7 q p r q p r p q r p q r p q r p q r p q r p q r p q r p q r 主析取范式 0 1 2 3 4 5 7 因为 p q r 与 q p r 的主析取范式相同 所以 p q r q p r p q p r 和 p q p p q p r p q p r p q r p q p q p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r 主析取 范式 0 1 2 3 7 p q p p q p p q p p p q p q p q p q p q p q p q p q 主析取范式 0 1 3 因为 p q p r 与 p q p 的主析取范式不相同 所以 p q p r 与 p q p 不等价 8 用主合取范式判断下列命题公式是否等价 p q r 和 p q r p q r p q r p q r p r q r p q r p q r p q r 0 2 6 p q r p q r p q r 6 因为 p q r 与 p q r 的主合取范式不相同 所以 p q r 与 p q r 不等价 p q p q 和 p q p q p q p q 1 2 0 3 p q p q p q p q p q p q 0 3 因为 p q p q 和 p q p q 的主合取范式相同 所以 p q p q p q p q 习题 1 6 1 将下列命题公式用只含 的等价式表示 p q r p q q p r p q p q r p q q r p q q r q q r p q r q q r p q r q p q r p p q p p q p p q p p q p q p p q p q r p q p q r p q p q r p q p q r p q r p q r p q p q r p q r p q r p q p q r p q r t p q q p r t p q q p r t p q q p r t p q q p r t p q q p r t 2 将下列命题公式用只含 的等价式表示 p q p p q p p q p q q p p q q p p q r p q r p q r p q p q p q q p p q p q p q r p q q p r p q q p r 3 将下列命题公式用只含 的等价式表示 p q r p p q r p p q r p p q p r p q p r p r p q p r p r p q p q p q p q p q p q p q p q p q p q p q p q p q p q p q p q p q r p r p q r p r T 4 下列结论是否成立 若成立 请证明 若不成立 举反例说明 p q q p 成立 p q p q q p q p p q q p 成立 p q p q q p q p p q r p q r 不成立 p q r p q r p q r p q r p q r p q r p q r 4 5 6 而 p q r p q r p q r p q r p q r p q r p q r 1 3 5 显然上式不成立 p q r 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 2 3 而 p q r p q r p q r p q r p q r p q r p q r 2 4 6 显然上式不成立 5 证明下列等价式 p q p q 证明 p q p q p q p q p q p q p q 所以 p q p q p q p q 证明 p q p q p q p q p q p q 所以 p q p q 6 将下列命题公式仅用 表示 p p p p q p q p q p q p q p q p q p p q q 7 将下列命题公式仅用 表示 p p p p p p q p q p q p p q q p q p q p q p q p q 习题 1 7 1 写出下列命题公式的对偶式 p q r 的对偶式是 p q r p q r p 对偶式是 p q r p p q p q p q q p p q q p p q q p 所以 p q 的对偶式是 p q q p 而 p q q p p q q p p q p q p q p q 所以 p q 的对偶式是 p q p q r p q r p q r 所以 p q r 的对偶式是 p q r p q r 的对偶式是 p q r p q r p q r 所以 p q r 的对偶式是 p q r p q r p q p q r p q p q p q r 所以 p q r p q 的对偶式是 p q p q r p q r p q r p q q p r p q q p r p q p q r 所以 p q r 的对偶式是 p q p q r 2 设 p q 为公式 则 q p 称为该公式的逆换式 p q 称为反换式 q p 称 为逆反式 证明 公式与它的逆反式等价 即 p q q p 证明 p q p q 而 q p q p p q 所以 p q q p 公式的逆换式与公式的反换式等价 即 q p p q 证明 q p q p 而 p q p q p q q p 所以 q p p q 3 用真值表或等价演算证明下列蕴含式 p q p q 证明 p q p q p q p q p q p q T 所以 p q p q p q p p q 证明 作 p q p p q 的真值表 如表 1 53 所示 表 1 53 p q p q p q p p q p q p p q 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 由以上真值表可知 p q p p q 是一个永真式 所以 p q p p q p p q 证明 p p q p p q p p q T 所以 p p q p q r p q p r 证明 p q r p q p r p q r p q p r p q r p q p r p q r r p q p p r q r r r p p p q p r q r p q p r p q r p q q r p q 1 所以 p q r p q p r p p q q 证明 作 p p q q 的真值表 如表 1 54 所示 表 1 54 p q p q p p q p p q q 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 由以上真值表可知 p p q q 是一个永真式 所以 p p q q q p q p 证明 作 p p q q 的真值表 如表 1 55 所示 表 1 55 p q q p q q p q q p q p 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 由以上真值表可知 q p q p 是一个永真式 所以 q p q p 4 用 假设前件为真 推证后件也为真或假设后件为假 推证前件也为假 的方法证 明下列蕴含式 p q p q 证明 假设前件 p q 为真 证明后件 p q 也为真 因为 p q 为真 所以 p 为真并且 q 也为真 根据条件的定义可知 p q 也为真 所以 p q p q p q p p q 证明 假设后件 p p q 为假 证明前件 p q 必为假 因为 p p q 为假 则 p 为真 q 为假 根据条件的定义可知 p q 也为假 即 p q p p q p p q 证明 假设前件 p 为真 则 p 为假 根据条件的定义可知 p q 必为真 所以 原蕴含式成立 p q r p q p r 证明 假设后件 p q p r 为假 证明前件 p q r 必为假 因为 p q p r 为假 所以 p q 为真 p r 为假 因为 p r 为假 所以 p 为 真 r 为假 所以 q 必为真 因为 q 为真 r 为假 所以 q r 必为假 因为 p 为真 所以 p q r 必为假 所以 原蕴含式成立 p p q q 证明 假设前件 p p q 为真 证明后件 q 也为真 因为 p p q 为真 所以 p 为 真 p q 也为真 根据条件的定义 q 必为真 所以 原蕴含式成立 q p q p 证明 假设前件 q p q 为真 证明后件 p 也为真 因为 q p q 为真 所以 q 为真 q 为假 又因为 p q 为真 根据条件的定 义 p 为假 所以 p 必为真 所以 原蕴含式成立 5 设 A 是任意的命题公式 证明 A A 证明 由条件的定义可知 A A 是一个永真式 根据蕴含式的定义可知 A A 习题 1 8 1 用全真值表或部分真值表证明下列各题的有效结论 p q r p q r p q r p q r 的全真值表如表 1 56 所示 表 1 56 p q r q r p q r p q p q r p q p q r p q r 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 由真值表可知 p q r p q r 是永真式 所以 p q r p q r p q q r r p p q q r r p 的全真值表如表 1 57 所示 表 1 57 p q r p q r q r p q q r r p q q r r p 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 由真值表可知 p q q r r p 是永真式 所以 p q q r r p p q r q p r p q r q p r 的真值表如表 1 58 所示 表 1 58 p q r p q r q p r p q r q p q r q p r 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 由真值表可知 p q r q p r 是永真式 所以 p q r q p r p q q r p r p q q r p r 的真值表如表 1 59 所示 表 1 59 p q r p q q r p r p q q r p q q r p r 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 由真值表可知 p q q r p r 是永真式 所以 p q q r p r p p p q p q q p p p q p q q 的真值表如表 1 60 所示 表 1 60 p q r p p p q p q p p p q p q p p p q p q q 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 由真值表可知 p p p q p q q 是永真式 所以 p p p q p q q p q q r p r p q q r p r 的真值表如表 1 61 所示 表 1 61 p q r p q q r p r p q q r p q q r p r 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 由真值表可知 p q q r p r 是永真式 所以 p q q r p r 2 用等价演算法 主析取范式法或蕴含演算法证明上题中的各有效结论 p q r p q r p q r p q r 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 所以 p q r p q r p q q r r p p q q r r p p q q r r p p q q r r p p q q r r p p q p q r r p q q r 1 所以 p q q r r p p q r q p r p q r q p r p q r q p r p q r q p r p q r q p r p q p r q r p q q r 1 所以 p q r q p r p q q r p r p q q r p r p q q r p r p q q r p r p q r q p r p q p r q r p q q r 1 所以 p q q r p r p p p q p q q p p p q p q q 1 p q p q q p q p q q p q p q q q q 1 所以 p p p q p q q p q q r p r p q q r p r p q q p q r r q p r p q q p q r r q p r p r p q p r r q q r q p p r p q r q r r q q p p r q r q r p q r r q q p p r T p q r r q q p p r p q r r q q p p r p q r q p p r r q p q r p q r q r p q r p q r T 所以 p q q r p r 3 推理证明下列各题的有效结论 p q r t s p t s q r 证明 t s P t s p P p T 假言推理 p q r P q r T 假言推理 p q p q t s t s 证明 p q P p T 化简律 q T 化简律 p q T 例 1 30 2 q p T 例 1 30 2 p q q p T 合取引入 p q T 双条件等价式 p q t s P t s T 假言推理 p q r s q p r r p q 证明 r P q p r P q p T 析取三段论 r s T 附加律 p q r s P p q T 拒取式 p q q p T 合取引入 p q T 双条件等价式 p q r r s s p q 证明 s P r s P r T 析取三段论 p q r P p q T 拒取式 p q T 德 摩根律 p p p q p q q 证明 q P 附加前提 p q P p T 拒取式 p q P q T 假言推理 q q 矛盾 T 合取引入 p s p q r s p r 证明 p r P 附加前提 p r T 条件等价式 p T 化简律 r T 化简律 r s P s T 假言推理 p s P p T 析取三段论 p p 矛盾 T 合取引入 4 用 CP 规则推证下列各题的有效结论 p q r q p r 证明 p P 附加前提 p q P q T 析取三段论 r q P r T 拒取式 p r CP 规则 p q r s s t u p u 证明 p P 附加前提 p q T 附加律 p q r s P r s T 假言推理 s T 化简律 s t T 附加律 s t u P u T 假言推理 p u CP 规则 p q r q s t u s q p t q t 证明 q P 附加前提 q s P s T 析取三段论 t u s P t u T 拒取式 t u T 条件等价式 t u T 德 摩根律 t T 化简律 q t CP 规则 p q p r q s s r 证明 因为 s r s r 原题可改写为 p q p r q s s r s P 附加前提 q s P q T 拒取式 p q P p T 析取三段论 p r P r T 假言推理 s r CP 规则 p q r r s p s p q 证明 p P 附加前提 p s P s T 假言推理 r s P r T 析取三段论 p q r P p q T 拒取式 p q T 德 摩根律 q T 析取三段论 p q CP 规则 p r q s p r s q 证明 s P 附加前提 s p P p T 析取三段论 p r q P r q T 假言推理 q T 化简律 s q CP 规则 5 用归谬法推证下列各题的有效结论 p q p q t s t s 证明 t s P 附加前提 p q t s P p q T 拒取式 p q p q T 例 1 17 p q p q T 德 摩根律 p q T 化简律 p q P p q p q 矛盾 T 合取引入 r q r s s q p q p 证明 p P 附加前提 p T 双重否定律 p q P q T 假言推理 r q P r T 拒取式 r s P s T 析取三段论 s q P q T 假言推理 q q 矛盾 T 合取引入 p q q r r p s s 证明 s P 附加前提 s T 双重否定律 p s P p s T 德 摩根律 p T 析取三段论 p q P q T 假言推理 q r r P q r T 化简律 r T 化简律 r T 析取三段论 r r 矛盾 T 合取引入 p q r s q t s u t u p r p 证明 p P 附加前提 p T 双重否定律 p r P r T 假言推理 p q r s P p q T 化简律 r s T 化简律 q T 假言推理 s T 假言推理 q t s u P q t T 化简律 s u T 化简律 t T 假言推理 u T 假言推理 t u T 合取引入 t u P t u t u 矛盾 T 合取引入 p q r t s p t s q r 证明 q r P 附加前提 p q r P p T 拒取式 t s p P t s T 拒取式 t s P t s t s 矛盾 T 合取引入 p q r q r p 证明 p P 附加前提 p T 双重否定律 p q P q T 假言推理 r q P r T 拒取式 r P r r 矛盾 T 合取引入 6 证明下面各命题推得的结论是有效的 如果今天是星期三 那么我有一次离散数 学或数字逻辑测验 如果离散数学课老师有事 那么没有离散数学测验 今天是星期三 且离散数学老师有事 所以 我有一次数字逻辑测验 证明 设 p 今天是星期三 q 我有一次离散数学测验 r 我有一次数字逻辑测验 s 离散数学课老师有事 该推理就是要证明 p q r s q p s r p s P p T 化简律 s T 化简律 s q P q T 假言