ブール関数

ブール関数（ブールかんすう、英: Boolean function）は、非負整数 k 個のブール領域 B の引数をとり、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 の二値数列である。そのような関数は 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。