廊下の電気と排他的論理和

教え子の物理期末テストの最後の問題が意味不明で、帰りの電車の中で考えていたのですが、その真相が理解できました。

階段や廊下では、どちらかのスイッチを押すと電気が消えているときは点灯するように、点灯しているときは消えるようになっています。その仕組みはFig.1のような回路によって実現することが出来ます。線がつながっているときは電気の通り道が出来るので点灯し、どこかで行き止まりになるようなスイッチ構成の時は点灯しないようになっているわけです。

問題として出題されていたのはその先で、「これが3つになった場合、それぞれ3箇所にはどのようなスイッチを置けばよいか。解凍らんの図（Fig.2）にスイッチを書き込め」という問題でした。また、「スイッチは2つ同時に切り替わるものがあってもよい」という注釈もついていました。

さて、解こうとしたものの意味不明だったのがヒントとして出された、「スイッチは2つ同時に切り替わるものがあってもよい」という部分です。そもそも「2つ」とは一体どの2つを指すのかと。異なるスイッチが連動するという意味なのか、同じスイッチの中に接点を共有する2回路が存在しているという意味なのか。解答(Fig.3)を見れば後者、すなわちFig.4のように接点を共有し、連動する2回路のスイッチが存在するという意味だと捉えることができますが、普通に文章を読んだだけでは全く理解できません。テストとしてはかなりの悪問です。

さらに「これが3つになった場合」という文言では、この回路が一体どういう状況を想定しているのかを素早く理解することが出来ません。私が考える限りでは、この問題が想定している状況というのは、Fig.5のようにT字路の廊下があったときに、3方のどこから来ても廊下の電気をON/OFFできるようにしなければならない状況であると考えられます。それを実現するためにはFig.3のような回路が必要だということのようです。では、果たしてこの回路を組めば、3つのうち任意のスイッチ一つを切り替えると状態が反転（点灯→消灯、消灯→点灯）するようになるのでしょうか。検証する必要があります。

もちろん、解答に書いてあったようにスイッチの全ての可能性、すなわち2の3乗＝8通りをすべてチェックするという方法も一つではあります。しかし、すべてを書き出すのはスマートではありませんし、スイッチの数が4個、5個と増えると考えることが難しくなります。なんとかうまく数学的な法則性を見つけられないだろうかと電車の中で悩んだ末、出た結論がこれでした。

この回路は基本的に排他的論理和回路Exclusive ORと同値である。

[証明]左から順にスイッチにA、B、C・・・と名前をつけます。Fig.1の場合は左がA、右がBで、Fig.3の場合は左から順にA、B、Cです。さらに1回路2接点のスイッチではONになっている接点が上にある状態を1、下にある状態を0と定義します。2回路2接点のスイッチ（Fig.3のB)では交叉している状態を1、交叉せず、両方ともまっすぐに向こう側に接続する状態を0とします。また、電灯が点灯する状態を1、消灯する状態を0とします。

Fig.1では、電気が点灯する状態（1とする）は(A, B)がそれぞれ(1, 1)あるいは(0, 0)のときのみです。これをFig.6のようにNOT (A EXOR B)と置き換えてやります。EXORは排他的論理和で、入力が2つの時、両方が同じ数の時は0、それ以外は1を出力します。したがって、A EXOR Bの真理値表を書くと次のようになります

入力A	入力B	出力O
1	1	0
1	0	1
0	1	1
0	0	0

ただし、このままでは、(1,1)、(0,0)では出力が0になってしまって消灯していることになってしまうので、出力の後にNOTゲートを置いて反転させます。

スイッチが2つの時はこれで説明することが出来ました。では、スイッチが3つの時はどうでしょうか。ここでは、Fig.1のスイッチAを、Fig.3の「スイッチA〜スイッチB」の部分に置き換えて考えます。すると、Fig.1のA=1に相当する状態を作り出すためには、定義よりFig.3では(A,B)=(0,1)または(1,0)である必要があります。逆にFig.1のA=0に相当する状態を作り出すためには、(A,B)=(0,0)または(1,1)である必要があります。これは先ほどのEXORと全く同じことであるため、Fig.1のAはFig.3ではA EXOR Bと置き換えることが出来るのです。すなわち、これを回路図にしてやるとFig.7のようになります（入力端子は上から順にA,B,C)。すなわち、NOT (C EXOR (A EXOR B))となるわけです。同様にいくら操作できるスイッチが増えても、左上にEXORをどんどん追加してやれば、同値な回路を書くことが出来ます。

