Медианная алгебра

В математике медианная алгебра — это множество с тернарной операцией, удовлетворяющее набору аксиом, которые обобщают понятия медиан троек действительных чисел и булевой функции большинства .${\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}$

Вторая и третья аксиомы подразумевают коммутативность: можно (но нелегко) показать, что при наличии трех других аксиома (3) излишняя. Четвертая аксиома подразумевают ассоциативность. Возможны и другие системы аксиом: например, две

• ${\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}$

Медианный граф — это неориентированный граф , в котором для каждых трех вершин , , и существует уникальная вершина , которая принадлежит кратчайшим путям между любыми двумя из , , и . Если это так, то операция определяет медианную алгебру, элементами которой являются вершины графа.${\displaystyle x}$${\displaystyle у}$${\displaystyle z}$${\displaystyle \langle x,y,z\rangle}$${\displaystyle x}$${\displaystyle у}$${\displaystyle z}$${\displaystyle \langle x,y,z\rangle}$

Наоборот, в любой медианной алгебре можно определить интервал как множество элементов, таких что . Можно определить граф из медианной алгебры, создав вершину для каждого элемента алгебры и ребро для каждой пары, так что интервал не содержит других элементов. Если алгебра обладает свойством, что каждый интервал конечен, то этот граф является медианным графом, и он точно представляет алгебру в том, что медианная операция, определяемая кратчайшими путями на графе, совпадает с исходной медианной операцией алгебры.${\displaystyle [x,z]}$${\displaystyle у}$${\displaystyle \langle x,y,z\rangle =y}$${\displaystyle (x,z)}$${\displaystyle [x,z]}$

• Биркгоф, Гарретт ; Кисс, С.А. (1947). «Тернарная операция в дистрибутивных решетках». Bull. Amer. Math. Soc. 53 (8): 749– 752. doi : 10.1090/S0002-9904-1947-08864-9 .
• Isbell, John R. (август 1980). «Медианная алгебра». Trans. Amer. Math. Soc. 260 (2). Американское математическое общество: 319– 362. doi : 10.2307/1998007 . JSTOR  1998007.
• Кнут, Дональд Э. (2008). Введение в комбинаторные алгоритмы и булевы функции . Искусство программирования . Том 4. Upper Saddle River, NJ: Addison-Wesley. С.  64–74 . ISBN 978-0-321-53496-5.

• Доказательство Медианной Алгебры