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

命题逻辑部分 1．计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？ p q ?p ?púq ? (?púq) ? (?púq)ùq 0 0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 2．设 A、B是两个命题公式，证明： a) A?B当且仅当A?B是永真式。b) A?B的充要条件是A?B且B?A。 等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：A?B?A?B ù B?A. 3．证明 P→(Q→R)?Q→(P→R)? ┐R→(Q→ ┐P)证明从前提P?Q，┐(QR)可演绎出┐P证明R?S可从前提P?(Q?S)，┐RP和Q推出。???├?Q, R??Q ,R∨S, S??Q ├?P 2) ?P?Q, S??Q, ?R, R∨S ├ P 集合与关系 AìBT ┐(BìA) ∪(A∪B)=(∪A)∪(∪B) 3、定理3.5.1 对于任意集合S，有S?S。 证明：设有集合S使S ∈S，由此构造一个单元集{S}，显然S ∈{S}，即{S}不空。由正则公理可知{S}有极小元，而{S}只有元素S，故S∩{S}= ?。但由假设S ∈S，所以S∩{S} ≠ ?，矛盾。 4、定理3.5.2 对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)。 证明：设S={S1，S2}，假设有(S1∈S2)∧(S2∈S1)，则S1 ∈(S2 ∩S)且S2 ∈(S1 ∩S)。于是S2 ∩S ≠ ?， S2 ∩S ≠ ?，而S1与S2都是S的极小元，故与正则公理矛盾。因此对对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1) 5、一个集合A是传递集当且仅当A?P(A)。 6、从集合的观点来定义有序对x,y={{x},{x,y}}，解释其合理性。 6、设R={a，b，b，c，c，a}，试求r(R)，s(R)和t(R) 7、设R、S、T、W为关系，证明 1) (R?S)-1=R-1?S-1 2) R?S?T?W ?R?T?S?W 3) R?(S?T)=(R?S) ? (R?T) 4) (R?S)-1=S-1?R-1 8、设R是实数集合，定义R?R上关系Q： u,vQx,y 当且仅当 u+y=x+v，证明Q是R?R上等价关系。 9、习题35。 10、已知集合{a,b,c,d,e}上的一个关系R={a,b,b,c,c,d,d,e}，若将其中的有序对x,y解释成为：从结点x到结点y的有向边连接，则关系R可表示为一个有向图模型，如下 1)计算关系R的传递闭包t(R)，并在上图中画出其余的连接边。 2)若用矩阵来表示关系R，写出Mt(R)的形成过程。 代数部分 1、定理12.2.5 给定S，⊙且 | S |＞1。如果θ，e∈S，其中θ和e分别为关于⊙的零元和幺元，则θ ≠ e。 2、定理12.2.6 给定S，⊙及幺元e∈S。如果⊙是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。 3、定理12.2.7 给定S，⊙及幺元e∈S。如果⊙是可结合的并且x的逆元x-1存在，则x-1是惟一的。 4、给定X，⊙ ~ Y，?且f为其满同态映射，则 (a)如果⊙满足结合律，则?也满足结合律。 (b)如果⊙满足交换律，则?也满足交换律。 5、定理12.4.1 设S，⊙与T，*是同类型的且f为其同态映射。对应于f，定义关系Ef如下： xEf y：=f(x)= f(y)， 其中x，y∈S 则Ef是S，⊙中的同余关系，并且称Ef为由同态映射f所诱导的同余关系。 6、习题7、8、9、12。 7、积代数：例题12.6.1. 8、两个代数系统来源于同一个代数系统，说明两个代数结构{0,1},⊙,{0,1},?之间的关系(_同构，同构映射_┐)，解释对应的两种运算，⊙_ú，?_ù并用一个命题公式表示(┐(PúQ) ?┐Pù┐Q)。代数结构一样，表明运算规则相同，但当元素的角色不同时，具体的运算含义不一样。 * ? ? ? ? ? ? ? ? ⊙ 0 1 0 0 1 1 1 1 ? 1 0 1 1 0 0 0 0 设Z为整数集合，代数系统Z，+，?，+，?为通常的加法与乘法运算。定义Z上的关系E={x,y|x-y=3k，k∈Z,x,y∈Z}，E为Z上的等价关系，由此得到三个等价