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

《离散数学第1章习题解答.pdf》由会员分享，可在线阅读，更多相关《离散数学第1章习题解答.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第 1 章习题解答 第一章 命题逻辑 习题与解答 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)如果晚上做完了作业并

2、且没有其它事情，小杨就看电视或听音乐。(7)如果林芳在家里，那么他不是在做作业就是在看电视。(8)三角形三条边相等是三个角相等的充分条件。(9)我进城的必要条件是我有时间。(10)他唱歌的充分必要条件是心情愉快。(11)小王总是在图书馆看书，除非他病了或者图书馆不开门。解(1)逻辑是枯燥无味的。:p“逻辑不是枯燥无味的”符号化为 p?。(2)我看见的是小张:p 我看见的是老李:q“我看见的既不是小张也不是老李”符号化为 q p?。(3)年他生于 1963:p 年他生于 1964:q“他生于 1963 年或 1964 年”符号化为 q p。(4)害怕困难:p 战胜困难:q“只有不怕困难，才能战胜

3、困难”符号化为 p q?。(5)我上街:p 我去书店:q“只要上街，我就去书店”符号化为 q p。(6)小杨晚上做完了作业:p 小杨晚上没有其它事情:q 小杨晚上看电视:r 小杨晚上听音乐:s“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为 s r q p。(7)林芳在家里:p 林芳在做作业:q 林芳在看电视:r“如果林芳在家里，那么他不是在做作业就是在看电视”符号化为 r q p。(8)三角形三条边相等:p 三角形三个角相等:q“三角形三条边相等是三个角相等的充分条件”符号化为 q p。(9)我进城:p 我有时间:q“我进城的必要条件是我有时间”符号化为 q p。(10)

