ブール関数

定義：

ブール関数[Boolean function]は,ブール値[0 または 1]を入力とし,ブール値を出力する関数である.あるいは,ブール関数は,ブール代数の演算を使って構築される関数である.ブール演算子[Boolean Operator]ともいう.

すなわち,$n$ を入力変数の数,$\{0,1\}^n$ を $n$ 個の入力変数がそれぞれ 0 または 1 を取る全ての組み合わせとすると,\[f: \{0,1\}^n \to \{0,1\}\]と表される.

ブール関数の概念は,ジョージ・ブール[George Boole, 1815/1864]が1854年に"An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities"という著書の中で発表.

1938年に,クロード・シャノン[Claude Shannon] が論文 "A Symbolic Analysis of Relay and Switching Circuits"[リレーとスイッチング回路の記号的解析] によって,ブール関数を電気回路の設計に応用する道を開いた.

ブール関数の例

演算子名記号定義
NOT $\neg x$ $x = 0 \Rightarrow 1, x = 1 \Rightarrow 0$
AND $x \land y$ $x, y$ が両方 1 のとき 1、それ以外は 0
OR $x \lor y$ $x$ または $y$ の少なくとも 1 つが 1 のとき 1
XOR $x \oplus y$ $x$ と $y$ が異なるとき 1
含意 $x \Rightarrow y$ $\neg x \lor y$/td>
同値 $x \equiv y$ $(x \land y) \lor (\neg x \land \neg y)$/td>

Mathematics is the language with which God has written the universe.

SIMH オーバーコミット PTX メモリのバンド幅 OSI参照モデル仮想化

演算子名	記号	定義
NOT	$\neg x$	$x = 0 \Rightarrow 1, x = 1 \Rightarrow 0$
AND	$x \land y$	$x, y$ が両方 1 のとき 1、それ以外は 0
OR	$x \lor y$	$x$ または $y$ の少なくとも 1 つが 1 のとき 1
XOR	$x \oplus y$	$x$ と $y$ が異なるとき 1
含意	$x \Rightarrow y$	$\neg x \lor y$/td>
同値	$x \equiv y$	$(x \land y) \lor (\neg x \land \neg y)$/td>