ブール関数のソースを表示

{{Expand English|Boolean function|date=2024-04}}
'''ブール関数'''（ブールかんすう、{{lang-en-short|Boolean function}}）は、非負整数 ''k'' 個の[[ブール領域]]  '''B''' <math> = \{0, 1\}</math> の引数をとり、1個のブール領域の値となる[[関数 (数学)|関数]] f : '''B'''<sup>''k''</sup> &rarr; '''B''' である。''k''&nbsp;=&nbsp;0 では、単に定数 '''B''' となる。

ブール関数を一般化すると、''f'' : ''X'' &rarr; '''B''' という形式の関数において、''X'' が任意の集合である場合を「[[ブール値関数]]」と呼ぶ。''X'' = '''M''' = {1,&nbsp;2,&nbsp;3,&nbsp;&hellip;} であるとき、''f'' は無限の「二値数列; {{en|binary sequence}}」すなわち 0 と 1 の無限[[列 (数学)|列]]である。''X'' = [''k''] = {1,&nbsp;2,&nbsp;3,&nbsp;&hellip;,&nbsp;''k''} であるとき、''f'' は長さ ''k'' の二値数列である。そのような関数は <math>2^{2^k}</math> 個存在する。これは[[計算複雑性理論]]における問題で基本的な役割を果たす。

== 効率的表現 ==
（[[命題論理]]の）論理式で表現できるが、効率的な表現としては次のようなものがある。
*[[二分決定図]] (BDD)
*[[否定標準形]]
*[[:en:Propositional directed acyclic graph|Propositional Directed Acyclic Graph]] (PDAG)

=== 簡単化 ===
簡単な表現に変換する手法として次のようなものがある。
* カット・アンド・トライ法
:[[ブール代数]]の定義を用い、効率的な表現に変形していく。
*ベン図
:[[ベン図]]を用いて視覚的にわかりやすい表現にする。
以上は人間の直感によるものであり「変換する手法」と言えたものではない。
*カルノー図法
:[[カルノー図]]を用い、効率的な表現に変形していく。
*クワイン・マクラスキー法
:[[クワイン・マクラスキー法]]を用い、効率的な表現に変形していく。計算機で簡単化するのに適している。

==標準形==
[[選言標準形]]と[[連言標準形]]が代表的である。他に、リード-マラー標準形などがある。
===リード-マラー標準形===
リード-マラー標準形（[[:en:Algebraic normal form]]）は、積（[[論理積|AND]]）の排他的論理和（[[排他的論理和|XOR]]）による標準形である。
{| cellpadding="4"
|-
|<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（立方）である。

==関連項目==
{{col-begin}}
{{col-break}}
* [[集合の代数学]]
* [[ブール代数]]
* [[ブール領域]]
* [[ブール論理]]
{{col-break}}
* [[ブーリアン型]]
* [[ブール値関数]]
* [[論理演算子|論理結合子]]
{{col-break}}
* [[真理関数]]
<!-- どうも日本では言わない用語らしい * [[Zeroth order logic]] -->
{{col-end}}

{{DEFAULTSORT:ふうるかんすう}}
[[Category:数理論理学]]
[[Category:ジョージ・ブール]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]