ブール関数
ブール関数（ブールかんすう、英: Boolean function）は、非負整数 k 個のブール領域 B [math] = \{0, 1\}[/math] の引数をとり、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 の二値数列である。そのような関数は [math]2^{2^k}[/math] 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。
Contents
効率的表現
（命題論理の）論理式で表現できるが、効率的な表現としては次のようなものがある。
- 二分決定図 (BDD)
- 否定標準形
- Propositional Directed Acyclic Graph (PDAG)
簡単化
簡単な表現に変換する手法として次のようなものがある。
- カット・アンド・トライ法
- ブール代数の定義を用い、効率的な表現に変形していく。
- ベン図
- ベン図を用いて視覚的にわかりやすい表現にする。
以上は人間の直感によるものであり「変換する手法」と言えたものではない。
- カルノー図法
- カルノー図を用い、効率的な表現に変形していく。
- クワイン・マクラスキー法
- クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。
標準形
選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。
リード-マラー標準形
リード-マラー標準形（en:Algebraic normal form）は、積（AND）の排他的論理和（XOR）による標準形である。
| [math]f(x_1, x_2, \ldots , x_n) = \![/math] | [math]a_0 + \![/math] |
| [math]a_1x_1 + a_2x_2 + \ldots + a_nx_n + \![/math] | |
| [math]a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \![/math] | |
| [math]\ldots + \![/math] | |
| [math]a_{1,2,\ldots,n}x_1x_2\ldots x_n \![/math] |
ここで [math] a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^* [/math] である。
従って、列 [math]a_0,a_1,\ldots,a_{1,2,\ldots,n}[/math] の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの（AND）項に現われる [math]x_i[/math] の個数で表される。つまり、[math]f(x_1,x_2,x_3) = x_1 + x_3[/math] の次数は 1（線形）であり、[math]f(x_1,x_2,x_3) = x_1 + x_1x_2x_3[/math] の次数は 3（立方）である。