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

离散数学Part1_数理逻辑部分1．将下列命题符号化。P48（1）豆沙包是由面粉和红小豆做成的.（2）苹果树和梨树都是落叶乔木.（3）王小红或李大明是物理组成员.（4）王小红或李大明中的一人是物理组成员.（5）由于交通阻塞，他迟到了.（6）如果交通不阻塞，他就不会迟到.（7）他没迟到，所以交通没阻塞.（8）除非交通阻塞，否则他不会迟到.（9）他迟到当且仅当交通阻塞.分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）—（4）的符号化形式设p:交通阻塞，q:他迟到（5）pq,（6）pq或qp（7）qp或pq,（8）qp或pq（9）pq或pq可见（5）与（7），（6）与（8）相同（等值）3．用真值表判断下面公式的类型P51（1）pr(qp)（2）((pq)(qp))r（3）(pq)(pr)按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式例用等值演算法判断下列公式的类型P59（1）q(pq)（2）(pq)(qp)（3）((pq)(pq))r)解（1）q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，（1）为矛盾式.（2）(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.（3）((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101,111是成真赋值，000,010等是成假赋值.总结：从此例可看出A为矛盾式当且仅当A0A为重言式当且仅当A1例求公式A=(pq)r的主析取范式与主合取范式.P71（1）求主析取范式(pq)r(pq)r（析取范式）①(pq)(pq)(rr)(pqr)(pqr)m6m7②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）（2）求A的主合取范式(pq)r(pr)(qr)（合取范式）①prp(qq)r(pqr)(pqr)M0M2②qr(pp)qr(pqr)(pqr)M0M4③②,③代入①并排序，得(pq)rM0M2M4（主合取范式1．设A与B均为含n个命题变项的公式，判断下列命题是否为真？P85（1）AB当且仅当A与B有相同的主析取范式（2）若A为重言式，则A的主合取范式为0（3）若A为矛盾式，则A的主析取范式为1（4）任何公式都能等值地化成{,}中的公式（5）任何公式都能等值地化成{,,}中的公式（1）为真，这是显然的（2）为假.注意,任何公式与它的主范式是等值的，显然重言式不能与0等值。重言式的主合取范式不含极大项，因而主合取范式为1.（3）的分析类似于（2），矛盾式的主合取范式为0.（4）为假，因为{,}不是完备集，比如矛盾式(pq)q不能化成{,}中的公式.（5）为真，注意{,,}的子集{,}为完备集.2．通过求主范式判公式类型P87（1）(pq)(qp)（2）(pq)q（3）(pq)p（1）重言式，（2）矛盾式，（3）可满足式解用等值演算法求解（1）(pq)(qp)(pq)(qp)(消去)①(pq)(qp)(内移)②(pq)(pq)(pq)(pq)③m2m1m3m0④m0m1m2m3⑤1⑥问由②如何得③？⑤为主析取范式，⑥为主合取范式结论：（1）为重言式（2）(pq)q(pq)q①pqq②0③M0M1M2M3④问：由②如何得③？③为主析取范式，④为主合取范式结论：（2）为矛盾式.（3）(pq)pm0m1①M2M3②请自己等值演算得①与②结论：（3）为可满足式请用真值表再解此题3．已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取范式，及A对应的真值函数.P90答案A的主析取范式为m1m2m7A的主合取范式为M0M3M4M5M6设A对应的真值函数为F，则F(001)=F(010)=F(111)=1F(000)=F(011)=F(100)=F(101)=F(110)=0试说明以上得出答案的理由5.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：P94（1）若赵去，钱也去.（2）李、周两人中必至少有一人去（3）钱、孙两人中去仅去一人.（4）孙、李两人同去或同不去.（5）若周去，则赵、钱也去.用等值演算法分析该公司如何选派他们出国？解此类问题的步骤应为：○1将简单命题符号化○2写出各复合命题○3写出由②中复合命题组成的合取式○4将③中公式化成析取式（最好是主析取范式）解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))③设(1)—(5)构成的合取式为AA=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))④A(pqrsu)(pqrsu)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）例用构造证明法构造下面推理的证明：P112若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，说明天是星期一或星期三是不对的.构造证明（1）设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课（2）形式结构前提：(pq)r,rs,s结论：pq（3）证明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置换2.附加前提证明法（1）欲证：前提：A1,A2,…,Ak结论：CB（2）等价地证明前提：A1,A2,…,Ak,C结论：B（3）理由：(A1A2…Ak)(CB)(A1A2…Ak)(CB)(A1A2…AkC)B(A1A2…AkC)B例构造下面推理的证明P1152是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.用附加前提证明法构造证明（1）设p：2是素数，q：2是合数，r：是无理数，s：4是素数（2）形式结构前提：pq,pr,rs结论：sq（3）证明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段论⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段论请用直接证明法证明之2．在P系统中构造下面推理的证明：P125如果今天是周六，我们就到颐和园或圆明园玩.如果颐和园游人太多，就不去颐和园.今天是周六，并且颐和园游人太多.所以我们去圆明园或动物园玩.（1）设p：今天是周六，q：到颐和园玩，r：到圆明园玩，s：颐和园游人太多t：到动物园玩（2）前提：p(qr),sq,p,s结论：rt（3）证明：①p(qr)前提引入②p前提引入③qr①②假言推理④sq前提引入⑤s前提引入⑥q④⑤假言推理⑦r③⑥析取三段论⑧rt⑦附加2．在一阶逻辑中将下列命题符号化P150（1）大熊猫都可爱（2）有人爱发脾气（3）说所有人都爱吃面包是不对的（4）没有不爱吃糖的人（5）一切人都不一样高（6）并不是所有的汽车都比火车快由于没指出个体域，故用全总个体域（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))),或xy(F(x)F(y)H(x,y)L(x,y))其中，F(x):x是人,H(x,y),x与y相同,L(x,y):x与y一样高（6）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快几点说明使用的是全总个体域(1)与(2)是两个基本公式的使用(3)与(4)是否定式(5)与(6)使用了二元谓词(3)-(6)的不同符号化形式是等值的离散数学Part2_集合论部分2．计数实例P14例求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解方法一方法二令S={x|xZ1x1000},A={x|xSx0(mod5)}B={x|xSx0(mod6)},C={x|xSx0(mod8)}则|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=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,yA且x+2y6}，P104S={1,2,1,3,2,2},求（1）R的集合表达式（2）R1||CBA（3）domR,ranR,fldR（4）RS,R3（5）r(R),s(R),t(R)（1）R={1,1,1,2,2,1,2,2,3,1}（2）R1={1,1,2,1,1,2,2,2,1,3}（3）domR={1,2,3},ranR={1,2},fldR={1,2,3}（4）RS={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,1,1,3};t(R)={1,1,1,2,2,1,2,2,3,1,3,2}2．设A={1,2,3,4}，在AA上定义二元关系R：P106x,y,u,vRx+y=u+v，求R导出的划分.解AA={1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}根据有序对x,y中的x+y=2,3,4,5,6,7,8将A划分