1. 任何計算設備都可以求解某個問題。
解析:P(x): x是計算機設備,Q(x): x問題,R(x,y):x求解y
二、填空題
1. 設集合A={1, 2, 3, 4},則集合A上有 ? 15 種等價關系。
解析:使用 第二類 Stirling 求其不同的劃分個數 :
根據公式 : ? , 計算 Stirling 數的值 :
根據公式 : ,計算 Stirling 數的值 :
根據公式: ( Stirling 數計算公式 ) ,計算 Stirling 數的值 :
據公式 : , 計算 Stirling 數的值 :
2. 設P是所有人的集合,R和S是集合P上的關系,R={<x,y> | x是y的父親},S={<x,y> |x是y的母親} ,( ),當關系Q為 ? 時,xQy表示x是y的妻子。註:用R1OR2表示關系R1與R2的復合。
解析:本題考的是逆關系和復合關系,假設z是x的子女記作 = {<z,y>| z 是y的子女},S={<x,z> |x是z的母親},根據復合關系: 得 ,得到答案。
3. 有5個男同學和3個女同學站成壹排,如果沒有2個女同學相鄰,***有 14400 種不同的排法。
解析:男生的排法有 ,要求2個女生不能相鄰,則用插排,將3位女同學插排到5個同學的空當中間,5個男生(包括首尾)有6個空當,即女生的排法有 ,因此壹***有
4. 設G是有10個頂點的無奇圈的簡單連通圖,則G的著色數是 2 ? (簡單圖的著色數是指相鄰的頂點著不同的顏色所需的最少顏色的個數)。
解析:定理壹壹個圖為二部圖當且僅當圖G中無奇圈。因此G為二部圖。而二部圖的著色數為2;
定理二圖G是2-可著色的當且僅當G是二部圖; 因此可知該二部圖的著色數位為2。
定理二奇圈和奇數階輪圖都是3-色圖,而偶數階輪圖都是4-色圖。
5. 如果? 則 ?
解析:根據牛頓公式: ,以及牛頓公式推廣公式 題目中,a=-2,n=2,代入推廣公式可得:
三、計算題
1. 設個體域為{a, b, c},試寫出公式(?x)P(x) →(?y)Q(y)的命題邏輯表達。
解析: 個體域{a,b,c} 對於邏輯命題量詞 , 即是個體域做析取計算, 而 則是對個體域做合取運算。因此得
2. 寫出(﹁PVQ)→((Q∧﹁R)VP)的主析取範式和主合取範式(需寫出計算過程,且結果簡潔表示)。
解析:這個解析方法有兩種方法,在本題中就用真值表來做了,另外壹種推導的就留給網友們自己推導:
則主析取範式為
則主合取範式為?
四、解答題
1. 設有四對夫妻圍壹圓桌就坐,則至少有1對夫妻不相鄰的就坐方式有多少種。
解析:四對夫妻至少有壹對夫妻不相連,即至多3對夫妻相鄰,可以理解成全排列減去4對夫妻相連,得到的就是至多有3對夫妻相鄰了。
四對夫妻8人全排列(圓周排列公式見 我的 公式集 ) ,4對夫妻相鄰的全排列分為兩個階段先女士圍成壹圈 ,再讓男士坐到自己的妻子身邊,每位男士有兩種坐法,坐到妻子左邊或者右邊,即 ,因此四對夫妻相鄰的排列有 ,則題中至少壹對夫妻不相鄰的排列數為
即至少有1對夫妻不相鄰的坐法有4944種。
2. 設某單位安排A、B、C、D、E和F六人從周壹到周六值班。每天有且僅有壹人值班,條件是A不能周壹值班,B不能周二值班,C不能周三值班,求***有多少種安排值班的方法。
解析:知識點是完全錯排,用容斥原理來推斷。
用X,Y,Z表示A,B,C分別在周壹,二,三上值班的集合,都不在原位的集合表示為:
3. 把6個不同的口罩放到5個相同的盒子裏,使得不出現空盒,有多少種不同的方法。
解析:(之前解法有問題,更新壹下解釋),五個相同的盒子不用排序,因此只要將6個口罩分成5份即選兩個捆綁在壹起: 則有 種組合。
?,即15種解法
五、證明題,
給定集合A={1, 2, 3, 4, 5, 6}
1)寫出壹個A上的既是等價關系又是偏序關系的例子
2)證明1)中例子的正確性
解析:此題考的是等價關系與偏序關系的條件。
等價關系:自反,對稱,傳遞;偏序關系:自反,反對稱,傳遞。
(1)A的關系R需滿足等價和偏序關系,也就是R必須滿足既是對稱又是反對稱關系。則 R = {<x,y>| x=y}即關系矩陣對角線上的數都為1,因此該關系為集合A上的每個元素自成環,無其他關系路徑。
(2)只需證明R符合等價關系和偏序關系。
證明:R = {<x,y>| x=y} 等價關系:
1.對於任意的a = a 恒成立,因此R滿足自反;
2.對於任意的 ,則有 滿足對稱;
3.對於任意的 且 ,則有 滿足傳遞性;
由以上3點可知R滿足等價關系,再證偏序關系,只需證明反對稱關系;
對於任意的 , 且 ,滿足反對稱,結合上述結論得證 R 滿足偏序關系。
綜上所述,關系R是正確的。