吉大11春学期《离散数学》复习题

久爱奥鹏晓林

吉大11春学期《离散数学》复习题

1. 请给出集合的分配律。
2. 请给出集合的吸收律。
3．设A={1，2，3}，请给出A上的一个既具有对称性又具有反对称性的关系。
4．设A={1，2，3}，请给出A上的所有不同的划分。
5．请给出P→（PQ）的真值表。
6．什么是前束范式？
7．什么是Euler路？
8．请给出3次交代群中的所有元素。
9. R，S是集合A上的两个关系。试证明下列等式：
（1）(R•S)-1= S-1•R-1
（2）(R-1)-1= R
10.请给出一个8元布尔代数。
11.请给出集合的等幂律。
12.请出给集合的吸收律。
13.设A={1，2，3}，B={2 ，4，5}，求A-B，AB。
14.设A={a，b，c}，请给出A上的所有不同的等价关系。
15.设A={1，2，3，4，5，8}，R是模3同余关系，求出A/R。
16.请给出R→（PQ）的真值表。
17.请给出&#61656，PQ，PQ的真值表。
18.设公式G，共有n个不同的原子，问G有多少种不同的解释。
19.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？
20.二、设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错的？为什么。
21．设A={1，2，3}，请给出A上的相等关系和全域关系。
22．设A={1，2，3，4}，R=IA{（1，2），（2，1），（1，3），（3，1），（2，3），（3，2）}，请给出在等价关系R下的所有等价类。
23．请给出PQ，PQ的真值表。
24.{a}S,{a}R,{a,4,{3}}S,{{a},1,3,4}R,R=S,{a}S,{a}R,R,{{a}}RE,{}S,R,{{3},4}。
25.请给出公式R→P的真值表。
26.．什么是恒真公式？举一例。
27.．什么是恒假公式？举一例。
28．设G=xyP(x,y),   D={a,b}，请给出一个满足G的解释。
29．什么是谓词逻辑公式的解释？
30．给出有向树的定义，请举一例。
31．请给出命题xG(x)的真值规定。
32．请给出命题xG(x)的真值规定
33、指出下列公式哪些是恒真的哪些是恒假的：
(1)P（P Q）Q
(2)（P Q）（&#61656Q）
(3)（P Q） （QR）（P R ）
(4)（P Q）（P Q&#61656 Q）
34．什么是谓词逻辑公式的前束范式？
35．什么是Skolem函数？
36．什么是Skolem范式？
37. 叙述谓词逻辑公式G与它的Skolem范式之间的区别与联系。
38．什么是支撑子图？
39．有根的有向图是否一定强连通？有向图中的根是否一定唯一？
40．什么是图中点的度，举一例。
41．什么是图的关联矩阵？
42．什么是图的相邻矩阵？
43. 什么是简单路？举一例。
44．什么是权图？
45. 判断下列公式是恒真？恒假？可满足？
  a) (P(QR))(&#61656(QR))；
  b) P(P(Q&#61614))；
  c) (Q&#61614)(&#61656Q)；
d) (&#61656Q)(PQ)。
46．试举出一个连通的(即漠视为图后是连通的)，但无根的有向图。
47．什么是有向树？举一例。
48．什么是群？举一例。
49．请给出4次交代群中的所有元素。
50．设C*是非零复数乘法群，请给出由-i生成的子群（-i），并求出（i）中各元素的周期。
51．设G为整数加群，H为5的所有倍数组成的加法群，给出H的所有陪集。
52．什么是同态核？举一例。
53．什么是代数格？举一例。
54. 一公司在六个城市c1，c2，…，c6中的每一个都有分公司。从ci到cj的班机旅费由下列矩阵中的第i行第j列元素给出(表示没有直接班机)：
                         0   50      40   25   10
                         50   0   15  20       25
                            15   0   10   20   
                         40   20  10   0   10   25
                         25      20  10    0   55
                         10   25     25   55   0

公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。
55．判断下列公式是恒真？恒假？可满足？
a) (P(QR))(&#61656(QR))；
b) P(P(Q&#61614))；
c) (QP)(PQ)；
d) (PQ)(PQ)。

久爱奥鹏网：www.92open.com