上から言えることは、スイッチがn個のとき、このようなスイッチによる回路は「n個のうち上から2個をEXOR演算子し、その結果をさらに一つ下の入力と次々EXOR演算して出てくる結果を反転させた回路」に置き換えることが出来るということです。で、実はこれはEXORの定義として「2個以上の入力を同時にEXOR演算し、その結果を反転させたこと」と同じことになります。どういうことかというと、3個以上のEXOR演算というのが「任意の2個をEXOR演算し、その結果をさらに別の入力と次々とEXOR演算させていった結果」というように決まりとして定義されているのです。私がこのスイッチ回路をEXORと一緒と評価したのはこのためです。

ここまでの整理をします。今までに分かったことは上の斜体字のようなスイッチ状態・電灯状態の定義をすれば、Fig.1やFig.3のようにして組んだ回路は、スイッチの数nがどれだけ大きくなろうとも、「すべてのスイッチの状態のEXOR演算の結果を反転するロジック回路」に置き換えることが可能であるということです。

さて、あともう一息です。スイッチの数がn個のとき、回路全体が廊下のスイッチ回路として成り立つ、すなわち、「任意のスイッチ一つを切り替えると状態が反転（点灯→消灯、消灯→点灯）する」ことが成立するためには、「EXOR演算の入力どれか一つの状態を反転させれば、EXORの出力も反転する」ことを証明する必要があります。これを今から証明します。

先ほども説明したように、複数入力のEXOR演算の定義は「任意の2個をEXOR演算し、その結果をさらに別の入力と次々とEXOR演算させていった結果」というものでした。このことからEXOR演算は次のように説明されることがあります。「全入力のうち1の数が偶数個ならEXORは0であり、1の数が奇数個ならEXORは1である」。これは数学的帰納法によって証明できます。

入力の数をnとすると、n=2のときは(1,1)、(0,0)でEXORが0になるのですから、命題は真です。また、n=kのとき(k≧2)、命題が真、すなわち「k個の入力のうち1の数が偶数個ならEXORは0、奇数個なら1になる」ということが成り立つと仮定すると、n=k+1のときは

i)n=kの時に1の数が偶数個のとき
k個のEXORの結果は0であるため、k+1個目の入力が0の時は結果は0、入力が1の時は1となる。
つまり、k+1個の入力のうち1の数が偶数個ならばEXORの結果は0、奇数個ならばEXORの結果は1となる。
ii)n=kの時に1の数が奇数個のとき
k個のEXORの結果は1であるため、k+1個目の入力が0の時は結果は1、入力が1の時は0となる。
つまり、k+1個の入力のうち1の数が偶数個ならばEXORの結果は1、奇数個ならばEXORの結果は0となる。

従って、i)、ii)よりn=k+1のときも命題は成り立つ。数学的帰納法により、n≧2であれば、「全入力のうち1の数が偶数ならEXORは0であり、1の数が奇数ならEXORは1である」という命題は常に成り立つ。

最後です。「全入力のうち1の数が偶数個ならEXORは0であり、1の数が奇数個ならEXORは1である」ということが分かれば、「EXOR演算の入力どれか一つの状態を反転させれば、EXORの出力も反転する」ことは明らかです。なぜなら、EXOR演算の入力のどれか一つの状態を反転させるということは、全入力のうちの1の数が偶数個→奇数個となるか、奇数個→偶数個となるかのどちらかだからです。「全入力のうち1の数が偶数個ならEXORは0であり、1の数が奇数個ならEXORは1である」わけですから、奇数個が偶数個になったり、偶数個が奇数個になるということは当然、EXORの結果が1から0または0から1に反転することを意味します。したがって、常に「EXOR演算の入力どれか一つの状態を反転させれば、EXORの出力も反転する」ことが成り立ちます。

上記より

Fig.1やFig.3のようにして組んだ回路はスイッチの数nがどれだけ大きくなろうとも、「すべてのスイッチの状態のEXOR演算の結果を反転するロジック回路」に置き換えることが可能である
EXOR演算の入力どれか一つの状態を反転させれば、EXORの出力も反転する

ことが分かりました。

以上より、Fig.1やFig.3のようにして組んだ回路はスイッチの数nがどれだけ大きくなろうとも、任意のスイッチ一つを切り替えると状態が反転（点灯→消灯、消灯→点灯）し、廊下のスイッチの動作条件を満たします。[証明終]

結局、こういうことだったんですね。いくつスイッチの数が増えても、この原則を守って回路を組み立てれば正しく廊下の電気を作働させることが出来るわけです。排他的論理和恐るべしです。もともと、排他的論理和は画像処理などで反転する技術にも用いられているわけで、反転や偶数奇数がキーポイントとなる回路で使われても全くおかしなことはないのですが、ふと出くわした物理の悪問がこれにつながるとは予想だにしませんでした。

しかし、いくら東大・京大・国公立医学部にたくさんの人間を輩出させている学校とはいえ、中学3年生にこの日本語的に意味不明な悪問をやらせる教師も教師だなぁと思います。さすがは今はどこかに行ってしまったO師をけなした先生だけありますね。