4、他唱歌:p，他心情愉快:q“他唱歌的充分必要条件是心情愉快”符号化为 q p?。(11)图书馆开门小王病了，小王在图书馆看书，:r q p“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为 p r q?)(。3.列出除，?之外的所有二元联结词的真值表。解 共有 16 个二元联结词，记除，?之外的二元联结词为 1121,。p q q p 1q p 2q p 3q p 4q p 5q p 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 q p 7q p 8q p 9q p 10q p 11 0 0

5、 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/(4321p p p p 下的值：(1)(321p p p (2)()()(4321321p p p p p p p?(3)()(4321321p p p p p p p?(4)4312)(p p p p?(5)()(4231p p p p?(6)421321)(p p p p p p?(7)()(4231p p p p?解 记真值赋值)0/,0/,1/,1/(4321p p p p 为 v。(1)1)01(1)(321=p p p v。(2

6、)1)00()11()011()()()(4321321=?=?p p p p p p p v(3)()(4321321p p p p p p p v?。1)0)0)11(0)11(=?=(4)100)11()(4312=?=?p p p p v。(5)0)01()01()()(4231=?=?p p p p v。(6)101)101(1)(421321=?=?p p p p p p v。(7)0)01()01()()(4231=?=?p p p p v。5.用真值表判断以下公式是不是永真式、永假式、可满足式。(1)()()(r q p r q r p (2)p p p?)(3)()(p q

7、p q p?(4)()()(r p q p r q p (5)r r q r p q p)()()(6)(q p p?(7)()(p q p q p?解(1),(2),(4),(5),(7)是永真式，(6)是永假式，(3)是非永真的可满足式。6.指出满足下列公式的所有真值赋值。(1)()(r p q p?(2)(q p r q p?(3)()(r q r p r p?(4)(r q p?解(1)0/,0/,0/(r q p，)1/,0/,0/(r q p，)0/,1/,0/(r q p，)1/,1/,0/(r q p，)1/,0/,1/(r q p，)0/,1/,1/(r q p，)1/,1/

8、,1/(r q p。(2)0/,1/,0/(r q p，)0/,0/,1/(r q p，)1/,0/,1/(r q p，)0/,1/,1/(r q p，)1/,1/,1/(r q p。(3)0/,0/,0/(r q p，)0/,1/,0/(r q p。(4)0/,0/,0/(r q p，)1/,1/,0/(r q p，)1/,0/,1/(r q p，)0/,1/,1/(r q p。7.若公式 A 既不是永真式，也不是永假式，则 A 的每个替换实例一定既不是永真式，也不是永假式。对吗？解 不对。若 A 是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有非永真的可 满足式。8.用真值

9、表证明以下等值式。(1)(2)(3)(4)9.用等值演算证明以下等值式。(1)()(r p q r q p?(2)r q p r p q p?)()(3)q r p q r q p?)()(4)()(q p p p q p?(5)q r p q r q p?)()(6)q p q p)(解(1)()()()(r p q r p q r q p r q p?(2)r q p r q p r p q p r p q p?)()()()()(3)q r p q r p q r q p q r q p?)()()(4)(1)(q p p q p p p q p p q p?(5)q r p q r q

10、 p q r q p?)()()()()(q r p q r p?)(6)q p q p q p q p q p?)(1)1()(10.用等值演算证明以下公式是永真式。(1)p q p p q?)()(2)()()(s q r p s r q p (3)()()()(s r q p s p r p q p (4)()()(r q r p r q p 解(1)p q p p q?)()(1)()(?p p p q p p q(2)()()(s q r p s r q p s q r p s r q p?)()(s q r s r p q p?)()(1?s q r s p q(3)()()()(

11、s r q p s p r p q p )(s r q p s p r p q p?1?s r q p s r q p(4)()()(r q r p r q p r q r p r q p?)(r q p r q p?)(111)()(?r q p r r q p q p 11.用等值演算证明以下公式是永假式。(1)p q p p q?)()(2)()()(r p r q q p?解(1)p q p p q?)()(0)()(?p p p q p p q(2)()()(r p r q q p?)()()(r p r q q p?r p r q q p?)()()()(r r q p q p?0

12、?r q q p 12.找出与下列公式等值的尽可能简单的由,?生成的公式。13.找出与下列公式等值的尽可能简单的由,?生成的公式。(1)(p r q p?(2)q p r q p?)(3)p q p?解(1)(p r q p?)(p r q p?)()(p q p r q p?r q p?)(r q p?(2)()()(q p r q p q p r q p q p r q p?(3)(p q p p q p?14.设 A 是由?生成的公式。证明：A 是永真式当且仅当每个命题变元在 A 中出现偶数次。证 首先证明：若 A 是由?生成的仅出现一个命题变元 p 的公式，则 中出现奇数次在若中出现偶

13、数次在若 1A p p A p A 对 p 在 A 中的出现次数进行归纳。若 p 在 A 中出现 1 次，即 A 为 p，显然 p A?。若 p 在 A 中出现 2 次，即 A 为 p p?，显然 1?A。设 p 在 A 中的出现 n 次，A 为 C B?，p 在 B，C 中的出现次数分别为 k 和 l，则 l k n+=，n k 且 n l。若 n 为偶数，则 k 和 l 的奇偶性相同，B 和 C 等值于同一公式，1?A。若 n 为奇数，则 k 和 l 的奇偶性不同，B 和 C 中一个等值于 p，另一个是永真式，因此 p p A 1。设在 A 中的出现的所有命题变元为 n p p,1，它们的

14、出现次数分别为 n k k,1。因为 A B A B B A B A?)()(，并且 11)()(?C B A C B A C B A)()(11C B A C B A C B A?所以?满足交换律和结合律，存在由?生成的公式 n B B,1，使得n B B A 1，并且 i B 仅出现命题变元 i p，出现次数为 i k，n i,1=。若 n k k,1 全为偶数，则 1111?n B B A。若n k k,1 中有 m l l k k,1 是奇数，则 m l l n p p B B A 11，显然 A 不是永真式。15.设 A 是由生成的公式。证明：A 是永假式当且仅当每个命题变元在 A

15、中出现偶数次。证 首先证明：若 A 是由生成的仅出现一个命题变元 p 的公式，则 中出现奇数次在若中出现偶数次在若 0A p p A p A 对 p 在 A 中的出现次数进行归纳。若 p 在 A 中出现 1 次，即 A 为 p，显然 p A?。若 p 在 A 中出现 2 次，即 A 为 p p，显然 0?A。设 p 在 A 中的出现 n 次，A 为 C B，p 在 B，C 中的出现次数分别为 k 和 l，则 l k n+=，n k 且 n l。若 n 为偶数，则 k 和 l 的奇偶性相同，B 和 C 等值于同一公式，0?A。若 n 为奇数，则 k 和 l 的奇偶性不同，B 和 C 中一个等值于

16、 p，另一个是永假式，因此 p p A?0。设在 A 中的出现的所有命题变元为 n p p,1，它们的出现次数分别为 n k k,1。因为满足交换律和结合律，所以存在由生成的公式 n B B,1，使得 n B B A?1，并且 i B 仅出现命题变元 i p，出现次数为 i k，n i,1=。若 n k k,1 全为偶数，则0001?n B B A。若 n k k,1 中有 m l l k k,1 是奇数，则 m l l n p p B B A?11，显然 A 不是永假式。16.北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。甲说：“天津第一，上海第二。”乙说：“天津第二，广州第

17、三。”丙说：“北京第二，广州第四。”比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？解 用字母表示命题如下：广州第四。广州第三，天津第二，天津第一，上海第二，北京第二，:432122s s r r q p 由已知条件列出以下方程：甲猜对了一半：121=q r 乙猜对了一半：132=s r 丙猜对了一半：142=s p 每个城市只能得一个名次：021=r r，043=s s 没有并列名次：022=q p，022=r p，022=q r 解以上 8 个方程组成的方程组：000)()()(1221221222=q r r r q r r r r 将 02=r 代入 132=s

18、r 得 13=s，将 13=s 代入 043=s s 得04=s，将 04=s 代入 142=s p 得 12=p，将 12=p 代入 022=q p 得 02=q，将 02=q 代入 121=q r 得 11=r。因此，天津第一，北京第二，广州第三，上海第四。17.某勘探队取回一块矿样，三人判断如下。甲说：“矿样不含铁，也不含铜。”乙说：“矿样不含铁，含锡。”丙说：“矿样不含锡，含铁。”已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？解 矿样含锡矿样含

19、铜，矿样含铁，:r q p。甲说的两句话为：p?，q?乙说的两句话为：p?，r 丙说的两句话为：r?，p 如果用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常复 杂。其实我们不必完全写出这样的公式。因为矿样只含一种金属，所以 0=q p，0=r q，0=p r。甲是实习队员，即甲说的两句话都是错的，可表示为：q p。乙是实习队员，即乙说的两句话都是错的，可表示为：r p?。丙是实习队员，即丙说的两句话都是错的，可表示为：p r?。甲、乙、丙三人中至少有一个是实习队员，可表示为：1)()()(=?p r r p q p 因为 0=q p，所以 1)()(=?p r

20、r p，即 1=r p，p 和 r 中恰好有一个为 1，因此 0=q。甲是老队员，即甲说的话一半对一半错，可表示为：q p?。乙是老队员，即乙说的话一半对一半错，可表示为：r p?。丙是老队员，即丙说的话一半对一半错，可表示为：p r?。甲、乙、丙三人中有奇数个老队员，可表示为：1)()()(=?p r r p q p 由教材上的等值式可得到)()()(p r r p q p?)()()(p q r r p p?)1(10p q?p q?又知道 0=q，所以 1=p。因为 0=p r，所以 0=r。因此，甲说的话一半对一半错，甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。18

21、.先用等值演算证明下列等值式，再用对偶定理得出新等值式。(1)p q p q p?)()(2)()()()(q p q p q p q p?(3)1)(?p q p q 解(1)p q q p q p q p q p q p?)()()()()(，由对偶定理得 p q p q p?)()(。(2)()()()()(q p q q p q p q p q p?)()()(q p p p q p p?)(q p q p?由对偶定理得)()()()(q p q p q p q p?。(3)19.设 A 是由,1,0?生成的公式，*A 与 A 互为对偶式。(1)若 A 是永真式，则*A 是永假式。(2

22、)若 A 是永假式，则*A 是永真式。证明(1)设 A 是永真式，则 1?A，由对偶定理得 0*=A，因此*A 是永假式。(2)设 A 是永假式，则 0?A，由对偶定理得 1*=A，因此*A 是永真式。20.证明以下联结词集合是极小完全集。(1),0(2),(3),?(4),?证明(1)00?p p p，因为,?是完全集，所以,0是完全集。任取由0生成的不 出现除命题变元 p 之外的命题变元的公式 A，令真值赋值)0/(p v=，则 0)(=A v，而 1)(=?p v，因此0不能定义?。所以0不是完全集。任取由生成的仅出现命题变元 p 的公式 A，令真值赋值)1/(p v=，则 1)(=A

23、v，而 0)(=?p v，因此不能定义?。所以不是完全集。所以,?是极小完全集。(2)(1p p p p p?，因为,?是完全集，所以,是完全集。任取由生成 的仅出现除命题变元 p 的公式 A，令真值赋值)0/(p v=，则0)(=A v，而 1)(=?p v，因此不能定义?。所以不是完全集。不是完全集。所以,是极小完全集。(3)(1p p p p p?，因为,?是完全集，所以,?是完全集。任取由,生成的仅出现除命题变元 p 的公式 A，令真值赋值)0/(p v=，则 0)(=A v，而 1)(=?p v，因此,不能定义?。所以,不是完全集。任取由,?生成的仅出现命题变元 p 的公式 A，令真

24、值赋值)1/(p v=，则 1)(=A v，而 0)(=?p v，因此,?不能定义?。所以,?不是完全集。,?不是完全集。所以,?是极小完全集。(4)(1p p p p p?，因为,?是完全集，所以,?是完全集。任取由,生成的仅出现除命题变元 p 的公式 A，令真值赋值)0/(p v=，则 0)(=A v，而 1)(=?p v，因此,不能定义?。所以,不是完全集。任取由,?生成的仅出现命题变元 p 的公式 A，令真值赋值)1/(p v=，则 1)(=A v，而 0)(=?p v，因此,?不能定义?。所以,?不是完全集。,?不是完全集。所以,?是极小完全集。21.证明以下联结词集合不是完全集。(

25、1),?(2),证明(1)任取由,?生成的仅出现命题变元 p 的公式 A，令真值赋值)1/(p v=，则 1)(=A v，而 0)(=?p v，因此,?不能定义?。所以,?不是完全集。(2)任取由,生成的仅出现命题变元 p 的公式 A，令真值赋值)0/(p v=，则 0)(=A v，而 1)(=?p v，因此,不能定义?。所以,不是完全集。22.二元联结词（称为“与非”）和（称为“或非”）的真值表如下。p q q p q p 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 证明：(1)是完全集。(2)是完全集。(3)若 是二元联结词且 是完全集，则 是或。证明(1)p p p?

26、，)()()()(q p q p q p q p q p?因为,?是完全集，所以是完全集。(2)p p p?，)()()()(q p q p q p q p q p?因为,?是完全集，所以是完全集。(3)若 000=或 111=，则?不能由 定义。因此，100=且011=。若 0110，则 的真值表的最后一列有偶数个 1，真值表最后一列有奇数个 1 的不能由 定义。所以，0110=。若 10110=，则 是。若00110=，则 是。23.三元联结词 的真值表如下。p q r),(r q p 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

27、0 1 1 1 1 0 证明 是极小完全集。证 pqq q p?，因为是完全集，所以 是极小完全集。24.在下列公式中，哪些是析取范式，哪些是合取范式?p，q p，r q p)(，r p?，p p?，r q q p?)(解 p，q p，r p?，p p?是析取范式，p，q p，r q p)(，r p?，p p?是合取范式。25.在下列公式中，哪些是关于 p,q,r 的主析取范式，哪些是关于 p,q,r 的主合取范式？r q p,r q p?,)()(r q p r q p?,)(r q p,)()(r q p q p p?解 r q p?是关于 p,q,r 的主析取范式，r q p 是关于 p

28、,q,r 的主合取范式。26.是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。解 有。p 既是关于 p 的主析取范式，又是关于 p 的主合取范式。27.求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。(1)r q p?(2)r q p)(3)(q p q p?(4)(r q q p p?(5)()(r q p r q p?(6)(q p q p?解(1)r q p?r q p)(r q p?r q p?的主合取范式是 r q p?，包含一个极大项，因此它是非永真的可满足式。(2)r q p)(r q p)(r q p?)()()(r q r p?)()(r q

29、 p p r q q p?)()()(r q p r q p r q p?r q p)(的主合取范式是)()()(r q p r q p r q p?，包含了三个极大项，因此它是非永真的可满足式。(3)(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，包含了一个极大项，因此它是非永真的可满足 式。(4)(r q q p p?)(r q q p p?1?)(r q q p p?的主合取范式为 1，不包含任何极大项，因此它是永真式。(5)()(r q p r q p?)()(r q p r q p?

30、)()()()(r q r q p r q r q p p p?)()(r q p r q p?)()(r q p r q p?的主析取范式为)()(r q p r q p?，包含了两个极小项，因此它是非永真的可满足式。(6)(q p q p?)()()(q p q p p q q p?)()()()(q p q p q p q p?)(q p q p?的 主 合 取 范 式 为)()()()(q p q p q p q p?，包含了所有的四个极大项，因此它是永假式。28.用主范式证明下列等值式。(1)q p q p)()()(p r p p?(2)()(r p q p r q p?解(1)q

31、 p q p)()()(q p q p )()(q p q p?)()(r r q p r r q p?)()()()(r q p r q p r q p r q p?)()(p r p p?)()(p r p p?)(r p p?p?)()(r r q q p?)()()()(r q p r q p r q p r q p?q p q p)(和)()(p r p p?等值于同一个关于,p q r 的主析取范式)()()()(r q p r q p r q p r q p?，因此，q p q p)()()(p r p p?。(2)()(r p q p)()(r p q p?)()(r q q

32、p r r q p?)()()()(r q p r q p r q p r q p?)()()(r q p r q p r q p?r q p)(r q p?)()(r p q p?)()(r q q p r r q p?)()()()(r q p r q p r q p r q p?)()()(r q p r q p r q p?)()(r p q p 和 r q p 的主合取范式相同，所以，)()(r p q p r q p?。29.判断以下关系是否成立，并说明理由。(1)q p,q p=?|(2)q p,p q=|(3)11q p,22q p,2121|q q p p=(4)q p,q

33、p p q=|(5)r q p,r q p r q p=?|解(1)若真值赋值 v 使得 1)()(=?=p v q p v，则 1)(=q v。所以 q p,q p=?|。(2)真值赋值)1/,0/(q p v=使得 1)()()(=q v q p v q p v，但 0)(=p v，所以 q p,q p,p q/|=。(3)若真值赋值 v 使得 1)()()(212211=p p v q p v q p v，则 1)()(21=p v p v，因而 1)()(21=q v q v，1)(21=q q v。所以 11q p,22q p,2121|q q p p=。(4)真值赋值)0/,0/(

34、q p v=使得 1)()(=p q v q p v，但 0)(=q p v。所以 q p,q p p q=/|。(5)真值赋值)0/,1/,0/(r q p v=使得 1)()(=?=r q p v r q p v，但 0)(=r q p v。所以 r q p,r q p r q p=?/|。30.判断以下公式组成的集合是否可满足，并说明理由。(1)()(r s q p?，)(r s?(2)1p，21p p?，321p p p?，11+?n n p p p，(3)q p，q p?，q p 解(1)可满足。真值赋值)0/,1/,0/,1/(s r q p 满足它。(2)可满足。若真值赋值 v

35、使得,2,1,1)(=i p v i，则 v 满足它。(3)可满足。真值赋值)1/,0/(q p 满足它。31.设 A,B,C 是任意公式。C B A=|当且仅当 C A=|且 C B=|。证明 1（?）设 C B A=|。任取满足 A 的真值赋值 v，则 1)(=B A v，因为 C B A=|，所以 1)(=C v。这表明 C A=|。任取满足 B 的真值赋值 v，则 1)(=B A v，因为 C B A=|，所以 1)(=C v。这表明 C B=|。（?）设 C A=|且 C B=|。任取满足 B A 的真值赋值 v，则1)(=A v 或 1)(=B v。若 1)(=A v，因为 C A

36、=|，所以 1)(=C v。若 1)(=B v，因为 C B=|，所以 1)(=C v。因此，C B A=|。证明 2 C B A C B A C B A?)()()()()()(C B C A C B C A?C B A=|当且仅当 C B A 是永真式 当且仅当)()(C B C A 是永真式 当且仅当 C A 和 C B 都是永真式 当且仅当 C A=|且 C B=|32.设 1 和 2 是公式集合，B 是公式，B=|2，对于 2 中每个公式 A，A=|1。证明：B=|1。证 任取满足 1 的真值赋值 v。对于 2 中每个公式 A，因为 A=|1，所以1)(=A v。这表明v 满足2。又

37、因为B=|2，所以1)(=B v。因此，B=|1。33.公式集合 不可满足当且仅当 0|=。证（?）设 0/|=，则存在真值赋值 v 满足 且 0)0(=v，因此 可满足。（?）设 0|=。若 可满足，有真值赋值 v 满足，由 0|=得出1)0(=v，这是不可能的。因此，不可满足。34.设 n 是正整数，1|)(,111n j i q q p p q p q p j i n n n?=。证明：)()(|11n n p q p q=。证 设真值赋值 v 满足，则 1)(1=n p p v，存在 n i 使 1)(=i p v。因为 1)(=i i q p v，所以 1)(=i q v。若 i j 1，因为 1)(=?i j q q v，因此 0)(=j q v。若 n j i，因为 1)(=?j i q q v，因此 0)(=j q v。所以1)()(11=n n p q p q v。