一度だけ読み込む関数

数学において、一度だけ読み込まれる関数とは、各変数が一度だけ現れるブール式で記述できる、特殊なタイプのブール関数のことである。

より正確には、式は論理積、論理和、および否定の演算のみを使用する必要がある。ド・モルガンの法則を適用することにより、このような式は、個々の変数にのみ否定を使用する式（各変数は依然として一度だけ出現する）に変換できる。否定された各変数を、その否定を表す新しい正の変数に置き換えることにより、このような関数は、否定のない一度だけ読み込まれる式で表される、同等の正の一度だけ読み込まれるブール関数に変換できる。 ^{[ 1 ]}

例えば、3つの変数a、b、cの場合、式は次のようになります。

${\displaystyle a\wedge b\wedge c}$

${\displaystyle a\wedge (b\vee c)}$

${\displaystyle (a\wedge b)\vee c}$、 そして

${\displaystyle a\vee b\vee c}$

これらはすべて一度だけ読み込まれます（これらの式内の変数を順列することによって得られる他の関数も同様です）。ただし、式で与えられるブール中央値演算は

${\displaystyle (a\vee b)\wedge (a\vee c)\wedge (b\vee c)}$

一度だけ読み込まれる式ではありません。この式には各変数のコピーが複数あり、各変数を一度だけ使用する同等の式はありません。^{[ 2 ]}

（正の）一度だけ読み取る関数の選言標準形は、一般にそれ自体は一度だけ読み取る関数ではありません。しかしながら、それは関数に関する重要な情報を持っています。特に、頂点が変数を表し、エッジが連言標準形の同じ節に両方とも出現する変数のペアを接続する共起グラフを形成すると、一度だけ読み取る関数の共起グラフは必然的にコグラフになります。より正確には、正のブール関数は、その共起グラフがコグラフであり、さらに共起グラフのすべての最大クリークが選言標準形の連言（主含意）の1つを形成する場合に限り、一度だけ読み取る関数です。^{[ 3 ]}つまり、一度だけ読み取る関数は、その共起グラフの頂点の集合上の関数として解釈されると、最大クリークを含む頂点の集合に対しては真であり、それ以外の場合は偽です。例えば、中央値関数は、3 つの変数の論理積と同じ共起グラフ、つまり三角形グラフを持ちますが、このグラフの 3 つの頂点を持つ完全部分グラフ (グラフ全体) は、論理積の場合にのみ節の部分集合を形成し、中央値の場合には形成しません。^{[ 4 ]}正の読み取り専用式の 2 つの変数は、式の中でそれらの最小共通祖先が 論理積である場合に限り、共起グラフで隣接します。 ^{[ 5 ]}したがって、式ツリーは対応するコグラフのコツリーとして解釈できます。^{[ 6 ]}

正の読み取り専用関数の別の代替的な特徴付けは、それらの選言標準形と連言標準形を組み合わせたものである。与えられた変数系の正の関数は、そのすべての変数を使用するが、選言標準形のすべての主含意と連言標準形のすべての節がちょうど 1 つの変数を共有する場合に限り、読み取り専用である。^{[ 7 ]}

多項式時間で、その選言標準形表現から読み取り専用関数を識別することが可能です。^{[ 8 ]}また、任意の真偽値割り当て で評価を可能にする「ブラックボックス」を介してのみ関数にアクセスできる場合、関数評価の2乗回数のみを使用して、正の読み取り専用関数の読み取り専用表現を見つけることも可能になります。^{[ 9 ]}