《离散数学》单元作业题2集合
管理学 点击： 2014-05-13
《离散数学》单元作业题2集合篇一
离散数学习题一,二参考答案
《离散数学》习题一参考答案
第一节 集合的基数
1.证明两个可数集的并是可数集。
证明：设A，B是两可数集，A{a1,a2,a3,,an,}，B{b1,b2,b3,,bn,} ABNf:ai2i1 ，f是一一对应关系，所以|A∪B|=|N|=0。
b2jj
2．证明有限可数集的并是可数集
证：设A1,A2,A3Ak是有限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3,,k
kkAAiN，f是一一对应关系，所以|A|=|Ai|=|N|=0。 f:i1
i1aijj(k1)i
3.证明可数个可数集的并是可数集。
证：设A1,A2,A3Ak是无限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3,
AAiNi1f:， 1aij(ij1)(ij2)i2
所以f是一一对应关系，所以|A|=|A|=|N|=。 i0
i1
4.证明整系数多项式所构成的集合是可数集。
证明：设整系数n次多项式的全体记为
An{a0xna1xn1an1xan|aiZ}
则整系数多项式所构成的集合AAn；
N1
由于xk的系数ak是整数，那么所有xk的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得An是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合AAn也是可数集。
N1
5.证明不存在与自己的真子集等势的有限集合.
证明：设集合A 是有限集，则|A|=n，若B是A的真子集，则|B|≤|A|=n，A-B≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B）∪B，（A-B）B=φ，所以，，就是|A|＞|B|，即得结论。
6．证明正有理数集合是可数集，从而能证明有理数集是可数集。
m证明：因为Q{|m,nN}，是正分数集， n
n设Ai{|nN},i1,2,3,4,,m}，Ai是可数集，并QAi ii1
由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。
有理数集Q=Q{0}Q，由可数集性质1，2，马上可得有理数集是可数集。
7．A、B为无限集，试说明下面的集合是否是无限集。
（1）A∪B （2）A∩B；（3）A－B；（4）A×B
答：（1）A∪B是无限集，由可数集性质（2）可得。
（2）A∩B不一定是无限集，若A∩B=φ，则|A∩B|=0；
（3）A－B不一定是无限集，若A=B，则A－B=φ，
（4）A×B是无限集。相当于无限个无限集的并是无限集。
8．已知A{n7|nN}，B{n109|nN}，求
（1）A，B的基数；（2）A∪B，A∩B的基数。
A[n7|nN)N解：（1）f:，f是一一对应关系，所以|A|=N|=0 7nn
B[n109|nN)Nf:，f是一一对应关系，所以|B|=N|=0 109nn
（2）有可数集性质（2）可得A∪B是可数集，既| A∪B|=N|=0
因为(n7)109(n109)7AB，所以A∩B≠φ
AB[(n109)7|nN)N，f是一一对应关系，所以| A∩B|=N|=0 f:1097(n)n
9.设A为任意集合，证明P（A）与{0，1} A等势，其中{0，1} A为A到{0，1}的全体函数。
1xA解：若fA(x)是A到{0，1}上的一个集函数，则fA(x) 0xA
f：ρ（A）→{0,1}
B →fB(x) 所以f是一一对应的，即ρ（A）与{0,1}等势。 AA
10.集合A，B的笛卡尔乘积可表示为
A×B＝｛〔a，b〕│a∈A，b∈B｝， 若A1，A2，„，An是可数集，证明A1×A2ׄ×An 也是可数集。 解：．设A={a1,a2,a3,,an,}，B={b1,b2,b3,,bn,}，并 C=A×B{(a,b)|aA,bB}=A
n1n，An{(an,bi)|biB}，
因为An是可数集，n=1，2，3，„，所以C=A×B=A
n1n也是可数集，（可数个可数集是可
数集）。同理 A×B×C也是可数集，由于A1,A2,A3,,An是有限个可数集，所以A1A2A3An也是可数集。
《离散数学》单元作业题2集合篇二
离散数学练习题2
典型习题及解析
1-1．下面的是否是命题：
（1）不在同一直线上的三点确定一个平面。
（2）郑州是河南省的省会。
（3）今年的冬天将是一个暖冬。
（4）这碗汤味太淡了。
（5）1011+1000=10011。
1-2设
P：明天天气晴朗
Q：我们就去郊游
则 P Q的含义为
1-3根据真值表求公式P (P∧(Q R ))的主析取范式。
1-4试证明(﹁P Q )∧(P R )∧(﹁Q∨S ) S∨R。
1-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。迈克没有向别人借钱，所以如果迈克没有卖掉洗衣机，则他没有电冰箱。
1-6如果今天我没课，则我去机房上机或去图书馆查资料；若机房没有空机器，则我没法去上机；今天我没课，机房也没有空机器，所以我去图书馆查资料。
1-7北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。 甲说：“天津第一，上海第二。”
乙说：“天津第二，广州第三。”
丙说：“北京第二，广州第四。”
比赛结果显示，每人猜对了一半，并且没有并列名次。问：实际名次怎样排列？ 2-1 说明下列各式中量词的辖域与变元约束的情况：
（1）(x)A(y)
（2）(x)(A(x)B(x))
（3）(x)(A(x)(y)B(x, y))
（4）(x)(y)(A(x, y)∧B(y, z))∧(x)A(x, y)
（5）(x)(A(x)∧(x)B(x, z)(y)C(x, y))∨B(x, y)
（6）(x)(A(x)B(x))∧(x)C(x)∧D(x)
2-2将公式(x)P(x)(x)Q(x)化成前缀范式。
2.3 将公式(x)(y)((z)(P(x, z)∧P(y, z))(v)Q(x, y, v))化成前缀范式。
3-1设集合X={a, b, c, d}，其上的关系R={<a, b>, <b, a>, <b, c>, <c, d>}，求t(R)。 3-2设集合A的幂集上的包含关系，试对
（1）A={a}
（2）A={a, b}
（3）A={a, b, c}
分别画出偏序集((A), )的哈斯图及其最小元、最大元、极小元和极大元。
3.3 X={a, b, c}；Y={a, b, d}，S={<x, y> | x, y∈X∩Y}，求S的元素。
3.4 设A={a, b, c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性，并画出R的关系图。
3.5 设n, m∈Z+（正整数集合），若集合A中恰有n个元素，那么求在A上能有多少个不同的m元关系？
3.6 若关系R和S都是对称的和传递的，试证明R∩S也是对称的和传递的。
3.7 设A为3元素集，问：
（1）A上自反且对称的关系有多少个？
（2）A上反对称的关系有多少个？
（3）A上既不是对称，也不是反对称的关系有多少个？
3.8 R是二元关系，且R=R•R•R•R，选择下面的哪一个一定是传递的。
（1）R （2）R•R （3）R•R•R （4）R•R•R•R
3.9 求关系的合成。设A={1, 2, 3, 4}，A上二元关系R1, R2分别定义为R1={<2, 2>, <2, 3>, <3, 1>}，R2={<2, 1>, <3, 1>, <3, 4>, <4, 3>}，请计算R1•R2，R2•R1，R12，R22。
3.10 证明题。在这类证明题中，通常为证明两个关系之间的等于，包含及被包含关系。由于关系是一种特殊的集合，在证明此类问题时，通常任选一个关系的元素，然后得出它也属于另一个关系。
设R, S, T均为A上的二元关系，那么证明(S∪T)•R=(S•R)∪(T•R)
3.11 “找出三个元素的集合A和A上关系R，使R, R2, R3, R4两两不等”是可能的吗？如可能请具体做出，并说明这一现象与t(R)=n
i1Ri不矛盾。
3.12 将n个元素的集合划分成两个分块，共有多少种不同的分块？
3.13 设A={1, 2, 3, 4, 5}，那么
（1）A上共有多少个二元关系？
（2）上述关系中，有多少个是等价关系？
请读者根据此题归纳出一般的结论。
3.14 已知N及其关系R如下，试说明R是等价关系，并指出等价类是什么。N是自然数集，R={<ni, nj> | ni/nj能表示成2n形式，n为任意整数}。
解 ni∈X，有ni/nj=1=20，故<ni, nj>∈R，所以R是自反的。
ni, nj∈X，若<ni, nj>∈R，即ni/nj=2k（k是整数），所以nj/ni=2−k，所以<nj, ni>∈R，所以R是对称的。
ni, nj, np∈X，若<nj, ni>∈R∧<nj, np>∈R，则ni/nj=2k1∧ni/nj=2k2（k1, k2是整数），则ni/np=2k1+k2，则<nj, np>∈R，故R是传递的。
总之，R是X上的等价关系，等价类是：
[1]R={1, 2, 4, 8, 16, …, 2n, …}
[3]R={3, 321, 322, …, 32n, …}
[5]R={5, 521, 522, …, 52n, …}
…
3.15 图（a）为一有序集<A, R>的哈斯图。
（1）下列命题那些为真？
aRb，dRa，cRd，cRb，bRe，aRa，eRa
（2）恢复R的关系图。
（3）指出R的最大、最小元，极大、极小元。
（4）求出子集B1={c, d, e}，B2={b, c, d, e}，B3={b, c, d, e}的上、下界，上、下确界。 ■
图 哈斯图和关系图
4.1 找出下图中所有不同的圈。
含圈、路的简单无向图
4.2 给定一右图G=(V, E)如图所示。
G
《离散数学》单元作业题2集合篇三
离散数学作业2_集合与关系
离散数学作业2_集合与关系
1. 设A={1,2,3,4,5}，R是集合A上的二元关系，aRb当且仅当a<b.
(1) 计算R2，R3.
(2) 给出aR2b的充要条件.
(3) 给出aR3b的充要条件.
2. 设A={a,b,c}, R={<a,b>,<b,c>,<c,a>}，求
R2,R3,R4,R∞，R*
《离散数学》单元作业题2集合篇四
离散数学综合作业2集合、关系解答页宽
《离散数学》阶段作业2
一、判断题
1、对任意集合A、B，都有A B和A B，
不能同时成立。 F
例如：A=，B={}，则有A B和A B。{《离散数学》单元作业题2集合}.
2、R1、R2是A上的具有自反性的二元关系，
R1－R2也具有自反性。 F
因为R1－R2不含IA
3、A上恒等关系IA具有自反性、对称性、
反对称性、传递性。 T
4、f：AB，g：BC，若fog是AC的满射，
则f、g都是满射。 F
只能得出g是满射。
5、A ={1，2，3，4}，f是从A到A的满射，
则也是从A到A的单射。 T
二、填空题
1、A－B∪AB = 。
2、A有2个元素，B有3个元素，从A到B的二
元关系有 23 个。
3、R是A上的二元关系，R∪R一定具有的性质是 对称性 。
－1
4、fx= lnx 是从 +到 的函数。
5、f、g都是从A到A的双射，
(fog)－1－1－1。
三、集合
1、A={{a，{b}}，c，{c}，{a，b}}、
B={{a，b}，c，{b}}
求A∪B、A∩B、A－B、AB
解：A∪B = {{a，{b}}，c，{c}，{a，b}，{b}}
A∩B = A={ c，{a，b}}
A－B = {{a，{b}}，{c}}
AB={{a，{b}}，{c}，{b}}
2、A={ {a，{b} }，c，Ø} 求A的幂集。
解：PA={《离散数学》单元作业题2集合}.
{ Ø，{{a，{b}}}，{c}，{Ø}，
{{a，{b}}，c}，{{a，{b}}，{Ø}}，{{c}，{Ø}}，A }
3、证明：A－B∪C = A－B∩A－C
证明：
A(BC)A(BC)AAA(AB)(AC)
四、二元关系
1、A＝{a，b，c，b}，
R＝{<a，b>，<b，a>，<b，c>，<c，d>}
用关系矩阵求R2，写出R2的集合表示。
解：
01M00100010001 000
012M001000010000011000100001000100010001001000010 0
R2＝{<a，a>，<b，b>，<a，c>，<b，d>}
2、指出二元关系满足哪种性质，不满足哪种性质。 1
解：1，1R，3，3R，
R 没有自反性，反自反性；
1，3R，3，1R，
2，1R，1，2R，
3，2R，2，3R，
R 没有对称性，有反对称性；
2，1R，1，3R，2，3R，
R 没有传递性。
2
1，1R，3，3R， R 没有自反性，反自反性；
1，2R，2，1R，
3，1R，1，3R，
3，2R，2，3R，
R 没有对称性，有反对称性；
3，11，1R，3，1 R，
3，11，2R，3，2 R，
1，11，2R，1，2 R，
R 有传递性。
3、 A ={1，2，3，4，5，6}，
S ={ {1，2}，{3}，{4，5，6} }
画出由S产生的等价关系的关系图。
解：
4、A={1，2，3，…，12}整除关系
1 画出偏序集的哈斯图
2 B={1，2，3，4，6，12}并指出B的最大元、
最小元、极大元、极小元；
3指出A的最大元、最小元、极大元、极小元。 解：1
2 B的最大元、极大元：12
最小元、极小元：1
《离散数学》单元作业题2集合篇五
离散数学第二部分测试题-有答案2
离散数学第二部分测试题{《离散数学》单元作业题2集合}.
一、 填空题
1．D={}，则幂集(D){,{}}.
2. B={1，{2，3}}，则幂集(B){,{1},{{2,3}},{1,{2,3}}} 3. 若集合A，B的元素个数分别为Am,Bn，则A到B有 2种不同的二元关系。
4. A={，a，{b}}，B={}，则AB,,a,,{b}, 5. 设A={1，2，3}，则在A上有 5 个不同的划分。
6.设P={<1, 2>, <1, 4>, <2, 3>, <4, 4>}和Q={ <1, 2>, <2, 3>,<4, 2>} 则dom(P∪Q)= {1,2,4} ，ran(P∪Q) = { 2,3,4}
7. IA是集合A上的恒等关系，A上的关系R具有性当且仅当
RR1IA
mn
8. IA是集合A上的恒等关系，A上的关系R具有性当且仅当
IAR
9. 设R为A上的关系，R在A上具有 传递 当且仅当RRR。 10．设R为A上的关系，R在A上自反的当且仅当 IAR 11.设R为A上的关系，R在A上对称的当且仅当RR1
二、 选择题
1．集合A={全班同学}上的同龄关系R为（ B ）
A．对称关系 B．等价关系 C．偏序关系 D．三个都不是 2．在由3个元素组成的集合上，可以有（ D ）种不同的关系。 A． 3； B．8； C．9 ； D．512
3．设集合Aa,b,c,A上的二元关系Ra,a,b,b不具备关系( D )性质
A．传递性 B．反对称性 C．对称性 D．自反性
三、 计算题
1.设集合A={1，2，3}，A上的关系R={<1，1>，<1，2>，<2，2>，<3，2>，<3，3>}
（1） 画出R的关系图； （2） 写出R的关系矩阵
问R具有关系的哪几些特殊性质（自反、对称、传递等）
解 （1）
110
010（2）M
011
该关系是自反的但不是反自反的，因为每个顶点都有个环；它是反对称的
但不是对称的，因为图中只有单向边；它也是传递的，因为不存在顶点x,y,z，使得x到y有边，y到z有边，但x到z没边，其中x,y,z{1,2,3}。
2.设A={0，1，2，3}，R是A上的关系，且
，0>，<0，3>，<2，0>，<2，1>，<2，3>，<3，2>}
用矩阵运算求R的自反闭包r(R)，对称闭包s(R)和传递闭包t(R)。 解
r(R){0,3,2,0,2,1,2,3,3,2}IA
s(R){0,3,3,0,2,0,0,2,1,2,2,1,2,3,3,2}IA
t(R)RR2R3R4
R2{0,0,0,3,0,2,2,0,2,3,2,2,3,0,3,1,3,3}
R3R2R{0,0,0,3,0,2,2,0,2,3,2,2,3,0,3,2,3,3,0,1,2,1}t(R)RR2R3R4
{0,0,0,3,0,2,2,0,2,3,2,2,3,0,3,2,3,3,0,1,2,1,3,1}
3.设A={2,3,4,5,6,7,8,9,10,12,20}，R为整除关系，求下列各题：
（1） 画出偏序集<A,R>的哈斯图； （2） 求该偏序集的极大元和极小元。 解：
（1）哈斯图如下：
R4R3R{0,0,0,3,0,2,2,0,2,3,2,2,3,0,3,2,3,3,0,1,2,1,3,1{《离散数学》单元作业题2集合}.
（2）极大元为7，8，9，12，20；极小元为2，3，5，7。 4.A={1，2，…，12}，
∈A∧2≤x≤4}
在偏序集<A，
>中求B的上界，下界，最小上界和最大下界。
为整除关系，
答案：B的上界：12；下界：1；最小上界：12；最大下界：1
5. 设A={1,2,3,4,5}，A上的偏序关系如图所示，
求A的子集合{3，4，5}和{1，2，3}的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界,填写下列表格：
四、 证明题
1.证明: (A－B)－C＝A－(B∪C) 证明：对任意的x
x(AB)Cx(AB)xC……1分
xAxBxC……1分 xAxBxC……1分
xAxBxC……1分 xAxBC……1分 xABC……1分
或者 (A－B)－C＝(A∩～B) ∩～C……2分 ＝A∩～B∩～C……1分 ＝A∩～(B∪C)……2分 ＝A－(B∪C)……1分
2.设N是自然数集合，定义N上的二元关系R：R证明R是一个等价关系。
证明：（1）对任意x，xx是偶数，有x,xR，所以R是自反；……2分
x,yx,y,xy是偶数，
（2）对任意x,y，若x,yR,即xy是偶数，则yx是偶数，有
y,xR，所以R是对称的；……2分
（3）对任意x,y,z，若x,yR且若y,zR，即xy是偶数，yz是偶数，则xzxyyz2y是偶数，有x,zR，所以R是可传递的；……2分
由（1）（2）（3）知R是等价关系。……1分
《离散数学》单元作业题2集合篇六
《离散数学》试题及答案
一、填空题
1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝; .
2. 设有限集合A, |A| = n, 则 |(A×.
3. 设集合A = {a, b}, B = {1, 2}, 则从A到B .
4. 已知命题公式G＝(PQ)∧R，则G的主析取范式是 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为，分枝点数为 3 .
6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AB＝; AB＝A－B＝.
7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是, .
8. 设命题公式G＝(P(QR))，则使公式G为真的解释有 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则
R1R2 = R2R1 = R12 =(A) - (B)＝
n2
10. 设有限集A, B，
|A| = m, |B| = n, 则| |(AB)| = .
11 设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, xR}, B = {x | 0≤x < 2, xR},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, xR} , A∩B = , .
13. 设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为 .
14. 设一阶逻辑公式G = xP(x)xQ(x)，则G的前束范式是. 15.设G是具有8个顶点的树，则G中增加条边才能把G变成完全图。(完全图的边数
n(n1)
，树的边数为n-1) 2
16. 设谓词的定义域为{a, b},将表达式xR(x)→xS(x)中量词消除 ，写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _.
17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则
RS＝ , R2＝ {(1, 1),(1, 2),(1, 3)}.
二、选择题
1 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( C )。 (A){2}A (B){a}A (C){{a}}BE (D){{a},1,3,4}B.
2 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( D ). (A)自反性 (B)传递性 (C)对称性 (D)反对称性
3 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = {2,3,4,5},则元素6为B的( B )。
(A)下界 (B)上界 (C)最小上界 (D)以上答案都不对
4 下列语句中，( B )是命题。
(A)请把门关上 (B)地球外的星球上也有人
(C)x + 5 > 6 (D)下午有会吗？ 5 设I是如下一个解释：D＝{a,b},
P(a,a) P(a,b) P(b,a) P(b,b)
1 0 1 0
则在解释I下取真值为1的公式是( D ).
(A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y).
6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( C ). (A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).
7. 设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x), H＝xP(x),则一阶逻辑公式GH是( C ). (A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.
8 设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是( A )。 (A)GH (B)HG (C)G＝H (D)以上都不是. 9 设A, B为集合，当( D )时A－B＝B. (A)A＝B (B)AB (C)BA (D)A＝B＝.
10 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( B )。 (A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对 11 下列关于集合的表示中正确的为( B )。
(A){a}{a,b,c} (B){a}{a,b,c} (C){a,b,c} (D){a,b}{a,b,c} 12 命题xG(x)取真值1的充分必要条件是( A ).
(A) 对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1. (D)以上答案都不对.
13. 设G是连通平面图，有5个顶点，6个面，则G的边数是( A ). (A) 9条 (B) 5条 (C) 6条 (D) 11条.
14. 设G是5个顶点的完全图，则从G中删去( A )条边可以得到树. (A)6 (B)5 (C)10 (D)4.
0111110100
，则G的顶点数与边数分别为( D ). 15. 设图G的相邻矩阵为
110111010110110
(A)4, 5
(B)5, 6 (C)4, 10 (D)5, 8.
三、计算证明题
1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界； (3) 写出A的最大元，最小元，极大元，极小元。 解：（1）
8
4
2
12
6
9
（2） B无上界，也无最小上界。下界1, 3; 最大下界是3 （3） A无最大元，最小元是1，极大元8, 12, 9; 极小元是1
2. 设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y) | x, yA 且 x y}, 求 (1) 画出R的关系图； (2) 写出R的关系矩阵.
解：（1）{《离散数学》单元作业题2集合}.
1
1
（2）MR
11
01110011
00 01
3. 设R是实数集合，,,是R上的三个映射，(x) = x+3, (x) = 2x, (x) ＝ x/4,试求复合
映射•，•, •, •，••. 解： (1)•＝((x))＝(x)+3＝2x+3＝2x+3.
(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6, (3)•＝((x))＝(x)+3＝x/4+3, (4)•＝((x))＝(x)/4＝2x/4 = x/2,
(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.
▲4. 设I是如下一个解释：D = {2, 3},
a 3
b 2
f (2) 3
f (3) 2
P(2, 2) 0
P(2, 3) 0
P(3, 2) 1
P(3, 3) 1
试求 (1) P(a, f (a))∧P(b, f (b));
(2) xy P (y, x).
解：
(1) P(a, f (a))∧P(b, f (b)) = P(3, f (3))∧P(2, f (2))
= P(3, 2)∧P(2, 3) = 1∧0 = 0.
(2) xy P (y, x) = x (P (2, x)∨P (3, x))
5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的最大元，最小元，极大元，极小元；
(3) 写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
解：(1) (2)无最大元，最小元1，极大元8, 12; 极小元是1. (3) B无上界，无最小上界。下界1, 2; 最大下界2.
= (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3)) = (0∨1)∧(0∨1) = 1∧1 = 1.
6. 设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。 解：
G = (P→Q)∨(Q∧(P→R))
= (P∨Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧P)∨(Q∧R)
= (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) = (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).
7. (9分)设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G化成前束范式. 解：
G = (xP(x)∨yQ(y))→xR(x)
9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},
(1) 求出r(R), s(R), t(R)； (2) 画出r(R), s(R), t(R)的关系图. 解：（1）
r(R)＝R∪IA＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)},
s(R)＝R∪R1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},
－
= (xP(x)∨yQ(y))∨xR(x) = (xP(x)∧yQ(y))∨xR(x) = (xP(x)∧yQ(y))∨zR(z) = xyz((P(x)∧Q(y))∨R(z))
t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}； (2)关系图:
11. 通过求主析取范式判断下列命题公式是否等价： (1) G = (P∧Q)∨(P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(P∧R)) 解： G＝(P∧Q)∨(P∧Q∧R)