ブール関数

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

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

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

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

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

標準形
選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。
リード-マラー標準形
リード-マラー標準形（:en:Algebraic normal form）は、積（AND）の排他的論理和（XOR）による標準形である。

ここで  である。

従って、列  の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの（AND）項に現われる  の個数で表される。つまり、 の次数は 1（線形）であり、 の次数は 3（立方）である。

関連項目

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

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

 真理関数

Category:数理論理学
Category:ジョージ・ブール
Category:数学のエポニム
Category:数学に関する記事