中央电大离散数学(本科)考试试题

5．下列等价公式成立的为( b )．

A．PQPQ B．P(QP) P(PQ) 一、单项选择题（每小题3分，本题共15分）

C．Q(PQ) Q(PQ) D．P(PQ) Q

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( a )． 1．若G是一个汉密尔顿图，则G一定是( d )．

A．AB，且AB B．BA，且AB A．平面图 B．对偶图 C．欧拉图 D．连通图 C．AB，且AB D．AB，且AB 2．集合A={1, 2, 3, 4}上的关系R={|x=y且x, yA}，则R2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结的性质为（ c ）．

论成立的是 ( d )． A．不是自反的 B．不是对称的 C．传递的 D．反自反

3．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，

则偏序集上的元素5是集合A的（ b ）．

A．最大元 B．极大元 C．最小元 D．极小元 4．图G如图一所示，以下说法正确的是 ( c ) ．

A．{(a, d)}是割边

B．{(a, d)}是边割集

A．（a）是强连通的 B．（b）是强连通的C．（c）是强连通的 C．{(a, d) ,(b, d)}是边割集

D．{(b, d)}是边割集

D．（d）是强连通的 011005．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”

100113．设图G的邻接矩阵为 可符号化为（ a ）． 10000则G的边数为( b )． A．(x)(A(x)∧B(x)) B．(x)(A(x)∧B(x)) 01001A．6 B．5 C．┐(x)(A(x) →B(x)) D．┐(x)(A(x)∧┐B(x)) 01010C．4 D．3 1．若集合A＝{ a，{a}}，则下列表述正确的是( a )．

4．无向简单图G是棵树，当且仅当( a )． A．{a}A B．{{{a}}}A C．{a，{a}}A D．A

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 2．命题公式（P∨Q）的合取范式是 ( c ) C．G的边数比结点数少1 D．G中没有回路． A．（P∧Q） B．（P∧Q）∨（P∨Q） 5．下列公式 ( c )为重言式． C．（P∨Q） D．（P∧Q）

A．PQPQ B．(Q(PQ)) (Q(PQ)) 3．无向树T有8个结点，则T的边数为( b )． C．(P(QP))(P(PQ)) D．(P(PQ)) Q A．6 B．7 C．8 D．9 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（ a ）． 4．图G如图一所示，以下说法正确的是 ( b )． A．AB，且AB B．AB，但AB A．a是割点 C．AB，但AB D．AB，且AB B．{b, c}是点割集

C．{b, d}是点割集

2．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x,

D．{c}是点割集

yA}，则R的性质为（ b ）．

5．下列公式成立的为( d )．

A．自反的 B．对称的 C．传递且对称的D．反自反且传递的

A．P∧Q  P∨Q B．PQ  PQ

3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中

C．QP  P D．P∧(P∨Q)Q

自反关系有（ b ）个．

1．“小于5的非负整数集合”采用描述法表示为___a___．

A．0 B．2 C．1 D．3

A．{xxN, x<5 } B．{xxR, x<5 }

4．如图一所示，以下说法正确的是 ( d ) ．

C．{xxZ, x<5 } D．{xxQ, x<5 }

A．{(a, e)}是割边

2．设R1，R2是集合A={a,b,c,d}上的两个关系，其中

B．{(a, e)}是边割集

R1={(a,a),(b,b),(b,c), (d,d)}，R2={(a,a),(b,b),(b,c),(c,b),(d,d)}，

C．{(a, e) ,(b, c)}是边割集

则R2是R1的__b____闭包．

D．{(d, e)}是边割集

A．自反 B．对称 C．传递 D．以上答案都不对

5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都

3．设函数f：R→R，f(a)=2a+1；g：R→R，g(a)=a2，则___c___有

是学生”可符号化为（ c ）．

反函数．

A．(x)(A(x)∧B(x)) B．┐(x)(A(x)∧B(x))

A．fg B．gf C．f D．g

C．┐(x)(A(x) →B(x)) D．┐(x)(A(x)∧┐B(x))

010114．已知图G的邻接矩阵为， 1．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且10001R1={, }，R2={, , }，R3={, }，则（ b ）不是从A到B的函数． B．6点，7边 C．6点，8边

