川大离散数学习题6

第6章习题答案1．列举出从X到Y的关系S的各元素（1）X={0，1，2}，Y={0，2，4}，S={<x，y>|x+y∈X⋂Y}（2）X={1，2，3，4，5}，Y={1，2，3}，S={<x，y>|x=y2，x∈X，y∈Y}解：（1）S={<0，0>，<0，2>，<2，0>}（2）S={<1，1>，<4，2>}2．设P={<1，2>，<2，4>，<3，3>}Q={<1，3>，<2，4>，<4，2>}求dom（P），ran（P），并证明：dom（P⋃Q）=dom（P）⋃dom（Q）解：dom（P）={1，2，3}ran（P）={2，3，4}证明：对于任意xx∈dom（P⋃Q）⇔∃y（<x，y>∈P⋃Q）⇔∃y（<x，y>∈P∨<x，y>∈Q）⇔∃y（<x，y>∈P）∨∃y（<x，y>∈Q）⇔ x∈dom（P）∨x∈dom（Q）⇔ x∈dom（P）⋃dom（Q）所以，dom（P⋃Q）=dom（P）⋃dom（Q）3．若关系R和S自反的，对称的和传递的，证明：R⋂S也是自反的，对称的和传递的。

证明：设R和S是集合A上的关系。

因为R和S是自反的，所以，对于A中的任意元素x，有<x，x>∈R和<x，x>∈S。

因此<x，x>∈R⋂S，即R⋂S是自反的。

因为R和S是对称的，所以对于任意<x，y>，<x，y>∈R⋂S⇔<x，y>∈R∧<x，y>∈S⇔<y，x>∈R∧<y，x>∈S⇔<y，x>∈R⋂S因此，R⋂S是对称的。

因为R和S是传递的，所以对于任意<x，y>和<y，z><x，y>∈R⋂S ∧<y，z>∈ R⋂S⇔<x，y>∈R∧<x，y>∈S∧<y，z>∈ R∧<y，z>∈ S⇔（<x，y>∈R∧<y，z>∈ R）∧（<x，y>∈S ∧<y，z>∈ S）⇔<x，z>∈R∧<x，z>∈ S⇔<x，z>∈R⋂S因此，R⋂S是传递的。

离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

b)我今天进城，除非下雨。

c)仅当你走，我将留下。

2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。

（4分）4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。

川大离散数学习题习题 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. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限max(d(v)) ≤ n-1, G 图的总点度上限为max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

离散数学练习题及答案6离散数学是一门研究离散结构及其运算规律的数学学科，它在计算机科学、信息科学、电子工程等领域有着广泛的应用。

在学习离散数学的过程中，练习题是不可或缺的一部分。

通过解答练习题，我们可以巩固所学的知识，提高问题解决能力。

本文将为大家提供一些离散数学练习题及其答案，希望对大家的学习有所帮助。

1. 集合与命题逻辑(1) 设集合A={1,2,3,4,5}，集合B={3,4,5,6,7}，求A与B的交集、并集和差集。

答案：A与B的交集为{3,4,5}，并集为{1,2,3,4,5,6,7}，A与B的差集为{1,2}。

(2) 已知命题p："我喜欢数学"，命题q："我喜欢编程"，求命题“我既不喜欢数学也不喜欢编程”的否定。

答案：命题“我既不喜欢数学也不喜欢编程”的否定为“我喜欢数学或者喜欢编程”。

2. 关系与函数(1) 设A={1,2,3,4}，B={a,b,c,d}，关系R={(1,a),(2,b),(3,c),(4,d)}，判断关系R是否为A到B的函数。

答案：关系R是A到B的函数，因为每个元素在关系R中只有一个对应的值。

(2) 设函数f(x)=2x+1，求f(3)的值。

答案：将x=3代入函数f(x)=2x+1，得到f(3)=2*3+1=7。

3. 图论(1) 给定一个无向图G，顶点集合V={A,B,C,D,E}，边集合E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求图G的邻接矩阵。

答案：邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 0 1 0C 1 0 0 1 0D 0 1 1 0 1E 0 0 0 1 0(2) 给定一个有向图G，顶点集合V={A,B,C,D,E}，边集合E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求图G的出度和入度。

答案：图G的出度为：A的出度为2，B的出度为1，C的出度为1，D的出度为2，E的出度为0；图G的入度为：A的入度为0，B的入度为1，C的入度为1，D的入度为2，E的入度为1。

