05-06(1)《離散數(shù)學(xué)》期末考試試題(A)

PAGE北京交通大學(xué)2005-2006學(xué)年第一學(xué)期《離散數(shù)學(xué)》期末考試試卷（A）一、填空題（共16分，每空2分）我們稱(chēng)為命題。在命運(yùn)題邏輯中，任何命題公式的主合取范式都存在，并且是。設(shè)集合，A的冪集。在推理理論中，前提在推導(dǎo)過(guò)程中的任何時(shí)候都可以引入使用，這一推理規(guī)則叫做。設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有對(duì)稱(chēng)性和性，則稱(chēng)R是相容關(guān)系。設(shè)R是集合A上的二元關(guān)系，如果R是自反的，則它的關(guān)系矩陣的主對(duì)角線元素。設(shè)R是集合A上的二元關(guān)系，R-1是R的逆關(guān)系，則R的關(guān)系矩陣與R-1的關(guān)系矩陣具有的關(guān)系是。設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有自反性、和傳遞性，則稱(chēng)R是A上的一個(gè)偏序關(guān)系。二、選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中。（共16分，每小題2分）下列語(yǔ)句中不能成為命題的是（）。A．小王是我的同學(xué)，也是我的好朋友；B．地球外的星球上也有人；C．11+1=100；D．我正在說(shuō)慌。下列各式中，哪一個(gè)是析取范式（）。A．?PùQ；B．?PùPù(QúR)；C．Pù(?(?QúR))；D．?Pù(Qú?R)。個(gè)體域?yàn)檎麛?shù)集合，下列公式中（）不是命題。A．(x)(y)(x*y=y)； B．(x)(y)(x*y=1)；C．(x)(x*y=x)； D．(x)(y)(x*y=2)下列謂詞公式中（）不正確。A．(x)(A(x)B)(x)A(x)B；B．(x)(BA(x))B(x)A(x)；C．(x)(BA(x))B(x)A(x)；D．(x)(A(x)úB)(x)A(x)úB；下列命題中正確的是（）。A．∪{}=； B．{,{}}-{{}}={}；C．{,{}}-{}={，{}}； D．{,{}}-={{}}；設(shè)A,B,C為任意三個(gè)集合，下列各命題中正確的是（）。A．若AB且BC，則AC； B．若AB且BC，則AC；C．若AB且BC，則AC； D．若AB且BC，則AC。設(shè)R1，R2是集合A={a，b，c，d}上的兩個(gè)關(guān)系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，則R2是R1的（）閉包。A．自反B．對(duì)稱(chēng)C．傳遞D．以上都不是設(shè)偏序關(guān)系R是集合A={1，2，3，4，5，6}中數(shù)的“整除”關(guān)系，則A的極大元、極小元的個(gè)數(shù)分別是（）。A．2，1B．2，2C．3，1D三、計(jì)算題（共40分，每小題10分）求命題公式(P(QR))((PQ)(PR))的真值表。通過(guò)求主析取范式判斷下列命題公式是否等值。（1）（PùQ）ú（?PùQùR）；（2）（Pú（QùR））ù（Qú（?PùR））；將公式x((yP(x，y))(zQ(z)R(x)))化成等價(jià)的前束范式：設(shè)已知集合A={1,2,3,4,5,6}上的等價(jià)關(guān)系R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3)(6,6)}求A的由R誘導(dǎo)出的劃分和A關(guān)于R的商集。四、證明題（共28分）用等價(jià)變換方法證明：P?(Q?B)(P?Q)?(P?R)用歸納法證明(A1?B)ù(A