10101A．R1和R2 B．R2 C．R3 D．R1和R3 D．5点7边 111102．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，5．无向完全图K4是___a___．

则集合B的最大元、最小元、上界、下界依次为 ( b )． A．汉密尔顿图 B．欧拉图 C．非平面图D．树 A．8、2、8、2 B．无、2、无、2 6．在5个结点的完全二叉树中，若有4条边，则有___b___片树叶． C．6、2、6、2 D．8、1、6、1 A．2 B．3 C．4 D．5

7．无向树T有7片树叶，3个3度结点，其余的都是4度结点，3．若集合A的元素个数为10，则其幂集的元素个数为（ a ）．

则T有__c___个4度结点． A．1024 B．10 C．100 D．1

A．3 B．2 C．1 D．0 4．设完全图Kn有n个结点(n≥2)，m条边，当（ c ）时，Kn中

8．与命题公式P（QR）等值的公式是___a___． 存在欧拉回路．

A．(PQ)R B．(PQ)R C．(PQ)R D．P(QR) A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数

9．谓词公式中量词x的辖域是___b___． 5．设图G的邻接矩阵为 ，

则G有（ d ）．

中央电大离散数学（本科）考试试题

A．5点，8边

B．6点，7边

C．6点，8边 D．5点，7边

1．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( c )． A．{a，{a}}A B．{2}A C．{a}A D．A

deg(v)E2．设图G＝，vV，则下列结论成立的是 ( c ) ． A．deg(v)=2E B． deg(v)=E C． D．vV 3．命题公式（P∨Q）→R的析取范式是 ( d ) A．（P∨Q）∨R B．（P∧Q）∨R C．（P∨Q）∨R D．（P∧Q）∨R 4．如图一所示，以下说法正确的是 ( a )．

A．e是割点

B．{a,e}是点割集 C．{b,e}是点割集

deg(v)vV2Ex(P(x)yR(y)) P(x)yR(y) x(P(x)yR(y))Q(x)xP(x)(xQ(x)xQ(x)) 10．谓词公式的类型是___c___．

A．蕴涵式 B．永假式

1

C．永真式 D．非永真的可满足式

1．设A={1,2,3,4}，B={1,3}，C={-1,0,1,2}，则___a___．

A．BA B．BC C．BA D．BC

2．若集合A的元素个数为10，则其幂集的元素个数为___b___．

A．1000 B．1024 C．1 D．10

3．设集合A={1,2}，B={a,b}，C={}，则(AB)C__c____．

 A．{<1,a,>,<1,b,>,<2,a,>,<2,b,>}

9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各

一个，T的树叶数为 5 ．

10．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y )中的y

6．若集合A的元素个数为10，则其幂集的元素个数为

1024 ．

7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数

为 8 ．

8．若A={1,2}，R={|xA, yA, x+y=10}，则R的自反闭包

为{<1,1>,<2,2>}．

9．结点数v与边数e满足 e=v-1 关系的无向连通图就是树．

Q(x)10．设个体域D＝{a, b, c}，则谓词公式(x)A(x)消去量词后的等值

式为A (a) ∧A (b)∧A（c）

B．{<1,>,<1,>,<2,>,<2,>} 6．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或 C．{<<1,a>,>,<<1,b>,>,<<2,a>,>,<<2,b>,>} ） ．

 D．{{1,2},{a,b},{}} 7．设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，

4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，g={<1,3>,<2,2>,<3,2>,}，则复合函数gf ={<1, 2>, <2, 3>, <3, 则集合B的最大元、最小元、上界、下界依次为___d___． 2>,}

A．8、1、6、1 B． 8、2、8、2 8．设G是一个图，结点集合为V，边集合为E，则G的结点度数 C．6、2、6、2 D．无、2、无、2 之和为2|E|（或“边数的两倍”） 5．有5个结点的无向完全图K5的边数为___a___． 9．无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1

A．10 B．20 C．5 D．25 关系时是树． 6．设完全图Kn有n个结点(n≥2)，m条边，当___b___时，Kn中10．设个体域D＝{1, 2, 3}， P(x)为“x小于2”，则谓词公式(x)P(x) 存在欧拉回路． 的真值为假（或F，或0） ．

