読者です 読者をやめる 読者になる 読者になる

XORをAND、OR、NOTで表す

基本情報技術者の教本に以下の記述を見つけた。

排他的論理和の展開式は次の通りなので、しっかりと覚えておこう。

    a ^ b = a & ~b | ~a & b

※ "^" は XOR、"&" は AND、"|" は OR、"~" は NOT の意味
   演算子の優先順位は OR < XOR < AND < NOT

何がどうしてそうなるのか、論理代数の基礎勉強をしていないこともあり、分からなかった。
自分で求めたのは以下の解答である。

    a ^ b = ~(a & b) & (a | b) = answer
    -   -   --------   -------   ------
    0 ^ 0 =    1     &    0    =   0
    0 ^ 1 =    1     &    1    =   1
    1 ^ 0 =    1     &    1    =   1
    1 ^ 1 =    0     &    1    =   0

実際にはこれでも間違ってはいない(と言うよりも、こちらの方が加算器で使われている)が、この式を展開することができなかった。そこで以下のサイトを参考に式展開して見た。

参考:http://www.ccad.sist.chukyo-u.ac.jp/~mito/syllabi/dscrtMath2/alg/index.htm

式展開の経過は以下のようになる。

    a ^ b = ~(a & b) & (a | b)
          = (~a | ~b) & (a | b)
          = (~a | ~b) & a | (~a | ~b) & b
          = (~a & a | ~b & a) | (~a & b | ~b & b)
          = (0 | ~b & a) | (~a & b | 0)
          = ~b & a | ~a & b
          = a & ~b | ~a & b

なるほど、分配律や補元律で簡単に展開できるものだ。