2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Функции одновременно монотонные и самодвойственные
Сообщение12.03.2009, 23:30 
помогите,пожалуйста

1)M∩S (функция принадлежит классу монотонных и самодвойственных)
я считаю,что это так называемая формула "голосования"(т.е. функция от набора переменных равна 0 или 1 в зависимости от значений переменных,чего больше,то и будет).. но не могу понять,единственная ли она в пересечении и что будет базисом.
и как в общем случае искать базис?(можно ли использовать таблицу выражающую принадлежность 5и классам T0,T1,M,L,S)

 
 
 
 
Сообщение13.03.2009, 00:05 
Аватара пользователя
Найдите книгу Марченкова С.С. "Замкнутые классы булевых функций" или какое-нибудь другое описание решетки Поста. Там приведены базисы для всех замкнутых классов.
Медиана действительно является базисом $S\cap M$.

Добавлено спустя 30 минут 36 секунд:

Кстати, есть очень красивое утверждение, с помощью которого это можно доказать:
Для монотонной функции
$f(x_1,x_2,x_3,\dots) = m(f(x_1,x_1,x_3,\dots),f(x_1,x_2,x_2,\dots),f(x_3,x_2,x_3,\dots))$
Это утверждение, правда, нетривиально докзывается. Используется то, что из $x_1,x_2,x_3$ обязательно есть 2 одинаковых. Далее, если, скажем, $x_1=x_2$, то $f(x_1,x_1,x_3)$ не меньше одного из $f(x_1,x_2,x_2) = f(x_1,x_1,x_1)$ и $f(x_3,x_2,x_3)=f(x_3,x_1,x_3)$ и не больше другого, а значит медиана выдаст именно его.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group