A．n为偶数 B．n为奇数 C．m为偶数 D．m为奇数 6．设集合A={2, 3, 4}，B={1, 2, 3, 4}，R且是xA到yBR{x,yxA且yB}的二元关系， 7．一棵无向树T有5片树叶，3个2度分支点，其余的分支点都 是3度顶点，则T有__c___个顶点． 则R的有序对集合为{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，

A．3 B．8 C．11 D．13 <4, 4>} 8．命题公式（P∨Q）→R的析取范式是___b___． 7．如果R是非空集合A上的等价关系，a A，bA，则可推知R

A．（P∧Q）∨R B． （P∨Q）∨R 中至少包含，< b, b >等元素． C．（P∧Q）∨R D．（P∨Q）∨R 8．设G＝是有4个结点，8条边的无向连通图，则从G中9．下列等价公式成立的是___b___． 删去 5 条边，可以确定图G的一棵生成树．

A．PQPQ B． P(QP) P(PQ) 9．设G是具有n个结点m条边k个面的连通平面图，则m等于 C．P(PQ) Q D．Q(PQ) Q(PQ) n+k2

(x)A(x)10．谓词公式xP(x)(xQ(x)xQ(x))的类型是10．设个体域D＝{1, 2}，A(x)为“x大于1”，则谓词公式

__c__． A．蕴涵式 B．永假式C．永真式D．非永真的可满足式 的真值为真（或T，或1）

11．设集合A={1,2,3}，用列举法写出A上的恒等关系IA，全关系

二、填空题（每小题3分，本题共15分） EA： 6．命题公式P(QP)的真值是 T （或1） ． IA = __ IA ={<1,1>,<2,2>,<3,3>}； 7．若图G=中具有一条汉密尔顿回路，则对于结点集V的每 EA ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

个非空子集S，在G中删除S中的所有结点得到的连通分支数 12．设集合A＝{a，b}，那么集合A的幂集是{,{a},{b},{a,b}} 为W，则S中结点数|S|与W满足的关系式为 W|S| ． 13．设集合A={1,2,3}，B={a,b}，从A到B的两个二元关系8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 R={<1,a>,<2,b>,

0 ，则该序列集合构成前缀码． <3,a>}，S={<1,a>,<2,a>,<3,a>}，则R-S=_ R-S={<2,b>}． 9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各 14．设G是连通平面图，v, e, r分别表示G的结点数，边数和面

一个，T的树叶数为 5 ． 数，则v，e和r满足的关系式v-e+r=2． 10．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y )中的y 15．无向连通图G是欧拉图的充分必要条件是结点度数均为偶6．若集合A的元素个数为10，则其幂集的元素个数为 数．

1024 ． 16．设G＝是有6个结点，8条边的连通图，则从G中删7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数去 3 条边，可以确定图G的一棵生成树．

为 8 ． 17．设G是完全二叉树，G有15个结点，其中有8个是树叶，8．若A={1,2}，R={|xA, yA, x+y=10}，则R的自反闭包则G有____14___条边，G的总度数是___28_____，G的分支点

为{<1,1>,<2,2>}． 数是____7____． 9．结点数v与边数e满足 e=v-1 关系的无向连通图就是树． 18．设P，Q的真值为1，R，S的真值为0，则命题公式

(PQ)RSQ的真值为___0_____． 6．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b }}．

7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2 19．命题公式P(QR)的合取范式为P(QR)析

中自反关系有 2 个． 取范式为(PQ)(PR) 8．设图G是有6个结点的连通图，结点的总度数为18，则可从G 20．设个体域为整数集，公式xy(xy0)真值为

中删去 4 条边后使之变成树． ___1_____． 9．设连通平面图G的结点数为5，边数为6，则面数为 3 ． 11．设集合A={1,2,3,4}，B={3,4,5,6}，则：

1AB_____{1,2,3,4,5,6}_____． 10．设个体域D＝{a, b}，则谓词公式(x)A(x)∧（x）B（x）消10， AB___{3,4}_____

去量词后的等值式为(A (a)∧A (b))∧(B（a）∨B（b）) ． 12．设集合A有0n个元素，那么A的幂集合P(A)的元素个数106．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 为 ．

R{x,yxA且yB且x,yAB}00合1A={a,b,c,d}，B={x,y,z}， 13．设集

