下载文档原格式
离散数学期末试题及答案HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】326《离散数学》期末考试题(B )一、填空题(每小题3分，共15分)1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ).2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数.3.谓词公式))()(())()((y P y Q y x Q x P x ⌝∧∃∧→∀中量词x ∀的辖域为( ), 量词y ∃的辖域为( ).4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元.5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=⨯||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个.2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧⌝)(； (5)q q p →→)(.4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).三．1.设}}{},,{{c b a A =，}}{},,{},{{c c b a B =，则)(=⋃B A ，)(=⋂B A ，)()(=A P .2.集合},,{c b a A =，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式1)(↑∧q p 的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.四、(10分)设B A f →:且C B g →:，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A =,A 上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R =,1.画出R 的关系图R G .2.判断R 所具有的性质.3.求出R 的关系矩阵R M .六、(10分)利用真值表求命题公式))(())((p q r r q p A →→↔→→=的主析取范式和主合取范式.七、(10分) 边数30<m 的简单平面图G ，必存在节点v 使得4)deg(≤v . 八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(B)参考答案一、1. {{a , b }, a , b , ?}， {{a , b }, a , b }，16.2.92, 27.3.)()(x Q x P →, )()(y P y Q ⌝∧.4. 2, 4, 6, 12.5.4≤，奇数.二、1.22,2,m mn mn ., g , g . ,2,4.，不存在，不存在. 5.连通，3，10.三、1. }}{},,{},,{},{{c c b b a a B A =⋃，}}{{c B A =⋂，{)(=A P ?, {{a , b }}, {{c }}, {{a , b }, {c }}}.2.27933,3,3. 3.0)(↓∨q p .4.{-1，-2，-3，-6，1，2，3，6}. .四、证 对于任意A y x ∈,，若)()(y f x f =，则))(())((y f g x f g =，即))(())((y g f x g f =. 由于g f 是单射，因此y x =，于是f 是单射.例如取},,{},3,2,1(},,{γβα===C B b a A ，令)}2,(),1,{(b a f =，)},3(),,2(),,1{(ββα=g ，这时)},(),,{(βαb a g f = 是单射，而g 不是单射.五、解 1. R 的关系图R G 如下：2.(1)由于R b b ∉),(，所以R 不是自反的. (2)由于R a a ∈),(，所以R 不是反自反的.(3)因为R b d ∈),(，而R d b ∉),(，因此R 不是对称的. (4)因R a c c a ∈),(),,(，于是R 不是反对称的.(5)经计算知R c d a d c c b c a c c a b a a a R R ⊆=)},(),,(),,(),,(),,(),,(),,(),,{( ，进而R 是传递的.综上所述，所给R 是传递的.3.R 的关系矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111R M .六、解 命题公式))(())((p q r r q p A →→↔→→=的真值表如下:由表可知，))(())((p q r r q p A →→↔→→=的主析取范式为A 的主合取范式为)()(r q p r q p A ⌝∨⌝∨∧∨⌝∨⌝=.七、证 不妨设G 的阶数3≥n ，否则结论是显然的. 根据推论1知，63-≤n m . 若G 的任意节点v 的度数均有5)deg(≥v ，由握手定理知n v m v5)deg(2≥=∑.于是m n 52≤，进而652363-⋅≤-≤m n m . 因此30≥m ，与已知矛盾. 所以必存在节点v 使得4)deg(≤v .八、解 设满足要求的r 位数的个数有a r 种，r = 0，1，2，…，则排列计数生成函数65432121211219619431x x x x x x ++++++=,因而38!412194=⋅=a .。
北邮离散数学期末复习题 第一章集合论 一、判断题（1）空集是任何集合的真子集． （ 错 ）（2）{}φ是空集． （ 错 ） （3）{}{}a a a },{∈ （ 对 ） （4）设集合{}{}{}{}AA 22,1,2,1,2,1⊆=则. ( 对 ） （5）如果B A a ⋃∉，则A a ∉或B a ∉． （ 错 ）解 B A a ⋃∉则B A B A a ⋂=⋃∈，即A a ∈且B a ∈，所以A a ∉且B a ∉（6）如果A ∪.,B A B B ⊆=则 （ 对 ）（7）设集合},,{321a a a A =，},,{321b b b B =，则},,,,,{332211><><><=⨯b a b a b a B A （ 错 ）（8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A2到A 的关系． （ 对 ）解 A 2}},1{},0{,{A φ=， =⨯A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><><A A φφ（9）关系的复合运算满足交换律． （ 错 ）（10）.条件具有传递性的充分必要上的关系是集合ρρρρA =ο （ 错 ）（11）设.~,上的传递关系也是则上的传递关系是集合A A ρρ ( 对 ) （12）集合A 上的对称关系必不是反对称的. （ 错 ）（13）设21,ρρ为集合A 上的等价关系, 则21ρρ⋂也是集合A 上的等价关系( 对 )（14）设ρ是集合A 上的等价关系, 则当ρ>∈<b a ,时， ρρ][][b a = ( 对 )（15）设21,ρρ为集合 A 上的等价关系, 则 ( 错 )二、单项选择题（1）设R 为实数集合，下列集合中哪一个不是空集 （ A ）A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2C. {}R x x x x ∈+=且,1|D. {}R x x x ∈-=且,1|2（2）设B A ,为集合，若φ=B A \，则一定有 （ C ）A. φ=B B ．φ≠B C. B A ⊆ D. B A ⊇（3）下列各式中不正确的是 （ C ）A. φφ⊆ B ．{}φφ∈ C. φφ⊂ D. {}}{,φφφ∈ （4）设{}}{,a a A =，则下列各式中错误的是 （ B ）A. {}A a 2∈ B ．{}A a 2⊆ C. {}A a 2}{∈ D. {}Aa 2}{⊆ （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A I ⨯为 （ B ） A. {}><><c c ,2,1, B ．{}><><c c ,2,,1C. {}><><2,,,1c cD. {}><><2,,1,c c（6）设{}b A ,0=，{}3,,1b B =，则B A Y 的恒等关系为 （ A ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0C. {}><><><3,3,,,0,0b bD. {}><><><><0,3,3,,,1,1,0b b（7）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ D ）A. {}><><><><=a b b a a c c a ,,,,,,,1ρB ． {}><><=a c c a ,,,2ρC. {}><><><><=c b a b c c b a ,,,,,,,3ρD. {}><=a a ,4ρ（8）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （ B ）A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈.（9）映射的复合运算满足 （ B ）A. 交换律 B ．结合律 C. 幂等律 D. 分配律（10）设A ，B 是集合，则下列说法中（ C ）是正确的.A ．A 到B 的关系都是A 到B 的映射B ．A 到B 的映射都是可逆的C ．A 到B 的双射都是可逆的D ．B A ⊂时必不存在A 到B 的双射（11）设A 是集合，则（ B ）成立.A ．A A #22#=B ．A X X A⊆↔∈2 C ．{}A2∈φ D ．{}AA 2∈ （12）设A 是有限集（n A =#），则A 上既是≤又是～的关系共有（B ）.A ．0个B ．1个C ．2个D ．n 个三、填空题1. 设}}2,1{,2,1{=A ，则=A2____________.填}}},2,1{,2{}},2,1{,1{},2,1{}},2,1{{},2{},1{,{2A A φ=2.设}}{,{φφ=A ，则A 2= . 填}}},{{},{,{2A A φφφ=3.设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=⋃B A ，则集合B A ⋂中元素的个数=⋂)(#B A .34.设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是，}5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A Y 中元素的个数为 .405.设 },{b a A =, ρ 是 A2 上的包含于关系，,则有ρ= .},,},{,}{},{,},{,}{},{,,,}{,,}{,,,{><><><><><><><><><A A A b b b A a a a A b a φφφφφ6.设21,ρρ为集合 A 上的二元关系, 则=21ρρο .~1~2ρρο7.集合A 上的二元关系ρ为传递的充分必要条件是 ．ρρρ⊆ο8. 设集合{}{}><><==0,2,2,02,1,01ρ上的关系A 及集合A 到集合{}4,2,0=B 的关系=2ρ｛><b a ,|><b a ,A b a B A ∈⨯∈,且∩}=21,ρρο则B ___________________.填 }2,2,0,2,2,0,0,0{><><><><四、解答题1. 设 A d c b a A },,,,{=上的关系 },,,,,,,,,,,,,,,{><><><><><><><><=c d d c a b b a d d c c b b a a ρ（1）写出ρ的关系矩阵；（2）验证ρ是A 上的等价关系；（3）求出A 的各元素的等价类。
离散数学期末考试题附答案和含解析LELE was finally revised on the morning of December 16, 2020一、填空2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 (B⊕C)-A4．公式P RSRP⌝∨∧∨∧)()(的主合取范式为)()(RSPRSP∨⌝∨⌝∧∨∨⌝。
5．若解释I的论域D仅包含一个元素，则)()(xxPxxP∀→∃在I下真值为 1 。
6．设A={1，2，3，4}，A上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。
⎪⎪⎪⎪⎪⎭⎫⎝⎛=1111R⎪⎪⎪⎪⎪⎭⎫⎝⎛=11112R自补图:一个图如果同构于它的补图,则是自补图9．设A={a，b，c，d} ，A上二元运算如下：* a b c dabcda b c db c d ac d a bd a b c那么代数系统<A，*>的幺元是 a ，有逆元的元素为 a,b,c,d ，它们的逆元分别为 a,b,c,d 。
∈}}{{}{aa⊆}}{,{}}{{ΦΦ∈Φ}},{{ΦΦ∈Φ}}{{}{Φ∈ΦΦ⋃ΦΦ332⨯223⨯2n2SRSR SR SR RS SR|}||(|)(,|,{tsApt st sR=∧∈><=ΦΦ⊆→→⨯→→⇒A CX c b a ∈∀,,R >c ,a <,>b ,a <∈R a ,c <,>a ,b <∈>R >c ,b <∈⇐R>b ,a <∈R >c ,a <∈R >c ,b <∈X b a ∈,R >a ,a <∈R >b ,a <∈R >a ,b < ∈∴R>b ,a <∈R >c b,<∈R c b, R >a b,<>∈<∧∈R >c ,a < ∈∴)}()(|{1x g x f G x x =∈且C b a ∈∀,)()(),()(b g b f a g a f ==)()(,)()(1111b g b g b fb f ----==)()()()(1111----===∴b g b g b f b f a f (∴a g b g a g b f a f b ()(*)()(*)()111===---)1-b a ∴C b ∈-1∴≥2)2(--≤k v k e rk F d e r i i ≥=∑=1)(2k e r 2≤2=+-r e v k e e v r e v 22+-≤+-=2)2(--≤k v k e 10,15,5===v e k 2)2(--≤k v k e )()())()((x xQ x xP x Q x P x ∀→∀⇒→∀)(x xP ∀)(c P ))()((x Q x P x →∀)()(c Q c P →)(c Q )(x xQ ∀)()(x xQ x xP ∀→∀⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0000100001010010R M ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==00000000101001012R R R M M M ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==000000000101101023R R R M M M ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==000000001010010134R R R M M M ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=0000100011111111432)(R R R R R t M M M M M > , < b , d > , < c , d > }。
离散数学期末考试试题(配答案)1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。
2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____；=A _____；=B A Y __ _____3. 设{}{}b a B c b a A ,,,,==；则=-)()(B A ρρ__ __________；=-)()(A B ρρ_____ ______。
二．选择题（每小题2分；共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=；A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。
（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ；求)(),(),(R t R s R r 的关系矩阵；并画出R ；)(),(),(R t R s R r 的关系图。
（10分）5. 试判断),(≤z 是否为格？说明理由。
（5分）（注：什么是格？Z 是整数；格：任两个元素；有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。
（10分）2. 设R 是实数集；b a b a f R R R f +=→⨯),(,:；ab b a g R R R g =→⨯),(,:。
求证：g f 和都是满射；但不是单射。
（10分）一；1； _ ∃x ∃y¬P(x)∨Q(y)2； {2} {4；5} {1；3；4；5}3； {{c}；{a ；c}；{b ；c}；{a ；b ；c}} Φ_ 二；B D三；解：主合取方式：p ∧q ∨r ⇔(p ∨q ∨r)∧(p ∨¬q ∨r)∧(¬p ∨q ∨r)= ∏0.2.4主析取范式：p ∧q ∨r ⇔(p ∧q ∧r) ∨(p ∧q ∧¬r) ∨(¬p ∧q ∧r) ∨(¬p ∧¬q ∧r) ∨(p ∧¬q ∧r)= ∑1.3.5.6.7 四；1；证明：编号 公式 依据 （1） （¬B∨C ）∧¬C 前提 （2） ¬B∨C ；¬C （1） （3） ¬B （2） （4） A →B （3） （5） ¬A （3）（4） （6） ¬（¬A∧D ） 前提 （7） A ∨¬D （6） （8）¬D （5）（6）2；证明：要证f 是满射；即∀y ∈R ；都存在（x1；x2）∈R ×R ；使f （x1；x2）=y ；而f （x1；x2）=x1+x2；可取x1=0；x2=y ；即证得；再证g 是满射；即∀y ∈R ；；都存在（x1；x2）∈R ×R ；使g （x1；x2）=y ；而g （x1；x2）=x1x2；可取x1=1；x2=y ；即证得；最后证f 不是单射；f （x1；x2）=f （x2；x1）取x1≠x2；即证得；同理：g （x1；x2）=g （x2；x1）；取x1≠x2；即证得。
离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 以下哪个选项是图的边数与顶点数的关系？A. 边数小于顶点数B. 边数等于顶点数C. 边数大于顶点数D. 边数与顶点数无固定关系答案：D2. 有限自动机的英文缩写是什么？A. FAB. PDAC. TMAD. NFA答案：A3. 布尔代数中，德摩根定律是指什么？A. ¬(A ∧ B) 等于¬ A ∨ ¬ BB. ¬(A ∨ B) 等于¬ A ∧ ¬ BC. A ∧ B 等于¬(A ∨ B)D. A ∨ B 等于¬(¬ A ∧ ¬B)答案：B4. 在命题逻辑中，以下哪个符号表示蕴含？A. ∧B. ∨C. →D. ↔答案：C5. 集合A = {1, 2, 3}，B = {2, 3, 4}，则A ∪ B等于：A. {1, 2, 3, 4}B. {1, 2, 3}C. {2, 3, 4}D. {1, 3, 4}答案：A6. 以下哪个选项是正确的递归定义？A. 一个数是偶数当且仅当它是2的倍数B. 一个数是偶数当且仅当它不是2的倍数C. 一个数是偶数当且仅当它是另一个偶数加1D. 以上都是正确的递归定义答案：A7. 有向图和无向图的主要区别是什么？A. 有向图的边有方向，无向图的边没有方向B. 有向图的顶点有方向，无向图的顶点没有方向C. 有向图的边可以相交，无向图的边不可以相交D. 有向图可以有环，无向图不可以有环答案：A8. 在命题逻辑中，以下哪个公式是矛盾的？A. A ∧ ¬ AB. A ∨ ¬ AC. A → BD. A ∧ B ∧ ¬ A答案：A9. 以下哪个是图的同义术语？A. 网络B. 矩阵C. 树D. 以上全部答案：A10. 以下哪个命题逻辑公式是有效的？A. (A → B) ∧ (B → A)B. (A ∧ B) → AC. (A ∨ B) → AD. (A ∧ B) → B答案：B二、填空题（每题2分，共20分）11. 在命题逻辑中，_________ 表示一个命题是真的，而 _________ 表示一个命题是假的。
大学离散数学期末考试题库和答案一、单项选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示“属于”？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 如果A和B是两个集合，那么A∪B表示什么？A. A和B的交集B. A和B的并集C. A和B的差集D. A和B的补集答案：B3. 以下哪个命题是真命题？A. ∀x∈N, x^2 > xB. ∃x∈N, x^2 = x + 1C. ∀x∈N, x^2 ≥ xD. ∃x∈N, x^2 < x答案：C4. 在图论中，一个无向图的边数为E，顶点数为V，那么这个图的生成树的边数是多少？A. EB. V-1C. VD. E-1答案：B5. 以下哪个算法是用于解决旅行商问题（TSP）的？A. 动态规划B. 贪心算法C. 分支限界法D. 回溯法答案：D6. 在逻辑中，以下哪个符号表示“蕴含”？A. ∧B. ∨C. →D. ↔答案：C7. 以下哪个是二进制数？A. 1010B. 2A3C. 12BD. ZYX答案：A8. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D9. 以下哪个是布尔代数的基本运算？A. 并集B. 交集C. 差集D. 所有以上答案：D10. 在离散数学中，以下哪个概念用于描述两个集合之间的关系？A. 函数B. 映射C. 序列D. 所有以上答案：D二、多项选择题（每题3分，共15分）11. 以下哪些是集合的基本运算？A. 并集B. 交集C. 差集D. 补集答案：ABCD12. 在图论中，以下哪些是图的基本类型？A. 无向图B. 有向图C. 完全图D. 二分图答案：ABCD13. 在逻辑中，以下哪些是命题逻辑的基本连接词？A. 与（∧）B. 或（∨）C. 非（¬）D. 蕴含（→）答案：ABCD14. 在关系数据库中，以下哪些是SQL的基本操作？A. SELECTB. INSERTC. UPDATED. DELETE答案：ABCD15. 在离散数学中，以下哪些是组合数学的基本概念？A. 排列B. 组合C. 二项式系数D. 图论答案：ABC三、填空题（每题3分，共30分）16. 如果集合A={1, 2, 3}，集合B={2, 3, 4}，那么A∩B=______。
离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个选项不是集合的基本运算？A. 并集B. 交集C. 差集D. 乘法答案：D2. 命题逻辑中，以下哪个命题不是基本的逻辑连接词？A. 与（∧）B. 或（∨）C. 非（¬）D. 等于（=）答案：D3. 在图论中，一个图的度数之和等于边数的几倍？A. 1B. 2C. 3D. 4答案：B4. 以下哪个是布尔代数的基本定理？A. 德摩根定律B. 布尔代数的分配律C. 布尔代数的结合律D. 所有选项都是答案：D5. 以下哪个不是组合数学中的计数原理？A. 加法原理B. 乘法原理C. 排列D. 组合答案：C6. 在关系数据库中，以下哪个操作不是基本的数据库操作？A. 选择B. 投影C. 连接D. 排序答案：D7. 以下哪个是有限自动机的组成部分？A. 状态B. 转移C. 输入符号D. 所有选项都是答案：D8. 以下哪个命题逻辑表达式是真命题？A. (p ∧ ¬p) ∨ qB. (p ∨ ¬p) ∧ qC. (p → q) ∧ (q → p)D. (p → q) ∧ (¬p → ¬q)答案：D9. 以下哪个是归纳法证明的基本步骤？A. 基础步骤B. 归纳步骤C. 反证法D. 所有选项都是答案：B10. 以下哪个是图的遍历算法？A. 深度优先搜索（DFS）B. 广度优先搜索（BFS）C. Dijkstra算法D. 所有选项都是答案：A二、简答题（每题10分，共30分）1. 简述命题逻辑中的德摩根定律。
答案：德摩根定律是命题逻辑中描述否定命题的两个重要定律。
它们分别是：- ¬(p ∧ q) ≡ ¬p ∨ ¬q- ¬(p ∨ q) ≡ ¬p ∧ ¬q2. 解释什么是图的连通分量，并给出一个例子。
答案：图的连通分量是指图中最大的连通子图。
离散数学试题(B卷答案1）一、证明题（10分）1)(⌝P∧(⌝Q∧R))∨(Q∧R)∨(P∧R)⇔R证明: 左端⇔(⌝P∧⌝Q∧R)∨((Q∨P)∧R)⇔((⌝P∧⌝Q)∧R))∨((Q∨P)∧R)⇔(⌝(P∨Q)∧R)∨((Q∨P)∧R)⇔(⌝(P∨Q)∨(Q∨P))∧R⇔(⌝(P∨Q)∨(P∨Q))∧R⇔T∧R(置换)⇔R2) ∃x (A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)⇔m0∨m1∨m2∨m7⇔M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D， (C∨D)→⌝E，⌝E→(A∧⌝B)， (A∧⌝B)→(R∨S)⇒R∨S 证明：(1) (C∨D)→⌝E P(2) ⌝E→(A∧⌝B) P(3) (C∨D)→(A∧⌝B) T(1)(2)，I(4) (A∧⌝B)→(R∨S) P(5) (C∨D)→(R∨S) T(3)(4)， I(6) C∨D P(7) R∨S T(5)，I2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明(1)∃xP(x) P(2)P(a) T(1)，ES(3)∀x(P(x)→Q(y)∧R(x)) P(4)P(a)→Q(y)∧R(a) T(3)，US(5)Q(y)∧R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)∧R(a) T(2)(7)，I(9)∃x(P(x)∧R(x)) T(8)，EG(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。
