嘉应学院离散数学2013年12复习本科.doc

一、 命题逻辑部分1计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？p q ppq (pq) (pq)q0 00 11 01 1110011010010000011111111 11110011 11110011 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq) (qp) rqp pq p q r2设 A、B是两个命题公式，证明：a) AB当且仅当AB是永真式。b) AB的充要条件是AB且BA。等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：ABAB BA.3证明 P(QR)Q(PR) R(Q P)4证明从前提PQ，(QR)可演绎出P.5证明RS可从前提P(QS)，RP和Q推出。6、使用推理规则或归结推理，论证推理形式1) PQ, RQ ,RS, SQ P2) PQ, SQ, R, RS P二、 集合与关系1、 AB (BA)2、 (AB)=(A)(B)3、定理3.5.1 对于任意集合S，有SS。证明：设有集合S使S S，由此构造一个单元集S，显然S S，即S不空。由正则公理可知S有极小元，而S只有元素S，故SS= 。但由假设S S，所以SS ，矛盾。4、定理3.5.2 对任何集合S1和S2，都有(S1S2S2S1)。证明：设S=S1，S2，假设有(S1S2)(S2S1)，则S1 (S2 S)且S2 (S1 S)。于是S2 S ， S2 S ，而S1与S2都是S的极小元，故与正则公理矛盾。因此对对任何集合S1和S2，都有(S1S2S2S1)5、一个集合A是传递集当且仅当AP(A)。6、从集合的观点来定义有序对=x,x,y，解释其合理性。6、设R=，试求r(R)，s(R)和t(R)7、设R、S、T、W为关系，证明1) (RS)-1=R-1S-12) RSTW R*TS*W3) R*(ST)=(R*S) (R*T)4) (R*S)-1=S-1*R-18、设R是实数集合，定义RR上关系Q： Q 当且仅当 u+y=x+v，证明Q是RR上等价关系。9、习题35。10、已知集合a,b,c,d,e上的一个关系R=,，若将其中的有序对解释成为：从结点x到结点y的有向边连接，则关系R可表示为一个有向图模型，如下1)计算关系R的传递闭包t(R)，并在上图中画出其余的连接边。2)若用矩阵来表示关系R，写出Mt(R)的形成过程。三、 代数部分1、定理12.2.5 给定且 | S |1。如果，eS，其中和e分别为关于的零元和幺元，则 e。 2、定理12.2.6 给定及幺元eS。如果是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。 3、定理12.2.7 给定及幺元eS。如果是可结合的并且x的逆元x-1存在，则x-1是惟一的。4、给定 且f为其满同态映射，则(a)如果满足结合律，则也满足结合律。(b)如果满足交换律，则也满足交换律。5、定理12.4.1 设与是同类型的且f为其同态映射。对应于f，定义关系Ef如下：xEf y：=f(x)= f(y)， 其中x，yS 则Ef是中的同余关系，并且称Ef为由同态映射f所诱导的同余关系。 6、习题7、8、9、12。7、积代数：例题12.6.1.8、两个代数系统来源于同一个代数系统，说明两个代数结构,之间的关系(_同构，同构映射_)，解释对应的两种运算，_，_并用一个命题公式表示(PQ) PQ)。代数结构一样，表明运算规则相同，但当元素的角色不同时，具体的运算含义不一样。*abaabbbb01001111101100004、 设Z为整数集合，代数系统，+，为通常的加法与乘法运算。定义Z上的关系E=|x-y=3k，kZ,x,yZ，E为Z上的等价关系，由此得到三个等价类分别为0E=,-6,-3,0,3,6,，1E=,-5,-2,1,4,7,，2E=.,-4,-1,2,5,8,。证明E为上的同余关系：设,E，即x1-y1=3m,x2-y2=3n,有1)(x1+x2)-(y1+y2)=3(m+n)，所以E。2)(x1x2)-(y1y2)=3(y1n+y2m+2mn)，E.说明：同余关系是一个高级的等价关系，即针对集合Z上的运算“+,”方式，仍然封闭。可以定义商集Z/E=0E, 1E, 2E中的运算” ，”xEyE=x+yExE yE=xyE这两种新定义的运算直接依赖于源系统中的运算形成一个商代数。它与源代数结构具有类似的运算规则_同态：因为存在一个自然同态映射为：gE(x)=xE (自然同态)gE(x+y)=x+yE =xEyE = gE(x) gE(y)gE(xy)=xyE =xE yE = gE(x) gE(y)以上说明：由同余关系可以构造出与源代数系统同态的代数系统。另一种方法：直接定义一个同态映射f:ZZ3=0,1,2f(i)=(i)(mod 3)与同态，a+3 b=(a+b)(mod 3)a3 b=(ab)(mod 3)与同构是比较明显的，但产生方式不同，一个来源于同余关系，不需要直接定义同态映射或者说与同态映射无关；一个源于直接定义或寻找同态映射。同态映射并不强调对原集合进行划分，但可以诱导出