则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3>． R={,,,,} 010． 7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则关系矩阵MR＝则v，e和r满足的关系式v-e+r=2 ． 14．设集合A={a,b,c,d,e}，A上的二元关系8．设G＝是有6个结点，8条边的连通图，则从G中删去 3 R={,,}，S={,

条边，可以确定图G的一棵生成树． ,}，则R·S={,,} 9．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全 15．无向图G存在欧拉回路，当且仅当G连通且__所有结点的

为偶数 度数全为偶数 10．设个体域D＝{1,2}，则谓词公式xA(x)消去量词后的等值 16．设连通平面图G的结点数为5，边数为6，则面数为 3 ．

式为A(1)A(2) 17．设正则二叉树有n个分支点，且内部通路长度总和为I，外6．命题公式P(QP)的真值是 T （或1） ． 部通路长度总和为E，则有E=___ I+2n 7．若图G=中具有一条汉密尔顿回路，则对于结点集V的每 18．设P，Q的真值为0，R，S的真值为1，则命题公式

(PR)(QS)的真值为_____1___． 个非空子集S，在G中删除S中的所有结点得到的连通分支数

为W，则S中结点数|S|与W满足的关系式为 W|S| ． 19．已知命题公式为G＝(PQ)R，则命题公式G的析取范式8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 是(PQ)R

0 ，则该序列集合构成前缀码． 20．谓词命题公式(x)(P(x)→Q(x)∨R(x，y))中的约束变元为

2

___x___．

三、逻辑公式翻译（每小题4分，本题共12分）

11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．

设P：所有人今天都去参加活动，Q：明天的会议取消， （1分） P Q． （4分） 12．将语句“今天没有人来．” 翻译成命题公式．

设 P：今天有人来， （1分） P． （4分） 13．将语句“有人去上课．” 翻译成谓词公式． 设P(x)：x是人，Q(x)：x去上课，（1分）

(x)(P(x) Q(x))． （4分） 11．将语句“如果你去了，那么他就不去．”翻译成命题公式． 设P：你去，Q：他去，（1分）PQ． （4分） 12．将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 设P：小王去旅游，Q：小李去旅游， （1分） PQ． （4分） 13．将语句“所有人都去工作．”翻译成谓词公式．

设P(x)：x是人，Q(x)：x去工作， （1分） (x)(P(x)Q(x))． （4分） 11．将语句“他不去学校．”翻译成命题公式．

设P：他去学校， （1分） P． （4分） 12．将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设 P：他去旅游，Q：他有时间， （1分） P Q． （4分） 13．将语句“所有的人都学习努力．”翻译成命题公式．

设P(x)：x是人，Q(x)：x学习努力， （1分） （x）(P(x)Q(x))． （3分） 11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成

命题公式．

设P：他接受了这个任务，Q：他完成好了这个任务， （2分） P Q． （6分） 12．将语句“今天没有下雨．”翻译成命题公式．

设P：今天下雨， （2分） P． （6分） 11．将语句“他是学生．”翻译成命题公式． 设P：他是学生，（2分）则命题公式为： P．（6分） 12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式． 设P：明天下雨，Q：我们就去郊游， （2分） 则命题公式为： P Q． （6分） 11．将语句“今天考试，明天放假．”翻译成命题公式．

设P：今天考试，Q：明天放假． （2分） 则命题公式为：P∧Q． （6分） 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式． 设P：我去旅游，Q：我有时间， （2分） 则命题公式为：PQ． （6分） ⑴ 将语句“如果明天不下雨，我们就去春游．”翻译成命题公式． ⑵ 将语句“有人去上课．” 翻译成谓词公式． ⑴设命题P表示“明天下雨”，命题Q表示“我们就去春游”. 则原语句可以表示成命题公式 P→Q. （5分） ⑵设P(x)：x是人，Q(x)：x去上课

则原语句可以表示成谓词公式 (x)(P(x) Q(x))．

R1和R2是自反的，x A，  R1， R2， 则  R1R2，

所以R1∪R2是自反的． （7分） 15．如图二所示的图G存在一条欧拉回路．

v1

e a v5 f v2 h d g v4 n c

b v3 正确． 图二 （3分）

因为图G为连通的，且其中每个顶点的度数为偶数． （7分）

14．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．

正确． （3分）

设x1，x2为自然数且x1x2，则有f(x1)= x1+6 x2+6= f(x2)，故f为单射． （7分）

