20分填空题+80分大题

用的是橙色封面的《离散数学》。

填空题

谓词演算的等价式与蕴含式  

带谓词的翻译，不难。

A有m个元素，从A到A有___个关系。（若X,Y有限，则从X到Y的关系有个。）

给定了两个集合P,Q，求其复合关系的关系闭包，Q的传递闭包。（是一个空集）______(具有/不具有)自反性，______(具有/不具有)可传递性。

给定一个哈斯图，______(是否)为分配格，_____是否为有补格。

大题

1-3题10分，4-5题20分。

1. 第1章 命题逻辑

关于3个人退休了去泰康养老院的方案。

填真值表，求主析取范式，并翻译其含义。
有坑，“除非A不去泰康，否则C也不去泰康。”

2. 第3章 集合与关系

给定集合{a,c,{a,b},{a,c},{b,c},{a,b,c}}，关系是被包含关系 ，画出哈斯图，关系图。

关系图有坑，自己可以被包含自己，考试时没想到。需要画一个自回路。

求{{b},{a,c}}的上界，最小元，极大元，（还有一个忘了）？

3. 第3章 集合与关系

如果R，Q是在A，B上的等价关系，……，证明

是在A✕B上的等价关系（对称性，自反性，传递性）。

4. 第6章 格与布尔代数

有点难。

题目初始给定的偏序关系是左图。

1. 是否为格？为什么？

2. 补充线条，变为布尔格S。

3.求  ?

4. 求  的值。

5. 在该布尔格S上有一个  运算，，问  是否为群?

5. 第7章 图论

该题目包装为一道工程运用题，连线代表公司的合作关系。

1. 求割点。

2. 是否可以不重复的调查完所有关系？（也就是求欧拉路）

3. 是否可以不重复的调查到所有公司？（也就是求汉密尔顿路）

4. 给定下面的这个关系图，画出邻接矩阵。

5. 从v2到v3存在几条长度为3的关系？

6. 求可达性矩阵P。

关系证明题

送分题，老大、老二、老三、老四的上学。谁去上学，那么谁也上学…………

内容和这个差不多，不过要简单一点。

(1) 符号化以上命题。

        前提：

        结论：

(2) 用PT规则给出证明过程。