中央代数

数学において、中央値代数とは、実数の三つ組の中央値とブール多数決関数の概念を一般化する公理の集合を満たす三項 演算を持つ集合である。 ${\displaystyle \langle x,y,z\rangle }$

公理は

1. ${\displaystyle \langle x,y,y\rangle =y}$
2. ${\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }$
3. ${\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }$
4. ${\displaystyle \langle \langle x,w,y\rangle ,w,z\rangle =\langle x,w,\langle y,w,z\rangle \rangle }$

2番目と3番目の公理は可換性を意味します。他の3つの公理が存在する場合、公理(3)が冗長であることを示すことは可能ですが、簡単ではありません。4番目の公理は結合性を意味します。他の公理体系も考えられます。たとえば、次の2つです。

• ${\displaystyle \langle x,y,y\rangle =y}$
• ${\displaystyle \langle u,v,\langle u,w,x\rangle \rangle =\langle u,x,\langle w,u,v\rangle \rangle }$

も十分です。

ブール代数、またはより一般的には分配格子では、中央値関数はこれらの公理を満たすため、すべてのブール代数とすべての分配格子は中央値代数を形成します。 ${\displaystyle \langle x,y,z\rangle =(x\vee y)\wedge (y\vee z)\wedge (z\vee x)}$

バーコフとキスは、0と1の要素を持つメディアン代数が分配格子であることを示しました。 ${\displaystyle \langle 0,x,1\rangle =x}$

メジアン グラフは、3 つの頂点、 、ごとに、 、 、 の任意の2 つの間の最短経路に属する一意の頂点が存在する無向グラフです。この場合、この操作により、グラフの頂点を要素とするメジアン代数が定義されます。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle \langle x,y,z\rangle }$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle \langle x,y,z\rangle }$

逆に、任意のメジアン代数では、区間を となる要素の集合として定義できます。区間に他の要素が含まれないように、各代数要素の頂点と各ペアの辺を作成することにより、メジアン代数からグラフを定義できます。代数がすべての区間が有限であるという特性を持つ場合、このグラフはメジアン グラフであり、グラフ上の最短経路によって定義されるメジアン演算が代数の元のメジアン演算と一致するという点で代数を正確に表します。 ${\displaystyle [x,z]}$${\displaystyle y}$${\displaystyle \langle x,y,z\rangle =y}$${\displaystyle (x,z)}$${\displaystyle [x,z]}$

• バーコフ、ギャレット; キス、SA (1947)。「分配格子における3項演算」。Bull . Amer. Math. Soc. 53 (8): 749–752. doi : 10.1090/S0002-9904-1947-08864-9。
• Isbell, John R. (1980 年 8 月). 「Median algebra」. Trans. Amer. Math. Soc. 260 (2). American Mathematical Society: 319–362. doi : 10.2307/1998007 . JSTOR  1998007.
• Knuth, Donald E. (2008)。組み合わせアルゴリズムとブール関数の紹介。コンピュータプログラミングの芸術。第 4 巻。アッパーサドルリバー、ニュージャージー州: Addison-Wesley。pp. 64–74。ISBN 978-0-321-53496-5。

• 中央値代数の証明