15．设G是一个有6个结点14条边的连通图，则G为平面图． 错误． （3分）

不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”

13．下面的推理是否正确，试予以说明． (1) （x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）．

错误． （3分） （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆． （7分）

14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．

错误． （3分）

集合A的最大元不存在，a是极大元． （7分）

13．下面的推理是否正确，试予以说明． (1) （x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）．

错误． （3分） （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆． （7分）

14．如图二所示的图G存在一条欧拉回路．

四、判断说明题（每小题7分，本题共14分）

14．┐P∧（P→┐Q）∨P为永真式．

正确． （3分）

┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Q）∨P为真， （5分）

如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，

也即┐P∧（P→┐Q）∨P为真，

所以┐P∧（P→┐Q）∨P是永真式． （7分） 15．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．

错误． （3分） 因为图G为中包含度数为奇数的结点． （7分）

13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图．

错误． （3分） 当图G不连通时图G不为欧拉图． （7分） 14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元是f．

正确． （3分）

对于集合A的任意元素x，均有R（或xRa），所以a是集合A中的最大元．（5分）

14．如果R1和R2是A上的自反关系，则R1∪R2是自反的．

正确． （3分）

图二

错误． （3分） 集合A的最大元与最小元不存在， a是极大元，f是极小元，．

3

束变元．

（1）x量词的辖域为(P(x,y)zQ(y,x,z))，

16．设集合A={1，2，3，4}，R={|x, yA；|xy|=1或

（2分） xy=0}，试

z量词的辖域为Q(y,x,z), （4

（1）写出R的有序对表示； 分）

y量词的辖域为R(y,z)． （6 （2）画出R的关系图；

分）

（3）说明R满足自反性，不满足传递性．

（2）自由变元为(P(x,y)zQ(y,x,z))与F(y)（1）中的y，以及R(y,z)中的z R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} 约束变元为x与Q(y,x,z)中的z，以及R(y,z)中的（3分） y． （12分）

17．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （2）关系图为

（1）（AB）； （2）（A∩B）； （3）A×B．

（1）AB ={{1},{2}} （4分）

1 （2）A∩B ={1,2} （8分）  3 2 （3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，   <{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>, 4 <2, {1,2}>}  18．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，

(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

（1）给出G的图形表示； （2）写出其邻接矩阵； （6分）

（3）求出每个结点的度数； （4）画出其补图的图形． （3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素

的图形表示为： 构成的有序对均在R中，故R在A上是自反的。 1 ） G

（9分） 因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。

17．求PQR的析取范式，合取范式、主析取范式，主合取范式．

P→（R∨Q） ┐P∨(R∨Q)

 ┐P∨Q∨R （析取、合取、主合取范式） （9分）

(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R)

∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式） （12分）

18．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

画出G的图形表示； 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出图G的补图的图形．

五．计算题（每小题12分，本题共36分）

（2）

 0 0

（3）

v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （9分）

（4）补图如下：

01000110邻接矩阵：

110110110100110

16．试求出（P∨Q）→R

的析取范式，合取范式，主合取范式．

（P∨Q）→R┐(P∨Q)∨R (┐P∧┐Q)∨R（析取范式） （3分）

 (┐P∨R)∧

(┐Q∨R)（合取范式） （6分）

 ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P))

 (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P) ∧(┐Q∨R∨┐P)

 (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) （主合取范式） （12分） 17．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算 （1）（AB） （2）（A∪B） （3）（A∪B）（A∩B）． （1）（AB）={{a, b}, 2} （4分） （2）（A∪B）={{a, b}, 1, 2, a, b, {1}} （8分） （3）（A∪B）（A∩B）={{a, b}, 2, a, b, {1}} （12分）

18．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形；

（2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值． （1）G的图形表示为： 01101011 0 10（3）粗线表示最小的生成树，1 1（1）关系图 v1



v2 

  v5

 v4 v3

（3分） （2）邻接矩阵

01100 （6分）

11000110101111010110（3）deg(v1)=2

deg(v2)=3 deg(v3)=4

vdeg(v4)=3 1 deg(v5)=2 v 2  （9分）  v5

（4）补图

16

．

设

谓

词

（2）邻接矩阵：

00 1 111011110v公3



 式v4

