【正文】 1） 非空半序集合，其中某些子集沒(méi)有最大元素；2） 非空半序集合，其中有一子集存在最大下界，但沒(méi)有最小元素；3） 非空序集合，其中有一子集存在上界，但沒(méi)有最小上界。IA所以，R205。A，(a,b)206。B上的半序關(guān)系。?2) (217。?2) (?3的定義)222。?3222。的結(jié)合律、交換律)222。((a,c)206。((a,c)206。?2 (?1，?2都是自反的)222。B222。（a1，a2）∈?1∧（b1，b2）∈?2 證明?3是AB上的半序關(guān)系。A是傳遞的)222。A180。((a,b)206。(a,b)206。(A180。p)222。A180。((a,b)206。(a,b)206。(A180。(a,a)206。(a,a)206。A180。X，所以a∈X，由于R在X上是自反的，故此（a，a）∈R；由于a∈A，顯然（a，a）∈AA；所以（a，a）∈R∩（AA），即（a，a）R1。1）{1，2，3，4}2）{2，3，6，12，24，36}3）{1，2，3，4，5，6，7，8，9，10，11，12}4213243612623[解] 1）的Hasse圖 2）的Hass圖 在3）的Hasse圖中可以看出，1191263105718423）的Hasse圖①{2，3，6}的最大元素為6；極大元素也為6；極汴元素為2和3；上確界為6；下確界為1；沒(méi)有最小元素。如果∏1∩∏2=198。R (R是對(duì)稱的)所以，R是循環(huán)的；32．設(shè)∏1和∏2是非空集合A的劃分，說(shuō)明下面各種情況哪些是A的劃分？哪些不是A的劃分？哪些可能是A的劃分？并闡明理由。)：（a）R是自反的：因?yàn)镽是等價(jià)關(guān)系，所以R是自反的；（b）R是循環(huán)的：對(duì)任何a，b，c206。A，(a,b)206。A，(a,b)206。（c）R是傳遞的對(duì)任何（a，b）∈R，（b，c）∈R，由于R是循環(huán)的，所以（c，a）∈R，利用R是對(duì)稱的，就得到（a，c）∈R。根據(jù)A上的劃分與A上的等價(jià)關(guān)系一一對(duì)應(yīng)的原理，我們只需求出A上有多少個(gè)劃分就行了。 ；綜合這兩方面，就有=R1 ；4）是。A，(a,b)206。R1)222。另一方面，結(jié)任何（a，b）∈R1，由于R1是自反的，故此（b，b）∈R1，從而由復(fù)合關(guān)系之定義，有（a，b）∈R1R1，所以R1?，從而=R1，因此由R1是等價(jià)關(guān)系，知也是等價(jià)關(guān)系。28．設(shè)R1和R2是非容集合A上的等價(jià)關(guān)系，對(duì)下列各種情況，指出哪些是A上的等價(jià)關(guān)系；若不是，用例子說(shuō)明。R1關(guān)系圖 R2關(guān)系圖 R1∪R2關(guān)系圖而且|A|不可能再少了。(a,c)206。R2217。R1217。(b,c)206。R2 (R1，R2都是對(duì)稱的)222。R2222。(a,a)206。25．設(shè)R1和R2都是集合A上的等價(jià)關(guān)系1）證明R1∩R2也是A上的等價(jià)關(guān)系；2）用例于證明R1∪R2不一定是A上的等價(jià)關(guān)系（要盡可能小地選取集合A）。R217。217。222。綜合（a）（b）（c）可知是等價(jià)關(guān)系。[答] 上述推導(dǎo)不正解。2）[解] 因?yàn)閧（2，5）}R = {（a，b）|（a，b）∈AA（a，b）R（2，5）} = {（a，b）|（a，b）∈AA∧a+5 = b+2} = {（a，b）|（a，b）∈AA∧b = a+3} ={（1，4），（2，5，（3，6），（4，7），（5，8），（6，9））3）[答] R?AA不對(duì)。2)由于R+是包含R的最小傳遞關(guān)系，所以，取R1=R+即為所求。[解] 1）作圖法：R的關(guān)系圖 （R）的關(guān)系圖51234123455143253241 S（R）的關(guān)系圖 t（R）的關(guān)系圖因此：r（R）={（1，1），（1，2），（2，2），（2，3），（2，5），（3，3），（3，4），（4，3），（4，4），（5，5）}s（R）={（1，2），（2，1），（2，3），（2，5），（3，2），（3，4），（4，3），（5，2），（5，5）}t（R）={（1，2），（1，3），（1，4），（1，5），（2，3），（2，4），（2，5），（3，3），（3，4），（4，3），（4，4），（5，5）}2）矩陣運(yùn)算法：Mr（R）==MS（R）====MRοR=MRMR===MR=因此r（R），s（R），t（R）與1）作圖法一致。令A(yù)={a，b，c}，R1={（a，b），（b，a）}，R2={（b，c），（c，b）}。[解] 1）真。若k=n，則由（ai，ak）∈R2必有I=n，所以無(wú)論1≤j≤n1還是j=n，由R2的定義，有（ai，aj）=（an，aj）∈R2；若1≤k≤n1，則由（ai，ak）∈R2必有1≤j≤n1故此（ai，aj）∈R2總之證得= R2，綜合兩方面，我們證明了= R2。于是=R2=AA。所以R1R3?R2R3。因而Zij=xij∨yij=0；綜合上述兩種情況，就有zji=xij∨yij，i=1，2，……，m，j=1,2,……n。(x,y)∈ (R=)222。(x,y)∈222。(y,x)∈R (R是對(duì)稱關(guān)系)219。 (因IA199。R=198。(x,y)∈R (IA是幺關(guān)系，因此是自反關(guān)系)222。)首先 198。):對(duì)任何x，x∈A222。充分性若R∩ ?IA，則對(duì)任何（x，y）∈R及（y，x）∈R，從逆關(guān)系的定義，可得（x，y）∈R及（x，y）∈，也即（x，y）∈R∩，利用R∩ =IA可得（x，y）∈IA，于是x=y。這不可能，矛盾。R，從而（x，x）∈R′，由IA={（x，x）|x∈A} 可知IA?R′。5） R5是反自反的，反對(duì)稱的，傳遞的。2）R2是反自反的，對(duì)稱的。（BC）另一種證明方法：（A197。B，y∈C。（BC）。A且x∈B。x∈A \ B217。的結(jié)合律、交換律)222。(x∈A217。x207。(x∈A217。所以（AC）\（BC）205。B，y∈C 于是（x，y）∈AC，且（x，y）∈（A\B）C，且（x，y）207。D）與（AＣ）197。D）。B）（C197。（AC）\（BD）。（AC）\（BD）。事實(shí)上有：（AC）∪（BD）205。B）（C197。(x∈B217。x∈A∩B217。因而（A∩B）（C∩D）205。A，所以由205?！臕=B若AB=198。這說(shuō)明A中每個(gè)元素x，其結(jié)構(gòu)為元組的無(wú)窮次嵌套構(gòu)成，這不可能。{a}，，{a，b}}2BB{（198。Ｃ及Ａ197。C）2）（A∪B）∩（B∪C）205。B=A197。198。反之，當(dāng)A=B時(shí)，顯然A\B=B\A=198。所以a∈B\A，從而a207。=A\B=B=198。2）不一定。 (零壹律)=B∪(A∩B′) （條件A∩B′=198。222。A′∪B；所以，A′∪B=Ｘ。X，所以根據(jù)定理2的3162。A∪B=B （定理4）222。B219。C，所以，x∈A\C。因此（A\B）\C205。B\C。B，x207。B∪C，也就是說(shuō)x207。}}}5）{198。}}5）{{a，b}，{a，a，b}，{a，b，a，b}}[解] 1）{198。C。A∈C。 3）如果A205。例如A={a}，B={a，b}，C={{a}，a，b}，從而ACB∧B∈C，但A∈C。 2）如果A∈B∧B∈C，則A∈C。因?yàn)?98。}4）198。3. 確定下列各命題的真假性：1）198。216。I217。離散數(shù)學(xué)輔助教材概念分析結(jié)構(gòu)思想與推理證明第一部分集合論劉國(guó)榮交大電信學(xué)院計(jì)算機(jī)系離散數(shù)學(xué)習(xí)題解答習(xí)題一 （第一章集合）1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶數(shù)∧ x＜15}2）B={x|x∈N∧4+x=3}3）C={x|x是十進(jìn)制的數(shù)字}[解] 1）A={2，4，6，8，10，12，14}2）B=198。n179。($d206。205?！蕒198。是集合{198。 3）如果A204。5．對(duì)任意集合A，B，C，確定下列命題的真假性： 1）如果A∈B∧B205。B∧B∈C，則A205。2）假。4）假。{a}，，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}2）{，{a}，{{b，c}}，{a，{a，b}}}3）{198。{{a，b}}}7．給定自然數(shù)集合N的下列子集：A={1，2，7，8}B={ x|x2＜50}C={x|x可以被3整除且0≤x≤30}D={x|x=2K，K∈I∧O≤K≤6}列出下面集合的元素：1） A∪B∪C∪D2） A∩B∩C∩D3） B\（A∪C）4） （A′∩B）∪D[解] 因?yàn)锽={1，2，3，4，5，6，7}，C={3，6，9，12，15，18，21，24，27，30}，D={1，2，4，8，16，32，64，}，故此 1）A∪B∪C∪D={1，2，3，4，5，6，7，8，9，12，15，16，18，21，24，27，30，32，64}2）A∩B∩C∩D=198。A，x207。C，x∈A\C。由x∈A\C，可知x∈A， x207。（A\B）\C。又由x207。A′∪B=X219。B=A∪B （等號(hào)=的對(duì)稱性）222。）就有A′∪B205。(2)次證A′∪B=X222。A205。）=(B∪A)∩(B∪B′) (分配律)=(A∪B)∩(B∪B′) (∪的交換律)=(A∪B)∩X (互補(bǔ)律)=A∪B (零壹律)222。例如：A={a}，B={a，b}，C={b，c}。所以當(dāng)A\B=B時(shí)有A=B=198。A，矛盾。因此，A\B=B\A的充要條件是A=B。=A，由已知條件A197。198。AB′[解] 1）成員表如下A B CA197。（Ｂ197。{a}），（198。我們討論的元素的結(jié)構(gòu)必須是由元組的有限次嵌套構(gòu)成。則A=198。的反對(duì)稱性A=B。（AC）∩（BD）另一方面，對(duì)任一（x，y）∈（AC）∩（BD），于是有（x，y）∈AC且（x，y）∈BD，因而x∈A，y∈C，x∈B y∈D。y∈C∩D222。y∈D) (217。D）=（AC）197。（A∪B）（C ）205。因?yàn)锳\B205。 3）不成立。D）205。所以（AＣ）197。（BD）無(wú)任何包含關(guān)系。BC（否則x∈B），所以（x，y）∈（AC）\（BC）。（AB）C。y∈C)217。B)218。x207。(x∈A217。y∈C222。因此（x，y）∈（AC）197。則（x，y）∈AC且（x，y）207。因此（x，y）∈（A197。B）C=（（A\B）∪（B\A））C（對(duì)稱差的定義）=（（（A\B）C）（（B\A）C）（叉積對(duì)并運(yùn)算的分配律）=（（AC）\（BC）∪（BC）\（AC））（根據(jù)4））=（AC）197。3）R3是自反的，對(duì)稱的，傳遞的，因此是等價(jià)關(guān)系。6） R6是自反的，對(duì)稱的，傳遞的，循環(huán)的。于是IA∩R?R′∩R=198。3）必要性，若R是對(duì)稱的，則對(duì)任何（x，y）∈R，就有（y，x）∈R。所以R是反對(duì)稱的。(x,x)∈IA (IA是幺關(guān)系，因此是自反關(guān)系)222。205。(x,x)∈R則與R是反自反關(guān)系，(x,x)207。 ；220。R=198。(x,y)∈所以，R=；220。(x,y)∈R217。(y,x)∈R所以，R是對(duì)稱的；13．設(shè)A、B為有窮集合，R，S?AB，MR=（xij）mn，MS=（yij）mn1）為了R?S，必須且只須ij（xij≤ yij）2）設(shè)MR∪S=（Zij）mn，那么Zij=xijVyij，I=1，2……，m，j=1，2，……n.3）設(shè)MR∩S=（tij）mn，那么tij=xij^yij i=1，2，……m；j=1，2，……，n.[證] 由于A、B是有窮集合，不妨設(shè)A={a1，a2……，am}，B={b1，b2，……，bn}1）必要性若R?S，則對(duì)任何i∈{1，2，……，m}，對(duì)任何j∈{1，2，……n}，若（ai，bj）∈R，則R的關(guān)系矩陣MR=（xij）mn中第I行第j列元素xij=1，根據(jù)R?S，可得（ai，bj）∈S，從而得S的關(guān)系矩陣MS=（yij）mn中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）207。3）對(duì)任何i∈{1，2，……m}，對(duì)任何j∈{1，2，……，n}。2）對(duì)任何（x，y）∈R3R1，由復(fù)合關(guān)系之定義，必有z∈A，使得（x，z）∈R3且（z，y）∈R1，再由復(fù)合關(guān)系之定義，有（x，y）∈R3R2。2）由于A是有限個(gè)元素的集合，是不心設(shè)A={a1，a2，……an}令R1={（ai，aj）|ai∈A∧aj∈A∧|≤i≤n∧|≤j≤n|}R2={（an，an）∪R1} 則R1R2，即R1與R1是不同的關(guān)系。17．設(shè)R是集合A上的反對(duì)稱關(guān)系，|A|=h，指了在R∩的關(guān)系矩陣中有多少個(gè)非零