Turing Complete Unofficial

Odd Number of Signals

前提レベル

このレベルを前提とするレベル

概要

4つの入力のうち True となる入力が奇数個であれば True となる回路を構成する問題です。ただし青色のコンポーネントの使用数を3つ以内に抑えるという制約がついています。

攻略

単純に考えると、4つの入力のうち True となる入力が 1個または3個であればよいと考えられます。 ただしこれをそのまま実装してしまうと、コンポーネントの使用数が3つを超えてしまうことが 容易に想像されます。

解答

開く

XOR回路を使うことで実現することが可能です。 XOR演算の 真理値表 は次のようになっていました。

入力1FTFT
入力2FFTT
出力FTTF

入力が3つの場合は次のようになります (入力1と入力2のXORの結果を入力3とXORするのと同じです)。

入力1FTFTFTFT
入力2FFTTFFTT
入力3FFFFTTTT
出力FTTFTFFT

よく観察すると、入力の数が奇数のときに出力がTrueとなっていることがわかると思います。 この性質は入力が増えても変わりません。

したがって、次のように回路を構成することができます。