x(P(x,y)zQ(y,x,z))yR(y,z)F(y)，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约

（10分）

4

权为7： （12分） 15．求（P∨Q）→（R∨Q）的合取范式． （P∨Q）→（R∨Q）

（P∨Q）∨（R∨Q） （4分） (P∧Q)∨（R∨Q）

(P∨R∨Q)∧(Q∨R∨Q)

(P∨R∨Q) ∧R 合取范式 （12分） 16．设A={0，1，2，3，4}，R={|xA，yA且x+y<0}，S={|xA，yA且x+y3}，试求R，S，RS，R-1，S-1，r(R)．

R=, （2分）

S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分）

RS=， （6分） R-1=， （8分）

12 S-1= S， （10分）

约束变元为x与z． （12分）

16．设集合A={{1},1,2}，B={1,{1,2}}，试计算 （1）（AB）； （2）（A∩B）； （3）A×B．

（1）AB ={{1},2} （4分） （2）A∩B ={1} （8分） （3）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分）

17．设G=，V={ v1，v2，v3，v4 }，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，试

（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． （1）G的图形表示为(如图三)：（3分）

 7

 3   1

 2

 4 2

 5  3

0010（2）邻接矩阵： 0011 1101 1100（6分） （3）v1，v2，

v3，v4结点的度数依次为1，2，3，2 （9分）

（4）补图如图四所示：

r(R)=IA． （12分）

17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．

（10分） 权为13+23+22+32+42=27 21．化简下列集合表示式：

（12分）

15．求（P∨Q）→R的析取范式与合取范式．

（P∨Q）→R  （P∨Q）∨R （4分）  (P∧Q)∨R （析取范式） （8分）

 (P∨R)∧(Q∨R) （合取范式） （12分）

16．设A={0，1，2，3}，R={|xA，yA且x+y<0}，S={|xA，yA且x+y2}，试求R，S，RS，S -1，r(R)．

R=, S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>} （3分）

RS=， （6分） S -1= S， （9分）

r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}． （12分）

17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权． 最优二叉树如图三所

12 示 

=

(ABC)((AB)C)(ABC)(ABC)

=