离散数学试题带答案四、证明题1. 设<G ，*>是群，具有幺元e ，如果对G 的任意元素a ，都有 a²=e, 则<G ，*>是交换群2. 形式证明q s p r s r q p ⇒∧⌝→∨→,,3. 证明：P →(Q →R)⇔P ∧Q →R.4．试证明：R S Q P S R Q P →⇒∧∨⌝∧→→)())(( 5．试证明：Q R R Q Q P ⌝⇒⌝∧∨⌝∧⌝∧⌝)()( 6. 证明：)()(x xB x xA ∀→∃⇒))()((x B x A x →∀7．设G 是图，无回路，但若外加任意一条边于G 后，就形成一回路. 试证明G 必为树. 8. 设B 是任意集合，试验证(P(B),⊕)是群. P(B)是集合B 的幂集，⊕是集合的对称差运算， 9．给定代数系统(G,+,*), 二元运算见表一，表二.表一 表二证明(G ,+,*)是域.10. 证明如果非空集合A 上的二元关系R 和S 是偏序关系，则S R ⋂也是A 上的偏序关系． 11．试证A －(B －C)＝(A －B)⋃(A ⋂C)12．设非空集合A ，验证(A A P ,~,,,),(∅⋂⋃)是布尔代数，13. 试证明属于关系不满足传递性，即对于任意的集合A,B,C 若A ∈B 且B ∈C 不一定有 A ∈C14．设 A,B 为两个集合，证明 A —B=A 当且仅当A ∩B= ø15. 设R,S 都是非空集合A 上的二元关系，且他们是对称的，证明：RoS 具有对称性当且仅当 RoS=SoR.16. 已知g ：A->B,f ：B->C1） 已知fog 是单射的且g 是满射的，证明f 是单射的 2） 已知fog 是满射的且f 是单射的，证明g 是满射的 17．设A 是传递集，证明A+也是传递集。

18．设G 是n 阶无向简单图，其直径为d(G)=2, ο(G)=n-2，证明G 的边数m ≥2n-4 19．V=<S,*>是可交换半群,若a,b ∈S 是V 中得幂等元，证明a*b 也是V 中的幂等元20．设 L 是格，证明对于任意a,b,c,d ∈L 有：( a ∧b)∨(c ∧d)≤(a ∨c)∧(b ∨d)五、计算题1. 无向树T 有2个2度顶点，1个3度顶点，3个4度顶点，其他的都是树叶，问T 中有多少片树叶？2. 设公式()()x Q x P → ，其中P(x)：x>2，Q(x)：x=0，F 是永假式，个体域是{1，2}，求公式A(x)的真值 3. 设集合X={1，2，3, 4}，X 中的关系为F={<1，1>，<1，2>，<1，4>，<2，1>，<2，2>，<3，3>，<4，1>，<4，4>} 写出F 的关系矩阵及其关系图，F 有哪些性质？4. (1) n(n ≥1)阶无向完全图与有向完全图各有多少条边?为什么？ (2)完全二部图K m n ,中共有多少条边?为什么？(3) 每个顶点的度都为k 的无向图称为k 正则图，问：n 阶k 正则图中共有多少条边?为什么？5. 设集合L={a ，b}，在L 中规定 + 和·如下：a+a=a ，a+b=b+a=b ，b+b=b a ·a=a ，a ·b=b ·a=a ，b ·b=b问<L ，+，·>能构成代数系统吗？若可以，写出该代数系统的运算表。

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度结点。

习题1：1. 解 （1）{2，3，5，7，11，13，17，19}（2）{x|x=20*k,k 是自然数}（3）{2，-1}2. 解 （1）{2，4}（2）{1，2，3，4，5}（3）{1，3}（4）{1，3，5}3. 解 （1）{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}（2）φ（3）全体自然数（4）{0，2，4，6，8，10，12，14，16，18，20}（5）1，3，5，7，9，11，13，15，17，19}4. 解 （1）正确（2）正确（3）错误（4）正确5. 解 （1）A={1}，B={{1}}，C={{1}}（2）A={1}，B={{1}}，C={{{1}}}6. 解 （1）正确。

由子集的定义。

（2） 不一定。

如：A={1}，B={{1}}，C={{1}}。

（3）不一定。

如：A={1}，B={1，2}，C={{1，2}}（4）不一定。

如：A={1}，B={1，2}，C={{1，2}}。

7. 解 A={1，2}，B={1}，C={2}，有B A ≠，但是C B C A =成立。

A={1，2}，B={1}，C={1}，有B A ≠，但是C B C A =成立。

8. 解 （1）φ（2）{φ}（3）{{φ}}（4）{φ，{φ}}9. 解 （1）{1,2,3,4,5,6,7,8,9}（2）{0,1,2,3,4,5,6,7,8,9,10}（3）{0,3,6,7,8,9}10. 解 33311. 解 2512. 解（1）454（2）124（3）22013. 解 （1）{φ}（2）{φ，{a}}（3）{φ，{φ}，{a}，{φ,a}}（4）{φ，{φ}，{{φ}}，{{φ},φ}}（5）{φ，{{φ}}，{φ}，{a}，{{φ},φ}，{{φ},a}，{φ,a}，{{φ},φ,a}}14. 证明：假设B ≠C ，则至少存在一元素x ∈B 且x ∉C 。

习题六格与布尔代数
一、填空题
1、设是偏序集,如果_________, 则称<A, ≤>是(偏序)格.
2、设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______.
3、一个格称为布尔代数，如果它是______格和______格.
4、设<>是有界格，a,b L,若a b=0,则a=b=_____；若a b=1,则a=b=____.
二、证明题
1、设<L, ≤>是格，a,b,c,d∈L。

试证：若a≤b且c≤d，则
a∧c≤b∧d
2、证明：在有补分配格中，每个元素的补元一定唯一。

3、设<S,⊕,⊙,′,0,1>是一布尔代数，则
R={<a,b> | a⊕b=b}是S上的偏序关系
4、若<A，≤>是一个格，则对任意a、b 、c∈A，有若a≤c且b≤c，则a∨b ≤c。

5、若<A，≤>是一个格，则对于任意a，b∈A，证明以下两个公式等价；（1）a≤b
（2）a∨b =b
6、证明：如果格中交对并是分配的，那么并对交也是分配的，反之亦然。

7、如果<A,≤>是有界格，全上界和全下界分别是1和0，则对任意元素a∈A，证明：
a∨1=1∨a=1 ，a∨0=0∨a=a。

四川大学期末考试试卷（闭卷）（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} ）。

