ブール関数
ビット(0あるいは1)の列を入力として、最終的に1つの 0/1 を返すような関数、すなわちブール関数は、環状構造を持たない有向グラフで表現できる。ノードのうちの大部分は決定ノードと呼ばれ、それぞれの決定ノードは2つの行き先、つまり2つの子ノードを持つ。決定ノードには「入力の何ビット目を読め」というラベルが与えられている。従って、与えられたブール関数の答えを得るには、指示に従って入力のビット列を読みながら、ビットが0か1かによって、分岐点ごとに2つの行き先のどちらかを選べば良い。さらに、このような決定を十分な回数行うと、2つの終端ノード、0終端あるいは1終端のどちらかに行き当たる。その場合には、どちらの終端が得られたかを、ブール関数の答えとして返す。