ブール関数

テンプレート:Expand English ブール関数（ブールかんすう、テンプレート:Lang-en-short）は、非負整数 k 個のブール領域 B $=\{0,1\}$ の引数をとり、1個のブール領域の値となる関数 f : B^k → B である。k = 0 では、単に定数 B となる。

ブール関数を一般化すると、f : X → B という形式の関数において、X が任意の集合である場合を「ブール値関数」と呼ぶ。X = M = {1, 2, 3, …} であるとき、f は無限の「二値数列; テンプレート:En」すなわち 0 と 1 の無限列である。X = [k] = {1, 2, 3, …, k} であるとき、f は長さ k の二値数列である。そのような関数は $2^{2^k}$ 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。

効率的表現

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

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

簡単化

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

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

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

• ベン図

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

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

• カルノー図法

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

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

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

標準形

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

リード-マラー標準形

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

$f(x_1,x_2,\dots ,x_n)=$	$a_0+$
	$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n+$
	$a_{1,2}{x}_1{x}_2+a_{n-1,n}{x}_{n-1}{x}_n+$
	$\dots +$
	$a_{1,2,\dots ,n}{x}_1{x}_2\dots x_n$

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

従って、列 $a_0,a_1,\dots ,a_{1,2,\dots ,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（立方）である。

関連項目

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

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

• 真理関数