【正文】 立的大頭針，甲、乙兩人輪流把這些直立的大頭針扳倒。規(guī)定每人每次可扳倒1至根，且扳倒最后一根直立的大頭針者為獲勝者。試證明：如果甲先扳且(m+n)不能整除n，則甲總能獲勝。證明以下的二重歸納原理的正確性： 設(shè)i0, j0206。N。假定對(duì)任意自然數(shù)i≥i0及j≥j0，皆有一個(gè)命題P(i, j)滿足： i) P(i0, j0)真； ii)對(duì)任意自然數(shù)k≥i0及l(fā)≥j0，若P(k, l)真，則P(k+1, l)和P(k, l+1)皆真。則對(duì)任意自然數(shù)i≥i0及j≥j0，P(i, j)皆真。證明：若n206。N，則n207。n。證明：若n, m206。N，則n204。 m當(dāng)且僅當(dāng)n206。 m。證明：若n, m206。N，則n206。 m當(dāng)且僅當(dāng)n+206。 m+。證明：若n, m206。N，則n＜m當(dāng)且僅當(dāng)有x206。N使m = n+ x+。證明：若n206。N，則不可能有m206。N使n＜m＜n+。 設(shè)A={0,1}，B={1,2}。試確定下列集合：a) A{1}Bb) A2Bc) (BA )2 證明或用反例推翻下列命題：a) (A∪B)(C∪D)= (AC)∪(BD) b) (A∩B)(C∩D)= (AC)∩(BD)c) (A－B)(C－D)= (AC)－(BD) d) (A197。B)(C 197。D)= (AC)(BD) 如果B∪C205。A，則(AB) －(CD)= (A－C) (B－D)。這個(gè)命題對(duì)嗎？如果對(duì)，則給予證明；如果不對(duì)，則舉出反例。f) 證明：若x206。C且y206。C，則x, y206。195。 (195。(C))。證明：a206?！萢, b且b206?！萢, b。把三元偶a, b, c定義為{{ a },{ a, b },{ a, b, c }}合適嗎？說(shuō)明理由。為了給出序偶的另一定義，選取兩個(gè)不同集合A和B(例如取A=198。，B={198。})，并定義a, b={{ a, A },{b, B}}。證明這個(gè)定義的合理性。第二章 二元關(guān)系 列出從A到B的關(guān)系R中的所有序偶。a) A={0, 1, 2}，B={0, 2, 4}，R={x, y| x, y 206。 A∩B }b) A={1, 2, 3, 4, 5}，B={1, 2, 3}，R={x, y| x 206。A, y 206。B且x =y2}設(shè)R1和R2都是從{1, 2, 3, 4}到{ 2, 3, 4}的二元關(guān)系，并且R1={1, 2,2, 4,3, 3 }R2={1, 3,2, 4,4, 2 }求R1∪R2, R1∩R2, domR1, domR2, ranR1, ranR2, dom(R1∪R2)和ran(R1∪R2)。設(shè)和都是從集合到集合的二元關(guān)系。證明dom(R1∪R2)= domR1∪domR2ran(R1∩R2)205。 ranR1∩ranR2用L和D分別表示集合{1, 2, 3, 6}上的普通的小于關(guān)系和整除關(guān)系，試列出L, D和L∩D中的所有序偶。給出滿足下列要求的二元關(guān)系的實(shí)例：a) 既是自反的，又是反自反的；b) 既不是自反的，又不是反自反的；c) 既是對(duì)稱(chēng)的，又是反對(duì)稱(chēng)的；d) 既不是對(duì)稱(chēng)的，又不是反對(duì)稱(chēng)的。試判斷下面的論斷正確與否。若正確，請(qǐng)加以證明；若不正確，請(qǐng)給出反例。 設(shè)R和S都是集合A上的二元關(guān)系。若R和S都是自反的(反自反的，對(duì)稱(chēng)的，反對(duì)稱(chēng)的，或傳遞的)，則R∩S，R∪S，R－S，R197。S也是自反的(反自反的，對(duì)稱(chēng)的，反對(duì)稱(chēng)的，或傳遞的)。描述R上的下列二元關(guān)系S的性質(zhì)：a) S={x, y|x, y206。R且x y ＞0}；b) S={x, y|x, y206。R，4整除|x－y|且|x－y|＜10}；c) S={x, y|x, y206。R，x2 =1且y ＞0}；d) S={x, y|x, y206。R，4 |x|≤1且| y|≥1}。設(shè)n, m206。I+。若集合A恰有n個(gè)元素，則在A上能有多少個(gè)不同的m元關(guān)系？證明你的結(jié)論。設(shè)x和z都是由從集合A到集合B的二元關(guān)系構(gòu)成的集類(lèi)，并且z 198。證明a) dom(∪x)=∪{domR|R206。x}； b) ran(∪x)=∪{ranR|R206。x}；c) dom(∩z)205?！蓒domR|R206。z}；d) ran(∩z)205?！蓒ranR|R206。z}；設(shè)R為集合上的一個(gè)二元關(guān)系。如果R是反自反的和傳遞的，則R一定是反對(duì)稱(chēng)的。1設(shè)R為集合上的一個(gè)二元關(guān)系，若令fldR=domR∪ranR則fldR=∪(∪R)。1若R為集合上的一個(gè)二元關(guān)系，則也是∪(∪R)上的二元關(guān)系。習(xí)題 1. 設(shè)集合A={1,2,3,4,5,6}上的二元關(guān)系R為R={1,1,2,2,3,3,4,4,5,5,6,6,1,2,2,1,1,3,3,1,2,3,3,2,4,5,5,4}試畫(huà)出R的關(guān)系圖GR，求出R的關(guān)系矩陣MR,并指出R所具有的性質(zhì)。2. ={1,2,3}上的十二個(gè)二元關(guān)系的關(guān)系圖，寫(xiě)出相應(yīng)的關(guān)系矩陣，并指出各個(gè)關(guān)系所具有的性質(zhì)。3. ,D和L199。D，畫(huà)出它們的關(guān)系圖，并寫(xiě)出它們的關(guān)系矩陣。4. 設(shè)A為恰有n個(gè)元素的有限集。a) 共有多少個(gè)A上的不相同的自反關(guān)系？a) 共有多少個(gè)A上的不相同的反自反關(guān)系？b) 共有多少個(gè)A上的不相同的對(duì)稱(chēng)關(guān)系？c) 共有多少個(gè)A上的不相同的反對(duì)稱(chēng)關(guān)系？d) 共有多少個(gè)A上的不相同的既是對(duì)稱(chēng)又反對(duì)稱(chēng)的關(guān)系？1. 設(shè)R為非空有限集A上的二元關(guān)系。如果R是反對(duì)稱(chēng)的，則R199。R1的關(guān)系矩陣MR199。R1中最多能有多少個(gè)元素為1？2. 設(shè)R為集合A上的二元關(guān)系，則R200。R1為A上包含R的最小對(duì)稱(chēng)關(guān)系，R199。R1為A上的包含在R中的最大對(duì)稱(chēng)關(guān)系。3. 設(shè)IA為集合A上的恒等關(guān)系，即IA={x, x|x206。A}。則對(duì)A上的任意二元關(guān)系R，A上的二元關(guān)系IA200。R200。R1必是自反的和對(duì)稱(chēng)的。4. 設(shè)R為任意的二元關(guān)系。證明a) domR1=ranR。b) ranR1=domR。 設(shè)集合{a, b, c, d}上的二元關(guān)系R1和R2為R1={a, a,a, b,b, d}；R2={a, d,b, c,b, d,c, b}。試求R2oR1，R1o R2，及。若R為任意集合上的空關(guān)系或全關(guān)系，則R2=R。舉出使R1o(R2∩R3)204。 (R1oR2)∩(R1oR3), (R2∩R3)o R4204。 (R2oR4)∩(R3oR4)成立的二元關(guān)系R1，R2，R3和R4的實(shí)例。設(shè)R1和R2都是集合A上的二元關(guān)系。證明或用反例推翻以下的論斷：a) 如果R1和R2都是自反的，則R1oR2也是自反的；b) 如果R1和R2都是反自反的，則R1oR2也是反自反的；c) 如果R1和R2都是對(duì)稱(chēng)的，則R1oR2也是對(duì)稱(chēng)的；d) 如果R1和R2都是傳遞的，則R1oR2也是傳遞的；設(shè)A={0，1，2，3}上的二元關(guān)系R1和R2為R1={i,