离散数学习题答案习题一及答案：（P14-15） 14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q ∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→15、设p ：2+3=5.q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→ 解：p=1，q=1，r=0，()(110)1p q r ∧∧⌝⇔∧∧⌝⇔，(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔ ()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型： （2）()p p q →⌝→⌝解：列出公式的真值表，如下所示：由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值： （4）()p q q ⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p q ⇔⎧⎨⇔⎩ 所以公式的成真赋值有：01，10，11。

习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式， 所以成真赋值为011，111。

*6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式，所以成假赋值为100。

离散数学考试试题及答案一、单项选择题（每题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)。

第六章习题答案2. 设P = {< 1, 2 >, < 2, 4 >, < 3, 3 >}，Q = {< 1, 3 >, < 2, 4 >, < 4, 2 >}找出P⋃Q, P⋂Q, dom(P), dom(Q), ran(P)及ran(Q)，并证明：dom(P ⋃ Q) = dom(P) ⋃ dom(Q)ran(P⋂ Q) ⊆ ran(P) ⋂ ran(Q)解P ⋃ Q ={< 1, 2 >, < 2, 4 >, < 3, 3 >, < 1, 3 >, < 4, 2 >}，P ⋂ Q ={< 2, 4 >}dom(P)={1, 2, 3}，dom(Q)= {1, 2, 4}，ran(P) = {2, 3, 4}，ran(Q) = {2, 3, 4}。

x∈ dom(P⋃Q)⇔∃y (< x, y > ∈ P ⋃ Q)⇔∃y (< x, y > ∈ P∨ < x, y > ∈ Q)⇔∃y (< x, y > ∈ P) ∨∃y (< x, y > ∈ Q)⇔ x∈ dom(P) ∨ x∈ dom(Q)⇔ x∈ dom(P) ⋃ dom(Q)y∈ ran(P⋂ Q)⇔∃x (< x, y > ∈ P⋂Q)⇔∃x (< x, y > ∈ P ∧ < x, y > ∈ Q)⇒∃x (< x, y > ∈ P) ∧∃x (< x, y > ∈ Q)⇔y∈ ran(P) ∧ y∈ ran(Q)⇔y∈ ran(P) ⋂ ran(Q)如上例，ran(P⋂ Q) = {4}⊂ {2, 3, 4} = ran(P) ⋂ ran(Q)3. 若关系R和S自反的，对称的和传递的，证明：R⋂S也是自反的，对称的和传递的。