数理逻辑精品教学（华南理工大学）2014《数理逻辑》样卷.docx

《数理逻辑》样卷一、单选题（20分）1．下列命题公式中，是重言式的是____________。 A. (P Q) Q B. (Q P) Q P C. PQ D. P Q2．设A、B、C为任意集合，下面命题为真的是____________。 A．若AB=AC，则B=C B. 若 A－B = ，则A=B C. 若AB=AC，则B=C D. 3．在关于二元关系性质的叙述中，正确的是__________。A. 若关系R、S具有自反性，则RS一定有自反性；B. 若关系R、S具有自反性，则R－S一定有自反性；C. 若关系R、S具有传递性，则RS一定有传递性；D. 若关系R、S具有反对称性，则RS一定有反对称性；4．含有3个元素的集合共有_______种不同的划分. A. 4 B . 10 C. 5 D. 65．设A、B为任意集合，下面命题为真的是__________。A．P(A)P(B)=P(AB) B. P(AB)=P(A)P(B)C. P(A-B)=P(A)-P(B) D. 若A-B= ，则B A6．设A、B是集合，右图的文氏图的阴影部分的区域可用________表达式表示A. AB B. ABC.A-B D. (AB)-(AB) 7．设R、S、T是A上的二元关系，则下列命题中错误的是________。A．(R°S)°T = R°(S°T)B. t(R) t(S) = t(RS)C．R对称当且仅当 R=R-1 D．(R S)°T = R°T S°T 8．下列谓词公式中，是逻辑有效式的是____________。 A. x(F(x) G(x)) B. xF(x) xF(x) C．(F(x,y) R(x,y)) R(x,y) D. xyF(x,y) xyF(x,y) 9．设A为n元集，则在A上可定义的二元关系中，一共可定义___________不同的自反关系。 10．下列关系的性质中，等价关系不具备的是____________。 A．自反性 　B. 反对称性 C. 传递性 　D. 对称性二、填空题（20分）1．设P、Q的真值为0；R的真值为1，则命题公式：P(QR)的真值是______________。2．设论域为{1,2}，一元谓词定义为F(x): x2, G(x): x=0，则 (x)(F(x)→G(x)) 的真值为_________________。3．设P(x)：x是正整数，Q(x)：x是偶数，R(x)：x是奇数，则公式：(x)(P(x)→(Q(x)∨R(x))　翻译成自然语句为: _____________________。4．设A={a, b, c}，则A的全部子集共有________个，A的幂集P(A)共有________个元素。 5．在偏序关系P({a, b, c, d},R)的哈斯图中，最大元素是_______，极小元素是___________。6．两个集合A和B相等(A=B)用谓词形式可定义为：_____________。7．已知集合C定义为： C={x|x Z 3x6 }，则集合C中的元素为：C=_________________。8. R在A上反自反当且仅当 _________。9．用联系词 表示公式 P Q＝________________________。10．对集合A＝{1,2,3}，R是A上的关系（如下图所示），列出它所具有的性质：____________________。三．计算题（20分）1．求命题公式： (PQ)R 的主析取范式和成真赋值。2. 已知A={1,2,3 }，B={1,4}，求AB、A-B、AB和P(AB)。3. 设A={a, b, c}，R={a, b, b, c, c, a }，求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。4. 设 A={1, 2, 3, 4}，在 A上定义二元关系R： x,y,u,vR x+y = u+v，求 R 导出的划分.四．证明题（20分）1．用等值演算法证明等值式： PQ = P (P Q)2. 设q为命题变项，与个体变元x无关，证明：(x)(P(x)q) = (x)P(x) q3. 设 A={1,2,3,4,5,6,7,8}, A上的关系R定义为： R = { x,y | x,y∈A x≡y(mod 3) } 证明：R是一个等价关系。4．使用推理规则证明： P(QR)，SP, Q S R五．应用题（20分）1. 甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”,乙说：“是丁”,丙说：“是乙”,丁说：“不是我”.四人的回答只有一人符