1. let p(x,y) be a proposition function , prove or disprove
some x all y p(x,y)-> all y some x p(x,y) is always true
這應該是true吧 但要怎麼證明?
2. two dice are identical if they become excatly teh same after proper rotations and flips,
how many different dice are there?
想說假設固定骰子底面不動,隨便給一個數字,因為固定底面所以只剩下左右旋轉
所以我覺得是 (5*4*3*2)/4=30 但不知道對不對 ?
3. a binary relation R on a set s is a subset of s^2,the cardinality of s is n
a.how many equvilant relations are there on s?
這題我想法是 等價關係可以對應到分割 而 s 的power set有2^n
所以等價關係有 2^(n-1) 種?
b.let R1 be a relfexive cloure of R .then
R1={(a,b)屬於s^2: } 裡面要填什麼?
c.let R2 be a symmetric cloure of R .then
R2={(a,b)屬於s^2: } 裡面要填什麼?
R2={(a,b)屬於s^2: } 裡面要填什麼?
d.prove the transitive cloure of RUR1UR2 is an equivalent relation
最後還有圖片裡的那一題....
感謝感謝解答了 問題好多... orz
1 則留言:
1. true, 假設前面那句話是對的, 所以存在一個x', 使得x'對所有的y, p(x',y), 所以對所有的 y, 我們只要取 x' => p(x',y) (因為一定至少可以取到x'所以就得證了)
2. 我不太確定你的式子的意義, 是考慮四個側面的環狀排列? 如果是的話想法應該沒問題, 答案是30沒錯; 這題還可以用polya做
3.
(a): 等價關係的個數Pn有個遞迴式, 可參考書上p2-43
(b): R1 = {(a,b)∈S^2|(a,b)∈R or a=b}
(c): R2 = {(a,b)∈S^2|(a,b)∈R or (b,a)∈R}
(d): 令 T=R∪R1∪R2, t(T) 為 T 的 transitive closure,
根據 T 的定義, t(T)顯然具transitive, reflexive,
所以只剩下t(T)具symmetric要證:
t(T)=T∪T^2∪T^3∪...,
for all a,b in S, k>=2, 若 (a,b)∈T^k,
因為t(T)具transitive => ∃x_1,...,x_n-1 s.t.
(a,x_1)∈T, (x_1,x_2)∈T, ..., (x_n-1,b)∈T
因為T具symmetric
=> (x_1,a)∈T, (x_2,x_1)∈T, ..., (b,x_n-1)∈T
=> (b,a)∈T^k
所以, T^k 具 symmetric
=> t(T) 具 symmetric
最後4.5分那一題, 假設 f^-1 = f圈圈
這裡要證的事情其實很直覺, 所以把定義寫出來差不多就得證了: ∀a∈A' => f(a)∈f(A') => a∈f^-1(f(A'))
張貼留言