离散数学复习题(请参考课件)

离散数学Part1_数理逻辑部分将下列命题符号化。P48豆沙包是由面粉和红小豆做成的.苹果树和梨树都是落叶乔木.王小红或李大明是物理组成员.王小红或李大明中的一人是物理组成员.由于交通阻塞，他迟到了.如果交通不阻塞，他就不会迟到.他没迟到，所以交通没阻塞.除非交通阻塞，否则他不会迟到.他迟到当且仅当交通阻塞.分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）—（4）的符号化形式设p:交通阻塞，q:他迟到pq,（6）pq或qp（7）qp或pq,（8）qp或pq（9）pq或pq可见（5）与（7），（6）与（8）相同（等值）用真值表判断下面公式的类型P51pr(qp)((pq)(qp))r(pq)(pr)按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式例用等值演算法判断下列公式的类型P59（1）q(pq)（2）(pq)(qp)（3）((pq)(pq))r)解（1）q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，（1）为矛盾式.（2）(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.（3）((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101,111是成真赋值，000,010等是成假赋值.总结：从此例可看出A为矛盾式当且仅当A0A为重言式当且仅当A1例求公式A=(pq)r的主析取范式与主合取范式.P71（1）求主析取范式(pq)r(pq)r（析取范式）=1\*GB3①(pq)(pq)(rr)(pqr)(pqr)m6m7=2\*GB3②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7=2\*GB3②,=3\*GB3③代入=1\*GB3①并排序，得(pq)rm1m3m5（2）求A的主合取范式(pq)r(pr)(qr)（合取范式）=1\*GB3①prp(qq)r(pqr)(pqr)M0M2=2\*GB3②qr(pp)qr(pqr)(pqr)M0M4=3\*GB3③=2\*GB3②,=3\*GB3③代入=1\*GB3①并排序，得(pq)rM0M2设A与B均为含n个命题变项的公式，判断下列命题是否为真？P85AB当且仅当A与B有相同的主析取范式若A为重言式，则A的主合取范式为0若A为矛盾式，则A的主析取范式为1任何公式都能等值地化成{,}中的公式任何公式都能等值地化成{,,}中的公式（1）为真，这是显然的（2）为假.注意,任何公式与它的主范式是等值的，显然重言式不能与0等值。重言式的主合取范式不含极大项，因而主合取范式为1.（3）的分析类似于（2），矛盾式的主合取范式为0.（4）为假，因为{,}不是完备集，比如矛盾式(pq)q不能化成{,}中的公式.（5）为真，注意{,,}的子集{,}为完备集.2．通过求主范式判公式类型P87（1）(p®q)®(Øq®Øp)（2）Ø(p®q)Ùq（3）(p®q)ÙØp（1）重言式，（2）矛盾式，（3）可满足式解用等值演算法求解（1）(pq)(qp)(pq)(qp)(消去)=1\*GB3①(pq)(qp)(内移)=2\*GB3②(pq)(pq)(pq)(pq)=3\*GB3③m2m1m3m0=4\*GB3m0m1m2m31=6\*GB3⑥问由=2\*GB3②如何得=3\*GB3③？=5\*GB3⑤为主析取范式，=6\*GB3⑥为主合取范式结论：（1）为重言式（2）(pq)q(pq)q=1\*GB3①pqq=2\*GB3②0=3\*GB3③M0M1M2M3问：由=2\*GB3②如何得=3\*GB3③？=3\*GB3③为主析取范式，=4\*GB3④为主合取范式结论：（2）为矛盾式.（3）(pq)pm0m1=1\*GB3①M2M3=2\*GB3②请自己等值演算得=1\*GB3①与=2\*GB3②结论：（3）为可满足式请用真值表再解此题3．已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取范式，及A对应的真值函数.P90答案A的主析取范式为m1A的主合取范式为M0M3M4设A对应的真值函数为F，则F(001)=F(010)=F(111)=1F(000)=F(011)=F(100)=F(101)=F(110)=0试说明以上得出答案的理由5.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：P94若赵去，钱也去.李、周两人中必至少有一人去钱、孙两人中去仅去一人.孙、李两人同去或同不去.若周去，则赵、钱也去.用等值演算法分析该公司如何选派他们出国？解此类问题的步骤应为：eq\o\ac(○,1)将简单命题符号化eq\o\ac(○,2)写出各复合命题eq\o\ac(○,3)写出由=2\*GB3②中复合命题组成的合取式eq\o\ac(○,4)将=3\*GB3③中公式化成析取式（最好是主析取范式）解=1\*GB3①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去=2\*GB3②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))=3\*GB3③设(1)—(5)构成的合取式为AA=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))=4\*GB3④A(pqrsu)(pqrsu)结论：由=4\*GB3④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）例用构造证明法构造下面推理的证明：P112若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，说明天是星期一或星期三是不对的.构造证明设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课形式结构前提：(pq)r,rs,s结论：pq证明=1\*GB3①rs前提引入=2\*GB3②s前提引入=3\*GB3③r=1\*GB3①=2\*GB3②拒取式=4\*GB3④(pq)r前提引入=5\*GB3⑤(pq)=3\*GB3③=4\*GB3④拒取式=6\*GB3⑥pq=5\*GB3⑤置换附加前提证明法欲证：前提：A1,A2,…,Ak结论：CB（2）等价地证明前提：A1,A2,…,Ak,C结论：B（3）理由：(A1A2…Ak)(CB(A1A2…Ak)(CB(A1A2…AkC)(A1A2…AkC)B例构造下面推理的证明P1152是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.用附加前提证明法构造证明（1）设p：2是素数，q：2是合数，r：是无理数，s：4是素数（2）形式结构前提：pq,pr,rs结论：sq（3）证明=1\*GB3①s附加前提引入=2\*GB3②pr前提引入=3\*GB3③rs前提引入=4\*GB3④ps=2\*GB3②=3\*GB3③假言三段论=5\*GB3⑤p=1\*GB3①=4\*GB3④拒取式=6\*GB3⑥pq前提引入=7\*GB3⑦q=5\*GB3⑤=6\*GB3⑥析取三段论请用直接证明法证明之在P系统中构造下面推理的证明：P125如果今天是周六，我们就到颐和园或圆明园玩.如果颐和园游人太多，就不去颐和园.今天是周六，并且颐和园游人太多.所以我们去圆明园或动物园玩.设p：今天是周六，q：到颐和园玩，r：到圆明园玩，s：颐和园游人太多t：到动物园玩（2）前提：p(qr),sq,p,s结论：rt（3）证明：=1\*GB3①p(qr)前提引入=2\*GB3②p前提引入=3\*GB3③qr=1\*GB3①=2\*GB3②假言推理=4\*GB3④sq前提引入=5\*GB3⑤s前提引入=6\*GB3⑥q=4\*GB3④=5\*GB3⑤假言推理=7\*GB3⑦r=3\*GB3③=6\*GB3⑥析取三段论=8\*GB3⑧rt=7\*GB3⑦附加 在一阶逻辑中将下列命题符号化P150大熊猫都可爱有人爱发脾气说所有人都爱吃面包是不对的没有不爱吃糖的人一切人都不一样高并不是所有的汽车都比火车快由于没指出个体域，故用全总个体域（1）x(F(x)G(x))其中，F(x):x为大熊猫，G(x):x可爱（2）x(F(x)G(x))其中，F(x):x是人，G(x):x爱发脾气（3）x(F(x)G(x))或x(F(x)G(x))其中，F(x):x是人，G(x):x爱吃面包（4）x(F(x)G(x))或x(F(x)G(x))其中，F(x):x是人，G(x):x爱吃糖（5）x(F(x)y(F(y)H(x,y)L(x,y))),或xy(F(x)F(y)H(x,y)L(x,y))其中，F(x):x是人,H(x,y),x与y相同,L(x,y):x与y一样高（6）xy(F(x)G(y)H(x,y))或xy(F(x)G(y)H(x,y))其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y快几点说明使用的是全总个体域(1)与(2)是两个基本公式的使用(3)与(4)是否定式(5)与(6)使用了二元谓词(3)-(6)的不同符号化形式是等值的离散数学Part2_集合论部分2．计数实例P14例求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解方法一方法二令S={x|xZ1x1000},A={x|xSx0(mod5)}B={x|xSx0(mod6)},C={x|xSx0(mod8)}则|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600．设A={1,2,3},R={<x,y>|x,yA且x+2y6}，P104S={<1,2>,<1,3>,<2,2>},求（1）R的集合表达式（2）R1（3）domR,ranR,fldR（4）RS,R3（5）r(R),s(R),t(R)（1）R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}（2）R1={<1,1>,<2,1>,<1,2>,<2,2>,<1,3>}（3）domR={1,2,3},ranR={1,2},fldR={1,2,3}（4）RS={<1,2>,<1,3>,<2,2>,<2,3>,<3,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}（5）r(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}s(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,