※ 引述《Desperato (Farewell)》之銘言：
: (以上省略)
: : 推 wa007123456 : 可以問一下怎麼證明XOR不多有多少變數 只要是奇數 04/25 09:53
: : → wa007123456 : 個1 答案就會是1 嗎? @@ 04/25 09:53
: XOR有：
: 1. 分配律
: (A⊕B)⊕C = A⊕(B⊕C)
: 意思是 我們可以隨便挑要先加哪兩個 不需要從頭開始加
: 2. 單位元素 0
: A⊕0 = A
: 意思是 0加上任何一個東西都會自己消失
: 3. 1⊕1 = 0
: 可以說 1 是 1 的反元素 (不過應該不需要這麼麻煩的說法)
: 意思是 兩個1加起來會變成0然後根據2.會消失 = 兩個1會消掉
: 因此對於任意的 X1⊕X2⊕...⊕Xn
: 我們都可以用1.和2. 把所有0拿掉
: 只要考慮全部是1的情況就好
: 現在如果有偶數個 1
: 根據3. 會消光光變成 0
: 如果有奇數個 1
: 一樣根據3. 會消到剩一個 1
: 比較正式的作法是用數學歸納法 概念上是這樣
練習一下數學歸納法。
n=2，⊕(X1, X2)=1，若且唯若，X1~X2裡有奇數個1。
n=k+1時，可以想成是(⊕(X1...Xk)⊕(Xk+1))。
由於IH，⊕(X1...Xk)=1，若且唯若，X1~Xk有奇數個1。
(⊕(X1...Xk)⊕(Xk+1))=1，若且唯若，
X1~Xk有奇數個1而且Xk+1不是1，或者X1~Xk有偶數個1而且Xk+1是1。
無論是哪一種情況，X1~Xk+1裡會是奇數個1。
還是D大的想法比較有趣。
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.225.143.156
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1493303567.A.8F5.html
※ 編輯: tzudata (36.225.143.156), 04/27/2017 22:33:00
※ 編輯: tzudata (36.225.143.156), 04/27/2017 22:33:36