ブール関数

ブール関数︵ブールかんすう、英: Boolean function︶は、非負整数 k個のブール領域 B

=\{0,1\}

=\{0,1\}

の引数をとり、1個のブール領域の値となる関数 f : B^k→ 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}}

2^{2^{k}}

個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。

効率的表現[編集]

︵命題論理の︶論理式で表現できるが、効率的な表現としては次のようなものがある。 ●二分決定図 (BDD) ●否定標準形 ●Propositional Directed Acyclic Graph (PDAG)

簡単化[編集]

簡単な表現に変換する手法として次のようなものがある。 ●カット・アンド・トライ法ブール代数の定義を用い、効率的な表現に変形していく。 ●ベン図ベン図を用いて視覚的にわかりやすい表現にする。以上は人間の直感によるものであり﹁変換する手法﹂と言えたものではない。 ●カルノー図法カルノー図を用い、効率的な表現に変形していく。 ●クワイン・マクラスキー法クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。

標準形[編集]

選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。

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

リード-マラー標準形︵en:Algebraic normal form︶は、積︵AND︶の排他的論理和︵XOR︶による標準形である。

$f(x_{1},x_{2},\ldots ,x_{n})=\!$	$a_{0}+\!$
	$a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}+\!$
	$a_{1,2}x_{1}x_{2}+a_{n-1,n}x_{n-1}x_{n}+\!$
	$\ldots +\!$
	$a_{1,2,\ldots ,n}x_{1}x_{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_{1}x_{2}x_{3}$ の次数は 3（立方）である。

効率的表現[編集]

簡単化[編集]

標準形[編集]

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

関連項目[編集]