新疆大学2013—2014学年度第二学期期末考试《离散数学》试卷A第一部分 选择题(共20 分)一、单项选择题(本大题共10小题,每题只有一个正确答案,答对一题得2分共20分) 1、对任意集合A 、B 、和C ,下列论断中正确的是: 【 】A. 若A ∈B ,B ⊆C ,则A ∈CB. 若A ∈B ,B ⊆C ,则A ⊆CC. 若A ⊆B ,B ∈C ,则A ∈CD. 若A ⊆B ,B ∈C ,则A ⊆C2、设A={a,{a}},下列式子中正确的有: 【 】A. {a}∈ρ(A)B. a ∈ρ(A)C. {a}⊆ρ(A)D. 以上都不是3、P :我将去镇上。
Q :我有时间。
命题“我将去镇上,当且仅当我有时间”符号化为:【 】A. P →Q B. Q →P C. P ↔Q D. Q ∨¬P4、命题公式:(P ∧(P →Q ))→Q 是 【 】A .矛盾式 B. 可满足式 C. 重言式 D. 不能确定5、谓词公式)())()((x Q y yR x P x →∃∨∀中,量词x ∀的辖域是: 【 】A. ))()((y yR x P x ∃∨∀B. )(x PC. )(),(x Q x PD. )()(y yR x P ∃∨6、在如下各图中,哪一个是欧拉图? 【 】7、设|V|>1,G= < V , E >是强连通图,当且仅当: 【 】A .G 中至少有一条通路B .G 中至少有一条回路C .G 中有通过每个结点至少一次的通路D .G 中有通过每个结点至少一次的回路8、设}}2,1{},1{,{Φ=S ,则 ρ(S) 有多少个元素? 【 】A .3;B .6;C .7;D .8 ;9、集合A={1,2,3,4,5,6,7,8,9,10}上的关系R={<x, y> | x + y = 10},则R 的性质为:【 】A .自反的;B .对称的;C .传递的、对称的;D .反自反的、传递的10、集合A 上的等价关系R ,其等价类集合{[ a]R | a ∈ A}称为: 【 】A .A 与R 的并集,记作A ∪RB .A 与R 的交集,记作A ∩RC .A 与R 的商集,记作A /RD .A 与R 的差集,记作A - R二、填空题(本大题共10小题,每题2分,共20分)11、已知集合A={φ,{φ}},则A 的幂集为 。
12、已知序偶< x-2,18>=< 9,2x-y >,则x= ; y= 。
13、P 、Q 为两个命题,当且仅当 时,P →Q 的真值为0 14、(¬P ∧Q )∨(¬P ∧¬Q )可化简为: 。
15、设}整除,2被,121{Z x x x x M ∈≤≤=,}整除,3被,121{Z x x x x N ∈≤≤=则 M ∩N= ,M – N=16、个体域为自然数集,P (x ):x 为奇数,Q (x ):x 为偶数,则命题“不存在既是奇数又是偶数的自然数”形式化为: 。
17 、设R 为非空集合A 上的等价关系,其等价类记为〔x 〕R 。
x,y ∈A ,若〈x,y 〉∈R ,则〔x 〕R与〔y 〕R 的关系是__ ___,而若〈x,y 〉∉ R ,则〔x 〕R ∩〔y 〕R =______。
18.K n 为汉米顿图,当且仅当 。
19.设A 、B 为集合,|A|=n ,|B|=m ,则A 到B 的二元关系共有 个,A 上的二元关系共有个。
20.一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,它有个度数为1的结点?三、计算题 (本大题共6小题,其中21、22、23三题每题5分,24、25、26三题每题7分,共36分)21、某班有学生50人,有26人在第一次考试中得优,有21人在第二次考试中得优,有14人在两次考试都得优,那么两次考试中都没得优的学生有多少人?22、是否可以分别画出无向简单图,使各点的度与下面给出的序列一致。
如可能,画出符合条件的无向图,如不可能,说明原因。
(1)1,1,2,2,3 (2)1,1,2,2,223、给定个体域D={3,5,7},P (x )解释为“x 是素数”,求公式)(x xP ∀的真值。
24、设集合A={1,2,3},A上关系R={<x , y>|x∈A ∧y∈A∧x +3y<8},关系S={ <2,3>,<4,2>}。
求Dom(R),Ran(R),RοS,R~,r(R)及s(R)25. 求公式q∧(p∨¬q)的析取范式、合取范式、主析取范式,并根据主析取范式直接确定公式的弄真指派和弄假指派。
26、对{2,3,6,12}集合上的整除关系画出哈斯图,并对子集{2,3,6}找出最大元素,最小元素,极大元素,极小元素。
四、证明题(3小题,每题5分,共15分。
)27、证明:A\(B∪C)=(A\B)∩(A\C)28、证明逻辑等价式∀x∀y(P(x)∨Q(y))⇔∀x P(x)∨∀y Q(y)。
(方法不限)五、应用题(本大题共1小题,9分)30、有七位客人入席,A只会讲英语;B会讲汉语;C会讲英语、意大利语及俄语;D会讲汉语及日语;E会讲意大利语及德语;F会讲法语,日语及俄语;G会讲德语和法语。
问主人能否把七位客人安排在一张圆桌上,使每一位客人与左右邻不用翻译便可交谈。
若能安排,请给出一个方案。
新疆大学2013至2014学年第第二学期期末考试{离散数学} 试题A标22、(1)不符合握手定理,所以不能画出图(2)符合条件的无向图为:23、主析取范式:(¬P∧¬Q∧R)∨(¬P∧Q∧R)∨(P∧Q∧¬R)∨(P∧Q∧R)或者主析取范式=m1∧m3∧m6∧m7成真赋值为:001,011,110,111 成假赋值为:000,010,100,10124、dom(R)=A,Ran(R)={1,2},RοS={<1,3>},R-1={<1,1>,<2,1>,<1,2>,<1,3>}r(R)={<1,1>,<1,2>,<2,1>,<3,1>,<2,2>,<3,3>}s(R)={<1,1>,<1,2>,<2,1>,<3,1>,<1,3>}25、不会打这三种球的人数为:X=10A、B、C为会打篮球、排球、网球的人的集合,则有:|S|=30|A|=16,|B|=14,|C|=11,|A∩B|=10,|A∩C|=8,|B∩C|=8,|A∩B∩C|=5 X=|S|-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|)-|A∩B∩C|=1026、R={<1,1>,<1,3>,<1,5>,<1,9>,<1,15>,<1,45>,<3,3>,<3,9>,<3,15>,<3,45>,<9,9>,<9,45>,<15,15>,<15,45>,<45,45>}根据R中元素,可知R是偏序关系,其哈斯图为:最大元:45,最小元:1,极大元:45,极小元:1四、证明题(2小题,每题5分,共10分。
)27、28、证明:∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)五、综合应用题(本题共2小题,每题7分,共14分)29、[解] 能安排,其方案为:H=(A,C,B,E,D,G,F,A)将每个人作为一个项点,如果两个人会讲同一种语言,就在代表他们的二个项点间连一条边,边上标明二人公用的语言,这样就可得一简单无向图G。
所求问题转化为图G中有无Hamilton回路问题。
而上边指出的回路H正好是图G的一条Hamilton回路,因此问题得到解决。
30、令p:他是计算机系本科生q:他是计算机系研究生r:他学过DELPHI语言s:他学过C++语言t:他会编程序前提:(p∨q)→(r∧s),(r∨s)→t结论:p→t证①p P(附加前提)②p∨q T①附加规则③(p∨q)→(r∧s) (前提引入)④r∧s T②③假言推理规则⑤r T④花间规则⑥r∨s T⑤附加规则⑦(r∨s)→t (前提引入)⑧t T⑤⑥假言推理规则新疆大学2013—2014学年度第二学期期末考试《离散数学》试卷A一、单项选择题(本大题共10小题,每题只有一个正确答案,答对一题得2分共20分) 1、设P={x| (x+1)2≤4}, Q={x | x 2+16≥5x} ,则下列各式中成立的是: 【 】A. Q ⊂PB. Q ⊆PC. P ⊂QD. P ⊆Q2、}}2,1{,1,{Φ=S ,下列式子中正确的有: 【 】 A. {1}∈ρ(S) B. 1∈ρ(S) C. {1}⊆ρ(S) D. 以上都不是3、P :你努力,Q :你失败。
“虽然你努力了,但还是失败了”符号化为: 【 】A. P →QB. Q →PC. P ∧QD. P ∨¬Q4、设论域E={a, b },且P(a,a)=T , P(a,b)=F , P(b,a)=T , P(b,b)=F ; 则在下列公式中真值为T的是: 【 】 A .∃x ∀yP (x,y) B .∀x ∀yP (x,y) C .∀xP(x,x) D .∀x ∃yP (x,y)5、谓词公式)())()((x Q y yR x P x →∃∨∀中,变元x 是: 【 】A .自由出现B .约束出现C .既是约束出现,又是自由出现D .以上都不是6、.一个连通的无向图G ,如果它的所有结点的度数都是偶数,那么它具有一条: 【 】A .汉密尔顿回路B .欧拉回路C .汉密尔顿通路D .初级回路7、设|V|>1,G= < V , E >是强连通图,当且仅当: 【 】A .G 中至少有一条通路B .G 中至少有一条回路C .G 中有通过每个结点至少一次的通路D .G 中有通过每个结点至少一次的回路8、由5个结点构成的根树中,其边数m 最多为: 【 】A .2;B .3;C .5;D .4 ;9、设A={1,2,3},A 上二元关系S={<1,1>,<1,2>,<3,2>,<3,3>},则S 具有的性质是:【 】A .自反关系B .传递关系C .对称关系D .反自反关系10、集合A 上的等价关系R ,决定了A 的一个划分,该划分就是: 【 】A .A 与R 的并集A ∪RB .A 与R 的交集,记作A ∩RC .A 与R 的商集,记作A /RD .A 与R 的差集,记作A - R二、填空题(本大题共10小题,每题2分,共20分)11、已知集合A={{1},{1,2}},则A 的幂集为 。