发信人: yanyr (yyr), 信区: CS
标 题: F982，F983班数理逻辑期末考试试题
发信站: 饮水思源站 (Sun Jul 23 20:14:04 2000) , 转信
以下是F982，F983班数理逻辑期末考试试题
（有些符号无法打印改为语言叙述。“≤”，“≥”代表集合包含关系。
“ R（＋）”代表R的传递闭包。“⊙”代表函数复合关系。)：
集合与逻辑（2000）
（下面带※号的是附加题）
1。给定函数 ｆ：Ａ－>B（Ａ，Ｂ不空），由ｆ诱导出的集函数为 f〖。〗：P（
A）－>P（B）。
设 X 属于P（A），Y属于P（B），f 〖X〗定义为：f〖x〗：x属于X 。
（1）。集函数 f 〖〗的逆函数（也是集函数）总是存在的，试给出其定义
（记为f（－1）〖。〗）。
（2）。Sｈｏｗ f〖f（－1）〖Y〗〗＝（Y与f〖A〗的交集）。
（3）。Sｈｏｗ f（－1）〖f〖X〗〗≥X。举反例说明，反向一般不成立。
问：f 满足什么条件时，等号成立？证明你的判断。
2。设下标ｉｎｄｅｘ集 I 是可数无限的（又称可列）。对每一ｉ∈Ｉ，Ａｉ是
可数集。
问：集合（对任意的i 属于I ，A i 的并集）的基数是什么？证明你的论断。
3。令 R 是非空集 A 上的二元关系： R ≤ A× A 。试证：
R 是传递封闭的（ｉ.ｅ.Ｒ（＋）＝Ｒ）当且仅当Ｒ⊙Ｒ≤Ｒ。
4。（给出一个数论函数的归纳法定义，实际上就是给定了计算该函数的一个算法
）
下面 ，m , n 均为自然数。
（1）。ｒｅｍ为“除以所得的余数”，给定 N 上的后继函数 S（x）。
用归纳法定义二元函数 ｒｅｍ：Ｎ×Ｎ－>Ｎ；
rem(a,b)=b<a?b:rem(a-b,b)
※（２）。ｇｃｄ（ｍ，ｎ）表示ｍ与ｎ的最大公约数，试用归纳法定义二元函
数ｇｃｄ（ｍ，ｎ）。
if (y == 0) {
return x;
} else {
return gcd (y, x % y);
}
5。（1）。直接从T a r s k i 语义出发，验证：
|= 对 任意的ｘ，（ f （x）－> g ）－>（存在着的 x ，f （x）－> g）；
其中g 是语句。此外，须注明，在论证的哪一步要用到“g 是语句”这一条件。
（2）。用 T a b l e a u方法证明：
|－ 对 任意的ｘ，（ f （x）－> g （x））－>（对 任意的ｘ，f （x）－>
对 任意的ｘ，g（x））；
|≠ （对 任意的ｘ，f （x）－>对 任意的ｘ，g （x））－>对 任意的ｘ，（
f （x）－> g（x））；
6。设 L ＝〔S，ｆ＋，ｇ×，ｃ〕为数论语言，N ＝< N ，S，＋，×，O>为自
然数的标准模型。
（1）。说明：有足够的 L－闭项（指：对每一自然数 n 属于N，有一闭项
Tn 代表之，使 Tn =n。）
（2）。令 P （x）表示性质：x 是素数（prime），给出性质 P 的一个 F
O 规范（一个L－公式，仍记为P（x），使得，对任 一 L－闭项 T ，N|＝P（t）
iff Tn是素数。
（3）。Ｇｏｌｄｂａｃｈ猜想：E v e r y e v e n n u m b e r
g r e a t e r t h a n 2 i s t h e s u m o f
ｌｄｂａｃｈ猜想成立。
--
※ 来源:．饮水思源站WWW bbs.sjtu.edu.cn. [FROM: 202.109.48.171]