南昌大学本科离散试卷及答案1

南昌大学2007~2008学年第一学期期末考试试卷试卷编号: （A）课程编号： 课程名称：离散数学 考试形式： 闭卷适用班级： 姓名： 学号： 班级学院： 专业： 考试日期:题号 一 题分 20 80得分

三 四 五 六 七 八 九 十 总100

累分人签名考生注意事项：1、本试卷共5页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题（420分）得分 评阅人1、使得公式p→(q∨r)成真的赋值是 使得公式p→(q∨r)成假的赋值是： 2、设个体域为D=1,2,3，试消去公式（x）P(x)∨（y)Q（y)量词的等价式 3、4个元素的集合共有

个不同的划分，并给出三个划分块的划分 4、设A=1,2，求：A×P(A）= 5、无向树T有8片树叶，2个3度分枝点，其余的分枝点都是4度点，问T有 个4度分枝点？第1页共7页二、综合题（1080分）得分 评人1、有向图G.⑴写出G.（2)求G3其中有多少条回路。（3）求G的可达性矩阵。2、用等价演算证明：p→(q∨r）(p∧q）→r3、求命题公式(p→q）→(p∨q）的主析取范式，并求命题公式的成真赋值第2页共7页4、将下列命题符号化.并讨论它们的真值（1）有些实数是有理数.(2）每个自然数都有比它大的自然数。5、证明x)(F）∨G(x)，(）(（x）→R(x)（x）（）（x)F(x)第3页共7页6、设A=1,2,3，4，ARR，22,2,334求R.70、1,(2）01，11,000,0010,0011第4页共7页8710a2，…,a10p1,p5，p6,p2,p6，p7p3，p4p1，p5p6，p7p3p，p3p1，p3p1，p5.如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。离散数学A卷答案一填空题1、成真的赋值是：000，001，010，011，101，110，111，成假的赋值是:100.2、(x）P（x）∨（y）(y）（P（1)∧(2)∧P（3）∨（Q（1)∨Q(2)∨Q(3))31，2，3,4，1，3,2，4，1,4,2,3，2,3，1,4，2，4,1，3，3,4,1，21+C1C21C2+1=1+4+6+3+1=15种4 4 2 44111,2,12,2，1，25T24度分枝点二、综合题M=1、解：⑴ M=R 000

1 1 00 0 01 0 10 0 044第5页共7页110111011110011011011000 ，A3=01100

0 0 0

0 0 0 0 44

44长度为3的路有8条,其中回路3条。3321111123321111123111111002、p→(q∨r）p∨（q∨r）（p∨q）∨r（p∧q)∨r(p∧q)→r

2 2 0 0

44

P=00

1 1 10 0 1（条件等价式）（结合律）(德·摩根律）3、(p∨q）∨（p∨q）（p∧q)∨(p∧q)∨(p∧q）(主析取范式）∑0，2，3使得命题公式(p→q)→（p∨q)成真的赋值是：00,10，11。4（1）解:R(x)：xQ(x）:x是有理数。“有些实数是有理数（（）)它的真值为：真（2）设N（x)：x是自然数。G（x，y）:x比y大.“每个自然数都有比它大的自然数。"符号化为：(x)(N（x)→(y)（N(y)∧G（y，x)）它的真值为：真5证明：⑴（x)R（x)⑵R(c）⑶(x)(G（x)→R（x))⑷G（c）→R(c)⑸G(c)⑹⑺F（c)∨G（c)⑻F(c)⑼(x)F（x)

PUS⑴PUS⑶TPUS⑹TUG⑻、6、r(R)=1,2,2,1，2,33,4，1,1,2，23，3,〈4，4sR)=〈1,2,12,〈3,4，，R2=RR=1,1,1,3,2，22,4〉R3R2=1，12,R4=R2R=1,1,1,32,2〉,2，4〉=R2tR)=R∪R2∪R3∪R=1,，1，2，1，31，42，1，2,2,2,,2,4，〈3,4〉第6页共7页7解：是因为11前缀码.

01,10，11，000,111，不是111的前缀。01,11,000,0010,0011是8、解:按题意构造一个二部图G=〈X，E,Y〉,其中X=p1,p

，…，p

,Y=a,a

，…,a

，E表示合格工作岗位关系。如图所示