- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[嘉应学院离散数学2013年12复习本科
命题逻辑部分
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上的等价关系,由此得到三个等价
文档评论(0)