《软件所1994离散》由会员分享，可在线阅读，更多相关《软件所1994离散（3页珍藏版）》请在金锄头文库上搜索。
1、中国科学院软件所中国科学院软件所一九九四年招收硕士学位研究生入学考试试题试题名称：离散数学代数结构部分（33 分）一 （10 分）判断是非（对的打，错的打）1对于任意集合 A，B，C，若且，则。BA CBCA2若和是集合 A 上的等价关系，则也是集合 A 上的等价关系。1R2R21RR 3阶数的群都是交换群。54f 是群到群的群同态映射，若是交换群，则也是交换群。1G2G1G1G5格中的运算的最核心的性质是交换律，结合律和吸收律。,A,二.（10 分）设 R 是集合 A 上的关系，令使且，,| ),(AcbaSRca),(Rbc),(证明：如果 R 是等价关系，则 S 也是等价关系。三 （10
2、 分）设是一个交换群，H是G中的所有有限阶元素构成的集合.证明：,G1）是的正规子群。,H,G2）在商群中，除单位元H外，所有元素的阶都是无限的。,/ HG图论部分（34分）四 （12分）简单图G由图H和两个孤立结点组成，图H不含孤立结点，为平面G图，证明H为连通图。五 （12分）给定图，设，其中是EVG,Vvvvn ,10Eeeen ,21ie关联于结点与的边，称交替序列为联结到的1ivivnnveevev 21100vnv长为n的路，求完全图中任意两点间长为k的路的数目。nK六 （10分）若有向图的所有结点的入度都大于1，则此有向图至少含有两个不同的 有向圈。数理逻辑部分（33分）七 （10分）判断下列各式是否为永真式1)()()(QRPQRQP2)()()(RQPRPQP3)()(RPQRQP4)()()(QRPRQP5)()()()(SQRPSRQP八 （10分）设命题函数：x 属于实数集合A;)(xRA：x 属于实数集合B;)(xRB：xy),(yxL试将命题“并非A中的数都不比B中的数大”按下列要求分别用谓词公 式表示： 1只出现全称量词。 2只出现存在量词。 3量词全部放在左边。九 （13分）证明：，)()(xFx)()()(xTxRx)()()(),()()()(yTyRyyxQyxzFy),()(yxQxy
