華東師范大學(xué)離散數(shù)學(xué)章炯民課后習(xí)題第4,5章答案

1、 P591(1).用謂詞公式表達(dá)語(yǔ)句“所有的運(yùn)動(dòng)員都?xì)J佩某些教練”，個(gè)體域?yàn)槿倐€(gè)體域。解：P(x):x是運(yùn)動(dòng)員，G(y):y是教練，R(x,y):x欽佩y。原題量詞表達(dá)為：x(P(x)T,y(R(x,y)AG(y)此題錯(cuò)誤較多：1.x,yR(P(x),G(y)2.x,y(P(x)AG(y)TR(x,y)3.R(x):x欽佩某些教練3.將x(C(x),y(C(y)AF(x,y)翻譯成漢語(yǔ)，其中C(x)表示x有電腦，F(xiàn)(x,y)表示x和y是同班同學(xué)，個(gè)體域是學(xué)校全體學(xué)生的集合。解：學(xué)校的全體學(xué)生要么自己有電腦，要么其同班同學(xué)有電腦。80%能正確解釋。5.給定解釋I如下：個(gè)體域D：-2,3,6；個(gè)

2、體常元a：6；謂詞P：21，Q(x)：x3，R(x)：x5。求出謂詞公式x(PQ(x)R(a)在解釋I下的真值。解：R(a)總為1,故x(PQ(x)R(a)為x(PtQ(x)1=1都能做對(duì)最后答案。有的學(xué)生將D的每個(gè)元素代入求得，有的學(xué)生做法如上。(2).指出謂詞公式xy(P(x,y)Q(y,z)A,xR(x,y)的指導(dǎo)變?cè)?、量詞的轄域、約束變?cè)妥杂勺冊(cè)?。解：第一個(gè)x是指導(dǎo)變?cè)?，相?yīng)的轄域是y(P(x,y)Q(y,z)；第二、四個(gè)x是約束變?cè)?；第三個(gè)x是指導(dǎo)變?cè)?，相?yīng)的轄域是R(x,y)；第一個(gè)y是指導(dǎo)變?cè)?，相?yīng)的轄域是：(P(x,y)Q(y,z)；第二，三個(gè)y是約束變?cè)坏谒膫€(gè)y是自由變?cè)?/p>

3、；第一個(gè)z是自由變?cè)＜矗褐笇?dǎo)變?cè)旱谝粋€(gè)x,第三個(gè)x,第一個(gè)y轄域：y(P(x,y)Q(y,z)，R(x,y)，(P(x,y)Q(y,z)約束變?cè)旱诙€(gè)x,第四個(gè)x,第二個(gè)y,第三個(gè)y自由變?cè)旱谒膫€(gè)y,第一個(gè)z約一半學(xué)生錯(cuò)在第一個(gè)X為指導(dǎo)變?cè)獣r(shí)的轄域，錯(cuò)寫為(P(x,y)Q(y,z)，其余的正確。(1).求謂詞公式xy(P(x,y)oQ(x,y)T,xyR(x,y)的前束范式。解：xy(P(x,y)oQ(x,y)T,xyR(x,y)=xy(P(x,y)oQ(x,y)T,uvR(u,v)=xy(P(x,y)Q(x,y)A(Q(x,y)P(x,y)T,uvR(u,v)=,x,y(P(x,y)

4、AQ(x,y)(Q(x,y)AP(x,y),uvR(u,v)=,x,y,uv(P(x,y)AQ(x,y)(Q(x,y)AP(x,y)R(u,v)三分之一的學(xué)生出錯(cuò)。1.o不化簡(jiǎn)2.沒有改變相同的量詞，并將相同的量詞合并。3.計(jì)算錯(cuò)誤。11.構(gòu)造x(P(x)Q(x),x(Q(x)TR(x),xR(x)nxP(x)的形式證明。解：xR(x)R(e)x(Q(x)t,R(x)Q(e)T,R(e)，Q(e)x(P(x)vQ(x)P(e)vQ(e)x(P(x)前提引入U(xiǎn)S規(guī)則前提引入us規(guī)則析取三段論前提引入U(xiǎn)S規(guī)則P(e)EG規(guī)則析取三段論此題出錯(cuò)較多：1.誤用量詞的推理規(guī)則，如xR(x)前提引入R(x

5、)US規(guī)則2.形式證明的格式不規(guī)范15.證明下面的推理：“每個(gè)科研工作者都是努力工作的。每個(gè)努力工作而又聰明的人都取得事業(yè)的成功。某個(gè)人是科研工作者并且聰明。所以，某人事業(yè)取得成功。”解：命題符號(hào)化，個(gè)體域?yàn)槿?。定義謂詞P(x):x是科研工作者，Q(x):x努力工作，R(x):x是聰明的人，M(x):x事業(yè)取得成功.前提：x(P(x)tQ(x),x(Q(x)R(x)tM(x),x(P(x)R(x)結(jié)論:xM(x)構(gòu)造形式證明x(P(x)R(x)前提引入P(a)R(a)ES規(guī)則P(a)化簡(jiǎn)規(guī)則x(P(x)tQ(x)前提引入P(a)Q(a)US規(guī)則Q(a)假言推理規(guī)則R(a)Q(a)附加規(guī)則x(Q

6、(x)R(x)tM(x)前提引入(Q(a)R(a)TM(a)US規(guī)則M(a)假言推理規(guī)則xM(x)EG規(guī)則基本正確補(bǔ)充：用謂詞公式表達(dá)語(yǔ)句“本班的學(xué)生都已學(xué)過微積分”，個(gè)體域分別取ECNU的學(xué)生集合和本班的學(xué)生集合。解：個(gè)體域取ECNU的學(xué)生集合:P(x):x是本班學(xué)生，G(x):x學(xué)過微積分。則x(P(x)tG(x)個(gè)體域取本班的學(xué)生集合:P(x):x學(xué)過微積分，則xP(x)個(gè)體域取ECNU的學(xué)生集合時(shí)出錯(cuò)較多：H(x):X是ECNU的學(xué)生x(h(x)G(x)用謂詞公式表達(dá)語(yǔ)句“班上無(wú)人恰給另外兩個(gè)同班同學(xué)發(fā)過電子郵件”，個(gè)體域取本班學(xué)生的集合。解：p(x,y)：x給y發(fā)過電子郵件，論域?yàn)榘?/p>

7、上學(xué)生。原題量詞表達(dá)為：3x3y3z(p(x,y),p(x,z),(yMz),(xMz),(xMy),Vw(p(x,w)(w=y)(w=z)正確解答此題的學(xué)生很少。大都只表達(dá)了“給另個(gè)兩個(gè)同學(xué)發(fā)過電子郵件”，忽略“恰恰”。P81集合X=a,b,c上的一個(gè)關(guān)系R的關(guān)系矩陣如下(左)，請(qǐng)寫出這個(gè)關(guān)系。(注：矩陣的第1、2、3行以及第1、2、3列，分別對(duì)應(yīng)X中的元素a、b、c)。TOC o 1-5 h zab101010- HYPERLINK l bookmark0101-_Ccd解：R=(a,a),(a,c),(b,b)，(c,a),(c,c)全部正確一集合上的一個(gè)關(guān)系的關(guān)系圖如上圖(右，所示，請(qǐng)

8、寫出這個(gè)關(guān)系。解：R=(a，a，(a，b，(b，a，(b，b，(c，a，(c，d，(c，c，(d，d，全部正確6.設(shè)R是X到Y(jié)的二元關(guān)系，S是Y到Z的二元關(guān)系，證明(RS)-i=S-iR-i。解：對(duì)Vx,yeR,e(RoS)-iow(ROS)omu(wR,gS)omu(wS-i,GR-i)oG(S-iR-i)故(ROS)-i=S-iR-i基本正確7(2).設(shè)R、S、T都是X上的關(guān)系。證明：RO(SHT)匸(ROS)H(ROT),(RnS)OTu(ROT)n(S。解：對(duì)Vx,yeX,gRO(SnT)3u(eR,GSnT)3u(,RA,SA,T)3u(,RA,SA,TA,R)mu(,RA,S)A3u(,TA,R),(RS)A,(RT),(RS)n(RT)故R(SnT)(RS)n(RT)對(duì)Vx,y,X,(Rns)T3u(,RnSA,T)3u(,Ra,SA,T)3u(,Ra,SA,TA,T)3u(,RA,T)A3u(,SA,T),(RT)A,(ST),(RT)n(ST)故(Rns)Tu(RT)n(sT)基本正確，少數(shù)學(xué)生敘述雜亂，表達(dá)不清。或沒看清題意，證明=8.設(shè)X和Y都是有限集，|X|=m,|Y|=n。問X到Y(jié)的不同的關(guān)系有多少個(gè)？解：共2mn個(gè)大