О сложности доказательства повторности булевых функций в бинарном базисе

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

2011 Теоретические основы прикладной дискретной математики № 3(13)
УДК 519. 716
О СЛОЖНОСТИ ДОКАЗАТЕЛЬСТВА ПОВТОРНОСТИ БУЛЕВЫХ ФУНКЦИЙ В БИНАРНОМ БАЗИСЕ1
А. А. Вороненко
Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия
E-mail: dm6@cs. msu. ru
Показано, что для доказательства повторности булевой функции в базисе всех функций двух переменных в худшем случае требуется линейное по числу переменных функции количество наборов.
Ключевые слова: бесповторная булева функция, сложность доказательства.
Булева функция f (x,…, xn), представимая (не представимая) бесповторной формулой в некотором базисе, называется бесповторной (повторной) в этом базисе. Множество всех функций двух переменных называется бинарным базисом.
В настоящей работе доказываются две теоремы.
Теорема 1. Существует повторная в бинарном базисе функция n переменных, доказательство повторности которой требует предъявления не менее n + 3 наборов.
Теорема 2. Для любой повторной в бинарном базисе функции n переменных можно предъявить 4n наборов, доказывающих ее повторность.
Их следствием является
Теорема 3. Доказательство повторности булевой функции в базисе всех функций двух переменных в худшем случае требует линейного относительно числа переменных функции количества наборов.
Преобразованиями обобщенной однотипности называются замена переменной или самой функции на ее отрицание и перестановка переменных. Функции, получаемые друг из друга конечным числом преобразований обобщенной однотипности, называются обобщенно однотипными.
Функциями Стеценко называются функции следующих пяти семейств:
fds) = xi Л (x2 V Хз Л … Л xs) V x2 Л x3 Л … Л xs, s ^ 3,
(s) _ _ _
f (' = x1 Л x2 Л … Л xs V x1 Л x2 Л … Л xs, s ^ 2,
f& lt-? = x1 Л (x2 V … V xs) V x2 Л … Л xs, s ^ 3,
f4 = x1 Л (x2 V x3) V x3 Л x4,
f5 = x1 Л (x3 Л x4 V x5) V x2 Л (x3 V x4 Л x5).
Теорема Стеценко [1]. Из любой повторной в базисе {Л, V, -} функции можно подстановкой констант получить подфункцию, однотипную с одной из функций Сте-ценко.
хРабота выполнена при поддержке гранта Президента Р Ф МД-757. 2011.9.
Функциями Перязева называются следующие четыре функции:
Р = ж1 Л ж2 Л ж3 ф ж2 Л ж3, р2 = Жі Л (Ж2 V Жз) ф Ж2 Л Жз, р3 = ж1 Л ж2 Л ж3 Л ж4 ф (ж1 ф ж2) Л ж3 Л ж4, р4 = ж1 Л (ж2 V ж3 Л ж4) ф (ж3 V ж2 Л ж4).
Теорема Перязева [2]. Из любой повторной в бинарном базисе функции можно подстановкой констант получить подфункцию, однотипную с одной из функций Стеценко (для /?^ выполняется в ^ 3), либо одну из функций Перязева.
Рассмотрим повторную в бинарном базисе функцию (ж1 V ¦ ¦ ¦ V жп) Л (ж! V ¦ ¦ ¦ V Vжn), где п ^ 3. Оценим снизу количество наборов в доказательстве ее повторности. Для доказательства повторности этой функции требуется предъявить оба ее нуля, иначе предъявляемая частичная функция доопределима либо до ж1 V ¦ ¦ ¦ V жп, либо до жг V ¦ ¦ ¦ V жп.
Назовем 0−1-матрицу разнозначной, если все ее строки различны и она не имеет ни нулевых, ни единичных строк. Будем говорить, что функция ^ моделирует разнозначную матрицу, если & lt-^(ж) = 1 для всех строк ж матрицы и & lt-^(0) = & lt-^(1) = 0.
Лемма 1. Каковы бы ни были три (четыре) ненулевых и неединичных набора значений трех (четырех) переменных, найдется бесповторная функция, равная на них единице и нулю на единичном и нулевом наборах.
Доказательство. В силу возможности замены всех переменных их отрицаниями будем считать, что средний вес наборов не превосходит половины числа столбцов матрицы, составленной из этих наборов. В силу симметричности функции (ж1 V ¦ ¦ ¦ V жп) Л (жі V ¦ ¦ ¦ V жп) на каждом слое булева куба, начиная с первого, будем выбирать минимальные в лексикографическом порядке наборы. Для трех переменных
0 0 1 0 0 1 0 0 1
0 1 0 I, I 0 1 0 I, I 0 1 0
1 0 0 0 1 1 1 0 1
) (ж2 V ж3), последнюю — ж2 ф ж3.
матриц с четырьмя столбцами моделируется функцией
возникает три матрицы
моделирует функция Ж1 9 Заметим, что часть
Первые две из них
ж1 ® ж2 ® ж3 ® ж4 либо одной из функций вида (ж^ ф ж2) V (ж*3 ф ж4). Чтобы этого не произошло, матрица должна иметь набор веса два из каждой из трех пар противоположных наборов. Возможны четыре случая:
0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1
0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 0 1, 0 1 0 1, 0 1 0 1, 0 1 1 0
0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0
Все эти матрицы моделирует функция (ж1 V ж2) Л (ж3 V ж4). ¦
Для ненулевых и неединичных наборов длины не менее пяти введем следующую классификацию: наборы первого рода — имеющие ровно один ноль или ровно одну единицу- наборы второго рода — имеющие ровно два нуля или ровно две единицы (эти значения — 0 и 1 соответственно — назовём особыми) — наборы третьего рода — остальные.
Лемма 2. Пусть дана произвольная разнозначная 0−1-матрица размера т х п, где т ^ п и п ^ 5. Тогда либо эта матрица моделируется некоторой бесповторной функцией, либо в ней есть два столбца, удалением которых вместе со строками, имеющими в них разные значения, и удалением дублирующихся строк можно вновь получить разнозначную матрицу с числом строк, не превосходящим числа столбцов.
Доказательство. Пусть противоположных строк второго рода нет. Рассмотрим граф с п вершинами и ребрами между теми из них, для которых существует строка второго рода, имеющая особые значения в соответствующих позициях (граф второго рода). Если в графе второго рода есть две неизолированные вершины, не соединенные ребром, то выбор соответствующих столбцов приводит к удалению не менее двух строк. В противной ситуации рассмотрим два случая.
1. Граф второго рода пуст. Если т & lt- п, то можно взять любые два столбца так, чтобы они различались хотя бы в одной строке. Если т = п и есть хотя бы две строки первого рода, то можно взять два столбца, в которых одна из них принимает уникальное значение. Наконец, при т = п и наличии не более одной строки первого рода общее количество вариантов выбора пар столбцов не меньше, чем
3(п — 1)(п — 3) + п — 1, что больше, чем. Поэтому какая-то пара встретится не менее двух раз.
2. Граф второго рода — объединение клики размера I ^ 2 и изолированных вершин. Пусть в клику входят первые I вершин. Если имеется хотя бы одна строка первого или третьего рода, то, взяв два столбца: один из первых /, а другой — из оставшихся, которые отличаются в этой строке, получим утверждение леммы. Если строк первого и третьего родов нет, то при I ^ 5 матрицу моделирует функция
(ж1 ф жг+1) V (ж2 ф жг+2) V ¦ ¦ ¦ V (жг ф ж21).
При I = 4 с точностью до симметрий возможны два вида матриц:
/ 0 0 1 11 1 / 0 0 1 1 0 0
0 1 0 11 1 0 1 0 1 1 1
0 1 1 01 1 и 0 1 1 0 1 1
1 0 0 11 1 1 0 0 1 1 1
1 0 1 01 1 1 0 1 0 0 0
V 1 1 0 01 1 V 1 1 0 0 1 1 /
Данные матрицы моделируются функциями ж6Л (ж1 Vж2 Vж3 Vж4) и (ж1 Фж2) V (ж3фж5) соответственно. ¦
Для доказательства теоремы 1 достаточно воспользоваться леммами 1 и 2 и тем, что если функция ^ моделирует матрицу, полученную из исходной по лемме 2 удалением ?-го и ]-го столбцов, то функция (ж^ ф Жj) V ^ моделирует исходную матрицу.
Перейдем к доказательству верхней оценки — теоремы 2.
Дерево называется каноническим, если оно удовлетворяет следующим условиям:
1) Листья помечены попарно различными переменными или отрицаниями переменных.
2) Внутренние вершины помечены одним из следующих символов: Л, V, ф, ф (вершины любой степени захода, которым соответствует конъюнкция, дизъюнкция, сумма по модулю 2 или ее отрицание).
3) Смежные вершины не могут быть помечены одинаковыми символами из множества {Л, V, ф, ф}, а также символами ф и ф одновременно.
4) Корень расположен снизу. Вершина, смежная сверху с вершиной, помеченной ф или ф, не может быть помечена ни отрицанием переменной, ни конъюнкцией.
В работе [3] доказывается следующий факт.
Утверждение 1. Любая бесповторная функция (зависящая хотя бы от одной переменной) в бинарном базисе представима единственным каноническим деревом.
Переменную жг назовем особой для функции /(ж1 ,…, жп), если для любой другой переменной Жj подстановкой констант на места оставшихся переменных можно либо получить как линейную, так и нелинейную функции, существенно зависящие от жг и Жj, либо получить две нелинейных функции переменных Жг и Жj, одна из которых становится константой при подстановке жг = 0, другая — при подстановке жг = 1.
Из утверждения 1 вытекает
Лемма 3. Бесповторная в бинарном базисе функция не имеет особых переменных.
Лемма 4. Переменная ж1 -особая для функций семейства /8). Для доказательства этого достаточно предъявить 4з наборов.
Доказательство. Подстановки ж2 = ¦ ¦ ¦ = ж^ = ж,+1 = ¦ ¦ ¦ = ж5 = 0 дают всевозможные подфункции вида Ж! Л Ж, а подстановки ж2 = ¦ ¦ ¦ = ж, — = ж,+1 = ¦ ¦ ¦ = = ж5 = 1 -вида ж1 Л ж,. Общее число различных наборов равно 4з. ¦
Лемма 5. Переменная ж2 -особая для функций семейства /т^. Для доказательства этого достаточно предъявить 4з наборов.
Доказательство. Подстановки ж1 = 1, ж3 = ¦ ¦ ¦ = ж,-1 = ж,+1 = ¦ ¦ ¦ = = ж5 = 0 дают всевозможные подфункции вида ж2 Vж, для ] ^ 3, а подстановки ж1 = 0, ж3 = ¦ ¦ ¦ = ж,-1 = ж,+1 = ¦ ¦ ¦ = ж5 = 1 -всевозможные подфункции вида ж2 Л ж, для ] ^ 3. Подстановки ж3 = ¦ ¦ ¦ = ж5 = 0 и ж3 = ¦ ¦ ¦ = ж5 = 1 дают подфункции ж2 Л ж1 и ж2 V ж1 соответственно. Общее число различных наборов равно 4з. ¦
В каноническом дереве назовем эквивалентными переменные или отрицания переменных, если помеченные ими вершины смежны с одной внутренней вершиной. Если вершина, помеченная ж, или Ж, лежит в корневом поддереве с корнем — вершиной, смежной с вершиной, помеченной жг или Жг, то скажем, что переменная жг не слабее переменной Ж,.
Лемма 6. Для доказательства повторности функции семейства /^ достаточно предъявить 4з наборов.
Доказательство. Подстановки ж1 = 1, ж2 = 0, ж4 = ¦ ¦ ¦ = ж,-1 = ж,+1 = ¦ ¦ ¦ = = ж5 = 1 дают всевозможные подфункции вида ж3 Л ж, для ] ^ 4, а подстановки ж1 = 0, ж2 = 1, ж4 = ¦ ¦ ¦ = ж,-1 = ж,+1 = ¦ ¦ ¦ = ж5 = 0 — всевозможные подфункции вида ЖЗ Л Ж, для ] ^ 4. При этом подстановка ж2 = 0, ж4 = ¦ ¦ ¦ = ж5 = 1 дает остаточную функцию ж3 Л ж1, подстановка ж1 = ж4 = ¦ ¦ ¦ = ж5 = 1 — остаточную функцию ж3 V ж2, а подстановка ж1 = 0, ж4 = ¦ ¦ ¦ = ж5 = 1 — остаточную функцию ЖЗ Л ж2. В силу значений функции при этих подстановках переменная ж3 не может быть не слабее переменных ж4, …, ж5 и не может быть эквивалентна переменной ж2. Остаются неопровергнутыми два варианта для бесповторной реализации.
1. Переменная ж3 эквивалентна ж1. Тогда для гипотетической бесповторной функции можно сделать замену и = ж3 Л ж1, что противоречит соотношению / (1101… 1) = = /(01… 1).
2. Переменная ж3 не слабее эквивалентных друг другу переменных ж1 и ж2. Подстановка ж3 = 0, ж4 = ¦ ¦ ¦ = ж5 = 1 дает остаточную функцию ж1 Л ж2. Тогда для гипотетической бесповторной функции можно сделать замену и = ж1 Л ж2. Противоречивым окажется соотношение /(101… 1) = /(01… 1).
Общее число различных наборов не превосходит 4з. ¦
Лемма 7. Для доказательства повторности функции Стеценко /5 достаточно предъявить 14 наборов.
Доказательство. Подстановка ж2 = 0, ж4 = 1, ж5 = 0 дает подфункцию ж1 Л ж3, подстановка ж2 = 1, ж4 = 0, ж5 = 1 -подфункцию ж1 VжЗ. Таким образом, между ж1 и ж3 и нелинейной связкой в гипотетической бесповторной формуле должны быть линейные связки, как и после нелинейной связки, т. е. формула имеет вид
((ж1 ф ж^) V (жз ф ж^)) ф ж?*,
где {?,. ?'-,&-} = {2, 4, 5}. При этом остаточные функции переменных жг, жк и ж, жк будут линейными. Подстановка ж1 = 1, ж2 = 0, ж3 = 1 дает подфункцию ж4 Vж5, а подстановка ж1 = 0, ж3 = 0, ж5 = 1 -подфункцию ж2 Л ж4. Имеем противоречие. Получаемые при подстановках четверки имеют общие наборы. Общее количество различных наборов равно 14. ¦
Доказательство теоремы 2. Выделим по теореме Перязева подфункцию 5 ^ п переменных. При 5 ^ 4 теорема вытекает из неравенства 25 ^ 45, при больших п — из лемм 4, 5, 6 и 7.
ЛИТЕРАТУРА
1. Стеценко В. А. О предплохих базисах в Р2 // Матем. вопросы кибернетики. Вып. 4. М.: Физматлит, 1992. С. 139−177.
2. Перязев Н. А. Слабоповторные булевы функции в бинарном базисе // Дискретная математика и информатика. Вып. 4. Иркутск: Изд-во Иркут. ун-та, 1998. 12 с.
3. Вороненко А. А. О проверяющих тестах для бесповторных функций // Матем. вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163−176.

ПоказатьСвернуть
Заполнить форму текущей работой