ブール関数

ブール関数（ブールかんすう、）は、非負整数 "k" 個のブール領域 B formula_1 の引数をとり、1個のブール領域の値となる関数 f : B"k" → B である。"k" = 0 では、単に定数 B となる。
ブール関数を一般化すると、"f" : "X" → B という形式の関数において、"X" が任意の集合である場合を「ブール値関数」と呼ぶ。"X" = M = {1, 2, 3, …} であるとき、"f" は無限の「二値数列; 」すなわち 0 と 1 の無限列である。"X" = ["k"] = {1, 2, 3, …, "k"} であるとき、"f" は長さ "k" の二値数列である。そのような関数は formula_2 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。
効率的表現.
（命題論理の）論理式で表現できるが、効率的な表現としては次のようなものがある。
簡単化.
簡単な表現に変換する手法として次のようなものがある。
以上は人間の直感によるものであり「変換する手法」と言えたものではない。
標準形.
選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。
リード-マラー標準形.
リード-マラー標準形（）は、積（AND）の排他的論理和（XOR）による標準形である。
ここで formula_3 である。
従って、列 formula_4 の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの（AND）項に現われる formula_5 の個数で表される。つまり、formula_6 の次数は 1（線形）であり、formula_7 の次数は 3（立方）である。