①┐(?x)P(x) P（附加前提） ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)
解：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。
本题符号化为：
(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P ④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I ⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧
b)设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车 本题符号化为：
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③ ⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥
⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。 设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。 S（x）：x是优秀生。c：小张。 本题符号化为：
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c) ①G(c) P（附加前提） ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P ⑥ L(c) T④⑤I ⑦G(c) →L(c) CP
注意：本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S（x）：x是优秀生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证
仍是有效的。
3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解：Z1={} Z2={
,L和D刀均定义于{1,2,3,6}，分别写出L和D的所有元素并求出L∩D.
解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>} D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L∩D= {<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} 3-5.5对下列每一式，给出A上的二元关系，试给出关系图： a){
证明 a）设S为传递的，若＜x，z＞∈S○S，则存在某个y∈X，使得＜x，y
＞∈S，且＜y，z＞∈S。 若S是传递的，＜x，z＞∈S，所以（S○S）?S。 反之，设（S○S）?S ，假定＜x，y＞∈S且＜y，z＞∈S，则＜x，z＞∈S○S。因为（S○S）?S，故＜x，z＞∈S，得到S是传递的。 b）设S是自反的，令＜x，y＞∈IX，则x=y。但＜x，x＞∈S，因此＜x，y＞=＜x，x＞∈S，得IX?S。 反之，令IX?S，设任意x∈X，＜x，x＞∈IX，故＜x，x＞∈S，因此S是自反的。 c）设S是反对称的。假定＜x，y＞∈S∩Sc，则 ＜x，y＞∈S∧＜x，y＞∈Sc?＜x，y＞∈S∧＜y，x＞∈S 因为S是反对称的，故x＝y， 所以＜x，y＞＝＜x，x＞∈IX，即S∩Sc?IX。 反之，若S∩Sc?IX，设＜x，y＞∈S且＜y，x＞∈S，则 ＜x，y＞∈S∧＜x，y＞∈Sc ?＜x，y＞∈S∩Sc ?＜x，y＞∈IX 故x＝y，即S是反对称的。 3-7.3 设S为X上的关系，证明若S是自反和传递的，则S○S=S，其逆为真吗 ？ 证明 若S是X上传递关系，由习题3-7.2a）可知（S○S）?S， 令＜x，y＞∈S，根据自反性，必有＜x，x＞∈S，因此有＜x，y＞∈S○S，即S?S○S。得到 S=S○S. 这个定理的逆不真。例如X={1，2，3}，S={＜1，2＞，＜2，2＞，＜1，1＞}，3-8.1 根据图3-8.1中的有向图，写出邻接矩阵和关系R，并求出R的自反闭包和对称闭包。 解 a M1 1 0 R= 0 0 1 b c 0 1 0 图3-8.1 R={＜a，a＞，＜a，b＞，＜b，c＞，＜c，b＞＝ r（R）= R∪IX ={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝ s（R）= R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞} 3-8.2 设集合A={a，b，c，d}A上的关系 R={＜a，b＞，＜b，a＞，＜b，c＞，＜c，d＞} a） 用矩阵运算和作图方法求出R的自反、对称、传递闭包； b） 用Warshall算法，求出R的传递闭包。 解 a） 0 1 0 0 MR= 1 0 1 0 0 0 0 1 0 0 0 0 R的关系图如图所示。 a b d c M0 1 0 0 1 0 0 0 1 1 0 0 R+MIA= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 r（R）= R∪IA ={＜a，a＞，＜a，b＞，＜b，a＞，＜b，b＞，＜b，c＞，＜c，c＞，＜c，d＞，＜d，d＞}（图（a）） a b d c 图（a） 0 1 0 0 0 1 0 0 0 1 0 0 MR+MRc= 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 + 0 1 0 0 = 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0
3-10.1 设R和R′是集合A上的等价关系，用例子说明：R∪R′不一定是等价关系。 证明 设 A={1，2，3}，S=R∪R′ R={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞} R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，2＞，＜2，3＞} 则R∪R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞，＜3，2＞，＜2，3＞} 因为如＜2，3＞∈S∧＜3，1＞∈S，但＜2，1＞?S，故R∪R′不是传递的，即R∪R′不是A上的等价关系。 3-10.2 试问由4个元素组成的有限集上所有等价关系的个数为多少？ 解 因为集合X上的等价关系与X的划分是一一对应的，所以4个元素的有限集上等价关系的数目，与4个元素集合进行划分的数目是相同的，由习题3-9.1可知共有15个不同的等价关系。 3-10.3 给定集合S={1，2，3，4，5}，找出S上的等价关系R，此关系R能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解 我们可用如下方法产生一个等价关系： R1={1，2}×{1，2}={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞} R2={3}×{3}={＜3，3＞} R3={4，5}×{4，5}={＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} R= R1∪R2∪R3={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} 关系图如图。 3-9.1 4个元素的集合共有多少不同的划分。 解 整数4可划分为：4，1+3，1+1+2，2+2，1+1+1+1。 121 1+C4+C4+ C42+1=15（种） 2 3-9.2 设{A1，A2，?，Ak}是集合A的一个划分，我们定义A上的一个二元关系R，使＜a,b ＞∈R当且仅当a和b在这个划分的同一块中。证明R是自反的，对称的，和传递的。 证明 设对任意a∈A，则必存在Ai，使a∈Ai，因a与a必可看作在同一块中，故有＜a,a＞ ∈R。即R是自反的。 3-10.4 设R是一个二元关系，S={＜a，b＞∣对于某一c，有＜a，c＞∈R∧＜c，b＞∈R}，设a,b∈A，若有＜a,b＞∈R，则a与b必在同一块，故b与a亦在同一块，＜b, a＞∈R，即R是对称的。 对任意a,b,c∈A， ＜a,b＞∈R∧＜b,c＞∈R ?（?i）（a∈Ai∧b∈Ai）∧（?j）（b∈Aj∧c∈Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧b∈Ai∩Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧Ai∩Aj≠?） ?（?i）（?j）（a∈Ai∧c∈Aj∧i=j）（∵i≠j?Ai∩Aj= ?） ?a,c在同一块 ?＜a,c＞∈R ∴R传递 证明若R是一个等价关系，则S也是一个等价关系。 证明 设R是A上的等价关系： （1） 对任一x∈A，因为R在A上自反，所以＜x，x＞∈R。由S定义，＜x，x＞∈S，所以S是自反的。 （2） 对任意x,y∈A，若＜x，y＞∈S，则存在某个c，使得＜x，c＞∈R∧＜c，y＞∈R，因为R是对称，故有：＜y，c＞∈R∧＜c，x＞∈R，由S的定义，可知＜y，x＞∈S，所以S是对称的。 （3） 对任意x,y,z∈A，若＜x，y＞∈S，及＜y，z＞∈S，则必存在某个c1，使＜x，c1＞∈R，＜c1，y＞∈R。由R的传递性，可知＜x，y＞∈R，同理存在c2，使＜y，c2＞∈R∧＜c2，z＞∈R，由R传递，可知＜y，z＞∈R。再由S定义，得＜x，z＞∈S。故S是传递的。 3-10.5 设正整数的序偶集合A，在A上定义二元关系R如下：＜＜x,y＞, ＜u,v＞＞∈R，当且仅当xv=yu，证明R是一个等价关系。
