ブール関数

ブール関数（ブールかんすう、英: Boolean function）は、ブール領域の非負整数回の直積を定義域とし、ブール領域の元のうち片方を返す関数である。

${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$

ブール値関数の特殊なものである。

X = M = {1, 2, 3, …} であるとき、f は無限の「二値数列; binary sequence」すなわち 0 と 1 の無限列である。X = [k] = {1, 2, 3, …, k} であるとき、f は長さ k の二値数列である。そのような関数は ${\displaystyle 2^{2^{k}}}$ 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。

効率的表現

（命題論理の）論理式で表現できるが、効率的な表現としては次のようなものがある。

• 二分決定図 (BDD)
• 否定標準形
• Propositional Directed Acyclic Graph (PDAG)

簡単化

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

• カット・アンド・トライ法

ブール代数の定義を用い、効率的な表現に変形していく。

• ベン図

ベン図を用いて視覚的にわかりやすい表現にする。

以上は人間の直感によるものであり「変換する手法」と言えたものではない。

• カルノー図法

カルノー図を用い、効率的な表現に変形していく。

• クワイン・マクラスキー法

クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。

標準形

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

リード-マラー標準形

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

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\!}$	${\displaystyle a_{0}+\!}$
	${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}+\!}$
	${\displaystyle a_{1,2}x_{1}x_{2}+a_{n-1,n}x_{n-1}x_{n}+\!}$
	${\displaystyle \ldots +\!}$
	${\displaystyle a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\!}$

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

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

関連項目

集合の代数学 ブール代数 ブール領域 ブール論理

ブーリアン型 ブール値関数 論理結合子

真理関数