數(shù)理邏輯問答題

數(shù)理邏輯問答題：1.什么是“極小全功能集”，目前常用的極小全功能集有哪幾個(gè)？最小聯(lián)結(jié)詞組是指對(duì)于任何一個(gè)命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價(jià)代換的聯(lián)結(jié)詞組。目前常用的最小聯(lián)結(jié)詞組有：｛「，提，｛「，△｝，｛個(gè)｝，｛口。2：附加前提證明法是推理理論的一個(gè)間接證法，即若要證H1aH2△???△HmnR一C，將R作為附加前提，用直接證法得到C即可。請(qǐng)說明附加前提證明法合理性的理由。若要證H1aH2a???△HnR—C記A=H1AH2A???△Hm「即是要證AnR—C，A—(R—C)是重言式，「Av(「RvC)是重言式，「(AaR)vC是重言式，(AaR)—C是重言式，(AaR)nC即要證4aH2a???△HmaRnC，R作為附加前提，用直接證法得到虻即可。3：請(qǐng)解釋謂詞演算推理理論的US規(guī)則，UG規(guī)則，ES規(guī)則和EG規(guī)則。設(shè)P是謂詞全稱量詞消去規(guī)則，簡稱US規(guī)則：(Vx)P(x)nP(c)，c為個(gè)體域中某個(gè)任意的客體；全稱量詞引入規(guī)則，簡稱UG規(guī)則：P(x)n(Vx)P(x)；存在量詞消去規(guī)則，簡稱ES規(guī)則：Gx)P(x)nP(c)，這里c是論域中的某些客體。存在量詞引入規(guī)則，簡稱EG規(guī)則：P(c)nGx)P(x)，這里c是論域中的一個(gè)客體。集合解答題：1：簡述Warshall在1962年提出的求傳遞閉包的方法。置新矩陣A=M置i=1對(duì)所有j如果A[j,i]=1，則對(duì)k=1,2,…，nA[j,k]=A[j,k]+A[i,k]i=i+1如果i<n,則轉(zhuǎn)到步驟(3)，否則停止。3：什么是集合的劃分，如何根據(jù)集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)系？若把一個(gè)集合A分成若干個(gè)非空子集，使得A中每個(gè)元素屬于且僅屬于一個(gè)分塊，這些分塊的全體叫做A的一個(gè)劃分。設(shè)A的一個(gè)劃分為：S=｛A,A，…,A｝，則R=廿AxA就是由這個(gè)劃分確定A的12kiii=1元素間的一個(gè)等價(jià)關(guān)系。4：什么是商集，如何根據(jù)集合A的一個(gè)等價(jià)關(guān)系R求得A關(guān)于R的一個(gè)商集？關(guān)于R的全體不同的等價(jià)類為元素的集合｛[a]R|aeA｝稱為A關(guān)于R的商集，記為A/R。(3分)把彼此有關(guān)系的元素放在一個(gè)集合中，由這些集合組成一個(gè)集合就是關(guān)于R的商集。(2分)5：什么是偏序關(guān)系？如何確定偏序集〈L,W〉中最大元，極大元。設(shè)A更0，RgAxA，若R是自反的、反對(duì)稱的和傳遞的，則稱R是A上的偏序關(guān)系。設(shè)<A,<>為偏序集，BgA，若存在yeB，使得Vx(xeB—x<y)為真，則稱y為B的最大元；若存在yeB，使得Vx(xeB△y<x—x=y)為真，則稱y為B的極大元。6：已知一個(gè)偏序關(guān)系，如何畫出它的哈斯圖？哈斯圖是簡化的偏序關(guān)系圖，具體畫法如下：用小圓圈代表元素；若xWy，x豐y，將代表y的小圓圈放在代表x的小圓圈之上，如果<x,y>eCOVA，則在y與x之間用直線連接。集合證明題1：設(shè)A，B，C是三個(gè)集合，證明：Ac(B-C)=(AcB)-(AcC)。證明過程：Ac(B-C)=Ac(Bc~C)(AcB)-(AcC)=(AcB)c~(AcC)=(AcB)c(~AD~C)=(AcBc~A)D=(AcBc~C)所以Ac(B-C)=(AcB)-(AcC)。2：證明對(duì)集合A、B和^有(AHB)UC=An(BUC)當(dāng)且僅當(dāng)CgA。證明：“n”必要性：已知CgA，有ADC=A(AcB)dC=(AdC)c(bdC)=Ac(BDc)“U”充分性：已知(AcB)Dc=Ac(BDC)設(shè)任意的xeC，則xeCD(acb)nxeAc(bdc)nxeACga3：設(shè)R為集合A上的二元關(guān)系，如果R是反自反的和可傳遞的，則R一定是反對(duì)稱的。設(shè)R不是反對(duì)稱的，即存在<x,y>eR△<y,x>eR時(shí)有x豐y，則由R是可傳遞的得<x,x>,<y,y>eR,與R是反自反的矛盾，所以R不是反對(duì)稱的不成立，即R一定是反對(duì)稱的。4：設(shè)A={1，2,3}，在P(A)上規(guī)定二元關(guān)系如下：R={<s,t>ls,teP(A)a(IsI=I11)}(其中：P(A)為A的冪集，|s|為集合的元素個(gè)數(shù))證明：R是P(A)上的等價(jià)關(guān)系；寫出商集P(A)/R。證明過程：任取seP(A)，因?yàn)镮sl=lsl，所以有<s，s>eR，即日是自反的。任取<s，t>eR，有l(wèi)sl=l11，所以有<t，s>eR，即R是對(duì)稱的。任取<x，y>eR△<y，z>eR，有l(wèi)xl=lyl△lyl=lzl，從而lxl=lzl，所以<x，z>eR，即R是是傳遞的。由上面證明可知，R是等價(jià)關(guān)系。商集P(A)/R={[?],[{1}]，[{1，2}]，[{1，2,3}]}或：P(A)/R={{?},{{1},{2},{3}}，{{1，2},{1，3},{2,3}},{{1，2,3}}5：設(shè)R是A上具有自反性和傳遞性的關(guān)系。T是A上的關(guān)系，<x,y>ET當(dāng)且僅當(dāng)<x,y>GR且<y,x>GR。證明T是一個(gè)等價(jià)關(guān)系。證明：要證明T是自反的，對(duì)稱的和傳遞的，T才是等價(jià)關(guān)系。VxEA,因?yàn)镽是自反性的，所以<x,x>GR，由<x,x>GRA<x,x>GR^<x,x>GTo所以T是自反的。V(x,y)ET^g<x,y>ERAvy,x>ER。由<y,x>ERAvx,y>ER得vy,x>ET，所以T是對(duì)稱關(guān)系。V(x,y)ETA(y,z)ET,則vx,y>ERA<y,x>ERA<y,z>ERAvz,y>ER。由已知，R是傳遞關(guān)系，由vx,y>ERAvy,z>ER，得<x,z>ER,由vz,y>ERA<y,x>ER得vz,x>ER。由vx,z>ERAvz,x>ER得vx,z>ET，從而T是傳遞關(guān)系。由(1)(2)(3)得T是自反的，對(duì)稱的和傳遞的，從而T是等價(jià)關(guān)系。6：設(shè)R是一個(gè)二元關(guān)系，S={<a,b>|對(duì)于某一c,有<a,c>ER且<c,b>ER}，證明若R是一個(gè)等價(jià)關(guān)系，則S也是一個(gè)等價(jià)關(guān)系。證明過程：設(shè)R是定義在集合A上的二元關(guān)系，則S也是A上的二元關(guān)系，又由于R是等價(jià)關(guān)系，所以R具有自反性，對(duì)稱性和傳遞性。對(duì)于任意aEA，由R的自反性得<a,a>ER，又由<a,a>ERA<a,a>ERn<a,a>eS，所以S具有自反性。對(duì)于有任意a，beA，有<a,b>eS，則3c，使得<a,c>eRA<c,b>eR，由R的對(duì)稱性得<b,c>eRA<c,a>eR，從而由S的定義得<b,a>eS。所以S具有對(duì)稱性。對(duì)于任意a，b，ceA，如果<a,b>eS,<b,c>eS，則3c1,c2，有(<a,c1>eRA<c1,b>eR)A(<b,c2>eRA<c2,c>eR)，由R的傳遞性得<a,b>eRA<b,c>eRn<a,c>eS,所以S具有傳遞性。因?yàn)榫哂凶苑葱?，?duì)稱性和傳遞性，所以S是等價(jià)關(guān)系。7：設(shè)集合A={a,b,c,d}，A上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}寫出關(guān)系R的關(guān)系矩陣；求日的自反閉包，對(duì)稱閉包和傳遞閉包；求包含R的最小的等價(jià)關(guān)系。a'0100'b1010M=Rc0001d、0000/(1)(2)r(R)=RUIA={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}S(R)=RURc={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>}t(R)=RUR2UR3UR4={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>，<b,b>，<b,d>，<a,c>,<a,d>}也可用Warshall算法計(jì)算t(R)。包含R的最小的等價(jià)關(guān)系=r(R)US(R)Ut(R)={<a,b>,<a,c>,<a,d>,<b,a>,<b,c>，<b,d>,<c,d>,<d,c>}UIA8：設(shè)I+是正整數(shù)集,A={<x,y>|xEI+Ay^I+},R={<<x,y>,<u,v>>|xv=yuA<x,y>GAA<u,v>EA}，證明R是一個(gè)等價(jià)關(guān)系。證明過程：對(duì)任意<x,y>EA，由于xy=yx，有<<x,y>,<y,x>>ER，所以R具有自反性。對(duì)任意<<x,y>,<u,v>>ER，有xv=yu，即uy=vx,從而有<<u,v>,<x,y>>ER所以R具有對(duì)稱性。對(duì)任意<<x,y>，<u,v>>ERA<<u,v>，<w,z>>ER，有xv=yuAuz=vw,nxz=yw,I由定義得<<x,y>，<w,z>>GR，所以R具有傳遞性。由于R具有自反性，對(duì)稱性和傳遞性，所以R是等價(jià)關(guān)系。9:設(shè)A={1,2,3,…,9}，在AxA上定義關(guān)系R:?a,b〉,<c,d?eR當(dāng)且僅當(dāng)a+d=b+c，證明R是AxA上的等價(jià)關(guān)系，并求出[<2,5>]r。證明過程：要證明R是自反的，對(duì)稱的和傳遞的，R才是等價(jià)關(guān)系。V<a,b>eAxA，因?yàn)閍+b=a+b，所以V<<a,b〉,va,b>>eR，所以r是自反的。V<<a,b>,<c,d>>eR，則從而V<<c,d>,<a,b>>eR，所以r是對(duì)稱的。V<<a,b>,<c,d>>eR，<<c,d>,<e,f>>eR，則a+d=b+c,c+f=d+e，將上式左右相加得a+f=b+e,即V<<a,b>,<e,f>>eR，所以r是傳遞的。綜上所述，R是等價(jià)關(guān)系。[<2,5>]r是一個(gè)等價(jià)類集合，由和<2,5>有關(guān)系的元素構(gòu)成。[<2,5>]R={<1,4>,<2,5>,<3,6>,<4,7>,<5,8><6,9>}R10：若R和S都是非空集A上的等價(jià)關(guān)系，則RcS是A上的等價(jià)關(guān)系。證明：因?yàn)镽和S都是非空集A上的等價(jià)關(guān)系，所以R和S都有自反性，對(duì)稱性和傳遞性。VxeA，則<x,x>eR△<x,x>eS，所以<x,x>e