Монотонная булева

ФУНКЦИЯ - булева функция [img: http://localhost:8080/file/031418-95.jpg] обладающая следующим свойством: если для нек-рых наборов [img: http://localhost:8080/file/031418-96.jpg], [img: http://localhost:8080/file/031418-97.jpg] выполнено условие [img: http://localhost:8080/file/031418-98.jpg] для всех i(в этом случае пишут [img: http://localhost:8080/file/031418-99.jpg]), то [img: http://localhost:8080/file/031418-100.jpg]. Напр., функция [img: http://localhost:8080/file/031418-101.jpg] (сложение по модулю 2) не является монотонной, т. к. [img: http://localhost:8080/file/031418-102.jpg], но [img: http://localhost:8080/file/031418-103.jpg] [img: http://localhost:8080/file/031418-104.jpg] Примеры М. б. ф.: константы 0 и 1, тождественная функция [img: http://localhost:8080/file/031418-105.jpg], дизъюнкция [img: http://localhost:8080/file/031418-106.jpg] конъюнкция [img: http://localhost:8080/file/031418-107.jpg] и т. д. Примеры немонотонных булевых функций: отрицание [img: http://localhost:8080/file/031418-108.jpg], импликация [img: http://localhost:8080/file/031418-109.jpg] и т. д. Любая функция, полученная с помощью операции суперпозиции из М. б. Для числа [img: http://localhost:8080/file/031418-111.jpg] М. б. ф., зависящих от ппеременных, известно, что [img: http://localhost:8080/file/031418-112.jpg] где [img: http://localhost:8080/file/031418-113.jpg], с- нек-рая константа (см. [2]). Для сложности реализации класса М. б. ф. схемами из функциональных элементов и контактными схемами получены более низкие значения, чем для сложности реализации произвольных булевых функций (см. Синтеза задачи). Нек-рые дискретные экстремальные задачи сводятся к задаче расшифровки М. б. ф. В этой задаче требуется, зная, что нек-рая функция [img: http://localhost:8080/file/031418-114.jpg] является М. б. ф., выяснить ее значения на всех наборах, задав как можно меньше вопросов вида: "Чему равно значение [img: http://localhost:8080/file/031418-115.jpg] на нек-ром наборе [img: http://localhost:8080/file/031418-116.jpg] ". Был предложен [3] алгоритм, к-рый требует для расшифровки произвольной М. б. ф. задания не более [img: http://localhost:8080/file/031418-117.jpg] вопросов. С другой стороны, не существует алгоритма расшифровки, к-рый отличал бы функцию [img: http://localhost:8080/file/031418-118.jpg] от всех остальных М. б. ф. менее чем за [img: http://localhost:8080/file/031418-119.jpg] вопросов. Обобщением понятия М. б. ф. являются монотонные функции k- значной логики. Если на множестве [img: http://localhost:8080/file/031418-120.jpg] задано произвольное частичное упорядочение [img: http://localhost:8080/file/031418-121.jpg] (пишут [img: http://localhost:8080/file/031418-122.jpg]), то, по определению, для любых двух наборов [img: http://localhost:8080/file/031418-123.jpg] [img: http://localhost:8080/file/031418-124.jpg] и [img: http://localhost:8080/file/031418-125.jpg] запись [img: http://localhost:8080/file/031418-126.jpg] означает, что [img: http://localhost:8080/file/031418-127.jpg] для всех i. Функция k-значной логики [img: http://localhost:8080/file/031418-128.jpg] (т. е. определенная и принимающая значение на Е k)наз. монотонной относительно S, если для любых наборов [img: http://localhost:8080/file/031418-129.jpg] [img: http://localhost:8080/file/031418-130.jpg] и [img: http://localhost:8080/file/031418-131.jpg] из условия [img: http://localhost:8080/file/031418-132.jpg] вытекает [img: http://localhost:8080/file/031418-133.jpg]. Класс всех функций, монотонных относительно нек-рого частичного упорядочения [img: http://localhost:8080/file/031418-134.jpg] на [img: http://localhost:8080/file/031418-135.jpg], всегда является замкнутым классом; он является предполным классом в k-значной логике в том и только в том случае, если в Sимеются ровно один минимальный и ровно один максимальный элементы. Для числа [img: http://localhost:8080/file/031418-136.jpg] функций k-значной логики, зависящих от ппеременных и монотонных относительно S, при [img: http://localhost:8080/file/031418-137.jpg] имеет место соотношение [img: http://localhost:8080/file/031418-138.jpg] где С(S)- константа, эффективно вычисляемая по данному частичному упорядочению S(см. [5]).