首页 离散数学习题解答

离散数学习题解答

举报
开通vip

离散数学习题解答习题一 1.下列句子中,哪些是命题?在是命题的句子中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道? (1)中国有四大发明. 答:此命题是简单命题,其真值为1. (2) 是无理数. 答:此命题是简单命题,其真值为1. (3)3是素数或4是素数. 答:是命题,但不是简单命题,其真值为1. (4) 答:不是命题. (5)你去图书馆吗? 答:不是命题. (6)2与3是偶数. 答:是命题,但不是简单命题,其真值为0. (7)刘红与魏新是同学. 答:此命题是简单命题,其真值...

离散数学习题解答
习题一 1.下列句子中,哪些是命题?在是命题的句子中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道? (1)中国有四大发明. 答:此命题是简单命题,其真值为1. (2) 是无理数. 答:此命题是简单命题,其真值为1. (3)3是素数或4是素数. 答:是命题,但不是简单命题,其真值为1. (4) 答:不是命题. (5)你去图书馆吗? 答:不是命题. (6)2与3是偶数. 答:是命题,但不是简单命题,其真值为0. (7)刘红与魏新是同学. 答:此命题是简单命题,其真值还不知道. (8)这朵玫瑰花多美丽呀! 答:不是命题. (9)吸烟请到吸烟室去! 答:不是命题. (10)圆的面积等于半径的平方乘以 . 答:此命题是简单命题,其真值为1. (11)只有6是偶数,3才能是2的倍数. 答:是命题,但不是简单命题,其真值为0. (12)8是偶数的充分必要条件是8能被3整除. 答:是命题,但不是简单命题,其真值为0. (13)2008年元旦下大雪. 答:此命题是简单命题,其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:(1)p:中国有四大发明. (2)p:是无理数. (7)p:刘红与魏新是同学. (10)p:圆的面积等于半径的平方乘以π. (13)p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. (1) 是有理数. 答:否定式: 是无理数. : 是有理数. : 是无理数.其否定式 的真值为1. (2) 不是无理数. 答:否定式: 是有理数. : 不是无理数. : 是有理数. 其否定式 的真值为1. (3)2.5是自然数. 答:否定式:2.5不是自然数. :2.5是自然数. :2.5不是自然数. 其否定式 的真值为1. (4)ln1是整数. 答:否定式:ln1不是整数. :ln1是整数. :ln1不是整数. 其否定式 的真值为1. 4.将下列命题符号化,并指出真值. (1)2与5都是素数 答: :2是素数, :5是素数,符号化为 ,其真值为1. (2)不但 是无理数,而且自然对数的底e也是无理数. 答: : 是无理数, :自然对数的底e是无理数,符号化为 ,其真值为1. (3)虽然2是最小的素数,但2不是最小的自然数. 答: :2是最小的素数, :2是最小的自然数,符号化为 ,其真值为1. (4)3是偶素数. 答: :3是素数, :3是偶数,符号化为 ,其真值为0. (5)4既不是素数,也不是偶数. 答: :4是素数, :4是偶数,符号化为 ,其真值为0. 5.将下列命题符号化,并指出真值. (1)2或3是偶数. (2)2或4是偶数. (3)3或5是偶数. (4)3不是偶数或4不是偶数. (5)3不是素数或4不是偶数. 答: :2是偶数, :3是偶数, :3是素数, :4是偶数, :5是偶数 (1) 符号化: ,其真值为1. (2) 符号化: ,其真值为1. (3) 符号化: ,其真值为0. (4) 符号化: ,其真值为1. (5) 符号化: ,其真值为0. 6.将下列命题符号化. (1)小丽只能从筐里拿一个苹果或一个梨. 答: :小丽从筐里拿一个苹果, :小丽从筐里拿一个梨,符号化为: . (2)这学期,刘晓月只能选学英语或日语中的一门外语课. 答: :刘晓月选学英语, :刘晓月选学日语,符号化为: . 7.设 :王冬生于1971年, :王冬生于1972年,说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表: p q 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式. 8.将下列命题符号化,并指出真值. (1)只要,就有; (2)如果,则; (3)只有,才有; (4)除非,才有; (5)除非,否则; (6)仅当. 答:设p:,则:;设q:,则:. 符号化 真值 (1) 1 (2) 1 (3) 0 (4) 0 (5) 0 (6) 1 9.设p:俄罗斯位于南半球,q:亚洲人口最多,将下面命题用自然语言表述,并指出其真值: (1); (2);; (3); (4); (5); (6); (7). 答:根据题意,p为假命题,q为真命题. 自然语言 真值 (1) 只要俄罗斯位于南半球,亚洲人口就最多 1 (2) 只要亚洲人口最多,俄罗斯就位于南半球 0 (3) 只要俄罗斯不位于南半球,亚洲人口就最多 1 (4) 只要俄罗斯位于南半球,亚洲人口就不是最多 1 (5) 只要亚洲人口不是最多,俄罗斯就位于南半球 1 (6) 只要俄罗斯不位于南半球,亚洲人口就不是最多 0 (7) 只要亚洲人口不是最多,俄罗斯就不位于南半球 1 10.设p:9是3的倍数,q:英国与土耳其相邻,将下面命题用自然语言表述,并指出真值: (1); (2); (3); (4). 答:根据题意,p为真命题,q为假命题. 自然语言 真值 (1) 9是3的倍数当且仅当英语与土耳其相邻 0 (2) 9是3的倍数当且仅当英语与土耳其不相邻 1 (3) 9不是3的倍数当且仅当英语与土耳其相邻 1 (4) 9不是3的倍数当且仅当英语与土耳其不相邻 0 11.将下列命题符号化,并给出各命题的真值: (1)若2+2=4,则地球是静止不动的; (2)若2+2=4,则地球是运动不止的; (3)若地球上没有树木,则人类不能生存; (4)若地球上没有水,则是无理数. 答: 命题1 命题2 符号化 真值 (1) p:2+2=4 q:地球是静止不动的 0 (2) p:2+2=4 q:地球是静止不动的 1 (3) p:地球上有树木 q:人类能生存 1 (4) p:地球上有树木 q:人类能生存 1 12.将下列命题符号化,并给出各命题的真值: (1)2+2=4当且仅当3+3=6; (2)2+2=4的充要条件是3+36; (3)2+24与3+3=6互为充要条件; (4)若2+24,则3+36,反之亦然. 答:设p:2+2=4,q:3+3=6. 符号化 真值 (1) 1 (2) 0 (3) 0 (4) 1 13.将下列命题符号化,并讨论各命题的真值: (1)若今天是星期一,则明天是星期二; (2)只有今天是星期一,明天才是星期二; (3)今天是星期一当且仅当明天是星期二; (4)若今天是星期一,则明天是星期三. 答:设p:今天是星期一,q:明天是星期二,r:明天是星期三. 符号化 真值讨论 (1) 不会出现前句为真,后句为假的情况 (2) 不会出现前句为真,后句为假的情况 (3) 必然为1 (4) 若p为真,则真值为0;若p为假,则真值为1 14.将下列命题符号化: (1)刘晓月跑得快,跳得高; (2)老王是山东人或者河北人; (3)因为天气冷,所以我穿了羽绒服; (4)王欢与李乐组成一个小组; (5)李欣与李末是兄弟; (6)王强与刘威都学过法语; (7)他一面吃饭,一面听音乐; (8)如果天下大雨,他就乘班车上班; (9)只有天下大雨,他才乘班车上班; (10)除非天下大雨,否则他不乘班车上班; (11)下雪路滑,他迟到了; (12)2与4都是素数,这是不对的; (13)“2或4是素数,这是不对的”是不对的. 答: 命题1 命题2 命题3 符号化 (1) p:刘晓月跑得快 q:刘晓月跳得高 - (2) p:老王是山东人 q:老王是河北人 - (3) p:天气冷 q:我穿羽绒服 - (4) p:王欢与李乐组成一个小组 - - p:王欢与李乐组成一个小组 (5) p:李辛与李末是兄弟 - - p:李辛与李末是兄弟 (6) p:王强学过法语 q:刘威学过法语 - (7) p:他吃饭 q:他听音乐 - (8) p:天下大雨 q:他乘车上班 - (9) p:天下大雨 q:他乘车上班 - (10) p:天下大雨 q:他乘车上班 - (11) p:下雪 q:路滑 r:他迟到了 (12) p:2是素数 q:4是素数 - (13) p:2是素数 q:4是素数 - 15.设p:2+3=5. q:大熊猫产在中国. r:太阳从西方升起. 求下列符合命题的真值: (1) (2) (3) (4) 解:p真值为1,q真值为1,r真值为0. (1)0,(2)0,(3)0,(4)1 16.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值: (1) (2) (3) (4) 解:(1)0,(2)0,(3)0,(4)1 17.判断下面一段论述是否为真:“是无理数.并且,如果3是无理数,则也是无理数.另外,只有6能被2整除,6才能被4整除.” 解:p:是无理数q: 3是无理数r:是无理数s: 6能被2整除t:6能被4整除 符号化为: ,该式为重言式,所以论述为真。 18.在什么情况下,下面一段论述是真的:“说小王不会唱歌或小李不会跳舞是正确的,而说如果小王会唱歌,小李就会跳舞是不正确的.” 解:p:小王会唱歌。q:小李会跳舞。 真值为1.真值为0.可得,p真值为1,q真值为0. 所以,小王会唱歌,小李不会跳舞。 19.用真值表判断下列公式的类型: (1) (2)p (3) (4) (5) (6) (7). 解: (1) p q r 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 此式为重言式 (2) p q (p 0 0 1 0 1 0 1 0 1 1 1 1 此式为可满足式 (3) q r 0 0 0 0 1 0 1 0 0 1 1 0 此式为矛盾式 (4) p q 0 0 1 0 1 1 1 0 1 1 1 1 此式为重言式 (5) p q r 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 此式为可满足式 (6) p q r 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 此式为重言式 (7) p q r s 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 此式为可满足式 20.求下列公式的成真赋值: (1) (2) (3) (4) 解: p q 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 由真值表得:(1)的成真赋值是01,10,11(2)的成真赋值是00,10,11 (3)的成真赋值是00,01,10 (4)的成真赋值是01,10,11 21.求下列各公式的成假赋值: (1) (2) (3) 解: p q r 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 由真值表得:(1)的成假赋值是011 (2)的成假赋值是010,110 (3)的成假赋值是100,101 22.已知公式是矛盾式,求公式成真和成假赋值. 解:∵ 是矛盾式 ∴也是矛盾式。 由此可得:该式无成真赋值。而成假赋值为:000,001,010,011,100,101,110,111 23.已知公式是重言式,求公式的成真和成假赋值. 解:∵是重言式,∴也是重言式。 由此可得:该式无成假赋值。而成真赋值为:000,001,010,011,100,101,110,111 24.已知是重言式,试判断公式及的类型. 解:∵是重言式,而要使该式为重言式,其成真赋值只有11,∴都是重言式。 25.已知是矛盾式,试判断公式及的类型. 解:∵是矛盾式,而要使该式为矛盾式,其成假赋值只有00,∴都是重言式。 26.已知是重言式,是矛盾式,试判断及的类型. 解:是矛盾式。 是重言式。 27.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:是重言式当且仅当A和B都是重言式. 解: A B 0 0 0 0 1 0 1 0 0 1 1 1 由真值表可得,当且仅当A和B都是重言式时,是重言式。 28. 设A、B都是含命题变量项p1,p2,…,pn的公式,已知是矛盾式,能得出A和B都是矛盾式的结论吗?为什么? 解: A B 0 0 0 0 1 0 1 0 0 1 1 1 同样由真值表可得,的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。 29. 设A、B都是含命题变量项p1,p2,…,pn的公式,证明:是矛盾式当且仅当A和B都是矛盾式. 解: A B 0 0 0 0 1 1 1 0 1 1 1 1 由真值表可得,当且仅当A和B都是矛盾式时,是矛盾式。 30. 设A、B都是含命题变量项p1,p2,…,pn的公式,已知是重言式,能得出A和B都是重言式的结论吗? 解: A B 0 0 0 0 1 1 1 0 1 1 1 1 由真值表可得的成真赋值有01,10,11.所以无法得到A和B都是重言式。 习 题 二 1.设公式 , ,用真值表验证公式 和 适合德摩根律: 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 2.公式 和 同题(1),用真值表验证公式 和 适合蕴涵等值式. 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) 答:原式= = = 0 是矛盾式. 4.用等值演算法证明下面等值式. (1) 答:右式= = = (2) 答:右式= = = =左式 (3) 答:左式= = = (4) 答:左式= = 5.求下列公式的主析取范式,并求成真赋值: (1) 答: 成真赋值为00,10,11. (2) 答: 所以为矛盾式。 (3) 答 所以是重言式,真值为000,001,010,011,100,101,110,111. 6.求下列公式的主析取范式,并求成真赋值: (1) 答: ,是矛盾式,所有赋值均为成真赋值。 (2) 答: ,成假赋值为100. (3) 答: ,所以为重言式。所有赋值均为成真赋值。 7.求下列公式的主析取范式,再用主析取范式求主合取范式: (1) 答: (2) 答: 8.求下列公式的主合取范式,再用主合取范式求主析取范式: (1) 答: 为重言式。 (2) 答: (3) 答: 因此为矛盾式. 9.用真值表求下面的公式的主析取范式. (1) 答:公式的真值表如下: 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 其成真赋值为001,010,011,100,101,110,111,所以其主析取范式为 (2) 答:公式的真值表如下: EMBED Equation.KSEE3 \* MERGEFORMAT 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 故其成真赋值为001,010. 所以其主析取范式为 . 10.用真值表求下面公式的主合取范式. (1) 答: (2) 答: 11.用真值表求下面公式的主析取范式和主合取范式. (1) (2) (3) 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 答:(1)由真值表可得成真赋值为011,101,111,故主析取范式为 ,主合取范式为 (2)由真值表可得无成假赋值,故主析取范式为 ,主合取范式为1. (3)由真值表可得无成真赋值,故主析取范式为0,主合取范式为 . 12.已知公式 含3个命题变项 ,并且它的成真赋值为000,011,110,求 的主合取范式和主析取范式. 答:由题意得, 的主主合取范式为 ,主析取范式 . 13. 已知公式 含3个命题变项 ,并且它的成真赋值为000,011,110,求 的主合取范式和主析取范式. 答:由题意得, 的主主合取范式为 ,主析取范式 . 14.已知公式 含 个命题变相 ,并且无成假赋值,求 的主合取范式. 答: 的主合取范式为1.. 15.用主析取范式判断下列公式是否等值: (1) 与 答: 所以上述公式不等值. (2) 与 答: 16.用主合取范式判断下列公式是否等值. (1) 与 答: (2) 与 答: 17.将下列公式化成与之等值且仅含 中联结词的公式: (1) 答: (2) 答: ,原式已满足题目要求. (3) 答: 18.将下列公式化成与之等值且仅含 中联结词的公式: (1) 答:此公式已经符合题目要求. (2) 答: (3) 答: 19.将下列公式化成与之等值且仅含 中联结词的公式. (1) 答: (2) 答: (3) 答: 20.将下列公式化成与之等值且仅含{ }中联结词的公式: (1) (2) (3) 答: (2) 答: (3) 答: 21.证明: (1) (2) 证明:(1) ; (2)令 则 ,可知 22.从表2.6中,找出与下列公式等值的真值函数: (1) (2) (3) (4) 答: 23.设A、B、C为任意的命题公式,证明: (1)等值关系有自反性: (2)等值关系有对称性: (3)等值关系有传递性: 答:(1) (2) (3) EMBED Equation.KSEE3 \* MERGEFORMAT 24.设A、B为任意的命题公式,证明: 答: 因此 。 25.设A、B、C为任意的命题公式,(1)若 ,举例说明 不一定成立。(2)若 ,举例说明 不一定成立。由(1)、(2)可知,联结词 不满足消去率。 答:(1)设 ,则 ,但 ,二者不等价。 (2)设 ,则 ,但 ,二者不等价。 26.在上题(25)中,若已知 ,在什么条件下, 一定成立?又若已知 ,在什么条件下, 一定成立? 解:若 则 , 一定成立。 若 ;则 , 一定成立。 27.某电路中有一个灯泡和三个开关A、B、C。已知在且仅在下述四种情况下灯亮: (1)C的扳键向上,A、B的扳键向下。(2)A的扳键向上,B、C的扳键向下。(3)B、C的扳键向上,A的扳键向下。(4)A、B的扳键向上,C的扳键向下。 设F为1表示灯亮,p、q、r分别表示A、B、C的扳键向上。 (a)求F的主析取范式。 (b)在联结词完备集{ }上构造F。 (c)在联结词完备集{ }上构造F。 答:(a)由题意知,灯亮的情况如下: EMBED Equation.DSMT4 (b) (c) 28.一个排队线路,输入为A、B、C,其输出分别为 、 、 .本线路中,在同一时间只能有一个信号通过,若同时有两个或两个以上信号申请输出时,则按A、B、C的顺序输出,写出 、 、 在联结词完备集{ }中的表达式. 答: : 输入, : 输入, : 输入.有题意可得: 29.在某班班委成员的选举中,已知王小红、李强、丁金生3位同学被选进了班委会.该班的甲、乙、丙三名学生预言: 甲说:王小红为班长,李强为生活委员. 乙说:丁金生为班长,王小红为生活委员. 丙说:李强为班长,王小红为学习委员. 班委会分工名单公布后发现,甲、乙、丙三人都恰好猜对了一半.问王小红、李强、丁金生各任何职(用等值等演求解)? 答:设 :王小红为班长, :李强为生活委员 :丁金生为班长, :王小红为生活委员 :李强为班长, :王小红为学习委员 由题意得, 、 有且只有一个为真, 、 有且只有一个为真, 、 有且只有一个为真. 若 为真,则 为假,那么 为假,则 为真,这样 与 矛盾,因此这种假设行不通. 若 为假,则 为真,那么 为假,则 为真,则 为假,所以 为真,因此王小红、李强、丁金生的职位分别是:学习委员、生活委员、班长. 30.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件: (1)若赵去,钱也去. (2)李、周两人中必有一人去. (3)钱、孙两人中去且仅去一人. (4)孙、李两人同去或同不去. (5)若周去,则赵、钱也同去. 用等值演算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 该公司如何选派他们出国? 答:设 :派赵去, :派钱去, :派李去, :派孙去, :派周去 首先以条件(2)为基础,有三种情况: 1 若周去,李不去,由条件(5)得则赵、钱同去,由条件(3)得那么孙不去,符合5个条件,即 . 2 若李去,周不去,由条件(4)得则孙去,从而由条件(3)得钱不去,而由条件(1)得赵也不去,即 . 3 若周、李都去,那么由条件(4)得则孙去,由条件(5)得赵、钱都去,这样孙和钱都去,与条件(3)矛盾,因此这种情况不存在. 习题三 1. 从日常生活或数学中的各种推理中,构造两个满足附加律的推理定律,并将它们符号化。例如:“若2是偶数,则2是偶数或3是奇数”。令p:2是偶数,q:3是奇数,则该附加律符号为 。 解:(1)“若3是素数,则3是素数或5是奇数”。令p:3是素数,q:5是奇数,则该附加律符号化为 (2)“若明天不下雨,则明天不下雨或明天下雪”。令p:明天下雨,q:明天下雪,则该附加律符号化为 。 2. 从日常生活或数学的各种推理中,构造两个满足化简律的推理定律,并将它们符号化。例如:“我去过海南岛和新疆,所以我去过海南岛”。令p:我去过海南岛,q:我去过新疆,则该化简律符号化为 。 解:(1)“6能被2和3整除,所以6能被2整除”。令p:6能被2整除,p:6能被2整除,q:6能被3整除,则该化简律符号化为 。 (2)“小明会弹琴和跳舞,所以小明会弹琴”。令p:小明会弹琴,q:小明会跳舞,则该化简律符号化为 。 3. 随意构造三个满足假言推理定律的推理,并将它们符号化。例如:“如果2是素数,则雪是黑色的,2是素数,所以雪是黑色的”。令p:2是素数,q:雪是黑色的,该假言推理定律符号化为 。 解:(1)“如果小明会跳舞,则他会弹琴,小明会跳舞,所以他会弹琴”。 令p:小明会弹琴,q:小明会跳舞,该假言推理定律符号化为 。 (2)“如果3是奇数,则明天下雨,3是奇数,所以明天下雨”。令p:3是奇数,q:明天下雨,该假言推理定律符号化为 。 (3)“如果明天晴天,则小明去游泳,明天晴天,所以小明去游泳”。令p:明天晴天,q:小明去游泳,该假言推理定律符号化为 。 4. 参照1,2,3题,请构造满足拒取式、析取三段论、假言三段论、等价三段论、构造性二难等推理定律的实例各一个,并将它们符号化。 解:(1)拒取式:“明天是周末,小明就休息,小明没有休息,所以明天不是周末”。令p:明天周末,q:小明休息。该拒取式定律符号化为 。 (2)析取三段论:“小明会弹琴或跳舞,小明不会跳舞,所以小明会弹琴”。令p:小明会弹琴,q:小明会跳舞,该析取三段式定律符号化为 。 (3)假言三段论:“明天要是周末,小明明天休息,小明要是明天休息,他就会去游泳,所以,明天要是周末,小明就去游泳”。令p:明天是周末,q:小明明天休息,t:小明去游泳,该假言三段论定律符号化为 。 (4)等价三段论:“2是素数当且仅当3是奇数,3是奇数当且仅当4是偶数,所以2是素数当且仅当4是偶数”。令p:2是素数,q:3是奇数,t:4是偶数,该等价三段论定律符号化为 。 (5)构造性二难:“明天是周一,小明就要上学,明天是周末,小明就要去游泳,明天是周末或者周一,所以小明去上学或者去游泳”。令p:明天是周一,q小明要上学,s:明天是周末,t:小明要去游泳,该构造性二难定律符号化为 。 (6)破坏性二难:“明天是周一,小明就要上学,明天是周末,小明就要去游泳,小明没有去上学或者小明没有去游泳,所以明天不是周一或者明天不是周末”。令p:明天是周一,q小明要上学,s:明天是周末,t:小明要去游泳,该构造性二难定律符号化为 。 5. 分别写出德摩定律、吸收律所产生的推理定律(每个等值式产生两条推理定律)。 解:的摩定律1: 产生的推理定律:(1) (2) 的摩定律2: 产生的推理定律:(1) (2) 吸收律1: 产生的推理定律:(1) (2) 吸收律2: 产生的推理定律:(1) (2) 6. 判断下列推理是否正确。先将简单命题符号化,再写出前提、结论、推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ): (1) 若今天是星期一,则明天是星期三。今天是星期一,所以明天是星期三。 (2) 若今天是星期一,则明天是星期二。明天是星期二,所以今天是星期一。 (3) 若今天是星期一,则明天是星期三。明天不是星期三,所以今天不是星期一。 (4) 若今天是星期一,则明天是星期二。今天不是星期一,所以明天不是星期二。 (5) 若今天是星期一,则明天是星期二或星期三。 (6) 今天是星期一当且仅当明天是星期三。今天不是星期一,所以明天不是星期三。 解:(1)设p:今天是星期一,q:明天是星期三,推理的形式结构为 ,判断该推理是否正确,即判断 是否为重言式,不难看出,该式满足假言推理定律,所以推理正确。 (2)设p:今天是星期一,q:明天是星期二,推理的形式结构为 。 等值演算法: ,可见该式不是重言式,所以推理不正确。 主析取范式法: ,从而可知不是重言式,故推理不正确。 (3)设p:今天是星期一,q:明天是星期三,推理的形式结构为 ,判断该推理是否正确,即判断 是否为重言式,不难看出,该式满足拒取式定律,所以推理正确。 (4)设p:今天是星期一,q:明天是星期二,推理的形式结构为 。 等值演算法: ,可见该式不是重言式,所以推理不正确。 主析取范式法: ,从而可知不是重言式,故推理不正确。 (5)设p:今天是星期一,q:明天是星期二,r:明天是星期三。推理的形式结构为 。 ,由此可知 不为重言式,故推理不正确。 显然该式不是重言式,所以推理不正确。 (6)设p:今天是星期一,r:明天是星期三,推理的形式结构为 。 ,由此可知不为重言式,故推理不正确。 7. 在下面各推理中没给出结论。请对于每个推理前提给出两个结论,使其中之一是有效的,而另一个不是有效的: (1) 前提: , (2) 前提: , , (3) 前提: , , 解:(1)结论1: 为有效的(假言三段论) 结论2: 为无效的。 (2)结论1: 是有效的(拒取式) 结论2: 是无效的 (3)结论1: 是有效的(假言三段论) 结论2:r是无效的 8. 在下面各推理中没给出结论,请对于每个推理前提给出两个结论,使其中之一是有效的,而另一个不是有效的。 (1) 只有天气热,我才去游泳。我正在游泳,所以…… (2) 只有天气热,我就去游泳。我没去游泳,所以…… (3) 除非天气热并且我有时间,我才去游泳。天气不热或我没时间,所以…… 解: (1)设p:天气热,q:我去游泳 前提: 结论1: ,有效结论(假言推理) 结论2: ,无效结论 (2)设p:天气热,q:我去游泳。 前提: 结论1: ,有效结论(拒取式) 结论2: ,无效结论 (3)设p:天气热,q:我有时间,r:我去游泳。 前提: 结论1: ,有效结论(拒取式) 结论2: ,无效结论。 9. 用三种方法(真值表法,等值演算法,主析取范式法)证明下面推理是正确的: 若a是奇数,则a不能被2整除。若a是偶数,则a能被2整除。因此,如果a是偶数,则a不是奇数。 解:设p:a是奇数,q:a能被2整除,r:a是偶数。 推理的形式结构为 (*)。下面用三种方法证明该式为重言式: (1) 真值表法: p q r * 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 由真值表可知(*)为重言式,故推理是正确的。 (2) 等值演算法: (3) 构造证明法: 前提: 结论: 证明: ① 前提引入 ② ①置换 ③ 前提引入 ④ ③②假言三段论 主析取范式法 由方法2可以得知推理的形式结构(*)的主析取范式为 ,则(*)为重言式,推理正确。 10. 用两种方法(真值表法,主析取范式法)证明下面推理不正确: 如果a,b两数之积是负数,则a,b之中恰有一个是负数。a,b两数之积不是负数,所以a,b中无负数。 真值表法: p q r A 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 推理不正确 主析取范式法: 由于主析取范式只含有5个极小项,所以(3.8)不是重言式,推理不正确。 11. 填充下面推理证明中没有写出的推理规则。 前提: , , ,p 结论:s 证明: ①p 前提引入 ② 前提引入 ③q 析取三段论 ④ 前提引入 ⑤r 析取三段论 ⑥ 前提引入 ⑦s 假言推理 12. 填充下面推理证明中没有写出的推理规则。 前提: , 结论: 证明: ① 附加前提引入 ②p 化简规则 ③q 化简规则 ④ 前提引入 ⑤ 前提引入 ⑥r ③⑤假言推理 ⑦ 前提引入 ⑧ ③⑦假言推理 ⑨s ⑥⑧假言推理 13. 前提: , , 结论1:r 结论2:s 结论3: (1) 证明从此前提出发,推出结论1,结论2,结论3的推理都是正确的。 (2) 证明从此前提出发,推任何结论的推理都是正确的。 (1) 证明: 结论1: 结论2: 结论3: (2) 证明: 设任何可能的结论为*, 则: 14. 在自然系统p中构造下面推理的证明: (1) 前提: ,p,q 结论: (2) 前提: , ,r 结论: (3) 前提: 结论: (4) 前提: , , , 结论: (5) 前提: , , EMBED Equation.3 \* MERGEFORMAT 结论: (6) 前提: , EMBED Equation.3 \* MERGEFORMAT 结论: (1) 证明 (1) 前提引入 (2) 前提引入 (3) (1)(2)假言推理 (4) 前提引入 (5) (3)(4)假言推理 (6) (5)附加 (2) 证明 (1) 前提引入 (2) (1)置换 (3) 前提引入 (4) (2)(3)析取三段论 (5) 前提引入 (6) (4)(5)拒取式 (3) 证明 (1) 前提引入 (2) (1)置换 (3) (2)置换 (4) (3)置换 (5) (4)置换 (4) 证明 (1) 前提引入 (2) (1)置换 (3) (2)换件 (4) 前提引入 (5) (4)化简 (6) (3)(5)假言推理 (7) 前提引入 (8) (7)置换 (9) (8)化简 (10) (6)(9)假言推理 (11) 前提引入 (12) (10)(11)假言推理 (13) (10)(12)合取 (5) 证明 (1) 前提引入 (2) (1)化简 (3) (1)化简 (4) 前提引入 (5) (2)(4)假言推理 (6) 前提引入 (7) (3)(6)假言推理 (8) (5)(7)合取 (6) 证明 (1) 前提引入 (2) (1)化简 (3) (1)化简 (4) 前提引入 (5) (2)(4)析取三段论 (6) 前提引入 (7) (3)(6)析取三段论 (8) (5)(7)合取 (9) (8)附加 (10) (9)置换 15. 在自然推里系统p中用附加前提法证明下面各推理: (1) 前提: , ,q 结论: (2) 前提: , 结论: (1) 证明 (1) 附加前提引入 (2) 前提引入 (3) (1)(2)假言推理 (4) 前提引入 (5) (3)(4)假言推理 (6) 前提引入 (7) (5)(6)假言推理 (2) 证明 (1) 附加前提引入 (2) (1)附加 (3) 前提引入 (4) (2)(3)假言推理 (5) (4)化简 (6) (5)附加 (7) 前提引入 (8) (6)(7)假言推理 16. 在自然推理系统p中用归谬法证明下面推理: (1) 前提: , 结论: (2) 前提: , , 结论: (1) 证明 (1) 结论否定引入 (2) 前提引入 (3) (2)(1)假言推理 (4) 前提引入 (5) (3)(4)析取三段论 (6) 前提引入 (7) (6)化简 (8) (5)(7)合取 (2) 证明 (1) 结论否定引入 (2) (1)置换 (3) (2)化简 (4) (2)化简 (5) 前提引入 (6) (3)(5)拒取式 (7) 前提引入 (8) (4)(7)拒取式 (9) (9)置换 (10) 前提引入 (11) (10)(11)合取 17. 在自然系统p中构造下面推理的证明: 只要A曾到过受害者房间并且11点前没离开,A就犯了谋杀罪。A曾到过受害者房间, 如果A在11点以前离开,看门人会看见他。看门人没有看见他,所以A犯了谋杀罪。 设 p:A到过受害者房间 q:A在11点前离开 r:A是谋杀嫌疑犯 s:看门人看见A 前提: 结论:r 证明 (1) 前提引入 (2) 前提引入 (3) (2)(1)拒取式 (4) 前提引入 (5) (3)(4)合取 (6) 前提引入 (7) (5)(6)假言推理 18. 在自然系统p中构造下面各推理的证明: (1) 如果今天是星期六,我们就要去颐和园或圆明园玩。如果颐和园游人太多,我们就不去颐和园玩。今天是星期六,颐和园游人太多,所以我们去圆明园玩。 (2) 如果小王是理科学生,则他的数学成绩一定很好。如果小王不是文科生,则他一定是理科生。小王的数学成绩不好,所以小王是文科学生。 (1)设 p:今天是星期六 q:我们到颐和园玩 r:我们到圆明园玩 s:颐和园游人太多 前提: 结论:r 证明: (1) 前提引入 (2) 前提引入 (3) (1)(2)假言推理 (4) 前提引入 (5) 前提引入 (6) (4)(5)假言推理 (7) r (3)(6)析取三段论 (2)设 p:小王是理科学生 q:小王数学成绩好 r:小王是文科学生 前提: 结论: 证明: (1) 前提引入 (2) 前提引入 (3) (1)(2)拒取式 (4) 前提引入 (5) (3)(4)拒取式 习题四 1.将下列命题0元谓词符号化: (1) 小王学习过英语和法语。 (2) 除非李建是东北人,否则他一定怕冷。 (3) 2大于3仅当2大于4. (4) 3不是偶数。 (5) 2或3是素数。 解(1)设一元谓词 :小王学习过 。 :英语, :法语。(1)中命题符号化为0元谓词的蕴含式: 。 (2)设一元谓词 : 是东北人。 : 怕冷。 :李建。符号化为 。 (3)设二元谓词 : 大于 ; 符号化为: . (4)设一元谓词 : 不是偶数。 :3。命题符号化为0元谓词的蕴含式: 。 (5) 设一元谓词 : 是素数。 :2, :3. 符号化为 。 2.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1)凡有理数都能被2整除。 (2)有的有理数都能被2整除。 其中(a)个体域为有理数集合。 (b)个体域为实数集合。 解: 能被2整除; 是整数。 (a) (1) ,真值为0,(2) 真值为1. (b) (1) 真值为0,(2) ,真值为1. 3. 在一阶逻辑中将下列命题符号化,并分别讨论个体域限制为(a)(b)条件时的命题的真值: (1) 对任意的 ,均有 。 (2) 存在 ,使得 。 (a) 个体域为自然数集合。 (b) 个体域为实数集合。 解:设 (a) (1) ,真值为0,(2) 真值为1. (b) (1) ,真值为1,(2) 真值为1. 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数。 (2) 在北京卖菜的人不全是外地人。 (3) 乌鸦都是黑色的。 (4) 有的人天天锻炼身体。 解: (1) 或者 ,其中 是有理数, 能表示成分数 (2) 或 ,其中 在北京卖菜, 是外地人 (3) ,其中 是乌鸦, 是黑色的; (4) ,其中 是人, 天天锻炼身体。 5. 在一阶逻辑中将下列命题符号化: (1) 所有的火车都比轮船跑得快。 (2) 有的火车比有的汽车快。 (3) 不存在比所有火车都快的汽车。 (4) 说凡是汽车就比火车慢是不对的。 解: (1) ,其中 是火车, 是轮船, 比 快; (2) ,其中 是火车, 是汽车, 比 快; (3) ,其中 是火车, 是汽车, 比 快; (4) ,其中 是火车, 是汽车, 比 慢; 6.在下列命题符号化,个体域为实数集合R,并指出各命题的真值: (1)对所有的 ,都存在 ,使得 。 (2)存在着 ,对所有 都有 。 (3)对所有的 ,都存在 ,使得 。 (4)对所有的 和 ,都有 。 (5)对任意的 和 ,都有 。 (6)对任意的 ,存在 ,使得 。 解:各命题符号化如下: (1) , (2) , (3) , (4) , (5) , (6) 。 7. 将下列各公式翻译成自然语言,个体域为整数集Z, 并判断各命题的真假: (1) (2) (3) 解: (1)对所有整数 和 ,存在整数 ,使得 ,为真命题。 (2)对任意整数 ,存在整数 ,使得 ,为假命题。 (3),存在整数 ,使得对任意整数 与 ,均有 ,为假命题。 8.指出下列公式中的指导变元,量词的辖域,各个体变项的自由出现和约束出现: (1) (2) (3) 解: (1) 指导变元为 ,全称量词 的辖域为 。其中 是约束出现的, 是自由出现的。 (2) 蕴含式前件 中,指导变元为 ,全称量词 的辖域为 ,其中 是约束出现的, 是自由出现的。 (3) 在 ,指导变元为 和 ,辖域为 ,其中 和 约束出现的,而 是自由出现的。在 中,指导变元为 ,辖域为 ,其中 约束出现的,而 是自由出现的。 9.给定解释I如下: (a)个体域 为实数集合R. (b) 中特定元素 (c)特定函数 (d)特定谓词 . 说明下列公式在I下的含义,并指出各公式的真值: (1) . (2) (3) (4) 解: (1) EMBED Equation.KSEE3 \* MERGEFORMAT ,即对任意的实数 和 ,若 ,则 。 (2) 即对任意的实数 和 ,若 ,则 。 (3) 即对任意的实数 和 ,若 ,则 。 (4) 即对任意的实数 和 ,若 ,则 。 其中(1)(3)真值为1,(2)(4)真值为0。 10.给定解释 如下: (a)个体域 N(N为自然数集合) (b) 中特定元素 =2. (c) 上函数 (d) 上谓词 说明下列各式在I的含义,并讨论其真值: (1) . (2) . (3) . (4) . 解:各式在 下的解释为: (1) ,即对任意的自然数 ,有 ; (2) ,即对任意的自然数 和 ,如果有 ,则有 。 (3) ,即
本文档为【离散数学习题解答】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_257258
暂无简介~
格式:doc
大小:3MB
软件:Word
页数:54
分类:理学
上传时间:2013-03-31
浏览量:348