东 北 大 学 继 续 教 育 学 院离散数学 复习题 一、 有两个小题1．分别说明联结词 Ø、∧、∨、→和«在自然语言中表示什么含义。解：“Ø”表示“…不成立”，“不…”。“∧”表示“并且”、“不但…而且...”、“既…又 ...”等。“∨”表示“或者”， 是可兼取的或。“®”表示 如果… ，则 …；只要… ，就 …； 只有… , 才…； 仅当 … 。“«”表示“当且仅当”、“充分且必要”。2．分别列出 P«Q、 PÚQ、P®Q 、PÙQ 的真值表(填下表)。P Q P«Q PÚQ P®Q PÙQ解：P Q P«Q PÚQ P®Q PÙQF F T F T FF T F T T FT F F T F FT T T T T T二、 1.指出下面的命题公式中哪些是永真式(只写题号即可)。 (1). (P∧(P→Q))→Q (2). P→(P∨Q) 课程名称: 离散数学 (3). (P∧Q)→Q (4). (P∨Q)→P解:(1),(2),(3)为永真式。2.然后对上面的永真式任选其中一个给予证明(方法不限)。证明 (3). (P∧Q)→Q 设前件(P∧Q)为真，则得 Q 为真。所以(P∧Q)→Q 是永真式。 3.上面哪个不是永真式（找出一个即可），请说明它为什么不是永真式。解：(4). (P∨Q)→P 不是永真式。因为如果前件 P∨Q 为真，后件 P 不一定为真。所以(P∨Q)→P 不是永真式。三、 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 "x(B(x)®ØC(x)), $xA(x), "x(ØA(x)Ú C(x)) Þ $xØB(x)解：⑴ $xA(x) P A(a) ES ⑵ ⑴ ⑶ "x(ØA(x)ÚC(x)) P ⑷ ØA(a)ÚC(a) US ⑶ C(a) T I⑸ ⑵⑷ ⑹ "x(B(x)®ØC(x)) P ⑺ B(a)®ØC(a) US ⑹ ⑻ ØB(a) T I⑸ ⑺ ⑼ $xØB((x) EG ⑻四、令全集 E={1,2},A={1}, P(A)表示集合 A 的幂集。（注意：要求有计算过程，不能直接写出计算结果！）1. 指出 P(E)和 P(A)各有多少个元素。即求|P(E)|和|P(A)|。解：因为 P(E)＝{Φ,{1},{2}, {1,2}} 所以 P(E)有 4 个元素。即|P(E)|＝4。P(A)＝{Φ,{1}} 所以 P(A)有 2 个元素。即|P(A)|＝2。 2. 计算 P(E)－P(A)课程名称: 离散数学 T。。。132。。。132M。。132R。。。。132S解： P(E)－P(A)＝{Φ,{1},{2},{1,2}－{Φ,{1}} ＝{{2}, {1,2}}3．计算～AÅE解：因为～A＝E－A={1,2}-{1}={2} ～AÅE＝{2} Å{1,2}＝({2}È{1,2})－({2}Ç{1,2})＝{1,2}－{2}＝{1}五、给定集合 A={1,2,3},定义 A 上的关系如下： R= A×A(完全关系（全域关系）) S={<1,2>,<2,3>,<3,1>} T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>} M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} 1.写出关系 S 的矩阵；再画出上述各个关系的有向图。解：关系 S 的矩阵如下：下面是几个关系的有向图：2. 判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：自反的 反自反的 对称的 反对称的 传递的RSTM解：课程名称: 离散数学 自反的 反自反的 对称的 反对称的 传递的R √ × √ × √S × √ × √ ×T √ × √ × √M √ × × √ √3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。解：T 和 R 是等价关系。 M 是偏序关系。 A/T={{1,2},{3}} A/R={{1,2,3}}4.求复合关系 SoT解：SoT＝{<1,1>,<1,2>,<2,3>,<3,1>,<3,2>}六、写出命题公式 (Q→ØP)→Q 的主合取范式。（要求有解题过程）解： 方法 1：等价变换 (Q®ØP)®Q ÛØ(ØQ∨ØP)∨Q ( 去® ) Û (Q∧P)∨Q ( 摩根定律 ) Û Q ( 吸收律 ) Û (P∧ØP)∨Q （互补、同一律 ） Û (P∨Q)∧(ØP∨Q) ( 分配律 )方法 2：真值表法先列(Q®ØP)®Q 的真值表如下：P Q ØP Q®ØP (Q®ØP)®QF F T T F课程名称: 离散数学 F T T T TT F F T FT T F F T从真值表看出，该命题公式的主合取范式含有大项 M0和 M2，即(P∨Q)和(ØP∨Q)。于是此命题公式的主合取范式为：(Q®ØP)®Q Û (P∨Q)∧(ØP∨Q)七、用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 "xC(x), $x(A(x)ÚB(x)), "x(B(x)®ØC(x)) Þ $xA(x)解： ⑴ $x(A(x)ÚB(x)) P A(a)⑵ ÚB(a) ES ⑴ ⑶ "xC(x) P C(a) US ⑷ ⑶ ⑸ "x(B(x)→ØC(x)) P B(a)→⑹ ØC(a) US ⑸ ⑺ ØB(a) T I⑷ ⑹ A(a) T I⑻ ⑵ ⑺ ⑼ $xA(x)) EG ⑻八、令集合 A={1,{1}},B={1}，P(A)表示 A 的幂集。（注意：要求要有计算过程，不能直接写出计算结果！） (1) A×P(B) (2) A⊕B (3) P(A)－P(B)解： A={1,{1}}, B={1}， A×P(B)⑴ ＝{1,{1}}× {Φ,{1}} ＝{<1,Φ>,<1,{1}>,<{1},Φ>,<{1},{1}>} A⊕B⑵ ＝(AÈB)－(AÇB) =({1,{1}}È{1})－ ({1,{1}} Ç {1})＝{1,{1}}－{1}＝{{1}}。 P(A)⑶ －P(B)＝{Φ,{1},{{1}}, {1,{1}}－{Φ,{1}}课程名称: 离散数学 ＝{{{1}}, {1,{1}}}九、R 是实数集合，给出 R 上的运算：+、－、×、max、min、|x-y|,分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y 的绝对值运算。1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，填下表：+－× max min |x-y|有交换性有结合性有幂等性有幺元有零元2.分别指出 R 对上面哪些运算是半群、独异点和群。3.如果有群，请说明它为什么是群。解:1.+－× max min |x-y|有交换性√ × √ √ √ √有结合性√ × √ √ √ ×有幂等性× × × √ √ ×有幺元√ × √ × × ×有零元× × √ × × ×2. 构成半群的有：<R,＋>， <R,×>， <R,max>, <R,min>. 构成独异点的有： <R,＋>， <R,×>。课程名称: 离散数学 构成群的有： <R,＋>。3. <R,＋>是群的理由： (1) ＋在实数集合内满足封闭性。即 任何 a,b∈R, 有ａ＋ｂ∈R。 (2) ＋是可结合的。 (3) 0 是＋运算的幺元。任何 a∈R, 有 0+a=a=a+0 . (4) 任何实数 a, 都有逆元－a∈R , 使得 (-a)+a=0=a+(-a) .所以<R,＋>是群。十、有三个小题 1. 指出下面各个图中哪些是彼此同构的.解： a、h、i 同构； b、d 同构； c、g 同构； e、f 同构。2.完全二叉树中，设边数为 e，叶结点数为 t，求证 e=2(t-1)。解：由完全 m 叉树公式 (m－1)i=t－1 这里 m＝2，得 (2－1)i=t－1, ∴ i=t－1, ∴T 中总的结点数 v 为: v=i＋t =(t－1)＋t=2t－1，课程名称: 离散数学 abcdfghie 于是 T 的边数 e：e=v－1= 2t－1－1= 2t－2=2(t－1)3．根据给定一组权值:1,6,2,5,3,4,1,6,2 画出一棵最优完全二叉树。要求有画图的过程。解 权值排序并画图：课程名称: 离散数学 1,1,2,2,3,4,5,6,62,2,2,3,4,5,6,62,3,4,4,5,6,64,4,5,5,6,65, 5,6,6,86,6,8,108,10,1212,1830321 121851030841224665