(A~B~C)(A~BC)(AB~C)(AB((A~B)(~CC))((AB)(~CC))

= ((A~B)E)((AB)E) 设E为全

集

= (A~B)(AB) = A(~BB) = AE = A

A{x|1x2,xR} 22．设，

B{y|y0,yR}，求AB，BA，并画出其图像．

⑴ AB={x|1x2,xR}{y|y0,yR} ={x,y|1x2,y0,x,yR} AB的图像如下图1所示的阴影部分．

图1 图2

⑵BA={y|y0,yR}{x|1x2,xR} ={y,x|1x2,y0,x,yR} BA的图像如上图2所示的阴影部分．

7   5 3    3 4 2   （10分） 1 2

图三

权为13+23+22+32+42=27 （12分）

15．设谓词公式

(x)(A(x,y)(z)B(y,x,z))，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．

（1）x量词的辖域为（3分）

z量词的辖域为

(A(x,y)(z)B(y,x,z))，

B(y,x,z), （6分）

（2）自由变元为

(A(x,y)(z)B(y,x,z))中的y，

5

23．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试：

⑴ 给出G的图形表示；

⑵ 画出其补图的图形．

．⑴ G的图形表示见图3；⑵ G的补图的图形，见图4

（6）（x）R（x） EG(5) （6分） （7）（x）P（x）∧（x）R（x） T(5)(6)I （2分）

19．试证明集合等式A (BC)=(AB)  (AC) ．

证明：设S= A (BC)，T=(AB)  (AC)，若x∈S，则x∈A或x∈BC，即 x∈A或x∈B 且 x∈A或x∈C．

也即x∈AB 且 x∈AC ，即 x∈T，所以ST． （4分）

反之，若x∈T，则x∈AB 且 x∈AC， 即x∈A或x∈B 且 x∈A或x∈C，

也即x∈A或x∈BC，即x∈S，所以TS．

24．构造权为2，3，因此T=S．

19．试证明集合等式A (BC)=(AB)  (AC)．

4，4，5，5，7的最优树。 证明：设S= A (BC)，T=(AB)  (AC)，若x∈S，则x∈A或

x∈BC，即 x∈A或x∈B 且 x∈A或x∈C．

最优树如下图5所示．

也即x∈AB 且 x∈AC ，即 x∈T，所以ST． （4分）

反之，若x∈T，则x∈AB 且 x∈AC， 即x∈A或x∈B 且 x∈A或x∈C，

也即x∈A或x∈BC，即x∈S，所以TS．

18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G

21．设A，B和C是全集与G中的奇数度顶点个数相等(G是G的补图)． E的子集，化简下列集合表示式： 证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数， （3 (ABC)(A~BC)(~ABC) 分） (ABC)(A~BC)(~ABC) 因此，若G中顶点v的度数为奇数，则在G中v的度数一定也是 = 奇数， （6分）

所以G与G中的奇数度顶点个数相等． （8分） (ABC)(A~BC)(ABC)(~ABC)18．试证明集合等式A (BC)=(AB)  (AC) ．

证明：设S= A (BC)，T=(AB)  (AC)，若x∈S，则x∈A或 = ((AC)(B~B))((A~A)(BC))

x∈BC，即 x∈A或x∈B 且 x∈A或x∈C． = ((AC)E)(E(BC))

也即x∈AB 且 x∈AC ，即 x∈T，所以ST． （4

= (AC)(BC) 分） = (AB)C 反之，若x∈T，则x∈AB 且 x∈AC， 即x∈A或x∈B 且 x 22．设A＝{1,2,3}，用列举法给出A上的恒等关系IA，∈A或x∈C， 全关系EA，A上的小于关系 也即x∈A或x∈BC，即x∈S，所以TS． LA{x,yx,yAxy} 因此T=S． 及其逆关系和关系矩阵. 18．设A，B是任意集合，试证明：若AA=BB，则A=B．

证明：设xA，则AA， （1分） IA{1,1,2,2,3,3} （2分）

因为AA=BB，故BB，则有xB， （3

分） ,3,3}EA{1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2 所以AB． （5分）

设xB，则BB， （6分）

LA{1,2,1,3,2,3} （2分） 因为AA=BB，故AA，则有xA，所以1 LA的逆关系LA{2,1,3,1,3,2} BA． （7分）

故得A=B． （8分）

011000（P（x）∧R（x）） （x）P（x）∧（x） MLA001 ML1100. 试证明（x）

AR（x）． 000110证明：  ⑴（x）（P（x）∧R（x）） P

23．图G=，其图形如右图1所示。

⑵ P（a）∧R（a） ES(1) ⑴ 写出G的邻接矩阵；

⑶ P（a） T(2)I ⑵ 画出G的权最小的生成树以及计算出其权值．

⑷（x）P（x） EG(3) ⑸ R（a） T(2)I ⑴ G的邻接矩阵为： （4分）

⑹（x）R（x） EG(5)

⑺（x）P（x）∧（x）R（x） T(5)(6)I 110100 100110 26．试证明 (x)P(x)(x)P(x) 成立。 101001100000011111100110 ⑵ G的权最小的生成树如右上图1所示． （4分）

最小的生成树的权为：1+1+5+2+3=12． （2分）

证明：设公式中的个体变元为a1，a2，…，an，即个体域

E={a1，a2，…，an}，则有：

(x)P(x)(P(a1)P(a2)P(an)) P(a1)P(a2)P(an) (x)P(x)

25．设T是正则二叉树，有t片树叶，证明T的阶数n=2t-1． 证明：根据正则二叉树的概念和握手定理得 ⑴ n=t+i ，i为分支点数 ⑵ n=m+1 ，m为T的边数

⑶ m=2i （正则二叉树的定义） 由⑵和⑶可解得 n1 i= 代入⑴，解出 n=2t-1. 2 26．试证明 ((x)A(x)B)(x)(A(x)B) 成立。 ((x)A(x)B)(x)A(x)B (x)(A(x))B (x)(A(x)B) (x)(A(x)B)

六、证明题（本题共8分）

19．试证明（x）（P（x）∧R（x）） （x）P（x）∧（x）R（x）． 证明： （1）（x）（P（x）∧R（x）） P （2）P（a）∧R（a） ES(1) （2分）

（3）P（a） T(2)I （4）（x）P（x） EG(3) （4分）

（5）R（a） T(2)I

6