四川大学离散数学试题

四川大学期末考试试题（闭卷B）（2007-2008学年第1学期）1．下列命题公式是永真式的是（）A．（P∧～P）↔Q B．（～（P→Q）∧Q）→Q C．（P→Q）∨Q D．（P∨P）∧（P→～P）2．命题公式A不存在主合取范式，则A是（）A．矛盾式B．可满足式C．永真式D．都不对3．谓词公式（∀x）P（X）→（∃x）P（X）是（）A．可满足式B．矛盾式C．无法判别D．永真式4．公式（∀x）（∃y）（P（x,y）∧Q（z））→R（x）中的x （）A．仅是约束变元B．仅是自由变元C．既是约束变元又是自由变元D．既不是约束变元也不是自由变元5．设S={I，Q，R} ，下列命题哪个正确（）A．I⊂Q，Q⊂R则I⊂R B．-1∈I，I∈S 则-1∈S C．D．都不正确6．下面的表达哪个不正确（）A．{a}⊆{{a}} B．{a}∈{{a}} C．{a}⊆{a，{a}} D．{a}∈{a，{a}}7．若集合A中共有n个元素，那么A上不同二元关系的个数为（）A．n2B．2 n2C．2 n2-1 D．都不对8．下列判断正确的是（）A．若R，S是自反的，则R-S是自反的B．若R，S是对称的，则R○S是对称的C．若R，S是传递的，则R∩S是传递的D．若R，S是传递的，则R∪S是传递的9．设R，S是非空集合上的等价关系，则R∪S是（）A．一定具有自反性，但不一定保持对称性B．一定具有对称性，但不一定保持自反性C．一定具有自反性和对称性D．是等价关系10．在5个元素的集合上可以定义的单射数目为（）A．5 B．10 C．60 D．12011．设函数f：X→Y；X，Y是有限集合，f是单射，那么下列关系一定不成立的是（）A．|X|=|Y| B．|X|﹥|Y| C．|X|﹤|Y| D．X∈Y12．平面非连通图G，n-m+f 的值为（）A．2 B．ω（G）C．ω（G）+1 D．313．若一棵树G（n，n-1）只有两个叶节点，则（）不正确A．不包含点度大于等于3的枝点B．节点总度数大于等于4C．最少包含2个节点D．节点总度数=2+2（n-2）14．设10阶简单连通图有32条边，则最少要去掉（）条边才能使其成为平面图A．10 B．12 C．32 D．815．下列代数系统，（）是群A．〈S1={1，1/2，2，1/3，1/4，4}，*：为普通乘法〉B．〈S2={ai | ai∈R，i=1，2，3…n}，o：∀ai，aj∈S2 → aioaj=ai 〉C．〈S3={0，1}，*：为普通乘法〉D．〈S4={-1，1}，+：为普通加法〉二、多项选择题（本大题共5小题，每小题2分，共10分）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。

填空题（1/11）1、设无向图G有24条边，有4个3度的顶点，期顶点度数均小于3，则G中至少有( 22 ) 个顶点。

2、假设4={x|x*<10.x∈正整数}，B={x|x是素数，x<10}，c={13.5}（1）（C-4）U（B-4）=（2）（B∩O-d=3、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有( 9 )叶。

.4.假设P：今天天气好，Q：我就去锻炼身体。

命题“如果今天天气好，我就去锻炼身体"符号化为_ P Q学生答案：5.假设A={x|x2 <30.x∈正整数}，B={x| x是正奇数，x<20}，C={13.5}（1）（C-0U（B-4）=（2）（B∩Q）-d=学生答案：6、假设4=1.23），f，&8h是4倒4的的数，其中：（af0= f（）=f（3）=1，（b>8（1）=1，g（2）=3，g（）=2，（e）h0）=3，h2）=h（3）=1，则：（1）是满射；（2）____是双射；学生答案：7.假设A={a.b}（{}}，B={a}{0}，{（}}试求出：“的幂集p（4）=8、设无向图G有12条边，有3个3度的顶点，其余顶点度数均小于3，则G中至少有_11_个顶点。

