离散期中练习答案.doc

'1.将下列命题符号化：(1)要是明天不下雨且我有时间，那么我去步行街购物。解：令p：明天下雨，q：我有时间，r：我去步行街购物。（┐p∧q）→r(2)如果小王和小张是一个组，那么这次英语竞赛一定取胜。解：令p：小王和小张是一个组，q：这次英语竞赛一定取胜。p→q(3)除非天下雨，否则他不乘出租车上班。解：令p：天下雨，q：他乘出租车上班q→p(4)明天既不是晴天也不是下雨天。解：令p：明天是晴天，q：明天是下雨天┐p∧┐q2.设命题公式G＝Ø(P®(QÙR))，则使公式G为真的解释有(1,0,0),(1,0,1),(1,1,0).3.通过求主析取范式判断下列命题公式是否等价：(1)G=(P∧Q)∨(ØP∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(ØP∧R))解:G＝(P∧Q)∨(ØP∧Q∧R)＝(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)＝m6∨m7∨m3＝å(3,6,7)H=(P∨(Q∧R))∧(Q∨(ØP∧R))＝(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)＝m6∨m3∨m74.设命题公式G=Ø(P→Q)∨(Q∧(ØP→R)),求G的主析取范式。G=Ø(P→Q)∨(Q∧(ØP→R))=Ø(ØP∨Q)∨(Q∧(P∨R))=(P∧ØQ)∨(Q∧(P∨R))=(P∧ØQ)∨(Q∧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)=m3∨m4∨m5∨m6∨m7=S(3,4,5,6,7)=Π（0，1，2）5．公式p→(q→r)在联结词全功能集{┐，∧}中等值形式之一为┐（p∧q∧┐r）6.构造下面推理的证明：前提：ØA∨B,ØC→ØB,C→D结论：A→D证明：(1)A附加前提引入(2)ØA∨B前提引入(3)B析取三段论（1）（2）(4)ØC→ØB前提引入(5)C拒取式（3）（4）(6)C→D前提引入(8)D假言推理（5）（6）由附加前提证明法可知，推理正确。7、设F(x)：x是鸟，G(x)：x会飞翔。则命题“鸟都会飞”符号化为"x(F(x)->G(x))8设谓词的定义域为{a,b},将表达式"xR(x)→$xS(x)中量词消除，写成与之对应的命题公式是R(a)⋀R(b)→S(a)⋁S(b)9.设一阶逻辑公式：G=("xP(x)∨$yQ(y))→"xR(x)，把G化成前束范式.$x"y"z((ØP(x)⋀ØQ(y))⋁R(z))10设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________;P(A)-P(B)＝__________________________.{3};{{3},{1,3},{2,3},{1,2,3}}. 11.设有限集A,B，|A|=m,|B|=n,则||P(A´B)|=_____________________________.2.2m´n.12某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会打这三种球的共5人。13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记为{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。证明：因为<，>∈(A－B)×CÛ∈(A－B)∧∈CÛ(∈A∧ÏB)∧∈CÛ(∈A∧∈C∧ÏB)∨(∈A∧∈C∧ÏC)Û(∈A∧∈C)∧(ÏB∨ÏC)Û(∈A∧∈C)∧Ø(∈B∧∈C)Û<，>∈(A×C)∧<，>Ï(B×C)Û<，>∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。15.设集合A＝{1,2,3,4},A上的关系R1={<1,4>,<2,3>,<3,2>},R2={<2,1>,<3,2>,<4,3>},则R1·R2=,R2·R1=,R12={<2,4>,<3,3>,<4,2>}{<1,3>,<2,2>,<3,1>};{<2,2>,<3,3>}.16设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,yÎA且x³y},求(1)画出R的关系图；(2)写出R的关系矩阵.答：R={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>,<4,1>,<4,2>,<4,3>,<4,4>}. (1)(2)17设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R具备哪些性质（自反，反自反，对称，反对称，传递）？对称、反对称、传递的18集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，，，，，，，，，，，，}，(1)写出R的关系矩阵。(2)判断R是不是偏序关系，为什么？解(1)R的关系矩阵为：(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；＋≤1，故R是反对称的；可计算R2对应的关系矩阵为：由以上矩阵可知R是传递的。19.设R是集合A={a,b,c,d}.R是A上的二元关系,R={,,,}, (1)求出r(R),s(R),t(R)；(2)画出r(R),s(R),t(R)的关系图.答.(1)r(R)＝R∪IA＝{,,,,,,,},s(R)＝R∪R－1＝{,,,,},t(R)＝R∪R2∪R3∪R4＝{,,,,,,,,}；(2)关系图:20若S={1，2，3，……，19，20}，设R为S上的等价关系，且由x≡y(mod5)所定义，即x,y除5同余。写出由R导出的S的划分和商集S/R。S/R={{1,6,11,16},{2,7,12,17},{3,8,13,18},{4,9,14,19},{5,10,15,20}}21设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。（1）画出偏序集(A,R)的哈斯图；（2）写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；（3）写出A的最大元，最小元，极大元，极小元。.(1)(2)B无上界，也无最小上界。下界1,3;最大下界是3.(3)A无最大元，最小元是1，极大元8,12,9;极小元是1.22设集合A={a,b},B={1,2},则从A到B的所有映射有哪些？其中双射的是哪些？a1={(a,1),(b,1)},a2={(a,2),(b,2)},a3={(a,1),(b,2)},a4={(a,2),(b,1)};a3,a4.23R是实数集合，s,t,j是R上的三个映射，s(x)=x+3,t(x)=2x,j(x)＝x/4,试求复合映射s•t，s•s,s•j,j•t，s•j•t. (1)s•t＝s(t(x))＝t(x)+3＝2x+3＝2x+3.(2)s•s＝s(s(x))＝s(x)+3＝(x+3)+3＝x+6,(3)s•j＝s(j(x))＝j(x)+3＝x/4+3,(4)j•t＝j(t(x))＝t(x)/4＝2x/4=x/2,(5)s•j•t＝s•(j•t)＝j•t+3＝2x/4+3＝x/2+3.'