離散數(shù)學期末考試試卷A卷

1、離散數(shù)學期末考試試卷(a卷) 一、判斷題：（每題2分，共10分）（1） （1）（2）對任意的命題公式 , 若 , 則 （0）（3）設 是集合 上的等價關系, 是由 誘導的 上的等價關系，則 。（1）（4）任意一個命題公式都與某一個只含合取和析取兩種聯(lián)結詞的命題公式等價。（0）（5）設 是 上的關系， 分別表示 的對稱和傳遞閉包，則 （0）二、填空題：（每題2分，共10分）() 空集的冪集的冪集為（ ）。() 寫出 的對偶式（ ）。（）設 是我校本科生全體構成的集合，兩位同學等價當且僅當他們在同一個班，則等價類的個數(shù)為（ ），同學小王所在的等價類為（ ）。（）設 是 上的關系，則 滿足下列性質的

2、哪幾條：自反的，對稱的，傳遞的，反自反的，反對稱的。（ ）(5)寫出命題公式 的兩種等價公式( ）。三、用命題公式符號化下列命題（）（）（），用謂詞公式符號化下列命題（）（）（）。（12分）（） （）僅當今晚有時間，我去看電影。（） （）假如上午不下雨，我去看電影，否則就在家里讀書。（3）你能通你能通過考試，除非你不復習。（） （）并非發(fā)光的都是金子。 （） （）有些男同志，既是教練員，又是國家選手。 （） （）有一個數(shù)比任何數(shù)都大。四、設 ，給定 上的兩個關系 和 分別是（） （）寫出 和 的關系矩陣。（）求 及 （1分）五、求 的主析取范式和主合取范式。（分）六、設 是 到 的關系， 是

3、到 的關系，證明： （8分）七、設 是一個等價關系，設 對某一個 ,有 ，證明： 也是一個等價關系。（10分）八、（1分）用命題推理理論來論證 下述推證是否有效？甲、乙、丙、丁四人參加比賽，如果甲獲勝，則乙失??；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果丙獲勝，則丁不失敗。 九、（分）用謂詞推理理論來論證下述推證。任何人如果他喜歡步行，他就不喜歡乘汽車，每一個人或喜歡乘汽車，或喜歡騎自行車（可能這兩種都喜歡）。有的人不愛騎自行車，因而有的人不愛步行 (論域是人)。十、(8分) 利用命題公式求解下列問題。甲、乙、丙、丁四人參加考試后，有人問他們，誰的成績最好，甲說：“不是我，”

4、乙說：“是丁，”丙說：“是乙，”丁說：“不是我。” 四人的回答只有一人符合實際，問若只有一人成績最好，是誰？離散數(shù)學期末考試試卷答案(a卷)一、判斷題：（每題2分，共10分）（1） （ ） (2) 對任意的命題公式, 若 , 則 ( )（3）設是集合上的等價關系, 是由誘導的上的等價關系，則。 ( )（4） 任意一個命題公式都與某一個只含合取和析取兩種聯(lián)結詞的命題公式等價。（ ）（5）設是上的關系，分別表示的對稱和傳遞閉包，則 （ ）二、填空題：（每題2分，共10分）() 空集的冪集的冪集為 ( )。() 寫出的對偶式（ ）。（）設是我校本科生全體構成的集合，兩位同學等價當且僅當他們在同一個班

5、，則等價類的個數(shù)為（我校本科生的班級數(shù) ），同學小王所在的等價類為（小王所在的班的集合）。（）設是上的關系，則滿足下列性質的哪幾條：自反的，對稱的，傳遞的，反自反的，反對稱的。 （傳遞的，反自反的，反對稱的）(5)寫出命題公式的兩種等價公式( ）。三、用命題公式符號化下列命題（）（）（），用謂詞公式符號化下列命題（）（）（）。（12分）（） （）僅當今晚有時間，我去看電影。解：p: 今晚我有時間. q: 我去看電影 （） （）假如上午不下雨，我去看電影，否則就在家里讀書。解 p: 上午下雨, q: 我去看電影 r: 我在家里讀書。 （3）你能通你能通過考試，除非你不復習。解 p你能通過考試，

6、q: 你復習. （） （）并非發(fā)光的都是金子。 解 是發(fā)光的， 是金子 （） （）有些男同志，既是教練員，又是國家選手。 解 是男同志，是教練員，是國家選手 ）（） （）有一個數(shù)比任何數(shù)都大。 解 是數(shù)，比大， 四、設，給定上的兩個關系和分別是（） （）寫出和的關系矩陣。（）求及（1分）解 五、求的主析取范式和主合取范式。（分）解六、設是到的關系，是到的關系，證明：（8分）證明：七、設是一個等價關系，設對某一個,有，證明：也是一個等價關系。（10分）證明：（1） 對任一, 因為r在a上是自反的，所以. 由s的定義，s, 所以s是自反的。（） （）對任意，若則對于某個c 使得因為r對稱的，故有：

7、由s的定義可知：所以s是對稱的。（3）對任意，若及則必存在某個，使得由r傳遞性，可知，同理存在使得由r傳遞性，可知。再由s的定義，得故 s是傳遞的。綜上可知，s是a上的等價關系。八、（1分）用命題推理理論來論證下述推證是否有效？甲、乙、丙、丁四人參加比賽，如果甲獲勝，則乙失??；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果丙獲勝，則丁不失敗。解：設a：甲獲勝。b：乙獲勝。c：丙獲勝。 d:丁獲勝。前提為：結論為：（1） p (2) (1)t,e(3) p(4) (2)(3)t,i(5) p(6) (5)(4)t,i 九、（分）用謂詞推理理論來論證下述推證。任何人如果他喜歡步行，他

8、就不喜歡乘汽車，每一個人或喜歡乘汽車，或喜歡騎自行車（可能這兩種都喜歡）。有的人不愛騎自行車，因而有的人不愛步行 (論域是人)。解：設p(x):x喜歡不行。q(x)喜歡乘汽車。r(x):x喜歡騎自行車。本題符號化為：（1） p(2) (1)es(3) p (4) (3) us (5) (2)(4)t,i (6) p (7) (6)us (8) (5)(7)t,i(9) (8)eg十、(8分) 利用命題公式求解下列問題。甲、乙、丙、丁四人參加考試后，有人問他們，誰的成績最好，甲說：“不是我，”乙說：“是丁，”丙說：“是乙，”丁說：“不是我?！?四人的回答只有一人符合實際，問若只有一人成績最好，是誰？解：設a:甲