搜索
1.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是素数.1.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)为可满足式.2.4.用等值演算法证明下面等值式:(1)p⇔(p∧q)∨(p∧¬q)(3)¬(p↔q)⇔(p∨q)∧¬(p∧q)(4)(p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)(1)(p∧q)∨(p∧¬q)⇔p∧(q¬∨q)⇔p∧1⇔p.(3)¬(p↔q)⇔¬((p→q)∧(q→p))⇔¬((¬p∨q)∧(¬q∨p))⇔(p∧¬q)∨(q∧¬p)⇔(p∨q)∧(p∨¬p)∧(¬q∨q)∧(¬p∨¬q)⇔(p∨q)∧¬(p∧q)离散数学习题解4(4)(p∧¬q)∨(¬p∧q)⇔(p∨¬p)∧(p∨q)∧(¬q∨¬p)∧(¬q∨q)⇔(p∨q)∧¬(p∧q)2.7.求下列公式的主析取范式,再用主析取范式求合取范式:(1)(p∧q)∨r(2)(p→q)∧(q→r)(1)m1∨m3∨m5∨m6∨m7⇔M0∧M2∧M4(2)m0∨m1∨m3∨m7⇔M2∧M4∧M5∧M62.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)由条件(1)-(4)可知,F的主析取范式为F⇔(¬p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧q∧¬r)⇔m1∨m4∨m3∨m6⇔m1∨m3∨m4∨m6(b)先化简公式F⇔(¬p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧q∧¬r)⇔¬q∧((¬p∧r)∨(p∧¬r))∨q∧((¬p∧r)∨(p∧¬r))⇔(¬q∨q)∧((¬p∧r)∨(p∧¬r))⇔(¬p∧r)∨(p∧¬r)⇔¬(¬(¬p∧r)∧¬(p∧¬r))(已为{¬,∧}中公式)(c)F⇔(¬p∧r)∨(p∧¬r)⇔¬¬(¬p∧r)∨(p∧¬r)⇔¬(¬p∧r)→(p∧¬r)⇔(p∨¬r)→¬(¬p∨r)⇔(r→p)→¬(p→r)(已为{¬,→,↔}中公式)3.14.在自然推理系统P中构造下面推理的证明:(1)前提:p→(q→r),p,q结论:r∨s(2)前提:p→q,¬(q∧r),r结论:¬p(3)前提:p→q结论:p→(p∧q)(4)前提:q→p,q⇒s,s⇒t,t∧r结论:p∧q(5)前提:p→r,q→s,p∧q结论:r∧s(6)前提:¬p∨r,¬q∨s,p∧q结论:t→(r∨s)离散数学习题解5(1)证明:(2)证明:①¬(q∧r)前提引入②¬q∨¬r①置换③r前提引入④¬q②③析取三段论⑤p→q前提引入⑥¬p④⑤拒取式(3)证明:①p→q前提引入②¬p∨q①置换③(¬p∨q)∧(¬p∨p)②置换④¬p∨(p∧q)③置换⑤p→(p∧q)④置换也可以用附加前提证明法,更简单些.(4)证明:①s⇒t前提引入②(s→t)∧(t→s)①置换③t→s②化简④t∧r前提引入⑤t④化简⑥s③⑤假言推理⑦q⇒s前提引入⑧(s→q)∧(q→s)⑦置换⑨s→q⑧化简⑩q⑥⑥假言推理①p→(q→r)前提引入②p前提引入③q→r①②假言推理④q前提引入⑤r③④假言推理⑥r∨s⑤附加律○11q→p前提引入○12p⑩○11假言推理○13p∧q⑩○12合取(5)证明:①p→r前提引入②q→s前提引入③p∧q前提引入④p③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取(6)证明:①t附加前提引入②¬p∨r前提引入③p∧q前提引入④p③化简⑤r②④析取三段论⑥r∨s⑤附加说明:证明中,附加提前t,前提¬q∨s没用上.这仍是正确的推理.离散数学习题解63.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④化简⑥s∨t⑤附加⑦(s∨t)→u前提引入⑧u⑥⑦假言推理3.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)①⑤合取⑥为矛盾式,所以推理正确.3.17.P5317.在自然推理系统P中构造下面推理的证明:只要A曾到过受害者房间并且11点以前没用离开,A就犯了谋杀罪.A曾到过受害者房间.如果A在11点以前离开,看门人会看到他.看门人没有看到他.所以A犯了谋杀罪.离散数学习题解7令p:A曾到过受害者房间;q:A在11点以前离开了;r:A就犯了谋杀罪;s:看门人看到A.前提:p¬∧q→r,p,q→s,¬s;结论:r.证明:①¬s前提引入②q→s前提引入③¬q①②拒取④p前提引入⑤p¬∧q③④合取⑥p¬∧q→r前提引入⑦r⑤⑥假言推理4.4.在一阶逻辑中将下列命题符号化:(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天天锻炼身体.4.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慢.4.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.离散数学习题解84.11.判断下列各式的类型:(1)F(x,y)→(G(x,y)→F(x,y)).(3)∀x∃yF(x,y)→∃x∀yF(x,y).(5)∀x∀y(F(x,y)→F(y,x)).(1)是命题重言式p→(q→p)的代换实例,所以是永真式.(3)在某些解释下为假(举例),在某些解释下为真(举例),所以是非永真式的可满足式.(5)同(3).5.8.在一阶逻辑中将下列命题符号化,要求用两种不同的等值形式.(1)没有小于负数的正数.(2)相等的两个角未必都是对顶角.(1)令F(x):x小于负数,G(x):x是正数.符合化为:∃¬x((F(x)∧G(x))⇔∀x(G(x)→¬G(x)).(2)令F(x):x是角,H(x,y):x和y是相等的,L(x,y):x与y是对顶角.符合化为:¬∀x∀y(F(x)∧F(y)∧H(x,y)→L(x,y))⇔∃x∃y(F(x)∧F(y)∧H(x,y)∧¬L(x,y))⇔∃x(F(x)∧(∃y(F(y)∧H(x,y)∧¬L(x,y))).5.12.求下列各式的前束范式.(1)∀xF(x)→∀yG(x,y);(3)∀xF(x,y)↔∃xG(x,y);(5)∃x1F(x1,x2)→(F(x1)→∃¬x2G(x1,x2)).前束范式不是唯一的.(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))).5.15.在自然推理系统F中构造下面推理的证明:(1)前提:∃xF(x)→∀y((F(y)∨G(y))→R(y)),∃xF(x)结论:∃xR(x).(2)前提:∀x(F(x)→(G(a)∧R(x))),∃xF(x)结论:∃x(F(x)∧R(x))(3)前提:∀x(F