离散数学课后答案

离散数学课后答案习题一6.将下列命题符号化。（1）小丽只能从框里那一个苹果或一个梨.（2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：（1）（pΛ¬q）ν（¬pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（pΛ¬q）ν（¬pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语14.将下列命题符号化.(1)刘晓月跑得快,跳得高.(2)老王是山东人或河北人.(3)因为天气冷,所以我穿了羽绒服.(4)王欢与李乐组成一个小组.(5)李辛与李末是兄弟.(6)王强与刘威都学过法语.(7)他一面吃饭,一面听音乐.(8)如果天下大雨,他就乘班车上班.(9)只有天下大雨,他才乘班车上班.(10)除非天下大雨,他才乘班车上班.(11)下雪路滑,他迟到了.(12)2与4都是素数,这是不对的.(13)“2或4是素数,这是不对的”是不对的.答：(1)p∧q,其中,p:刘晓月跑得快,q:刘晓月跳得高.(2)p∨q,其中,p:老王是山东人,q:老王是河北人.(3)p→q,其中,p:天气冷,q:我穿了羽绒服.(4)p,其中,p:王欢与李乐组成一个小组,是简单命题.(5)p,其中,p:李辛与李末是兄弟.(6)p∧q,其中,p:王强学过法语,q:刘威学过法语.(7)p∧q,其中,p:他吃饭,q:他听音乐.(8)p→q,其中,p:天下大雨,q:他乘班车上班.(9)p→q,其中,p:他乘班车上班,q:天下大雨.(10)p→q,其中,p:他乘班车上班,q:天下大雨.(11)p→q,其中,p:下雪路滑,q:他迟到了.(12)¬(p∧q)或¬p∨¬q,其中,p:2是素数,q:4是素数.(13)¬¬(p∨q)或p∨q,其中,p:2是素数,q:4是素数.16.19.用真值表判断下列公式的类型:(1)p→(p∨q∨r)(2)(p→¬q)→¬q(3)¬(q→r)∧r(4)(p→q)→(¬q→¬p)(5)(p∧r)↔(¬p∧¬q)(6)((p→q)∧(q→r))→(p→r)(7)(p→q)↔(r↔s)答：(1),(4),(6)为重言式.(3)为矛盾式.(2),(5),(7)为可满足式习题二9.用真值表求下面公式的主析取范式.(1)(pνq)ν(¬pΛr)(2)(p→q)→(¬p↔q)答：(1)(2)pq(p→q)→(¬p↔q)001001011110100111111000从真值表可见成真赋值为01,10.于是(p→q)→(¬p↔q)⇔m1∨m211.用真值表求下面公式的主析取范式和主合取范式；(1)(pνq)Λr(2)p→(pνqνr)(3)¬(q→¬p)Λ¬p15.用主析取范式判断下列公式是否等值:(1)(p→q)→r与q→(p→r)(2)¬(pΛq)与(¬pνq)答：(1)(p→q)→r⇔¬(¬p∨q)∨r⇔¬(¬p∨q)∨r⇔p¬∧q∨r⇔p¬∧q∧(r¬∨r)∨(p¬∨p)∧(q¬∨q)∧r⇔p¬∧q∧r∨p¬∧q∧¬r∨p∧q∧r∨p∧¬q∧r∨¬p∧q∧r∨¬p∧¬q∧r=m101∨m100∨m111∨m101∨m011∨m001⇔m1∨m3∨m4∨m5∨m7=∑(1,3,4,5,7).而q→(p→r)⇔¬q∨(¬p∨r)⇔¬q∨¬p∨r⇔(¬p∨p)¬∧q∧(¬r∨r)∨¬p∧(¬q∨q)∧(¬r∨r)∨(¬p∨p)∧(¬q∨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)=m0∨m1∨m4∨m5∨m0∨m1∨m2∨m3∨m1∨m3∨m5∨m7⇔m0∨m1∨m2∨m3∨m4∨m5∨m7⇔∑(0,1,2,3,4,5,7).两个公式的主吸取范式不同,所以(p→q)→rkq→(p→r).16.用主析取范式判断下列公式是否等值:(1)(p→q)→r与q→(p→r)(2)¬(p∧q)与¬(p∨q)答：(1)(p→q)→r)⇔m1∨m3∨m4∨m5∨m7q→(p→r)⇔m0∨m1∨m2∨m3∨m4∨m5∨m7所以(p→q)→r)kq→(p→r)(2)¬(p∧q)⇔m0∨m1∨m2¬(p∨q)⇔m0所以¬(p∧q)k¬(p∨q)习题三15.在自然推理系统P中用附加前提法证明下面各推理:(1)前提:p→(q→r),s→p,q结论:s→r(2)前提:(p∨q)→(r∧s),(s∨t)→u结论:p→u答：(1)证明:①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理(2)证明:①P附加前提引入②p∨q①附加③(p∨q)→(r∧s)前提引入④r∧s②③假言推理⑤④化简⑥s∨t⑤附加⑦(s∨t)→u前提引入⑧u⑥⑦假言推理16.在自然推理系统P中用归谬法证明下面推理:(1)前提:p→¬q,¬r∨q,r∧¬s结论:¬p(2)前提:p∨q,p→r,q→s结论:r∨s答：(1)证明:①P结论否定引入②p→¬q前提引入③¬q①②假言推理④¬r∨q前提引入⑤¬r③④析取三段论⑥r∧¬s前提引入⑦r⑥化简⑧¬r∧r⑤⑦合取⑧
为矛盾式,由归谬法可知,推理正确.(2)证明:①¬(r∨s)结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥¬(r∨s)∧(r∨s)①⑤合取⑥为矛盾式,所以推理正确.18.在自然推理系统P中构造下面推理的证明.(1)如果今天是星期六,我们就要到颐和园或圆明园去玩.如果颐和园游人太多,我们就不去颐和园玩.今天是星期六.颐和园游人太多.所以我们去圆明园玩.(2)如果小王是理科学生,他的数学成绩一定很好.如果小王不是文科生,他必是理科生.小王的数学成绩不好.所以小王是文科学生.(1)令p:今天是星期六;q:我们要到颐和园玩;r:我们要到圆明园玩;s:颐和园游人太多.前提:p→(q∨r),s→¬q,p,s.结论:r.证明①p前提引入②p→q∨r前提引入③q∨r①②假言推理④s前提引入⑤s→¬q前提引入⑥¬q④⑤假言推理⑦
r③⑥析取三段论r¬qs→¬qsq∨rp→q∨rp(2)令p:小王是理科生,q:小王是文科生,r:小王的数学成绩很好.前提:p→r,¬q→p,¬r结论:q证明：①p→r前提引入②¬r前提引入③¬p①②拒取式④¬q→p前提引入⑤q③④拒取式习题四在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.(3)乌鸦都是黑色的.(4)有的人天天锻炼身体.没指定个体域,因而使用全总个体域.答：(1)¬∃x(F(x)∧¬G(x))或∀x(F(x)→G(x)),其中,F(x):x为有理数,G(x):x能表示成分数.(2)¬∀x(F(x)→G(x))或∃x(F(x)∧¬G(x)),其中,F(x):x在北京卖菜,G(x):x是外地人.(3)∀x(F(x)→G(x)),其中,F(x):x是乌鸦,G(x):x是黑色的.(4)∃x(F(x)∧G(x)),其中,F(x):x是人,G(x):x天天锻炼身体.5.在一阶逻辑中将下列命题符号化:(1)火车都比轮船快.(2)有的火车比有的汽车快.(3)不存在比所有火车都快的汽车.(4)“凡是汽车就比火车慢”是不对的.答：因为没指明个体域,因而使用全总个体域(1)∀x∀y(F(x)∧G(y)→H(x,y)),其中,F(x):x是火车,G(y):y是轮船,H(x,y):x比y快.(2)∃x∃y(F(x)∧G(y)∧H(x,y)),其中,F(x):x是火车,G(y):y是汽车,H(x,y):x比y快.(3)¬∃x(F(x)∧∀y(G(y)→H(x,y)))或∀x(F(x)→∃y(G(y)∧¬H(x,y))),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y快.(4)¬∀x∀y(F(x)∧G(y)→H(x,y))或∃x∃y(F(x)∧G(y)∧¬H(x,y)),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y慢.9.给定解释I如下:(a)个体域DI为实数集合\.(b)DI中特定元素⎯a=0.(c)特定函数⎯f(x,y)=x−y,x,y∈DI.(d)特定谓词⎯F(x,y):x=y,⎯G(x,y):xy,x,y∈DI.说明下列公式在I下的含义,并指出各公式的真值:(1)∀x∀y(G(x,y)→¬F(x,y))(2)∀x∀y(F(f(x,y),a)→G(x,y))(3)∀x∀y(G(x,y)→¬F(f(x,y),a))(4)∀x∀y(G(f(x,y),a)→F(x,y))答：(1)∀x∀y(xy→x≠y),真值为1.(2)∀x∀y((x−y=0)→xy),真值为0.(3)∀x∀y((xy)→(x−y≠0)),真值为1.(4)∀x∀y((x−y0)→(x=y)),真值为0.习题五5.给定解释I如下:(a)个体域D={3,4}.(b)⎯f(x)为⎯f(3)=4,⎯f(4)=3.(c)⎯F(x,y)为⎯F(3,3)=⎯F(4,4)=0,⎯F(3,4)=⎯F(4,3)=1.试求下列公式在I下的真值:(1)∀x∃yF(x,y)(2)∃x∀yF(x,y)(3)∀x∀y(F(x,y)→F(f(x),f(y)))答：(1)∀x∃yF(x,y)⇔(F(3,3)∨F(3,4))∧(F(4,3)∨F(4,4))⇔(0∨1)∧(1∨0)⇔1(2)∃x∀yF(x,y)⇔(F(3,3)∧F(3,4))∨(F(4,3)∧F(4,4))⇔(0∧1)∨(1∧0)⇔0(3)∀x∀y(F(x,y)→F(f(x),f(y)))⇔(F(3,3)→F(f(3),f(3)))∧(F(4,3)→F(f(4),f(3)))∧(F(3,4)→F(f(3),f(4)))∧(F(4,4)→F(f(4),f(4)))⇔(0→0)∧(1→1)∧(1→1)∧(0→0)⇔112.求下列各式的前束范式.(1)∀xF(x)→∀yG(x,y);(3)∀xF(x,y)↔∃xG(x,y);答：前束范式不是唯一的.(1)∀xF(x)→∀yG(x,y)⇔∃x(F(x)→∀yG(x,y))⇔∃x∀y(F(x)→G(x,y)).(3)∀xF(x,y)↔∃xG(x,y)⇔(∀xF(x,y)→∃xG(x,y))∧(∃xG(x,y)→∀xF(x,y))⇔(∀x1F(x1,y)→∃x2G(x2,y))∧(∃x3G(x3,y)→∀x4F(x4,y))⇔∃x1∃x2(F(x1,y)→G(x2,y))∧∀x3∀x4(G(x3,y)→F(x4,y))⇔∃x1∃x2∀x3∀x4((F(x1,y)→G(x2,y))∧(G(x3,y)→F(x4,y))).13.将下列命题符号化,要求符号化的公式全为前束范式:(1)有的汽车比有的火车跑得快.(2)有的火车比所有的汽车跑得快.(3)说所有的火车比所有的汽车跑得快是不对的.(4)说有的飞机比有的汽车慢是不对的.答：(1)令F(x):x是汽车,G(y):y是火车,H(x,y):x比y跑得快.∃x(F(x)∧∃y(G(y)∧H(x,y))⇔∃x∃y(F(x)∧G(y)∧H(x,y)).(2)令F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑得快.∃x(F(x)∧∀y(G(y)→H(x,y)))⇔∃x∀y(F(x)∧(Gy)→H(x,y))).;错误的答案:∃x∀y(F(x)∧G(y)→H(x,y)).(3)令F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑得快.¬∀x(F(x)→∀y(G(y)→H(x,y)))⇔¬∀x∀y(F(x)→(G(y)→H(x,y)))⇔¬∀x∀y(F(x)∧G(y)→H(x,y))(不是前束范式)⇔∃x∃y(F(x)∧G(y)∧H(x,y)).(4)令F(x):x是飞机,G(y):y是汽车,H(x,y):x比y跑得慢.¬∃x(F(x)∧∃y(G(y)∧H(x,y)))⇔¬∃x∃y(F(x)∧G(y)∧H(x,y))(不是前束范式)⇔∀x∀y¬(F(x)∧G(y)∧