9假设d= 1.23.423上的关系R=<1.2>}，则：（1）r（R）=_（2）s（R）=_（3）t（R）=_10、假设A={x|x2 <30.x∈整数}，B={x[x是素数，x<20}，C=13.5）（1）（A∩B）UC=（2）（B-AUC=（3）（C-4）U（B-4）=（4）（B∩9-4=11、-棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有_7_片叶。

二、综合题（59分）12、假设4、B是非空集合，并且P（4）=P（B）。

证明：d=B.学生答案：13、m≤二n（n-D）假设图G是n个顶点m条边的简单无向图，则”2学生答案：S={<xyxxy∈R.x→是整数}证明定义在实数集合R.上的关系”3是一个等价关系。

离散数学考试试题（A、B卷及答案）离散数学考试试题(A卷及答案)一、证明题(10分)1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→C。

P<->Q=(p->Q)合取(Q->p)证明: (P∧Q∧A→C)∧(A→P∨Q∨C)(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律((P∧Q∧A)∨(A∧?P∧?Q))∨C( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律( A∧(P?Q))∨C(A∧(P?Q))→C2) ?(P↑Q)??P↓?Q。

证明:?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。

二、分别用真值表法与公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式,并写出其相应的成真赋值与成假赋值(15分)。

主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。

主析取范式可由析取范式经等值演算法算得。

证明:公式法:因为(P→(Q∨R))∧(?P∨(Q?R))(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R))(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P ∨R∨?R) (?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)4M使(非P析取Q析取R)为0所赋真值,即100,二进制为4M∧6M∧50m∨1m∨2m∨3m∨7m所以,公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。

真值表法:0 0 1 0 1 00 1 11 0 0 1 0 1 1 1 0 1 1 1 0111111111111111111为000、001、010、011、111:成假赋值为:100、101、110。

川大离散数学习题习题61.设A={1，2，3，4}，B=A×A。

确定下述集合是否为A到B的全函数或部分函数。

(1){(1,(2,3)),(2,(2,2)),(3,(1,3)),(4,(4,3))}.(2){(1,(1,2)),(1,(2,3)),(3,(2,4))}.(3){(1,(3,3)),(2,(3,3)),(3,(2,1)),(4,(4,1))}.解：（1）、全函数（2）、不符合单值（3）、全函数要点：根据全函数定义，X中每个元素x都在Y中有唯一元素y与之对应。

2.判别以下关系中那些是全函数。

(1){(n1,n2)|n1,n2∈N,0<2n1-n2<5}。

(2){(n1,n2)|n1,n2∈N,n2是n1的正因子个数}。

(3){(S1,S2)|S1,S2?{a,b,c,d}且S1 S2=?}。

(4){(a,b)|a,b∈N,gcd(a,b)=3}.(5){(x,y)|x,y∈Z,y=x2}.解：(1) {(n1,n2)|n1, n2∈N, 0<2 n1-n2<5}不是函数，n1=0时无定义，且(3,4),(3,5)在其中。

(2) {(n1,n2)|n1, n2∈N, n2是n1的正因子个数}部分函数，n1=0时无定义(3) {(S1,S2)|S1, S2?{a,b,c,d}且S1? S2= ?}不是函数，因为({a},{b}) ,({a},{c})均在其中。

(4) {(a, b)|a, b ∈N, gcd(a,b)=3}不是函数，因为(3, 3) ,(3, 6), (3, 9)均在其中。

(5) {(x, y)|x, y ∈Z, y=x2}全函数3.在§3.1中已经定义了集合的特征函数。

请利用集合A和B的特征函数χA（x）和χB（x）表示出A B，A B，A-B，A以及A○+B对应的特征函数。

解：（略）4.试确定在含n个元素的集合上可以定义多少个二元关系，其中有多少个是全函数。

川大离散数学习题习题 51. 设A={(a,b)|a,b∈N}.定义A上的一个二元关系R={（（a,b ）,(c,d)）|ad=bc},证明:R 是A 上的等价关系. 证：(){}+∈=N b a b a A ,|,Θ，R={（（a,b ）,(c,d)）|ad=bc} ①自反性：由A 的定义，N b a baab ∈=,()()()R b a b a ∈∴,,,②对称性设()()()R d c b a ∈,,,，则bc ad = 即 ()()()R b a d c dacb ∈∴=,,,③传递性设()()()R d c b a ∈1111,,，则1111c b d a =()()()R d c d c ∈2211,,，则2121c d d c =2121211211211c b d a c d b d c b d d a =?==?()()()R d c b a ∈∴2211,,,2. 定义复数集合的子集合C 1={a+bi|i 2=-1,a 、b ∈R,a ≠0}，在C 1上定义关系S 为：(a+bi)S(c+di)?ac>0。

证明：S 是C 1上的一个等价关系，并给出S 的等价类的几何说明。

证明:因为(a+b i )S(c+d i )?ac>0(a,b ∈R,a ≠0,c ≠0)r:?a ≠0,a2>0?(a+b i )S(a+b i )s:(a+b i )S(c+d i )?ac>0?ca>0?(c+d i )S(a+b i ) t:(a+b i )S(c+d i )∧(c+d i )S(u+v i )?ac>0∧cu>0au>0?(a+b i )S(u+v i ) 综上，S 是C 1上的一个等价关系。

由于ac>0，必须a ≠0,c ≠0且a 和c 同号，故S 只有2个等价类，其一是[1]={a+bi|a>0}，另一个是[-1]={a+bi|a<0}，它们分别对应于复平面上右半部和左半部。

四川大学离散期末考试题附标准答案本文档记录了四川大学离散数学期末考试相关的题目，并提供了每个问题的标准答案。

离散数学作为一门重要的数学基础课程，为计算机科学、信息技术以及其他相关学科提供了重要的理论支持。

通过解析这些题目和答案，可以加深对离散数学的理解，提升解题能力。

1. 题目1问题：设A、B、C三个集合满足：A={1,2,3,4,5}，B={3,4,5,6,7}，C={4,5,6,7,8}。

求(A∪B)∩C。

答案：集合A∪B表示将集合A和集合B中的元素合并，去重得到的结果集合。

∩表示求两个集合的交集。

因此，(A∪B)∩C表示先将集合A和集合B合并去重，然后再和集合C求交集。

具体操作如下： 1. 将集合A和集合B的元素合并：A∪B = {1,2,3,4,5,6,7}。

2. 将(A∪B)与集合C求交集：(A∪B)∩C = {4,5}。

所以，(A∪B)∩C = {4,5}。

2. 题目2问题：对于一个图G=(V, E)，其中V={a, b, c, d, e}表示节点集合，E表示边集合。

给定边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，请问该图是否是欧拉图？答案：欧拉图是指一类特殊的连通图，可以经过每条边且每条边只经过一次的路径称为欧拉路径。

具有欧拉路径的图称为欧拉图或半欧拉图。

欧拉图有以下两个性质： - 每个顶点的度数都是偶数，或者只有两个顶点的度数是奇数，其余顶点的度数都是偶数。

- 图是连通的。

对于给定的图G=(V, E)，需要满足以上两个性质才能判断该图是否是欧拉图。

具体操作如下： 1. 统计每个顶点的度数： - a的度数为2 -b的度数为2 - c的度数为2 - d的度数为2 - e的度数为2由此可知，每个顶点的度数都是偶数，满足欧拉图的第一个性质。

2. 判断图是否是连通的：通过观察边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，可以看出这个图是一个环，即从任意一个顶点出发，可以经过每条边且每条边只经过一次返回原点。

习题一解答或提示1. (1) 设P:他是本片的编剧，Q: 他是本片的导演。

P∧Q(2) 设P:银行利率降低，Q:股价上扬。

P→Q(3) 设P:银行利率降低，Q:股价上升。

～(P→Q)(4) 设P:这个对象是占据空间的,Q: 这个对象是有质量的,R: 这个对象是不断变化的,S: 这个对象称为物质。

P∧Q∧R→S(5) 设P:他今天乘火车去了，Q: 他今天随旅行团去了九寨沟。

P∇Q(6) 设P:小身体单薄，设Q:小极少生病, 设R:小头脑好使。

P∧Q∧R(7) 设P:这个人不识庐山真面目，设Q:这个人身在庐山中。

Q→R(8) 设P:两个三角形相似, 设Q:两个三角形的对应角相等或者对应边成比例。

P↔Q(9) 设P:一个整数能被6整除，设Q:这个整数能被2和3整除。

P→Q设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。

R→S 2、(1) 命题T(2) 命题T/F(3) 不是命题，因为真值无法确定。

(4) 命题T(5) 不是命题。

(6) 命题T(7) 命题T/F(8) 不是命题，是悖论。

5、（1）证：～（（～P∧Q）∨（～P∧～Q））∨（P∧Q）⇔（～（～P∧Q）∧～（～P∧～Q））∨（P∧Q）⇔（（P∨～Q）∧（P∨Q））∨（P∧Q）⇔（P∨（～Q∨Q））∨（P∧Q）⇔ P∨（P∧Q）⇔P（3）证：P→(Q∨R)⇔～P∨(Q∨R)⇔～P∨Q∨～P∨R⇔（～P∨Q）∨（～P∨R）⇔ (P→Q）∨（P→R）6、解：如果P∨Q⇔Q∨R，不能断定P⇔R。

因为当Q=T时，P∨Q⇔Q∨R恒成立。

如果P∧Q⇔Q∧R，不能断定P⇔R。

因为当Q=F时，P∧Q⇔Q∧R恒成立。

如果～P⇔～R，则P⇔R。

8、把下列各式用↑等价表示出来：(1)解：（P∧Q）∨～P⇔（( P↑Q)↑( P↑Q)）∨（P↑P）⇔（（( P↑Q)↑( P↑Q)）↑（( P↑Q)↑( P↑Q)））↑（（P↑P）↑（P↑P））（3）解：（P→（Q∨～R））∧～P⇔（～P∨（Q∨～R））∧～P⇔（（P↑P）∨（Q∨（R↑R）））∧（P↑P）；⇔（（P↑P）∨（（Q↑Q）↑（（R↑R）↑（R↑R））））∧（P↑P）⇔（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））∧（P↑P）⇔（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））↑（P↑P））↑（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））↑（P↑P））9、证：∵P∨Q⇔～～P∨Q⇔（～P）→QP∧Q⇔～（～P∨～Q）⇔～（P→～Q）而{～，∨，∧}是功能完备集，∴{～，→}是功能完备集，～，→不能互相表示，故{～，→}是最小功能完备集。

习题41.设A={1,2,3,4},B={0,1,4,9,12}.分别把下面定义的从集合A 到集合B 的二元关系R 用序偶的集合表示出来. (1)xRy ⇔x|y （注：表示y 是x 的倍数）解：R={(1,0),(1,1),(1,4),(1,9),(1,12)，(2,0),(2,4),(2,12)，(3,0),(3,9),(3,12)，(4,0),(4,4),(4,12)}。

(2) xRy ⇔ x ≡y(mod 3)解：R={(1,1),(1,4)，(3,0),(3,9),(3,12)，(4,1),(4,4)}。

(3) /2y x xRy y x -⎢⎥⇔≤⎢⎥⎣⎦⎢⎥⎣⎦解：R={(3,9),(3,12)，(4,9),(4,12)}。

2．用关系图和关系矩阵表示出题1中的各个关系. 解：（1）关系图：关系矩阵：（2）关系图：关系矩阵：（3）关系图：关系矩阵：2,定义A上的二元关系R为:xRy⇔x∩y≠∅.用集合表示3.设A={0,1,2}出这个关系,并画出对应的关系图.解：A={∅,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}R={({0},{0,1}), ({0},{0,2}), ({0},{0,1,2}),({1},{0,1}), ({1},{1,2}), ({1},{0,1,2}), ({0,1},{0,1,2}), ({0,2},{0,1,2}}∪I A;关系图略。

4.设A是含n个元素的集合，请问在A上可以定义出多少个二元关系？解: 因为R是A上的二元关系,R⊆A⨯A,故：R共2n个二元关系.5.判别习题第1题和第3题中定义的二元关系各具有那些性质? 解：6.设在整数集合Z上定义了如下关系:(1)xR1y⇔x|y. (2)xR2y⇔x≡ y(mod m),m为确定的正整数.(3)xR3y⇔x.y>0. (4)xR4y⇔x=y或|x-y|=1(5)xR5y⇔x2>y2.在下表中用√对和X错填空,以确定这5个关系是否满足对应的性质：7. 设R是集合A上的一个二元关系,合于xRy yRz xRz∧⇒，称R是A上的一个反传递关系.试举一个实际的反传递关系的例子.解：例如：设A={a, b, c, d}则 R1={(a, b), (b, d), (d, c)} 反传递R2={(a, b), (a, c), (d, b)} 反传递、传递R3 ={(a, a), (a, b), (b, c)} 不是反传递R4 ={(a, a), (b, c)} 不是反传递传递和反传递不是绝对互相排斥实际中，如“父子关系”，“X=Y+1”关系等。

四川大学期末考试试题（闭卷）（2014-2015学年第1学期）课程号：304039040 课程名称：离散数学（A卷）任课教师：冯伟森石兵周莉陈瑜林兰适用专业年级： 2013级计算机科学与技术学号：姓名：一、单项选择题（本大题共16小题，每小题1分，共16分）提示：在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分1.令R: 小王吃饭；S：小王看电视。

则语句“小王一边吃饭一边看电视”可以符号化为（）。

（A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S2.令P(x):x是实数，Q(x):x是有理数。

则语句“并非每个实数都是有理数”可以符号化为（）。

（A）～∀x(R(x)→Q(x))；（B）～(R(x)→Q(x))；（C）～∀x(R(x)∧Q(x))；（D）～∀x(R(x)∨Q(x))3.下列公式中，（）是永真公式。

（A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S) ∧(R∧～S)4.下列公式中（）是等价公式。

（A）G∧(H∨S) ⇔ (G∨H) ∧(G∨S)；（B）G∧(H∨S) ⇔ (G∧H) ∧(G∧S)；（C）G∧(H∨S) ⇔ (G∧H)∨(G∧S)；（D）G∧(H∨S) ⇔ (G∨H) ∨(G∨S)；5.公式∀x((P(x)→Q(y，x))∧∃z R(y，z))→S(x)中，自由变元是( )。

（A）x和y ；（B）y和z；（C）x和z；（D）z或者y6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。

（A） 512 (B) 507 (C) 508 (D) 5067.下列关于有限集偏序集〈A,≤〉的描述，（）是正确的(A) 一定存在最大元(B) 一定存在最小元(C) 任意两元素都存在最大下界 (D) 一定存在极大元8.下列说法不正确的是（）(A)任意两个非空集合之间都可构造函数(B) 任意两个非空集合之间都可构造单射函数(C) 任意两个非空集合之间都可构造满射函数(D) 任意两个非空集合之间如可构造单射函数，也可构造满射函数，那么一定可构造双射函数9.下列各组数中，不能构成无向图的点度数序列的是（）。

四川大学期末考试试题课程名称：离散数学适用专业年级：课程号：课序号：任课教师：成绩：学生人数：印题份数：学号：姓名：一．单项选择题（每小题1.5分，共18分）１．下面关于集合基数正确的说法是（）①．A是B的真子集，则A的基数比B的基数小；②．实数集合的基数最大；③．没有最小的基数；④．偶数集合的基数与有理数集合的基数相同。

２．下列式子中（）是永真的。

①.（P∨Q）→（P∧Q）；②. （P→Q）∧（P∨Q）；③（.P→Q）→（P↔Q）；④（.P↔Q）→（p→Q）.３．设R和S是集合Ａ上的关系，R∩S 必为反对称关系的是（）①．当R是偏序关系、S是等价关系；②．当R和S都是自反关系；③．当R和S都是等价关系；④．当R和S都是传递关系。

４．下面对于群、环、格中运算都要求的性质是（）①.结合性；②.交换性；③.幂等性；④.分配性．５．一个格中每个元都有补元，则该格必是（）。

①．有限格；②．分配格；③．有界格；④．布尔格．6. Z为整数集，定义ｆ：Z→Z如下：ｆ(ｘ)＝ｘ(ｘ＋１)，则ｆoｆ是（）①．ｘ(ｘ＋１)；②．ｘ2 (ｘ＋１)2；③．ｘ2 (ｘ＋１)2＋ｘ(ｘ＋１)；④．2ｘ(2ｘ＋１)．7. 下面图中边数最多的是( )①．K15；②．K20,50；③．60阶的树；④．54阶的4度正则图．８．如果图G存在完备匹配M，下面叙述正确的是( )①．G中无割边；②．G中无割点；③．不存在M非饱和点；④．存在M增广道路。

9. 如果一个图的色数是3，则它必不是（）①．树；②．欧拉图；③．正则图；④．哈密顿图．10. 下面哪个是有限半群必然具备的？（）①．有幂等元；②．有零元；③．有幺元；④．方程有解。

11. 循环群之间的满同态映射（）。

①．是单射；②．是双射；③．把生成元映成生成元；④．把零元映成零元。

12. 设R是A上的二元关系，且R︒R⊆R，可以肯定R应是（）①．对称关系；②．全序关系；③．自反关系；④．传递关系．二．多项选择题（每小题2分，共12分）。

习题一解答或提示1. (1) 设P:他是本片的编剧，Q: 他是本片的导演。

P∧Q(2) 设P:银行利率降低，Q:股价上扬。

P→Q(3) 设P:银行利率降低，Q:股价上升。

～(P→Q)(4) 设P:这个对象是占据空间的,Q: 这个对象是有质量的,R: 这个对象是不断变化的,S: 这个对象称为物质。

P∧Q∧R→S(5) 设P:他今天乘火车去了，Q: 他今天随旅行团去了九寨沟。

P∇Q(6) 设P:小身体单薄，设Q:小极少生病, 设R:小头脑好使。

P∧Q∧R(7) 设P:这个人不识庐山真面目，设Q:这个人身在庐山中。

Q→R(8) 设P:两个三角形相似, 设Q:两个三角形的对应角相等或者对应边成比例。

P↔Q(9) 设P:一个整数能被6整除，设Q:这个整数能被2和3整除。

P→Q设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。

R→S2、(1) 命题T(2) 命题T/F(3) 不是命题，因为真值无法确定。

(4) 命题T(5) 不是命题。

(6) 命题T(7) 命题T/F(8) 不是命题，是悖论。

5、（1）证：～（（～P∧Q）∨（～P∧～Q））∨（P∧Q）⇔（～（～P∧Q）∧～（～P∧～Q））∨（P∧Q）⇔（（P∨～Q）∧（P∨Q））∨（P∧Q）⇔（P∨（～Q∨Q））∨（P∧Q）⇔ P∨（P∧Q）⇔P（3）证：P→(Q∨R)⇔～P∨(Q∨R)⇔～P∨Q∨～P∨R⇔（～P∨Q）∨（～P∨R）⇔ (P→Q）∨（P→R）6、解：如果P∨Q⇔Q∨R，不能断定P⇔R。

因为当Q=T时，P∨Q⇔Q∨R恒成立。

如果P∧Q⇔Q∧R，不能断定P⇔R。

因为当Q=F时，P∧Q⇔Q∧R恒成立。

如果～P⇔～R，则P⇔R。

8、把下列各式用↑等价表示出来：(1)解：（P∧Q）∨～P⇔（( P↑Q)↑( P↑Q)）∨（P↑P）⇔（（( P↑Q)↑( P↑Q)）↑（( P↑Q)↑( P↑Q)））↑（（P↑P）↑（P↑P））（3）解：（P→（Q∨～R））∧～P⇔（～P∨（Q∨～R））∧～P⇔（（P↑P）∨（Q∨（R↑R）））∧（P↑P）；⇔（（P↑P）∨（（Q↑Q）↑（（R↑R）↑（R↑R））））∧（P↑P）⇔（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））∧（P↑P）⇔（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R↑R）））））↑（P↑P））↑（（（（P↑P）↑（P↑P））↑（（（Q↑Q）↑（（R↑R）↑（R↑R）））↑（（Q↑Q）↑（（R↑R）↑（R ↑R）））））↑（P↑P））9、证：∵P∨Q⇔～～P∨Q⇔（～P）→QP∧Q⇔～（～P∨～Q）⇔～（P→～Q）而{～，∨，∧}是功能完备集，∴{～，→}是功能完备集，～，→不能互相表示，故{～，→}是最小功能完备集。

大学《离散数学》期末考试试卷及答案(1)一、选择题1. 离散数学的主要研究对象是（）。

A. 连续的数学结构B. 有限的数学结构C. 数学的综合应用D. 数学的哲学思考2. 命题逻辑是离散数学的一个重要组成部分，它主要研究（）。

A. 命题之间的真假关系B. 变量之间的关系C. 函数之间的关系D. 集合之间的关系3. 集合的基本运算包括（）。

A. 并、交、差、补B. 加、减、乘、除C. 包含、相等、不等、自反D. 大于、小于、等于、不等于二、填空题1. 若集合A={m|2m-1>3}，则A中的元素为______。

2. 有一个集合A={1，2，3}，则集合A的幂集为______。

3. 若命题p为真，命题q为假，则复合命题“p∧q”的真值为______。

三、解答题1. 请写出离散数学中常用的数学符号及其含义。

2. 请解释命题逻辑中的充分必要条件及其符号表示，并给出一个例子。

3. 请定义集合的笛卡尔积，并给出两个集合进行笛卡尔积运算的例子。

四、问答题1. 离散数学在计算机科学中有着重要的应用，请列举三个与计算机科学相关的离散数学应用领域并简要介绍。

2. 请简要解释归纳法在离散数学中的作用，并给出一个使用归纳法证明的例子。

3. 什么是有向图？请给出一个有向图的例子，并解释该图中的关系。

参考答案：一、选择题1. B2. A3. A二、填空题1. A={m|2m-1>3}2. {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}3. 假三、解答题1. 常用数学符号及含义：- ∪：并，表示集合的合并操作。

- ∩：交，表示集合的交集操作。

- ∖：差，表示减去一个集合中的元素。

- ⊆：包含，表示一个集合包含于另一个集合。

- =：相等，表示两个集合具有相同的元素。

2. 充分必要条件是指一个命题的成立与另一个命题的成立互为必要条件，若A是B的充分必要条件，那么当A成立时B一定成立，且当A不成立时B也一定不成立。

1、下列是真命题的有（ CD ） A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。

2、下列集合中相等的有（ BC ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

3、设A={1，2，3}，则A 上的二元关系有（ C ）个。

A ． 23 ； B ． 32 ； C ． 332⨯； D ． 223⨯。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A ） A ．若R ，S 是自反的， 则S R 是自反的； B ．若R ，S 是反自反的， 则S R 是反自反的； C ．若R ，S 是对称的， 则S R 是对称的； D ．若R ，S 是传递的， 则S R 是传递的。

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ D ）A ．A ；B ．P(A) ；C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ C ）7、下列函数是双射的为（ A ）A ．f : I →E , f (x) = 2x ；B ．f : N →N ⨯N, f (n) = <n , n+1> ；C ．f : R →I , f (x) = [x] ；D ．f :I →N, f (x) = | x | 。

（注：I —整数集，E —偶数集， N —自然数集，R —实数集） 8、图 中 从v 1到v 3长度为3 的通路有（ D ）条。

A．0；B．1；C．2；D．3。

9、下图中既不是Eular图，也不是Hamilton图的图是（ B ）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。

四川大学期末考试试卷（闭卷）（2007-2008学年第1学期）课程号：30485040、31100340 课程名称：离散数学（A卷）任课教师：适用专业年级：2006级计算机科学与技术、软件工程学号：姓名：考试须知一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分1、下列公式中，（）不是永真式。

①（P∧Q）→Q ② P→（P∨Q）③（P→Q）?（～Q→～P ）④（～P∨Q）∧（～（～P∧～Q））2、下列谓词公式中是前束范式的是（）(?x)F(x)??(?x)G(x)(?x)F(x)?(?y)G(y)②①(?x)(?y)(P(x)?Q(x,y))(?x)(P(x)?(?y)Q(x,y))④③3、对任意集合A、B、C，下列命题中为真的是（）。

①若A?B 且 B∈C，则A∈C ②若A?B 且 B∈C，则A?C③若A∈B 且 B?C，则A∈C ④若A?B 且 B∈C，则A?C4、设R、S 都是集合A上的二元关系，下列命题中（）不真。

①若R、S 都是自反的，则R∪S是自反的②若R、S 都是反自反的，则R∪S是反自反的③若R、S 都是对称的，则R∪S是对称的④若R、S 都是传递的，则R∪S是传递的5、设R1、R2都是集合A上的等价关系，下列关系中是A上的等价关系的是（）。

①（A×A）-R1 ② R1∩R2 ③ r（R1-R2）④ R1-R26、设集合A={1，2，3，4}，下列A上的关系构成A到A的映射的是（）。

① f1={(2,1),(2,4),(3,4),(4,1)} ② f2={(4,4),(3,1),(1,2),(4,2)}f4={(1,4),(2,1),(3,4),(4,1)}④ f3={(1,1),(2,1),(1,2),(3,4)} ③．的一个划分的是（）。

，6，9}，则下列子集族中构成A7、设集合A={1，2，3，46}} 9，3}，{3}，{4，{3，，4}，{9，6}} ② {{1，2，① {{1}9}} {6，，{2，3}，6}} ，{3}，{4，9，④ {{1，2}③ {{1，2} ）。

离散数学考试试题及答案一、单项选择题（每题5分，共20分）1. 在离散数学中，以下哪个概念不是布尔代数的基本元素？A. 逻辑与B. 逻辑或C. 逻辑非D. 逻辑异或答案：D2. 下列哪个命题不是命题逻辑中的命题？A. 所有学生都是勤奋的B. 有些学生是勤奋的C. 学生是勤奋的D. 勤奋的学生答案：D3. 在集合论中，以下哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 以下哪个图不是无向图？A. 简单图B. 完全图C. 有向图D. 多重图答案：C二、填空题（每题5分，共20分）1. 如果一个命题的逆否命题为真，则原命题的________为真。

答案：逆命题2. 在图论中，如果一个图的任意两个顶点都由一条边连接，则称这个图为________图。

答案：完全3. 一个集合的幂集是指包含该集合的所有________的集合。

答案：子集4. 如果一个函数的定义域和值域都是有限集合，那么这个函数被称为________函数。

答案：有限三、简答题（每题10分，共30分）1. 请简述什么是图的欧拉路径。

答案：欧拉路径是一条通过图中每条边恰好一次的路径。

2. 解释什么是二元关系，并给出一个例子。

答案：二元关系是指定义在两个集合之间的关系，它将第一个集合中的元素与第二个集合中的元素联系起来。

例如，小于关系就是一个二元关系。

3. 请说明什么是递归函数，并给出一个简单的例子。

答案：递归函数是一种通过自身定义来计算函数值的函数。

例如，阶乘函数就是一个递归函数，定义为：n! = n * (n-1)!，其中n! = 1当n=0时。

四、计算题（每题10分，共30分）1. 计算以下逻辑表达式：(P ∧ Q) ∨ ¬R答案：首先计算P ∧ Q，然后计算¬R，最后计算两者的逻辑或。

2. 给定集合A = {1, 2, 3}，B = {2, 3, 4}，求A ∪ B。

答案：A ∪ B = {1, 2, 3, 4}3. 已知函数f(x) = 2x + 3，求f(5)。

离散数学期末试卷A卷四川大学期末考试试题（闭卷）（2014-2015学年第1学期）课程号：304039040 课程名称：离散数学（A卷）任课教师：冯伟森石兵周莉陈瑜林兰适用专业年级： 2013级计算机科学与技术学号：姓名：一、单项选择题（本大题共16小题，每小题1分，共16分）提示：在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分1.令R: 小王吃饭；S：小王看电视。

则语句“小王一边吃饭一边看电视”可以符号化为（）。

（A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S2.令P(x):x是实数，Q(x):x是有理数。

则语句“并非每个实数都是有理数”可以符号化为（）。

（A）～?x(R(x)→Q(x))；（B）～(R(x)→Q(x))；（C）～?x(R(x)∧Q(x))；（D）～?x(R(x)∨Q(x))3.下列公式中，（）是永真公式。

（A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S) ∧(R∧～S)4.下列公式中（）是等价公式。

（A）G∧(H∨S) ? (G∨H) ∧(G∨S)；（B）G∧(H∨S) ? (G∧H) ∧(G∧S)；（C）G∧(H∨S) ? (G∧H)∨(G∧S)；（D）G∧(H∨S) ? (G∨H) ∨(G∨S)；5.公式?x((P(x)→Q(y，x))∧?z R(y，z))→S(x)中，自由变元是( )。

（A）x和y ；（B）y和z；（C）x和z；（D）z或者y6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。

注：试题字迹务必清晰，书写工整。

本题8页，本页为第1页（A） 512 (B) 507 (C) 508 (D) 5067.下列关于有限集偏序集〈A,≤〉的描述，（）是正确的(A) 一定存在最大元(B) 一定存在最小元(C) 任意两元素都存在最大下界 (D) 一定存在极大元8.下列说法不正确的是（）(A)任意两个非空集合之间都可构造函数(B) 任意两个非空集合之间都可构造单射函数(C) 任意两个非空集合之间都可构造满射函数(D) 任意两个非空集合之间如可构造单射函数，也可构造满射函数，那么一定可构造双射函数9.下列各组数中，不能构成无向图的点度数序列的是（）。