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

第 1 章习题解答 1 离散数学 习题 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 他乘班车上班 第 1 章习题解答 2 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 O2的面积相等 则它们的半径相等 反之亦然 当王小红心情愉快时 她就唱歌 反之 当她唱歌时 一定心情愉快 解 设 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 该命题是真命题 3 p 两圆 O1 O2的面积相等 q 两圆 O1 O2的半径相等 原命题符号化为 p q 该命题是真命题 p 王小红心情愉快 q 王小红唱歌 原命题符号化为 p q 该命题是真命 题 第 1 章习题解答 3 习题 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 等 将下列命题符号化 或者你没有给我写信 或者它在途中丢失了 如果张三和李四都不去 他就去 我们不能既划船又跑步 第 1 章习题解答 4 如果你来了 那末他唱不唱歌将看你是否伴奏而定 解 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 章习题解答 5 习题 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 pq p qq p q q p q p 第 1 章习题解答 6 00101 01110 10001 11111 使得公式 q p q p 成真的赋值是 00 10 11 使得公式 q p q p 成假的 赋值是 01 p q r 的真值表如表 1 25 所示 表 1 25 pqr q rp q r 00001 00111 01011 01111 10000 10111 11011 11111 使得公式 p q r 成真的赋值是 000 001 010 011 101 110 111 使得公式 p q r 成假的赋值是 100 p q q p 的真值表如表 1 26 所示 表 1 26 pq p qq p p q q p 00001 01111 10111 11111 所有的赋值均使得公式 p q q p 成真 即 p q q p 是一个永真式 p q r q r 的真值表如表 1 27 所示 表 1 27 pqr q p qr q p q r q p q r q r 00010001 00110001 第 1 章习题解答 7 01000001 01100111 10011010 10111011 11000001 11100111 使得公式 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 pq p q p q qp q 001010 011000 100111 111000 由上表可见 p q 和 p q 的真值表完全相同 所以 p q p q p q q p 表 1 28 pqr p q p p q p p q rq r p p q r q r 00000101 00100101 01000111 01100101 10011000 10111101 11001011 11101101 第 1 章习题解答 8 证明 证明 p q q p 的真值表如表 1 30 所示 表 1 30 pq p q p q q p 001111 011101 100010 111001 由上表可见 p q 和 q p 的真值表完全相同 所以 p q q p p q p q 证明 证明 p q 和 p q 的真值表如表 1 31 所示 表 1 31 pqp q p q qp q 001010 010101 100111 111000 由上表可见 p q 和 p q 的真值表完全相同 所以 p q p q p q r p q r 证明 证明 p q r 和 p q r 的真值表如表 1 32 所示 表 1 32 pqr q rp q r p q p q r 0001101 0011101 0100101 0111101 1001101 1011101 1100010 1111111 由上表可见 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 第 1 章习题解答 9 pq q pp q p p q p q p p q 00111111 01011011 10110111 11110001 由上表可见 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 pqp q p q p q p q p q p q p q 00100010 01011011 10011011 11101100 由上表可见 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 pqp q p q p q p q p q p q 0010000 0101011 1001101 1110000 由上表可见 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 pqr q rp q r qp q p q r 00001101 第 1 章习题解答 10 00111101 01011001 01111001 10000110 10111111 11011001 11111001 由上表可见 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 第 1 章习题解答 11 所以 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 pqr p q p q rq rp q r 0000000 0010111 0101111 0111111 1001101 1011111 1101111 1111111 表 1 38 pqr p q p q rq rp q r 0000000 0010000 0100000 0110010 1000000 1010000 第 1 章习题解答 12 1101000 1111111 由真值表可知结合律成立 分配律 p q r p q p r p q r p q p r 证明 证明合取对析取的分配律的真值表如表 1 39 所示 析取对合取的的分配律的 真值表如表 1 40 所示 表 1 39 pqr q rp q r p qp r p q p r 00000000 00110000 01010000 01110000 10000000 10111011 11011101 11111111 表 1 40 pqr q rp q r p qp r p q p r 00000000 00100010 01000100 01111111 10001111 10101111 11001111 11111111 由真值表可知分配律成立 假言易位式 p q q p 证明 证明假言易位式的真值表如表 1 41 所示 表 1 41 第 1 章习题解答 13 pq p q q p q p 001111 011011 100100 111001 由真值表可知假言易位律成立 双条件否定等价式 p q p q 证明 证明双条件否定的真值表如表 1 42 所示 表 1 42 pqp q p q p q 001111 010100 100010 111001 由真值表可知双条件否定等价式成立 第 1 章习题解答 14 习题 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 同一律 排中律 零律 第 1 章习题解答 15 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 pq p qp p q p p q q 00101 01101 10001 11111 q p q p q p q p 的真值表如表 1 44 所示 由表 1 44 可以看出 q p q p 是 重言式 表 1 44 pq p q q q p q p q p q p 0011111 0110011 1001001 1110001 p p q q p p q q 的真值表如表 1 45 所示 由表 1 45 可以看出 p p q q 是重 言式 表 1 45 pq p q p p p q p p q q 000101 011111 第 1 章习题解答 16 101001 111001 p q q r p r p q q r p r 的真值表如表 1 46 所示 由表 1 46 可以看出 p q q r p r 是重言式 表 1 46 pqr p qq r p q q r p r p q q r p r 00011111 00111111 01010011 01111111 10001001 10101011 11010001 11111111 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 pqr p qp rq r p q p r q r p q p r q r r 00001101 00101101 01011001 01111111 10010101 10111111 11010001 11111111 第 1 章习题解答 17 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 pqrs p qr s p q r s p rq s p r q s 原公式 00001110011 00011110011 00101000011 00111110011 01001110011 01011110111 01101000011 01111110111 10000100011 10010100011 10100001001 10110101001 11001110011 11011110111 11101001001 11111111111 p q q r p r p q q r p r 的真值表如表 1 49 所示 由表 1 49 可以看出 p q q r p r 是重言式 表 1 49 pqrp qq r p q q r p r p q q r p r 第 1 章习题解答 18 00011111 00110001 01000011 01101001 10001001 10100011 11010001 11111111 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 第 1 章习题解答 19 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 第 1 章习题解答 20 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 第 1 章习题解答 21 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 pqr p qp r p q p r 000000 001000 010000 011000 100000 101011 110101 111111 由真值表可知 原式 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 章习题解答 22 表 1 51 pq p q p q p q p q p q 0011100 0110111 1001111 1100001 由真值表可知 原式 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 第 1 章习题解答 23 pq p q p q qp q p q p q 0010110 0110010 1001111 1110001 由真值表可知 原式 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 第 1 章习题解答 24 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 第 1 章习题解答 25 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 章习题解答 26 习题 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 pq 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 第 1 章习题解答 27 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 第 1 章习题解答 28 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 pq p q p q q p p q q p p q q p 所以 pq 的对偶式是 p q q p 而 p q q p p q q p p q p q p q pq 所以 pq 的对偶式是 pq 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 第 1 章习题解答 29 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 pq p qp qp p q p q p p q 001011 011011 100001 111111 由以上真值表可知 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 第 1 章习题解答 30 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 pq p qp p q p p q q 00101 01101 10001 11111 由以上真值表可知 p p q q 是一个永真式 所以 p p q q q p q p 证明 作 p p q q 的真值表 如表 1 55 所示 表 1 55 pq q p q q p q q p q p 001111 010101 101001 110101 由以上真值表可知 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 第 1 章习题解答 31 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 章习题解答 32 习题习题 1 8 1 用全真值表或部分真值表证明下列各题的有效结论 p q r p q r p q r p q r 的全真值表如表 1 56 所示 表 1 56 pqr q rp q r p q p q r p q p q r p q r 00011001 00111001 01001001 01111001 10011001 10111001 11000101 11111111 由真值表可知 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 pqr p q r q r p q q r r p q q r r p 00011111 00110101 01011001 01110101 10001101 第 1 章习题解答 33 10100101 11011001 11110101 由真值表可知 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 pqr p qr q p r p q r q p q r q p r 00011111 00111111 01011111 01110101 10001101 10101001 11011111 11110001 由真值表可知 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 pqr p qq rp r p q q r p q q r p r 00011111 00111111 01010101 01111111 10001001 10101101 11010001 11111111 由真值表可知 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 章习题解答 34 表 1 60 pqr p p p q p q p p p q p q p p p q p q q 00011001 00111001 01011111 01111111 10010101 10110101 11011111 11111111 由真值表可知 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 pqrp qq rp r p q q r p q q r p r 00011111 00110001 01000101 01101001 10001001 10100101 11010001 11111111 由真值表可知 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 第 1 章习题解答 35 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 第 1 章习题解答 36 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 sP t s pP pT 假言推理 p q r P q rT 假言推理 p q p q t s t s 证明 p qP pT 化简律 qT 化简律 p qT 例 1 30 2 q pT 例 1 30 2 p q q p T 合取引入 p qT 双条件等价式 p q t s P t sT 假言推理 p q r s q p r r p q 证明 rP q p rP q pT 析取三段论 r sT 附加律 p q r s P p qT 拒取式 p q q p T 合取引入 p qT 双条件等价式 第 1 章习题解答 37 p q r r s s p q 证明 sP r sP rT 析取三段论 p q rP p q T 拒取式 p qT 德 摩根律 p p p q p q q 证明 qP 附加前提 p qP pT 拒取式 p qP qT 假言推理 q q 矛盾 T 合取引入 p s p q r s p r 证明 p r P 附加前提 p rT 条件等价式 pT 化简律 rT 化简律 r sP sT 假言推理 p sP pT 析取三段论 p p 矛盾 T 合取引入 4 用 CP 规则推证下列各题的有效结论 p q r q p r 证明 pP 附加前提 p qP qT 析取三段论 r qP rT 拒取式 p rCP 规则 第 1 章习题解答 38 p q r s s t u p u 证明 pP 附加前提 p qT 附加律 p q r sP r sT 假言推理 sT 化简律 s tT 附加律 s t uP uT 假言推理 p uCP 规则 p q r q s t u s q p t q t 证明 qP 附加前提 q sP sT 析取三段论 t u sP t u T 拒取式 t u T 条件等价式 t uT 德 摩根律 tT 化简律 q tCP 规则 p q p r q s s r 证明 因为 s r s r 原题可改写为 p q p r q s s r sP 附加前提 q sP qT 拒取式 p qP pT 析取三段论 p rP rT 假言推理 s rCP 规则 p q r r s p s p q 证明 pP 附加前提 第 1 章习题解答 39 p sP sT 假言推理 r sP rT 析取三段论 p q rP p q T 拒取式 p qT 德 摩根律 qT 析取三段论 p qCP 规则 p r q s p r s q 证明 sP 附加前提 s pP pT 析取三段论 p r qP r qT 假言推理 qT 化简律 s qCP 规则 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 qP p q p q 矛盾 T 合取引入 r q r s s q p q p 证明 pP 附加前提 pT 双重否定律 p qP qT 假言推理 r qP