ブール関数(ブールかんすう、英: Boolean function)は、非負整数 k 個のブール領域 B = { 0 , 1 } {\displaystyle =\{0,1\}} の引数をとり、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 の二値数列である。そのような関数は 2 2 k {\displaystyle 2^{2^{k}}} 個存在する。これは計算複雑性理論における問題で基本的な役割を果たす。 (命題論理の)論理式で表現できるが、効率的な表現としては次のようなものがある。 簡単な表現に変換する手法として次のようなものがある。 以上は人間の直感によるものであり「変換する手法」と言えたものではない。 選言標準形と連言標準形が代表的である。他に、リード-マラー標準形などがある。 リード-マラー標準形(en:Algebraic normal form f ( x 1 , x 2 , … , x n ) = {\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\!} a 0 + {\displaystyle a_{0}+\!} ここで a 0 , a 1 , … , a 1 , 2 , … , n ∈ { 0 , 1 } ∗ {\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}} である。 従って、列 a 0 , a 1 , … , a 1 , 2 , … , n {\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}} の値の列もブール関数を一意に表している。ブール関数の代数的次数は、1つの(AND)項に現われる x i {\displaystyle x_{i}} の個数で表される。つまり、 f ( x 1 , x 2 , x 3 ) = x 1 + x 3 {\displaystyle 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 {\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}} の次数は 3(立方)である。
目次
1 効率的表現
1.1 簡単化
2 標準形
2.1 リード-マラー標準形
3 関連項目
効率的表現
二分決定図 (BDD)
否定標準形
Propositional Directed Acyclic Graph
簡単化
カット・アンド・トライ法
ブール代数の定義を用い、効率的な表現に変形していく。
ベン図
ベン図を用いて視覚的にわかりやすい表現にする。
カルノー図法
カルノー図を用い、効率的な表現に変形していく。
クワイン・マクラスキー法
クワイン・マクラスキー法を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。
標準形
リード-マラー標準形
a 1 x 1 + a 2 x 2 + … + a n x n + {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}+\!}
a 1 , 2 x 1 x 2 + a n − 1 , n x n − 1 x n + {\displaystyle a_{1,2}x_{1}x_{2}+a_{n-1,n}x_{n-1}x_{n}+\!}
… + {\displaystyle \ldots +\!}
a 1 , 2 , … , n x 1 x 2 … x n {\displaystyle a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\!}
関連項目
更新日時:2018年6月20日(水)22:20
取得日時:2019/08/06 20:56
Size:9292 Bytes
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef