离散数学 刘任任 课后答案 习题2 VIP免费

习题二1.确定下列二元关系：（1）BABAyxyxRBA,,,5,3,1,3,2,1（2）AAxyxRAy2,,8,6,5,4,3,2,1,0解：(1)R{,,,,,,,}11133133(2)R{,,,,,,,}102142832.请分别给出满足下列要求的二元关系的例子：（1）既是自反的，又是反自反的；（2）既不是自反的，又不是反自反的；（3）既是对称的，又是反对称的；（4）既不是对称的，又不是反对称的.解：设R是定义在集合A上的二元关系。(1)令A，则R，于是R既是自反又是反自反的；(2)令AR{,},{,}1211，于是R既不是自反又不是反自反的；(3)令AR{,},{,,,}121122，于是R既是对称又是反对称的；(4)令AR{,,},{,,,,,}123122113，于是R既不是对称又不是反对称的。3.设集合A有n个元素，试问：（1）共有多少种定义在A上的不同的二元关系？（2）共有多少种定义在A上的不同的自反关系？（3）共有多少种定义在A上的不同的反自反关系？（4）共有多少种定义在A上的不同的对称关系？（5）共有多少种定义在A上的不同的反对称关系？解：设An，于是(1)共有22n种定义在A上的不同的二元关系；(2)共有22nn种定义在A上的不同的自反关系；(3)共有22nn种定义在A上的不同的反自反关系；(4)共有2221212nnnnn()/()/种定义在A上的不同的对称关系；(5)共有02223mnkmknmmkC种定义在A上的不同的反对称关系，其中，mnn()12。4.请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征.解：(1)自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。(2)反自反关系矩阵的主对角线上元素全为0;而关系图中每个结点上均无圈。(3)对称关系矩阵为对称矩阵;而关系图中任何两个结点之间的有向弧是成对出现的,方向相反。(4)反对称关系矩阵MrRijnn()的元素满足：当ij时，rrijji0。5．设2,3,4,2,3,2,4,1,4,2,2,1,1,1,4,3,2,1SRA，试求,,,2RRSSR及2S.解：RSSR••{,,,},{,}141334RS22111214223433{,,,,,},{,,,,,}。6.试举出使TRSRTSRPTPSPTS成立的二元关系PTSR,,,的实例.解：设RTSP{,,,},{,,,},{,,,},{,,,}3132133212232131,于是,有STRSTRSRT,(),{,,,},{,}323333,因此,()(){,}RSRT33,从而,RSTRSRT()()()。又，(),{,},{,,,}STPSPTP113111，因此，()(){,}SPTP11，从而,()()()STPSPTP。7.设R和S是集合A上的二元关系.下面的说法正确吗?请说出理由.（1）若R和S是自反的，则SR也是自反的；（2）若R和S是反自反的，则SR也是反自反的；（3）若R和S是对称的，则SR也是对称的；（4）若R和S是反对称的，则SR也是反对称的；（5）若R和S是传递的，则SR也是传递的解：(1)正确。因为对任意xA，有xRxSx,，所以xRSx()。故RS是自反的。(2)错误。例如，设xyAxy,,，且xRyySx,，于是xRSx()。故RS不是自反的。(3)错误。例如，设对称关系RxzzxSzyyz{,,,},{,,,}。于是，xyRS,，但yxRS,。故RS不是对称的。(4)错误。例如，设反对称关系RxzywSzywxxy{,,,},{,,,},。于是，xyyxRS,,,。故RS不是反对称的。(5)错误。例如，设传递关系RxwyvSwyvzwv{,,,},{,,,},。于是，xRSyyRSz(),()，但因为wv，所以，xzRS,。8．设1R和2R是集合A上的二元关系，试证明：（1）2121RrRrRRr；（2）2121RsRsRRs；（3）2121RtRtRRt并举出使1A时使2121RtRtRRt的实例.解：(1)rRRRRRR()()()1212120()()RRRR121020()()RRRR110220rRrR()()12(2)sRRRRRR()()()1212121()()RRRR...