ブール関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: 案内、 検索

ブール関数（ブールかんすう、Boolean Function）とは、数学において、非負整数 k 個のブール領域 B = \{0, 1\} の引数からブール領域の値を得る関数 f : Bk → B を指す。k = 0 であるような場合、この関数は単に定数要素 B を表す。

ブール関数は他の数理科学分野では別の名前で知られていることも多い。たとえば協力ゲーム理論で「シンプルゲーム」(投票ゲーム) とよばれる概念がそれに該当し、社会選択理論の重要な問題を解くために応用されている。

ブール関数を一般化すると、f : X → B という形式の関数において、X が任意の集合である場合を「ブール値関数」と呼ぶ。X = M = {1, 2, 3, …} であるとき、f は無限の「二値数列; binary sequence」すなわち 0 と 1 の無限列である。X = [k] = {1, 2, 3, …, k} であるとき、f は長さ k の二値数列である。そのような関数は 2^{2^k} 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす他、デジタルコンピュータの論理回路の設計でも利用される。ブール関数の特徴は暗号理論においても重要であり、特に共通鍵暗号の設計で重要である。

目次

リード-マラー標準形 [編集]

ブール関数は積（AND）の総和（XOR）で一意に記述できる。これを リード-マラー標準形と呼ぶ。

f(x_1, x_2, \ldots , x_n) = \! a_0 + \!
a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!
a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!
\ldots + \!
a_{1,2,\ldots,n}x_1x_2\ldots x_n \!

ここで a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^* である。

従って、列 a_0,a_1,\ldots,a_{1,2,\ldots,n} の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの（AND）項に現われる x_i の個数で表される。つまり、f(x_1,x_2,x_3) = x_1 + x_3 の次数は 1（線形）であり、f(x_1,x_2,x_3) = x_1 + x_1x_2x_3 の次数は 3（立方）である。

効率的表現 [編集]

ブール関数は命題論理での文として表現されることが多いが、より効率的な表現として次のようなものがある。

簡単化 [編集]

効率的な表現に変換する手法として次のようなものがある。

  • カット・アンド・トライ法
ブール代数の定義を用い、効率的な表現に変形していく。
  • カルノー図法
カルノー図を用い、効率的な表現に変形していく。
  • クワイン・マクラスキー法
クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。
  • ベン図
ベン図を用いて視覚的にわかりやすい表現にする。

関連項目 [編集]

外部リンク [編集]

「http://ja.wikipedia.org/w/index.php?title=ブール関数&oldid=47318942」から取得