Расшифровка монотонных функций

Известно, что в общем случае для однозначного определения функции алгебры логики необходимо знать значения функции во всех точках булевого куба. Если же функция принадлежит к некоторому классу, более узкому, чем множество всех функций алгебры логики, то для однозначного определения значений функций во всех точках Е^п не обязательно знать значения функций во всех точках Е^п, а иногда достаточно знать на некотором подмножестве Е^п. Так для однозначного определения симметрической функции достаточно знать ее значения на п наборах, по одному с каждого слоя куба.

Задача расшифровки монотонной функции состоит в следующем. Задан оператор Л/, вычисляющий для произвольной точки а Е Е^п значение монотонной функции /(х) в этой точке а, т. е. /(а). Вопрос: как минимальным числом обращений к оператору А/ полностью восстановить таблицу значений монотонной функции /(я)?

Очевидно, что работа любого алгоритма F, решающего указанную задачу, будет заключаться в следующем. Алгоритм выбирает некоторую точку а Е Е^п и с помощью оператора А/ вычисляет значение функции /(х) в точке а. Полученное значение функции в точке, а заносится в таблицу значений исследуемой функции. По монотонности определяются значения /(х) в других точках Е^п. Затем по некоторому правилу выбирается другая точка Е^п, и процесс повторяется до тех пор, пока таблица значений не окажется заполненной полностью.

Паре — алгоритм F и монотонная функция / — сопоставляем число v?(F, /), равное числу обращений к оператору Л/ в процессе восстановления таблицы значений функции / с помощью алгоритма F.

Обозначим

где М_п — множество монотонных функций п переменных;

где минимум берется по всем алгоритмам, решающим задачу расшифровки.

Пусть N — некоторый класс булевых функций п переменных и / Е N. Множество G (f_yN) точек их Е" называются разрешающим для пары (/, N), если из того, что функция g Е N, и на множестве G (f, N) значения функций / и g совпадают, следует, что / = д.

Разрешающее множество называется тупиковым разрешающим множеством для пары (/, JV), если никакое его собственное подмножество не является разрешающим для пары (/, N).

Легко видеть, что у каждой монотонной функции существует единственное тупиковое разрешающее множество, состоящее из всех ее верхних нулей и нижних единиц.

Теорема 7. Имеет место

Доказательство. Нижняя оценка [27|. Из единственности тупикового разрешающего множества монотонной функции /(х 1,…, х_п) следует, что необходимо восстановить ее значение во всех точках (7(/, М_п). Рассмотрим функцию.

Множество ее верхний нулей есть [п/2]-й слой куба Е^п, а нижних единиц — ([п/2] 4- 1)-й слой. Откуда сразу следует, что.

Верхняя оценка [6). Как мы уже отмечали, для произвольной монотонной функции /(xi,…, х_п) из свойства б) леммы 4 следует, что если значение функции /(xi,…, x_n) известно во всех вершинах цепей длины п — 2р — 1, то в каждой цепи длины п—2р+1 существует самое большее две (соседние) вершины, где значения /(хi,…, х_п) остаются неопределенными. Рассмотрим два случая.

1) п = 2к. Тогда по лемме 4 имеется С* — С*^-1 цепей длины 1, и С*^-1 цепей длины более 1. Для первой группы цепей нам надо одно обращение к оператору А/, а для второй — два. Следовательно.

2) п = 2к 4- 1. Тогда все С? цепей имеют длину более 1, и для каждой из них требуется два обращения к оператору А/. Следовательно.

Теорема доказана.

Упражнения.

• 1.28. Для данной обучающей выборки, заданной парой таблиц (Т_ЬТ₂) найти все тупиковые тесты и определить, к какому классу будет отнесен вектор (1010), если воспользоваться описанными выше тестовыми алгоритмами, а именно
• а) алгоритмом А [14],
• б) алгоритмом Л₂ [29],
• в) алгоритмом Аз (47, 48],
• г) алгоритмом голосования по тестам, где в качестве опорного взято множество тупиковых тестов,

при условии, что пара таблиц (Т, Т₂) имеет вид.

• 1.29. Перечислить все монотонные функции, зависящие (не обязательно существенно) от переменных: ri, х₂.
• 1.30. Найти число тр (3) монотонных булевых функций от 3-х переменных.
• 1.31. Перечислить, описанное в лемме Апселя покрытие булевого куба Е^п попарно непересекающимися цепями при условии, что а) n = 2,
• б) n = 3,
• в) n = 4.

: