应用离散数学(方景龙)课后答案.pdf
《应用离散数学(方景龙)课后答案.pdf》由会员分享，可在线阅读，更多相关《应用离散数学(方景龙)课后答案.pdf（93页珍藏版）》请在冰点文库上搜索。
1.1命题和逻辑连接词习题1.11.下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？
（1）中国有四大发明。
（2）你喜欢计算机吗？
（3）地球上海洋的面积比陆地的面积大。
（4）请回答这个问题！
（5）632=+。
（6）107+x。
（7）园的面积等于半径的平方乘以圆周率。
（8）只有6是偶数，3才能是2的倍数。
（9）若yx=，则zyzx+=+。
（10）外星人是不存在的。
（11）2020年元旦下大雪。
（12）如果311=+，则血就不是红的。
解是真命题的有：
（1）、（3）、（7）、（9）、（12）；是假命题的有：
（5）、（8）；是命题但真值现在不知道的有：
（10）、（11）；不是命题的有：
（2）、（4）、（6）。
2.令p、q为如下简单命题：
p：
气温在零度以下。
q：
正在下雪。
用p、q和逻辑联接词符号化下列复合命题。
（1）气温在零度以下且正在下雪。
（2）气温在零度以下，但不在下雪。
（3）气温不在零度以下，也不在下雪。
（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。
（5）若气温在零度以下，那一定在下雪。
（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。
（7）气温在零度以下是下雪的充分必要条件。
解
（1）qp；
（2）qp；（3）qp；（4）qp；（5）qp；（6））（）（qpqp；（7）qp。
3.令原子命题p：
你的车速超过每小时120公里，q：
你接到一张超速罚款单，用p、q和逻辑联接词符号化下列复合命题。
（1）你的车速没有超过每小时120公里。
（2）你的车速超过了每小时120公里，但没接到超速罚款单。
（3）你的车速若超过了每小时120公里，将接到一张超速罚款单。
（4）你的车速不超过每小时120公里，就不会接到超速罚款单。
（5）你接到一张超速罚款单，但你的车速没超过每小时120公里。
（6）只要你接到一张超速罚款单，你的车速就肯定超过了每小时120公里。
解
（1）p；
（2）qp；（3）qp；（4）qp；（5）pq；（6）pq。
4.判断下列各蕴涵式是真是假。
（1）若211=+，则422=+。
T
（2）若211=+，则522=+。
F（3）若311=+，则422=+。
T（4）若311=+，则522=+。
T（5）若猪会飞，那么422=+。
T（6）若猪会飞，那么522=+。
T（7）若311=+，猪就会飞。
T（8）若211=+，猪就会飞。
F解
（1）T；
（2）F；（3）T；（4）T；（5）T；（6）T；（7）T；（8）F。
5.对下列各语句，说一说其中的“或”是“同或”与“异或”时它们的含义并符号化。
你认为语句想表示的是哪个“或”？
（1）要求有使用过C+或Java的经验。
（2）你必须持护照或选民登记卡才能入境。
（3）要选修离散数学课，你必须已经选修过微积分课或高等数学课。
（4）从通用公司购买一部新车，你就能得到5000元现金回扣，或利率为4的低息汽车贷款。
（5）若下雪超过20公分或温度低于C10，学校就停课。
解
（1）“同或“的含义：
要求有使用过C+或Java或两者都使用过的经验；“异或“的含义：
要求有使用过C+或Java的但不能有两者都使用过的经验。
令原子命题p：
要求有使用C+的经验，q：
要求有使用Java的经验，则同或和异或分别符号化为：
qp和）（）（qpqp。
我认为该语句想表示的是“同或”。
（2）“同或“的含义：
你必须持护照或选民登记卡或两者都持有才能入境；“异或“的含义：
你必须持护照或选民登记卡但不是两者都持有的才能入境。
令原子命题p：
你必须持护照才能入境，q：
你必须持选民登记卡才能入境，则同或和异或分别符号化为：
qp和）（）（qpqp。
我认为该语句想表示的是“同或”。
（3）“同或“的含义：
要选修离散数学课，你必须已经选修过微积分课或高等数学课或者两者都选修过；“异或“的含义：
要选修离散数学课，你必须已经选修过微积分课或高等数学课但不是两们都选修过。
令原子命题p：
要选修离散数学课，你必须已经选修过微积分课，q：
要选修离散数学课，你必须已经选修过高等数学课，则同或和异或分别符号化为：
qp和）（）（qpqp。
我认为该语句想表示的是“同或”。
（4）“同或“的含义：
从通用公司购买一部新车，你就能得到5000元现金回扣，或利率为4的低息汽车贷款；或者两者都得到；“异或“的含义：
从通用公司购买一部新车，你就能得到5000元现金回扣，或利率为4的低息汽车贷款，但不能两者都得。
令原子命题p：
从通用公司购买一部新车，你就能得到5000元现金回扣，q：
从通用公司购买一部新车，你就能得到利率为4的低息汽车贷款，则同或和异或分别符号化为：
qp和）（）（qpqp。
我认为该语句想表示的是“异或”。
（5）“同或“的含义：
若下雪超过20公分或温度低于C10或两者都达到，学校就停课；“异或“的含义：
若下雪超过20公分或温度低于C10且不是两者都达到，学校就停课。
令原子命题p：
若下雪超过20公分，学校就停课，q：
若温度低于C10，学校就停课，则同或和异或分别符号化为：
qp和）（）（qpqp。
我认为该语句想表示的是“同或”。
6.给出下列各蕴涵形式命题的逆命题、否命题和逆否命题。
（1）如果今天下雪，我明天就去滑雪。
（2）只要有测验，我就来上课。
（3）只有当正整数没有1和它自己以外的因数时，它才是质数。
解
（1）逆命题：
如果我明天去滑雪，就今天会下雪；否命题：
如果今天不下雪，我明天就不去滑雪；逆否命题：
如果我明天没去滑雪，今天就没下雪。
（2）逆命题：
我来上课，就有测验；否命题：
只要没有测验，我就不来上课；逆否命题：
我不来上课，就没有测验。
（3）逆命题：
正整数是质数，则它没有1和它自己以外的因数；否命题：
只有当正整数有1和它自己以外的因数时，它才不是质数；逆否命题：
正整数不是质数，则它有1和它自己以外的因数。
7.求下列各个位串的按位NOT；各对位串的按位AND和按位OR：
（1）1011110，0100001
（2）11110000，10101010（3）0001110001，1001001000（4）1111111111，0000000000解
（1）按位NOT分别是0100001，1011110；按位OR是1111111；按位AND是0000000；
（2）按位NOT分别是00001111，01010101；按位OR是11111010；按位AND是10100000；（3）按NOT分别是1110001110，0110110111；按位OR是1001111001；按位AND是0001000000；（4）按NOT分别是0000000000，1111111111；按位OR是1111111111；按位AND是0000000000；8.你会用什么样的布尔检索寻找关于新泽西州海滩的网页？
如果你想找关于泽西岛（在英吉利海峡）海滩的网页呢？
解寻找关于新泽西州海滩网页的布尔检索为：
“NEW”AND“JERSEY”AND“BEACHES”，寻找关于泽西岛（在英吉利海峡）海滩网页的布尔检索为（“JERSEY”AND“BEACHES”）AND（NOT“NEW”）。
9.你会用什么样的布尔检索寻找关于徒步旅行西弗吉尼亚的网页？
如果你想找关于徒步旅行弗吉尼亚的网页，而不是西弗吉尼亚呢？
解寻找关于徒步旅行西弗吉尼亚网页的布尔检索为：
“WALKINGTOUR”AND“VIRGINIA”AND“WEST”，寻找关于徒步旅行弗吉尼亚的布尔检索为（“WALKINGTOUR”AND“VIRGINIA”）AND（NOT“WEST”）。
习题1.21.设p、q和r为如下简单命题：
p：
532=+。
q：
大熊猫产在中国。
r：
复旦大学在广州。
求下列复合命题的真值。
（1）rqp）（
（2）pqpr）（（3））（rqpr（4））（）（rqprqp解因为p、q和r分别取1，1，0。
所以
（1）00）11（）（=rqp；
（2）01）11（0（）（=pqpr；（3）0）011（0）（=rqpr；（4）1）0）11（）011（）（）（=rqprqp。
2.构造下列复合命题的真值表，并由此判断它们是否永真式、永假式和可满足式。
（1）qp
（2）qp（3））（）（qpqp（4））（）（qpqp（5））（）（qpqp（6））（）（qpqp解
（1）是可满足式。
pqqqp0011010110111100
（2）是可满足式。
pqpqp0010011110011100（3）是永真式。
pqqppqp）（）（qpqp001101011111100011111011（4）是可满足式。
pqpqqpqp）（）（qpqp0011111011010010011111100010（5）是永假式。
pqqppqp）（）（qpqp001100010110100010111000（6）是永真式。
pqpqqpqp）（）（qpqp00110110110101100110111000113.构造下列复合命题的真值表，并由此判断它们是否永真式、永假式和可满足式。
（1）rqp）（
（2）pqpr）（（3））（rqpr（4））（）（rqprqp解
（1）是可满足式。
pqrqprqp）（0001000111010010110110001101011101011111
（2）是可满足式。
pqrqp）（qprppqpr）（00001110010010010011101100101000100101000111011001111100（3）是可满足式。
pqrpqrrqp）（rqpr0001111100111011010101110111001110001111101010111100010011100011（4）是可满足式。
pqrrqpqprqp）（）（）（rqprqp000010100101100100101011011010001011010110110101111110104.用真值表证明下面的等价式
（1）BABA=）（
（2）ABAA=）（（3）BABA=（4））（）（ABBABA=（5））（）（）（CABACBA=解
（1）ABBAAB）（BABA0001111010101110001111110000
（2）ABBA）（BAA0000011010111111（3）ABABABA00111011111000011011（4）ABBAABBA）（）（ABBA001111011000100100111111（5）ABCCBBACA）（CBA）（）CABA（00000000001100000101000001110000100000001011011111011011111111115.只使用命题变元p和q能构造多少不同的命题公式真值表？
解能构造出16（2的4次方）种不同的命题公式真值表。
6.用等价演算法证明下面的等价式
（1））（）（qpqpp=
（2））（）（）（）（qpqpqpqp=（3））（）（qpppqp=（4））（）（）（qpqpqp=（5））（）（）（rqprpqp=（6）rqprqrp=）（）（）（（7）rqprqp=）（）（（8））（）（rpqrqp=解
（1）右边）（）（qpqp=）（qqp=1=pp=左边
（2）左边）（）（qpqp）（）（）（）（qqpqqppp=1）（）（1=pqqp）（）（pqqp=）（）（qpqp=右边（3）左边）（pqp）（pqp=1右边）（qpp=）（qpp=1所以左边右边（4）左边）（qp）（）（pqqp）（）（pqqp=）（）（pqqp=）（）（）（）（pqqqppqp=）（）（qpqp=右边（5）左边）（）（rpqp）（）（rpqp）（rqp=）（rqp=右边（6）左边）（）（rqrp）（）（rqrprqp）（rqp）（rqp=）（=右边（7）左边）（rqp）（rqp右边rqp=）（rqp=）（rqp=所以左边右边（8）左边）（rqp）（rqp右边）（rpq=）（rpq=所以左边右边下面4道题是智力游戏题，解题时可以先把语句翻译成命题公式，再利用其成真赋值进行求解。
7.边远村庄的每个人要么总说真话，要么总说谎话。
对旅游者的问题，村民要么回答“是”，要么回答“不”。
假定你在这一地区旅游，走到了一个岔路口，一条岔路通向你想去的遗址，另一岔路通向丛林深处。
此时恰有一村民站在岔路口，问村民什么样的一个问题就能决定走那条路？
解问“如果我问你右边的路是否通向遗址，你会说是，对吗？
”，如果回答“是”，则右边的路通向遗址，否则左边的路通向遗址，具体分析如下：
（1）被问者总说真话且回答“对”。
则右边的路通向遗址。
（2）被问者总说真话且回答“不对”。
则左边的路通向遗址。
（3）被问者总说谎话且回答“对”。
因为是说谎者，所以实际上他会回答“不是”；又因为是说谎者，他回答不是，表明右边的路通向遗址。
（4）被问者总说谎话且回答“不对”。
因为是说谎者，所以实际上他会回答“是”；又因为是说谎者，他回答是，表明右边的路不通向遗址。
现在假设用p表示被问的人总说真话，q表示被问的人回答“对”，r表示如果我问右边的路是否通向遗址，回答是，s表示右边的路通向遗址，则根据以上分析我们有如下表所示的真值表。
pqrs0010010110001111这里，r和s都不是独立的命题变元，可以看成命题p，q的逻辑表达式，即qpr=，）（qpps=8.一个探险者被几个吃人者抓住了。
有两种吃人者：
总是说谎的和永不说谎的。
除非探险者能判断出一位指定的吃人者是说谎者还是说真话者，否则就要被吃人者烤了吃。
探险者只被允许问这位吃人者一个问题。
（1）解释为什么问：
“你说谎吗？
”是不行的。
（2）找一个问题，使探险者可以用来判断该吃人者是说谎者还是说真话者。
解
（1）略
（2）问“如果我问你是否是说谎者，你会说是，对吗？
”，如果回答“是”，则是说谎者，否则不是说谎者。
9.侦探调查了罪案的四位证人。
从证人的话侦探得出的结论是：
如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁不可能都说真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。
侦探能判定这四位证人分别是在说谎还是在说真话吗？
解释你的理由。
解设p：
男管家说的是真话；q：
厨师说的是真话；r：
园丁说的是真话；s：
杂役说的是真话。
则有1=qp，0=rq，1=sr，1=qs。
若1=p，根据1=qp得1=q，再根据0=rq得0=r，再根据1=sr得1=s，与1=qs矛盾。
若0=p，根据1=qp得1=q或0=q。
若0=p，1=q，根据0=rq得0=r，再根据1=sr得1=s，与1=qs矛盾。
若0=p，0=q，根据0=rq得1=r或0=r。
若0=p，0=q，1=r，根据1=sr得1=s或0=s，都1=qs相容。
若0=p，0=q，0=r，根据1=sr得1=s，与1=qs相容。
从以上分析可以可以判定男管家和厨师说谎，但不能判断究竟是园丁还是杂役说真话。
10.四个朋友被认定为非法进入某计算机系统的嫌疑人。
他们已对调查员作了陈述.。
爱丽丝说“卡诺斯干的”，约翰说“我没干”，卡诺斯说“黛安娜干的”，黛安娜说“卡诺斯说是我干的，他说谎”。
（1）如果调查员知道四个嫌疑人中恰有一人说真话，那么谁非法进入了计算机系统？
说明理由。
（2）如果调查员知道四个嫌疑人中恰有一人说慌，那么谁非法进入了计算机系统？
说明理由。
解设p：
卡诺斯干的（爱丽丝说）；q：
我没干（约翰说）；r：
黛安娜干的（卡诺斯说）；s：
卡诺斯说是我干的，他说谎（黛安娜说）。
（1）根据题意，有1）（）（）（）（=srqpsrqpsrqpsrqp若1=srqp，则有1=p，1=q，这表明既是卡诺斯干的，又是约翰干的，矛盾。
若1=srqp，则有1=p，1=q，1=r，这表明既不是卡诺斯干的，又不是约翰干的，也不是黛安娜干的，而只能是爱丽丝干的，但这与1=s矛盾。
若1=srqp，则有1=r，1=q，这表明既是黛安娜干的，又是约翰干的，矛盾。
若1=srqp，则有1=q，这表明是约翰干的，这与1=p，1=r，1=s相容。
所以是约翰非法进入了计算机系统。
（2）略习题1.31.下列命题公式哪些是析取范式哪些是合取范式？
（1））（）（rqqp
（2））（）（qpqp（3）qrp）（（4）qqp）（（5）qp（6）rqp（7）p（8）q（9）1（10）0解是析取范式的有：
（1）、（3）、（5）、（6）、（7）、（8）、（9）、（10）；是合取范式有：
（2）、（4）、（5）、（6）、（7）、（8）、（9）、（10）。
2.在下列由3个命题变元rqp、组成的命题公式中，指出哪些是标准析取范式哪些是标准合取范式？
（1））（）（rqprqp
（2））（）（rqprqp（3）qrqp）（（4））（）（）（rqrpqp（5）rqp（6）rqp（7）1（8）0解是标准析取范式的有：
（1）、（6）、（8）；是标准合取范式的有：
（2）、（5）、（7）。
3.找出一个只含命题变元p、q和r的命题公式，当p和q为真而r为假时命题公式为真，否则为假。
解rqp。
4.找出一个只含命题变元p、q和r的命题公式，在p、q和r中恰有两个为假时命题公式为真，否则为假。
解）（）（）（rqprqprqp。
5.利用等价演算法求下列命题公式的标准析取范式，并求其成真赋值。
（1））（）（pqqp
（2）rqqp）（（3））（）（rqprqp解
（1））（）（pqqp）（）（pqqp=pqqp=）（）（）（）（）（）（qpqpqpqpqp=）（）（）（qpqpqp=除0=p，1=q外，其余均为成真赋值。
（2）rqqp）（rqqp=）（rqqp=0=这是永假式，不存在成真赋值。
（3）（）（rqprqprqprqp=）（rqprqp=）（rqprpqp=）（）（）（）（）（）（rqprqprqprqp=）（）（）（）（rqprqprqprqp）（）（）（）（rqprqprqprqp）（）（）（）（rqprqprqprqp）（）（）（）（rqprqprqprqp=）（）（）（）（rqprqprqprqp这是永真式，所有赋值都是成真赋值。
6.利用等价演算法求下列命题公式的标准合取范式，并求其成假赋值。
（1）pqp）（
（2））（）（rpqp（3）rqpp）（解
（1）pqp）（pqp=）（pqp=）（0=这是永假式，所有赋值都是成假赋值。
（2））（）（rpqp）（）（）（）（rqpqrppp=）（）（）（）（）（）（rqprqprqprqprqprqp=）（）（）（）（rqprqprqprqp=成假赋值为：
0,0,0=rqp；0,1,0=rqp；0,0,1=rqp；1,0,1=rqp（3）rqpp）（rqpp=1=这是永真式，不存在成假赋值。
7.利用真值表法求下列命题公式的标准析取范式和标准合取范式。
（1））（qp
（2））（）（qpqp（3）rqp）（（4））（）（rqprqp解
（1）pqqp）（qp0010011010011110所以标准析取范式为qpm=10标准合取范式为）（）（）（110100qpqpqpMMM=
（2）pqqpqp）（）（qpqp00100011111001111100所以标准析取范式为）（）（1001qpqpmm=标准合取范式为）（）（1100qpqpMM=（3）pqrqprqp）（0001000111010100111110001101011101011111所以标准析取范式为111101100011001mmmmm）（）（）（）（）（rqprqprqprqprqp=标准合取范式为）（）（）（110010000rqprqprqpMMM=（4）pqr）（rqp）（rqp）（）（rqprqp000111001100010100011100100010101010110010111111所以标准析取范式为）（）（111000rqprqpmm=标准合取范式为110101100011010001MMMMMM）（）（）（）（）（）（rqprqprqprqprqprqp=8.假定用n个命题变元给出一个真值表。
证明可依据此表构造一个命题公式，使其真值与此表一致。
证明略9.设A是含有n命题变元的命题公式，证明
（1）A是永真式当且仅当A的标准析取范式含有全部n2个最小项。
（2）A是永假式当且仅当A的标准析取范式不含任何最小项（即标准析取范式为0）。
（3）A是可满足式当且仅当A的标准析取范式至少含有一个最小项。
证明略10.设A是含有n命题变元的命题公式，证明
（1）A是永假式当且仅当A的合取析取范式含有全部n2个最大项。
（2）A是永真式当且仅当A的标准合取范式不含任何最大项（即标准合取范式为1）。
（3）A是可满足式当且仅当A的标准合取范式不包含所有最大项。
证明略11.求下列命题公式的标准析取范式，再根据标准析取范式求标准合取范式。
（1）rqp）（
（2））（）（rqqp解
（1）略
（2））（）（rqqp）（）（rqqp=）（）（）（）（rqqqrpqp=）（）（）（）（rqqqrpqp=）（）（）（）（rqprqprqprqp=111011001000mmmm=所以标准合取范式为110101100010MMMM）（）（）（）（rqprqprqprqp=12.求下列命题公式的标准合取范式，再根据标准合取范式求标准析取范式。
（1）qqp）（
（2）rqp）（（3）qppr）（解
（1）、（3）略
（2）rqp）（rpqqp=）（）（rpqqp=）（）（rpqqp=）（）（rpqqqppqp=）（）（）（）（rpqqp=）（）（）（）（rqprqp=110000mM=所以标准析取范式为111101100011010001mmmmmm）（）（）（rqprqprqp=）（）（）（rqprqprqp13.三个人估计比赛结果，甲说：
“A第1，B第2”，乙说：
“C第2，D第4”，丙说：
“A第2，D第4”。
结果三人估计的都不全对，但都对了一个。
试利用求范式的方法推算出DCBA、分别是第几名？
解略习题1.41.将下列命题公式化成与之等价且仅含，中联接词的命题公式。
（1）qrp）（
（2）prqp）（解略2.
升级会员 