离散数学习题集（十五套）

A、?A,?,??满足?对?的分配律；B、?a,b?A,a?b?a?b?b； C、 ?a,b,c?A,若a?b?a?c 则b?c ； D、?a,b?A,有a?(a?b)?b且 a?(a?b)?b。

6、设是偏序集，“?”定义为：?a,b?A,a?b?a|b，则当A=（ ）

时，是格。

A、{1,2,3,4,6,12}； B、{1,2,3,4,6,8,12,14}； C、{1,2,3,?，12}； D、{1,2,3,4}。 7、设?A ,? ,??是由格诱导的代数系统，若对?a,b,c?A，当b?a时，

有（ ）是模格。 A、a?(b?c)?b?(a?c)； B、c?(a?c)?a?(b?c)； C、a?(b?c)?b?(a?c)； D、c?(a?c)?b?(a?c)。 8、在（ ）中，补元是唯一的。

A、有界格； B、有补格； C、分配格； D、有补分配格。

9、在布尔代数?A ,? ,?,??中，b?c?0当且仅当（ ）。

A、b?c； B、c?b； C、b?c； D、c?b。

10、设?A ,? ,?,??是布尔代数，f是从An到A的函数，则（ ） 。 A、 f是布尔代数； B、f能表示成析取范式，也能表示成合取范式； C、若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式； D、若f是布尔函数，它一定能表示成析（合）取范式。

三、8%

设A={1，2}，A上所有函数的集合记为AA, ?是函数的复合运算，试给出AA上运算?的运算表，并指出AA中是否有幺元，哪些元素有逆元。

四、证明42%

1、 设是一个代数系统，*是R上二元运算，?a,b?R是幺元且是独异点。（8分）

a*b?a?b?a?b，则0

n2、 设是n阶循环群，G=(a)，设b=ak，k?I?则 元素b的阶为d，这里d=GCD ( n ,

k )。（10分）

3、 证明如果f是由到的同态映射，g是由到的同态映射，则g?f是由到的同态映射。（6分）

4、 设是一个含幺环，且任意a?A都有a·a=a，若|A|≥3则不

可能是整环。（8分）

5、 K={ 1, 2 , 5 , 10 , 11 , 22 , 55 ,110 }是110的所有整因子的集合，证明：具有全上界110

和全下界1的代数系统< K , LCM , GCD , ˊ >是一个布尔代数。（（10分）

?x?K,x??110x）。

五、布尔表达式 10%

},?,?,设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x1?x3)是布尔代数?{0,1的一个布尔表达式，试写出其析取范式和合取范式。（10分） 答案：

?上

一、填空 20%（每空2分）

1、LCM（x,y）；2、乘法；3、α、δ，γ、δ；4、群；5、G?{a,a,?a?12n?1，an?e}；

6、{?a,b?|a?G,b?G,a*b?H}、m/n；7、{x|x?G 且 f(x)?e?}

二、选择 20%（每小题 2分） 题目 答案

三、8%

解：因为|A|=2，所以A上共有22=4个不同函数。令A?{f1,f2,f3,f4}，其中：

A1 B 2 B，C 3 D 4 A 5 B 6 A 7 A 8 D 9 C 10 C，D f1(1)?1,f1(2)?2;f2(1)?1,f2(2)?1;f3(1)?2,f3(2)?2;f3 f4(1)?2,f4(2)?1

? f1 f2 f3 f1 f2 f4 f1 f2 f3 f2 f2 f3 f3 f4 f2 f3 f2 f3 f4 四、证明 42%

1、（8分） 证明：

f3 f3 f2 f1 f1为AA中的幺元，f1和f4有逆元。

[幺] ?a?R ，0*a?0?a?0?a?a,a*0?a?0?a?0

即 0*a?a*0?a?0为幺元

[乘] ?a,b?R，由于+，·在R封闭。所以a*b?a?b?a?b?R即*在R上封闭。 [群] ?a,b,c?R

(a*b)*c?(a?b?a?b)*c?a?b?a?b?c?(a?b?a?b)?c?a?b?c?a?b?a?c?b?c?a?b?ca*(b*c)?a?b?c?a?b?a?c?b?c?a?b?c所以(a*b)*c?a*(b*c)因此 ， 〈R，*〉是独异点。 2、（10分）

证明：（1）?d?GCD(n,k),设n?d?n1,k?d?k1

?e?ank1?adn1k1?akn1?bn1

（2）若b的阶不为n1，则b阶m

?an由（1）、（2）知，元素b的阶为d

3、（6分）

akm?e,adk1n1e?e，即adn1k1enk1e?e，?k1有因子l，这与d?GCD(n,k)矛盾。

?a,b?A,g?f(a☆b)?g(f(a☆b))?g(f(a)*f(b))?g(f(a))△g(f(b))?g?f(a)△g?f(b) 所以g?f是由到的同态映射。

4、（8分）

证明：反证法：如果是整环，且|A|≥3，则?a?A,a??,a?1且a?a?a 即有a??,a?1??且a?(a?1)?a?a?a?a?a??，这与整环中无零因子矛盾。

所以不可能是整环。 5、（10分）

（1） 代数系统 是由格

诱导的，其Hasst图为

Hass图中不存在与五元素格和

同构的子格。

所以格是分配格。 （2）?x?K,?x??100/x使得:LCM(x,x?)?110,GCD(x,x?)?1

如:22??即任元素都有补元，所以有补格。 是布尔代数。

110?5,LCM(22,5)?110,GCD(22,5)?122

五、布尔表达式 10%

解：函数表为： x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 E(x1,x2,x3) 0 1 1 1 1 1 1 0 E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)析取范式：

?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)

合取范式：E(x1,x2,x3)?(x1?x?2x3)?(x1?x2?x3)

试卷十三试题与答案

七、 填空 10% （每小题 2分）

1、Z?{x|x?Z?x?0}，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*

运算的幺元是 ，零元是 。 2、代数系统中，|A|>1，如果e和?分别为的幺元和零元，

则e和?的关系为 。

3、设是一个群，是阿贝尔群的充要条件是 。

?4、图的完全关联矩阵

为 。 5

、

一

个

图

是

平

面

图

的

充

要

条

件

是 。