ブール関数

ブール関数とは

ブール関数とは、k個のブール値（0または1）を入力として受け取り、1つのブール値を返す関数のことです。数式で表すと、f: Bk → B となります。ここで、B はブール領域 {0, 1} を意味し、k は非負の整数です。k=0 の場合は、定数Bとなります。

ブール値関数

ブール関数を一般化すると、入力が任意の集合Xである場合、f: X → B という形式の関数を「ブール値関数」と呼びます。例えば、X が自然数の集合M = {1, 2, 3, ...} の場合、f は無限の二値数列（0と1の無限列）を表します。また、X が有限集合 [k] = {1, 2, 3, ..., k} の場合、f は長さ k の二値数列を表します。

長さ k の二値数列の関数は 2^(2^k) 個存在し、これは計算複雑性理論において重要な役割を果たします。

ブール関数の効率的な表現

ブール関数は、論理式で表現できますが、より効率的な表現方法として以下のものが挙げられます。

二分決定図 (BDD): ブール関数をグラフ構造で表現する方法で、特に大規模な関数の表現に適しています。
否定標準形: 論理式を否定記号を最小限に抑えた形で表現する方法です。
Propositional Directed Acyclic Graph (PDAG): 論理式を有向非巡回グラフで表現する方法で、論理式の共有化や簡略化に役立ちます。

ブール関数の簡単化

ブール関数をより簡単な形に変換する手法は、以下の通りです。

カット・アンド・トライ法: これは、直感的な方法であり、ブール代数の定義を用いて効率的な表現に変形します。
ベン図: ベン図を用いてブール関数を視覚的に表現し、簡略化する方法です。直感的に理解するのに役立ちますが、体系的な変換手法ではありません。
カルノー図法: カルノー図を用いてブール関数を整理し、簡略化する方法です。特に少数の変数を持つ関数に適しています。
クワイン・マクラスキー法: 計算機でブール関数を簡単化するのに適したアルゴリズムです。効率的な表現への変形を体系的に行えます。

ブール関数の標準形

ブール関数の標準形には、以下のようなものがあります。

選言標準形 (DNF): 論理積（AND）の論理和（OR）で表現する形式です。
連言標準形 (CNF): 論理和（OR）の論理積（AND）で表現する形式です。
リード-マラー標準形 (Algebraic Normal Form, ANF): 積（AND）の排他的論理和（XOR）で表現する形式です。

リード-マラー標準形

リード-マラー標準形は、ブール関数を積（AND）の排他的論理和（XOR）で表現します。例えば、あるブール関数 f は、次のように表されます。


f(x1, x2, ..., xn) = a0 ⊕ a1x1 ⊕ a2x2 ⊕ ... ⊕ a1,2x1x2 ⊕ ... ⊕ a1,2,...,nx1x2...xn


ここで、a0, a1, ..., a1,2,...,n は 0 または 1 の係数です。この表現により、ブール関数は一意に表現されます。

ブール関数の代数的次数

リード-マラー標準形におけるブール関数の代数的次数は、AND項に現れる変数の最大数で定義されます。例として、次のブール関数を考えます。


f(x1, x2, x3) = x1 + x3


この関数の次数は1（線形）です。


f(x1, x2, x3) = x1 + x1x2x3


この関数の次数は3（立方）です。

まとめ

ブール関数は、情報科学や計算機科学において基礎的な役割を果たす重要な概念です。効率的な表現や簡単化の手法を理解することで、より複雑な問題を解決するための基礎を築くことができます。

関連項目

論理回路
計算複雑性理論
* ブール代数

もう一度検索