二 (本题10分)设是一个含有3个符号的集合，是上的所有字符串所 构成的集合，求的基数，并证明你的结论。
三 （本题12分）设<A，＋，·>是一个环，在集合AA （AA表示所 有从A到A的函数所成之集合）上定义加法与乘法如下：对AA中 的任意两个元素f，g，定义 (f＋g)(x)=f(x) ＋g(x) (f·g)(x)=f(x)·g(x) 证明，<AA，＋，·>是一个环。 进一步，令S是A的一个子环，证明 是<AA，＋，·>的一个子环。
注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。 2. 命题教师和审题教师姓名应在试卷存档时填写。
西北工业大学命题专用纸
问偏序集 < ，≤ >是否是一个格？是否是一个分配格？是否 有全上界？是否有全下界？ 7) 一阶谓词逻辑系统FC中的公式是否是可满足的？为什么？其 中，P是一个二元谓词，f是一个一元函词。 8) 在模态命题逻辑系统NSK中，公式(□A→◇A)是否是系统的定 理？是否是可满足的？为什么？
├ （A→（B→C））→（B→（A→C）） （要求给出形式证明，而不是使用真值表来证明） 六 （本题10分）请将下面的陈述用模态命题公式表示出来，并说 明其是否为永真：
“可能必然下雨，则可能下雨。” 级
学 号
姓 名
一 （本题共48分，每小题6分）简答题 1) 设A是一个无限集合，B是A的真子集，问B的基数是否一定小于A 的基数？请举例说明。 2) 两个可数集合的交集是否是可数集合，为什么？ 3) 三维欧几里得空间中所有点的集合的基数是多少，为什么？ 4) 代数系统＜I，＋，×＞是由普通的整数集合及其上的普通加法 和乘法运算构成的一个环，请给出它的一个非平凡子环。如果你认 为该代数系统没有非平凡子环，则请说明理由。 5) 设a、b是域中的两个不为0的元素，问是否有 ? 请对你的结论 给出说明。 6) 设是一个有限的符号集合，表示上所有有限长度字符串构成的集 合。对于中的任意两个元素s和t,当且仅当存在中的元素u，使 s·u=t时， 称s≤t成立（s·u表示字符串的连接运算）。易见 ≤是上的一个偏序关系。
四 （本题10分）设<S，∪，∩>是一个格，其中∪和∩分别是保联 运算和保交运算。S的非空子集J若满足以下条件就称为S的一 个理想：
1) ； 2) 。
证明： 1) 理想J是S的子格，而S的任意子格却不一定是它的理想。 2) 设h是格S到S’的同态映射（即对保联和保交运算保持），A是
S的子格，J是S的理想，则h(A)是h(S’)的子格，h(J)是h(S)的理 想。 五 （本题10分）在命题逻辑形式系统PC中，证明
诚信保证 本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守 考场规则，诚实做人。 本人签字：
编号：
西北工业大学考试试题（卷）
2008 －2009 学年第 二 学期
开课学院 计算机学院
课程 离散数学II
学时 48
考试日期 2009.5.26 考试时间 2 小时 考试形式（闭）（A）卷
题号 一 二 三 四 五 六 七 总分