山东交通学院《离散数学》试卷2016-2017学年第一学期期末试卷

1、设集合M={a，φ}，N=｛{a｝,φ}则MnN=。3、设集合H={1，2，3，4则H上的关系R=｛<x,y>x+y是偶数｝具有。A、自反性、反对称性和传递性B、反自反性、反对称性和传递性C、反自反性、对称性和传递性D、自反性、对称性和传递性4、设T是一棵完全二叉树，则T的每个结点都。A、至少有两个子结点B、至多有两个子结点C、恰有两个子结点D、可以有任意多个子结点政A、结合律B、交换律C、分配律D、幂等律A、简单通路B、初级通路C、简单回路D、初级回路A、10B、13C、11D、6二、填空题（本大题共8题，共10个空，每空2分，共20分）3、设集合M={1,2，3，5}，则M的幂集P（M）包含个元素。4、设T是一棵有n(n之2）个顶点的树，则T有条边.___________________7、设D是有向图，若D的基图是连通图，则称D是图8、既不含也不含的无向图称为简单图.3、设集合A={1，2，3，4，5}，关系R={<x，y>x，yA且x整除y｝,要R1、用命题公式将下列命题符号化:2和5是偶数，当且仅当5〉2。2、用谓词公式将下列命题符号化：1、在命题逻辑系统中用归结法证明下列推理是有效的:前提:sq，pq,s2、在谓词逻辑系统中写出下列推理的（形式)证明：6。设命题公式G=（P→Q）∨（Q∧（P→R)求G的主析取范式.11。通过求主析取范式判断下列命题公式是否等价：13.设R和S是集合A＝{a，b,c，d｝上的关系,其中R(a，a)a,cb，c)c，d)｝,证明题1。利用形式演绎法证明:{P→Q，R→S，P∨R}蕴涵Q∨S.：｛4.n—15.零元6。半群7。弱连通8。平行边环三.EQ\*jc3\*hps35\o\al(\s\up0(1),2)R|EQ\*jc3\*hps35\o\al(\s\up18(3),4)EQ\*jc3\*hps35\o\al(\s\up18(0),0)EQ\*jc3\*hps35\o\al(\s\up18(0),0)EQ\*jc3\*hps35\o\al(\s\up18(1),0)EQ\*jc3\*hps35\o\al(\s\up18(0),1)EQ\*jc3\*hps35\o\al(\s\up18(0),0)|四五11)s前提引入（5）M(x）2,4析取三段论（8）P（x）5,7假言推理=（P∨Q）∨(Q∧（P∨R))=（P∧Q）∨（Q∧（P∨R)）=(P∧Q∧R)∨(P∧Q∧R)∨（P∧Q∧R)∨（P∧Q∧R)∨(P∧Q∧R）∨（P∧Q∧R)=（P∧Q∧R）∨(P∧Q∧R）∨(P∧Q∧R)∨(P∧Q∧R）∨(P∧Q∧R）As(RR∪R－1(a，b）,(b，a),（b,c)，(c，b)（c，d）,(d,c）}，ababr(R)bd=(P∧Q∧R）∨(P∧Q∧R)∨（P∧Q∧R）=m∨m∨m=（3，6,7）H=（P∨（Q∧R)）∧（Q∨(P∧R）)=(P∧Q）∨(Q∧R）)∨(P∧Q∧R)=(P∧Q∧R)∨（P∧Q∧R）∨(P∧Q∧R)∨(P∧Q∧R)∨（P∧Q∧R）=(P∧Q∧R）∨（P∧Q∧R）∨(P∧Q∧R)=m∨m∨m=（3,6,7)G，H的主析取范式相同，所以G=H.EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),0EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),0)EQ\*jc3\*hps36\o\al(\s\up11(1),1)EQ\*jc3\*hps36\o\al(\s\up11(0),0)EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),1)EQ\*jc3\*hps36\o\al(\s\up11(0),1)－1a,a),（c,a)c，b）,（d,c)}，PPQ(2)(3）Q（4）PQ（5)(6)Q(7)2。证明:（A—B）-C=（A∩~B）∩~C=A∩(~B∩~C）=A∩~(B∪C)=A-(B∪C）3.证明:{A∨B，C→B,C→D}蕴涵A→D