离散数学题库及答案

数理逻辑部分选择、填空及判断 下列语句不是命题的（ A ）。(A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。(C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的。 命题公式P(PP)的类型是（ A ）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 析取范式 A是重言式，那么A的否定式是( A )A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 以下命题公式中，为永假式的是( C )A. p(pqr) B. (pp)p C. (qq)p D. (qp)(pp) 命题公式PQ的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 谓词公式中，变元x是 ( B )A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 命题公式P(QQ)的类型是( A )。(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 析取范式 设B不含变元x，等值于( A ) A. B. C. D. 下列语句中是真命题的是( D )。A你是杰克吗？ B凡石头都可练成金。C如果2+2=4，那么雪是黑的。 D如果1+2=4，那么雪是黑的。 从集合分类的角度看，命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 命题公式pq等价于( D )。 A. pq B. (pq) C. pq D. pq 一个公式在等价意义下，下面写法唯一的是( D )。(A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 下列含有命题p，q，r的公式中，是主析取范式的是 ( D )。(A) (p q r) (p q) (B) (p q r) (p q) (C) (p q r) (p q r) (D) (p q r) (p q r) 设个体域是整数集合，P代表xy(xy)(x-yx)，下面描述正确的是（ C ）。(A) P是真命题 (B) P是假命题(C) P是一阶逻辑公式，但不是命题 (D) P不是一阶逻辑公式 对一阶逻辑公式的说法正确的是( B ).(A) x是约束的，y是约束的，z是自由的； (B) x是约束的，y既是约束的又是自由的，z是自由的；(C) x是约束的，y既是约束的又是自由的，z是约束的；(D) x是约束的，y是约束的，z是约束的； n个命题变元可产生( D )个互不等价的布尔小项。(A) n (B) n2 (C) 2n (D) 2n 命题“没有不犯错误的人”符号化为（ D ）。 设是人，犯错误。(A) (B) (C) (D) 下列命题公式等值的是（ C ） 给定命题公式：，则所有可能使它成真赋值为（ B ），成假赋值为（ C ）。 (A) 111，011；000 (B) 111，011，100，101，110；(C) 000，010，001； (D) 000，110，011，001，100。 给定前提：，则它的有效结论为：（ B ）。 (A) S； (B) ； (C) P； (D) 。 命题：“所有的马都比某些牛跑得快”的符号化公式为：（ C ）。假设：x是马；：x是牛；：x比y跑得快。 (A) ； (B) ；(C) ； (D) 。 设P：a是偶数，Q：b是偶数.R：a +b是偶数，则命题“若a是偶数，b是偶数，则a +b也是偶数”符号化为( C )(A) PQR (B) PQR (C) PQR (D) PQR 表达式中的辖域是( B )(A) P(x,y) (B) P(x,y)Q(z) (C)R(x,y) (D)P(x,y)R(x,y) 判断一个语句是否为命题，首先要看它是否为陈述句，然后再看它是否有唯一的真值。 命题公式(PQ)R的只含联结词和的等值式为： 。 为假言推理规则。 在一阶逻辑中符号化命题“有会说话的机器人。”设M(x):x是机器人； S(x):x是会说话的；上述句子可符号化为： (x)(M(x)S(x) 。 设p:我们爬山,q:我们划船,在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式为（pq） . 设p:小王走路,q:小王唱歌,在命题逻辑中，命题“小王边走路边唱歌”的符号化形式为 （pq） . 量词否定等值式 。 设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为. 若含有n个命题变项的公式A是矛盾式，则A的主合取范式含 2n 个极小项。 取个体域为全体整数的集合，给出下列各公式： (1) (2) (3) 其中公式 (1) 的真值为真，公式 (3) 的真值为假。 若含有n个命题变项的公式A是重言式，则A的主合取范式为 1或T 。 命题公式的所有成假赋值为 000,001,010 。 谓词公式的前束范式为。 在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为 或（设：x是有理数；：x能表示成分数。） 设个体域D1,2,那么谓词公式消去量词后的等值式为 A(1)A(2)(B(1)B(2) . 设P，Q是两个命题，当且仅当P，Q的真值均为1时，的值为1。( ) 谓词公式A是的代换实例，则A是重言式。 ( ) 重言式的主析取范式包含了该公式的所有的极小项。 ( ) 命题公式A(BC)与(AB)C等价。 ( ) 设A，B，C为命题公式，若，则。 ( ) 在一阶谓词公式中，同一变元符号不能够既约束出现又自由出现。( ) 在一阶逻辑中，公式的前束范式是唯一的。 ( )计算 求命题公式(pq)p)q)r的主析取范式。答案：m1m3m5m7 用等值演算法求公式的主析取范式，并由主析取范式求主合取范式。解：主析取范式：主合取范式为： 求公式（PQ）（PR）的主析取范式，并由主析取范式求主合取范式。解：（PQ）（PR）的真值表如下： P Q R PQ PR （PQ）（PR） 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 10 0 00 1 10 0 00 1 10 0 00 0 01 0 11 0 1故主析取范式为：（PQR）（PQR）（PQR）（PQR）主合取范式为：（PRQ）（QPR）（PQR）（PQR） 化公式为前束范式。解：原式 （或）证明 构造下面推理的证明：任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。证明：先将原子命题符号化：设 ：为自然数，：为整数。则前提：，结论： 前提引入 ES规则 前提引入 US规则 假言推理 EG规则 用自然推理系统中，证明下列推理：(x)(A(x)B(x) (x)A(x)(x)B(x)证明：(x)A(x) 附加前提引入A(c) (x)(A(x)B(x) 前提引入A(c)B(c) B(c) 假言推理(x)B(x) (x)A(x)(x)B(x) CP规则所以 (x)(A(x)B(x) (x)A(x)(x)B(x) 判断下面推理是否正确，并证明你的结论。如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。证明：令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C+语言 t:他会编程序 前提：(pq)(rs),(rs)t 结论：pt 证p 附加前提 pq 附加律 (pq)(rs) 前提引入 rs 假言推理 r 化简律 rs 附加律 (rs)t 前提引入 t 假言推理 在自然推理系统中构造下面推理的证明：前提：结论：证明： 前提引入 前提引入 假言推理 前提引入 假言推理 附加律 判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。解：设p:小王今天家里有事，q:小王来开会，r:小张今天看到小王本题推理的形式结构是：前提：,结论：证明：1. 前提引入2. 前提引入3. 1,2假言推理4. 前提引入5. 3,4拒取式集合论部分选择、填空及判断 设集合A=1,2,3,4,B2,4,6,9，那么集合A，B的对称差AB（ C ）.(A) 1,3 (B) 2,4,6 (C) 1,3,6,9 (D) 1,2,3,4,6,9 集合A = 1 , 2 , 3 , 6 ，A上的小于等于关系具有的性质是 （ D ）。 (A) 自反的，对称的，传递的； (B) 反自反的，对称的，传递的；(C) 反自反的，反对称的，传递的；(D) 自反的，反对称的，传递的。 设A=a，b，c，R=，则R具有性质( C ).(A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的 设A,B,C为任意集合，下面结论正确的是( D ) A. 如果,则B=C B. 如果,则A=B C. D. 设，下列各式中( B )是正确的A. domSB B. domSA C. ranSA D. domS ranS = S 令A=1,2,3,4,R=,则s(R)=( B )。(A), (B), (C), (D), 设A=1，2，3，则A上的二元关系有（ C ）个。 (A) 23 (B) 32 (C) (D) 设集合A=1,2,3,5,6,8，A上的二元关系R=|a,bAa(b mod 3),则2R =( B )。(A) 1,2 (B) 2,5,8 (C) 3,6 (D) 1 偏序关系具有的性质是 ( D ) A. 自反的，对称的，传递的 B. 反自反的，对称的，传递的C. 反自反的，反对称的，传递的 D. 自反的，反对称的，传递的 等价关系具有的性质是 ( A )。 A. 自反的、对称的、传递的 B. 反自反的、对称的、传递的C. 反自反的、反对称的、传递的 D. 自反的、反对称的、传递的 集合A=1，2，10上的关系R=|x+y=10，xA，yA，则R的性质是( B )。 A自反的 B对称的 C传递的、对称的 D反自反的、传递的 设A=1,2,3,4,5,6,B=a,b,c,d,e，以下哪一个关系是从A到B的满射函数( B )。 A. f=,B. f=, C. f=, D. f=, 设R是集合A= a,b,c 上的二元关系，且R=,下面命题哪些为真？( B ) R是自反的且是传递的 R是对称的且是反对称的 R是A上的等价关系A. 只有 B. 只有 C. 和 D. 和 设是一个偏序集，其中，A=1,2,3,4,5,6,R是整除关系，下面说法不正确的是( C )A. 4,5,6全是A的极大元 B. A没有最大元C. 6是A的上界 D. 1是A的最大下界 设和都是X上的双射函数，则为( C )A B. C. D. 集合A=1,2,3上所有的等价关系的总数是( B )A. 2 B. 5 C. 9 D. 取决于元素是否为数值 设，则下面命题中唯一正确的是（ D ）(A)f是从X到Y的二元关系，但不是从X到Y的函数(B)f是从X到Y的函数，但不是满射，也不是单射(C)f是从X到Y的满射，但不是单射(D) f是从X到Y的双射 设Xa,b,c，R是X上的二元关系，其关系矩阵为MR，则传递闭包t(R)的关系图为 。 设集合A1,2,3,4，B=a，b，c，则AB 12 . 设A=a,b,c，则A的幂集(A)= 。 设集合A=1,2, 则A上的全域关系 =, 。 设R是实数集合，则 设个体域D1,2,那么谓词公式消去量词后的等值式为 ( A(1)A(2)(B(1)B(2) 。 给定集合和这个集合上的整除关系. 在这个关系下, 该集合的最小元是 不存在 , 而最大元是 120 设A，B，C，D为任意集合，则的充要条件为。( ) 非空集合A上的任意关系R不是对称的就是反对称的。 ( ) 关系R是反对称的当且仅当 。( ). 集合的笛卡尔积运算满足交换律。 ( ) 集合A上的恒等关系是一个双射函数。 ( ) 若集合A上的关系R是对称的，则也是对称的。 ( ) 设A，B为任意集合，如果AB=A，那么B=。 ( ) 设命题“如果f是双射的，则”是真命题。( ) 集合A上的全域关系是等价关系。 ( )计算 某班有25个男生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人3种球都会打。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。答案：利用包含排斥原理或文氏图可求得不会打球的有5人。 设，A上的关系R如下：，（1）证明：R是A上的等价关系；（2）求：A上对应于R的划分。解题要点：（1）分别说明R的自反性、对称性和传递性。 （2）1,6,11,16，2,7,12,17，3,8,13,18，4,9,14,19，5,10,15,20详细解答：(1) (k为整数)R的自反性：任意，所以；R的对称性：任意，若则，所以，R的传递性：任意，若，有所以，。即R是A上的等价关系。（2）， ，。所以，。 设，为上的关系，的关系图如下图所示，165432（1） 求的集合表达式；（2） 求的集合表达式。解：（1），（2） 设集合A1, 2, 3，R和S是A上的两个关系，它们的关系矩阵为：(1) 写出关系R和S 的集合表达式，(2) 画出R和S的关系图，(3) 说明R和S满足关系的哪些特性.解：(1) R = (1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,3);S = 1,1),(1,2),(2,3),(1,3)(2) R和S的关系图：（2分）(3) R满足自反性；S满足反对称性、传递性。 设A=1,2,3,4,5,A上偏序关系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。答：(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无证明 设R是集合A上的二元关系，试证明R是反对称的当且仅当证明：（1）R是反对称的，假定RRc ,则RRcRR,因为R是反对称的，故x=y.所以=IA.即 （2）R是反对称的，若，设R并且R，则RRcRRcIA,故x=y,即R是反对称的。 如果集合A上的关系R和S是自反的、对称的和传递的，证明：是A上的等价关系。证明：（1） 自反。（2），若，则由R ，S对称，所以， ，所以 对称。（3），若则由R ，S传递性知，从而 所以，传递。综上所述，是A上的等价关系。图论部分选择、填空及判断 无向完全图K4是（ B ）.(A) 欧拉图； (B) 哈密顿图； (C) 树； (D) 非平面图。 下列编码是前缀码的是( C ) A. 1,11,101 B. 1,001,0011 C. 1,01,001,000 D.0,00,000 设T为n阶无向树，T有几条割边？( C )A. n条 B. n-2条 C. n-1条 D. 没有 具有4个结点的非同构的无向树的数目是（ A ） A2 B3 C4 D5 下列编码是前缀码的是( B ) A. 0,11,1101 B. 1,01,0011 C. 1,0,01,000 D.0,00,000 如下图所示各图，其中存在哈密顿回路的图是 ( C )。(A) h (B) h h (C) h h (D) h h h h h h h h h h h h h h 图 下面哪个图可一笔画出( A ) 设A(G)是有向图G=V，E的邻接矩阵，其第i行中“1”的数目为（ B ）。(A) 顶点的度数； (B) 顶点的出度；(C) 顶点的入度； (D) 顶点的度数。 阶条边的无向连通图，对应它的生成树有( A )条边。 (A) n-1 (B) (C) m-1 (D) m-n-1 有向图D如图所示，D中长度为2的通路有( D )条。 (A) 8 (B) 9 (C) 10 (D) 11 设连通图G有8个顶点，12条边，则G的任意一颗生成树的总边数为( A )A. 7 B. 8 C. 9 D. 10 关于无向完全图K5的命题中，哪个（或哪些）是真命题？( D )G中存在欧拉回路 G中存在哈密顿回路A. 均不是 B. 只有 C. 只有 D.和 设仅包含根结点的二叉树的高度为0，则高度为K的二叉树的最大结点数为( C ) A. 2k+1 B. 2k+1 +1 C. 2k+1 -1 D. 2k+1 下面给出的四个图中，哪个不是Hamilton图（D） 给定无向图如本题图所示，下面哪个边集不是其边割集？( B )A. , B. ,C. ,D. , 一个3阶有向图的度数列是2，2，4，入度数列是2，0，2，出度数列是 0，2，2 。 在下图中，用避圈法构造最小生成树，边的加入顺序是 AE,BC,ED,DC 。图 无向图G有11条边，4个3度结点，其余结点均为5度结点，则G的结点数为 6 。 已知n个结点的无向简单图G有m条边，则G的补图中有 n(n-1)/2-m 条边。 无向图G含有欧拉回路的充要条件是 连通且每个结点都是偶结点 。 无向图G含有欧拉通路的充要条件是 连通且有且仅有两个奇结点 。 无向图G的结点数n与边数m相等，2度和3度结点各2个，其余结点为悬挂点，则G的边数m = 6 。 在有向图的邻接矩阵中，第i行元素之和与第j列元素之和分别为 结点vi的出度与结点vj的入度 设是各边带权均为的阶带权图的一棵最小生成树，则。 阶条边的无向连通图，对应它的生成树有个基本回路。 ( ) 图的邻接矩阵必为对称矩阵。 ( ) 当时,有个结点的完全图都不是欧拉图。 ( ) 欧拉图中一定不存在桥；哈密顿图中一定存在割点。 ( ) 有向图是强连通的，则它一定是单向连通的，也弱连通的。 （ ) 哈密顿图中存在经过图中每个顶点一次且仅一次的回路。 ( ) 无向图G必存在生成树。 ( ) 有割点的连通图可能是哈密尔顿图。 ( ) 一个n阶无向图G是二部图当且仅当G中无奇圈。 ( )计算 已知无向简单图G有9个结点，每个结点的度数不是5就是6（注：不存在全为6度的情况）。试讨论G的结点度数分配情况。解题要点：由握手定理的推论知：5度结点只能是偶数个，故度数分配情况有以下4种：（1）2个5度结点，7个6度结点；（2）4个5度结点，5个6度结点；（3）6个5度结点，3个6度结点；（4）8个5度结点，1个6度结点； 有向图G如图1所示，问： （1）图中v4到v3长度为2，3的路各有几条？ （2）图中v1到v1长度为3的回路有几条？ （3）该有向图是哪类连通图？答案：（1）2，2 （2）2 （3）强连通图 设有向图D如图所示，试用邻接矩阵求出求D中长度为2的通路数，并指出其中的回路数，并判断此图属于哪种连通类型。 解：邻接矩阵 D中长度为2的通路为11条，其中有3条是回路 。该图是单向连通图，同时也是弱连通图。 在通信中要传输字母a,b,c,d,e,f,g，它们出现的频率分别为30%,20%,15%,10%,10%,9%,6%。设计一个传输它们的最优前缀码，并求传输100个按上述频率出现的字母所需二进制数字个数。解题要点：以传输频率为树叶的权求最优树并分别对应前缀码即可。且传100个字母所需二进制数字个数为W（T）=265。 今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222223.55452634531解：该问题相当于求图的最小生成树问题，此图的最小生成树为：因此如图铺设煤气管道所需费用最小，最小费用为：（）2222222+33+4+125 世界上六大城市之间的航线距离表如下：(以100英里为一个单位) 伦敦 墨西哥 纽约 巴黎 北京 东京伦敦 / 55 34 2 50 59墨西哥 55 / 20 57 70 77纽约 34 20 / 36 68 67巴黎 2 57 36 / 51 60北京 50 77 68 51 / 13东京 59 70 67 60 13 /求出连接此六个城市的最短距离的航线网。(要求给出求解过程) 东京 59 伦敦 13 55 北京 墨西哥 51 20 巴黎 36 纽约 图1解题要点：(1) 首先将本题用带权图表示(见图1)。(2) 求解此题变成为求带权图中的最小生成树问题。如选择克鲁斯卡尔算法，可给出如图2所示的代表最短距离的航线网。 东京 伦敦 13 50 34 北京 2 墨西哥 20 巴黎 纽约 图2 利用Huffman算法,求带权为1, 1, 2, 3, 4, 5的最优二叉树。 解答：简述Haffman算法，最优二叉树如图，W(T)=38.证明 若图G的邻接矩阵为A=，试证明图G是强连通图。证明：方法一：由图G的邻接矩阵画出图G的示意图，说明图中存在经过每个顶点至少一次的回路，从而证明图G是强连通图。方法二：由A，求出A2, A3, A4,进而求出可达矩阵P，也可证明图G是强连通图。 今有6名学生要去完成3个实验，已知他们中的任何人至少与其余5个人中的三个人相互合作。问能否将他们分成三个小组，每组两个人能相互合作，分别去完成3个实验。解答：作无向图G=,其中V由6名学生组成，E=（u,v）|u,vVuvu与v能合作。则G为简单图，且由题意知（G）3。于是，任意u,v有)d(u)+d(v)6.由定理知，G为哈密尔顿图，存在哈密尔顿回路。在回路上2个结点相邻，说明他们代表的两个学生能够合作。设C=v1v2v3v4v5v6v1为G中的一条哈密尔顿回路，则v1,v2,v3,v4,v5,v6就是一种分配方案。代数结构部分选择、填空及判断 设A = 1 , 2 , , 10