试卷二十试题与答案.doc

试卷二十试题与答案一、填空 20% (每空 2 分) 个命题变元有个互不等价的极小项。 De-Morga n 定理,i ni nAAAA??????????1 21?=。 3 .公式)(RQP???的主析取范式为。4 .设 P(x) :x 是大象, Q(x) :x 是老鼠, R(x,y) :x比y 重,则命题“大象比老鼠重”的符号化为。 5 .设},,{cbaX?,X 上的关系 R 的关系矩阵是???????????111 011 101 RM ,则? RRM ?。 6 . 在具有 n 个结点的有向图中, 任何基本通路的长度都不超过。 7 .任何图的点连通度)(G?,边连通度)(G?,最小点度)(G?的关系为。 8 .结点数 n(3?n )的简单连通平面图的边数为 m ,则 m与n 的关系为。 的非空子集 H是G 的子群当且仅当若 x,y? H则。 10 .代数系统????,,A 是环,若对运算“· ”还满足则????,,A 是整环。二、选择 10% (每小题 2 分) 1 .集合},2{NnxxA n???对( )运算封闭。 A 、加法; B 、减法; C 、乘法; D、yx?。 为整数集合,m 是任意正整数,mZ 是由模 m 的同余类组成的同余类集合,在mZ 上定义运算] mod ) [(][][mjiji???,则代数系统??? mmZ, 最确切的性质是()。 A 、封闭的代数系统; B 、半群; C 、独异点; D 、群。 3 .设???,N 是偏序格,其中 N 是自然数集合,“≤”是普通的数间“小于等于”关系, 则Nba??, 有??ba ()。 A、a;B、b;C、 max(a , b);D、 min(a , b)。 4 .连通非平凡的无向图 G 有一条欧拉回路当且仅当图 G()。 A 、只有一个奇度结点; B 、只有两个奇度结点; C 、只有三个奇度结点; D 、没有奇度结点。 5 .设无向图??? EVG, 是连通的且 mEnV??, 若( )则 G 是树。 A、 M=N+1 ;B、 n=m+1 ;C、63??nm ;D、63??mn 。三、 12% 逻辑推理: 符号化命题“有些病人相信医生, 但是没有病人相信***, 因此医生都不信***”。用演绎法证明其结论。( P(x) :x 是病人, D(x) :x 是医生, Q(x) :x 是***练****者, L(x , y):x 相信 y) 四、序关系 8% :