О глубине функций многозначной логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ФГБОУ ВПО «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА»

На правах рукописи УДК 519.7

Кочергин Алексей Вадимович О ГЛУБИНЕ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

11 СКТ 2013

Москва 2013

005536820

Работа выполнена на кафедре дискретной математики Механико-математического факультета Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственний университет имени М. В. Ломоносова».

Научный руководитель: доктор физико-математических наук,

профессор Касим-Заде Октай Мурад оглы

Официальные оппоненты: доктор физико-математических наук,

профессор Косовский Николай Кириллович (ФГБОУ ВПО «Санкт-Петербургский государственный университет», зав. кафедрой информатики математико-механического факультета)

кандидат физико-математических наук, доцент Стеценко Владимир Алексеевич (ФГБОУ ВПО «Московский педагогический государственный университет», кафедра теоретической информатики и дискретной математики)

Ведущая организация: ФГБУН Институт математики им. С. Л. Соболева Сибирского отделения РАН

Защита диссертации состоится 22 ноября 2013 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» по адресу: Российская Федерация, 119991, ГСП-1, Москва, Ленинские горы, д. 1, МГУ имени М. В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» (Москва, Ломоносовский проспект, дом 27, сектор А, 8 этаж).

Автореферат разослан 22 октября 2013 г.

/V

Ученый секретарь диссертационного совета Д.501.001.84 при ФГБОУ ВПО МГУ доктор физико-математических наук,

профессор А. О. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Диссертационная работа относится к одной из центральных областей дискретной математики и математической кибернетики — теории синтеза и сложности управляющих систем1. Одним из важнейших модельных классов управляющих систем является изучаемый в работе класс схем из функциональных элементов2.

В диссертации рассматривается реализация функций fc-значной логики схемами из функциональных элементов над произвольным функционально полным базисом. Основная задача синтеза схем из функциональных элементов в данном случае может быть сформулирована следующим образом. Для произвольной функции ft-значной логики требуется построить такую реализующую ее схему из функциональных элементов над заданным базисом, которая является в том или ином смысле близкой к наилучшей (например, асиптотически оптимальной схемой) относительно выбранной меры сложности2'3.

Начиная со второй половины 1950-х годов О.Б. Лупановым были разработаны асимптотически оптимальные методы синтеза и получены асимптотически точные оценки сложности для многих важнейших классов управляющих систем, в том числе для схем из функциональных элементов над произвольным конечным полным базисом булевых функций4.

Одной из наиболее важных мер сложности является глубина схемы. С содержательной точки зрения рассматриваемое в данной работе понятие глубины связано с представлениями о задержке (или времени работы) схемы5. Время работы является одной из наиболее существенных характеристик современных вычислительных устройств.

Под глубиной схемы понимается максимальное число элементов в ориентированных цепях, ведущих от какого-либо из входов схемы к ее выходу.

^Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. — С. 7-38.

2Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во Московского университета, 1984.

3Shannon С. Е. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J. — 1949. — V. 28, № 1. — P. 59-98. (Русский перевод: Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963. — С. 59-101.)

Лупанов О. Б. Об одном методе синтеза схем // Известил высших учебных заведений. Радиофизика. — 1958. — Т. 1, № 1. — С. 120-140.

5См., например: Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 43-81; Храпчен-ко В. М. Новые соотношения между глубиной и задержкой // Дискретная математика. — 1995. — Т. 7, вып. 4. — С. 77-85.

Глубиной функции fc-значной логики / над базисом В называется минимальная глубина схем, реализующих функцию / над базисом В. В диссертационной работе под базисом понимается произвольное функционально полное множество функций fc-значной логики, т.е. такое, что суперпозициями функций этого множества можно реализовать любую функцию fc-значной логики. Базис называется бесконечным, если для любого натурального числа т существует функция из этого базиса, существенно зависящая более чем от т переменных. В противном случае базис называется конечным. Вообще говоря, при этом формально число функций в конечном базисе может быть бесконечным. Однако, по-существу, конечный базис с точностью до введения и изъятия несущественных переменных содержит лишь конечное число различных функций. Будем считать, что конечный базис задается как конечное множество функций fc-значной логики.

Отметим, что в ряде работ6 под «глубиной» (или «глубиной альтернирования») схемы понимается максимальное число перемен типов элементов в цепях, ведущих от входов схемы к ее выходу. Это понятие существенно отличается от изучаемого в данной работе, и в данной работе не рассматривается.

Отметим также, что в данной работе исследуется глубина функций fc-значной логики только над функционально полными системами. Однако глубина функций изучалась и над функционально неполными системами функций двузначной и fc-значной (к > 3) логики (см., например, работы А. Б. Угольникова7'8, А. А. Андреева9). В ряде работ также получены соотношения, связывающие глубину и формульную сложность функций

6См., например: Лупанов О. Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе &,V, // Проблемы кибернетики, вып. 6. — М.: Физматгиз, 1961. — С. 5-14; Лупанов О. В. О влиянии глубины формул на их сложность // Кибернетика. — 1970. — № 2. — С. 46-49.-Boppana R. В., Sipser М. The complexity of finite functions // Handbook of Theoretical Computer Science. — V. A. Algoritms and complexity — Amsterdam: Elsiver, 1990. — P. 757-804; Ложкин С. А., Коноводов В. А. О синтезе и сложности формул с ограниченной глубиной альтернирования // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. — 2012. — № 2. — С. 28-36.

7Угольников А. Б. О глубине формул в неполных базисах // Математические вопросы кибернетики, вып. 1. — М.: Наука, 1988. — С. 242-245.

8Угольников А. Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики, вып 2 — М.: Наука, 1989. — С. 174-176.

9Андреев А. А. Об одной последовательности функций многозначной логики // Вестник Московского университета. Сер. 1. Математика. Механика. — 2011 — № 6. — С. 3-7.

(см., например, работы Ф. М. Спиры10, В. М. Храпченко11, И. Вегенера12, А. Б. Угольникова13, М. Е. Рагаца14, Р. Ф. Сафина15). В работе в качестве меры сложности рассматривается только глубина схем, а ее взаимосвязи с другими мерами сложности, как и сами другие меры сложности, не рассматриваются.

В диссертации для произвольного базиса В исследуется поведение функции Шеннона глубины DB(n), характеризующей максимальную глубину функций от п переменных и определяемой равенством DB(n) = таxDB(f), где максимум берется по всем функциям fc-значной логики /, зависящим от п переменных.

В 1970 г. О. Б. Лупановым16 было установлено, что в случае двузначной логики (к = 2) для любого конечного базиса В выполняется равенство

DB(n) - Сп + а(п),

где а(п) = о(п) при п оо, а С = (logjm)"1 и т — максимальное число существенных переменных у функций из базиса В. В случае классического базиса двузначной логики, состоящего из конъюнкции двух переменных, дизъюнкции двух переменных и отрицания, эта оценка для функции Шеннона глубины уточнялась в работах Ф. М. Спиры17, У. ф. Мак-Колла и

10Spira Р. М. On time-hardware complexity tradeoffs for Boolean functions // Proc. Ith Hawai Symposium on System Sciences. — 1971. — P. 525-527.

"Храпченко В. M. О соотношении между сложностью и глубиной формул в базисе, содержащем медиану // Методы дискретного анализа в теории кодов и схем. Сб. научн. тр., вып. 37. — Новосибирск: Ин-т математики СО АН СССР, 1981. — С 7784.

12Wegener I. Relating monotone formula size and monotone formula depth of Boolean functions // Information Processing Letters. — 1983. — V. 16. — P. 41-42.

"Угольников А. Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Математические заметки. — 1987 — Т 42 № 4. — С. 603-612. ' '

"Ragaz М. Е. Parallelizable algebras // Archiv für Mathematische Logik und Grundlagenforschung. — 1986/87. — Bd. 26/1, № 2. — P. 77-99.

15Сафин Р. Ф. О равномерности систем монотонных функций // Вестник Московского университета. Сер. 1. Математика. Механика. — 2003. — № 2. — С. 15-20.

Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 43 81.

17Spira Р. М. On the time necessary to compute switching functions // IEEE Transactions on Computers. — 1971. — V. 20 (1). — P. 104-105.

M. С. Патерсона18, С. Б. Гашкова19, С. А. Ложкина20.

В 1996 г. С. А. Ложкиным21 было показано, что для произвольного конечного базиса В функций двузначной логики справедливо равенство

£>в(п) = С{п - log2 log2 п) + с(п),

где с(п) = 0(1).

Результатов о поведении функции Шеннона глубины в случае бесконечных базисов функций двузначной логики до появления работ О. М. Касим-Заде было известно немного. Асимптотики роста (или хотя бы порядки роста) были найдены только для небольшого числа базисов. При этом во всех известных примерах функция Шеннона либо была ограничена сверху константой (в частности, для базиса, состоящего из всех функций двузначной логики, или для базиса функций двузначной логики, состоящего из всех пороговых функций22, либо росла по порядку как log2n (например, для базиса функций двузначной логики, состоящего из конъюнкции двух переменных и всех линейных функций — фактически это следует из результатов работы С. А. Ложкина23).

В 2007 г. О. М. Касим-Заде24 было установлено, что для любого бесконечного базиса В функций двузначной логики порядок роста функции Шеннона глубины DB(n) при п оо равен либо 1, либо log2n. Позднее

0. М. Касим-Заде25,26 этот результат усилил: было показано, что для лю-

18McColl W. F., Paterson M. S. The depth of all Boolean functions // SI AM J. Comput — 1977. — V. 6, № 2. — P. 373-380.

19Гашков С. Б. О глубине булевых функций // Проблемы кибернетики, вып. 34. — М.: Наука, 1978. — С. 265-268.

20Ложкин С. А. О глубине функций алгебры логики в некоторых базисах // Annales Univ. Sei. Budapest. Sec. Comput. — 1983. — V. 4. — P. 113-125.

21Ложкин С. А. О глубине функций алгебры логики в произвольном полном базисе // Вестник Московского университета. Сер. 1. Математика. Механика. — 1996 — № 2. — С. 80-82.

22Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 26. — М.: Наука, 1973. — С. 109-140.

23Ложкин С. А. Асимптотическое поведение функций Шеннона для задержек схем из

функциональных элементов // Математические заметки. — 1976. — Т 19 № 6 _

С. 939-951.

24Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным базисом // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007. — № 1. — С. 18-21.

25Касим-Заде О. М. О глубине булевых функций над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Сер. 1. — 2007 — Т 14

1. — С. 45-69. ' '

26Касим-Заде О. М. О глубине булевых функций при реализации схемами над произ-

бого бесконечного базиса В функций двузначной логики либо существует константа а, 1 < а < 6, такая, что Ов(п) = о при всех достаточно больших п, либо существуют целочисленная константа Ь > 2, такая, что Р^п] < Ов(п) < [к^п] + 5 при всех п.

При к > 3 задача о поведении функции Шеннона глубины функций /с-значной логики при реализации схемами из функциональных элементов до последнего времени оставалась практически неисследованной. Можно указать, по-видимому, только на некоторые тривиальные результаты, являющиеся очевидными обобщениями на &-значные логики случая двузначной логики. Например, для конечного базиса В*, состоящего из всех функций &-значной логики от двух переменных, легко показать, что порядок роста функции Шеннона глубины £>в.(п) при п -> оо равен п. Отсюда очевидным образом следует, что и для любого конечного базиса В функций &-значной логики функция Шеннона глубины Вв(п) при п оо по порядку растет как п. В то же время вопрос о точном виде асимптотики функции Шеннона глубины функций £-значной логики при к > 3 над произвольным конечным базисом до самого последнего времени, по-видимому, оставался открытым. В случае бесконечных базисов при к > 3 оставался открытым даже вопрос о возможных порядках роста функции Шеннона глубины, в частности, оставалось неизвестным, конечно или бесконечно их число.

Цель работы.

Целью диссертационной работы является изучение асимптотического поведения функции Шеннона глубины схем из функциональных элементов над произвольным базисом (т. е. функционально полной системой) функций ¿-значной логики при всех к > 3 и получение асимптотических выражений для указанной функции Шеннона.

Методы исследования.

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

Научная новизна.

Все основные результаты диссертации являются новыми. Основные положения, выносимые на защиту, следующие:

1. При всех к > 3 установлено существование асимптотики вида Ов(п) = авп + о(п) для функции Шеннона глубины £>й(п) над произ-

вольным бесконечным базисом // Вестник Московского университета. Сер. 1. Математика. Механика. — 2012. — № б. — С. 55-57.

вольным конечным базисом В функций &-значной логики, где ав — положительная постоянная, зависящая только от базиса В, п —у оо.

2. Получено алгоритмическое решение проблемы нахождения константы в указанной выше асимптотике. Показано, что при любом к > 3 для произвольного конечного базиса В функций й-значной логики константа ав из соотношения Дв(п) = авп + о(п) имеет вид ав = тву1, где тв является алгебраическим числом. Описан алгоритм нахождения по системе В многочлена с целыми коэффициентами, максимальным действительным корнем которого является число тв.

3. Установлено, что для любого к > 3 и произвольного бесконечного (т. е. содержащего функции, имеющие сколь угодно большое число существенных переменных) базиса В функций &-значной логики либо существует константа ув > 1, такая, что Вв(п) — ув при всех достаточно больших п, либо существует константа ¡Зв > 0, такая, что при п оо имеет место соотношение 1>в(тг) = ¡Зв п + о(1о§2 п).

Результаты 1 и 3 дают полную качественную картину асимптотического поведения функции Шеннона глубины над произвольным базисом функций &-значной логики при всех к > 3.

Теоретическая и практическая ценность.

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

Апробация работы.

Научные результаты и положения диссертационной работы докладывались и обсуждались на научных семинарах «Синтез и сложность управляющих систем» (2012 г.) и «Математические вопросы кибернетики» (2013 г.) под руководством профессора О. М. Касим-Заде в МГУ, на XI Международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ, 18-23 июня 2012 г.), на научной конференции «Ломоносовские чтения» (Москва, МГУ, апрель 2013 г.), на IX Молодежной научной школе по дискретной математике и ее приложениям (Москва, ИПМ им. М. В. Келдыша РАН, 16-21 сентября 2013 г.).

Публикации. Основное содержание диссертации опубликовано в 3 работах автора, список которых приведен в конце автореферата [1-3].

Структура и объем работы. Диссертационная работа состоит из Введения, двух глав, разделенных в совокупности на 9 параграфов, и списка использованной литературы из 65 наименований. Полный объем работы составляет 86 страниц. Нумерация теорем, лемм, следствий, свойств и

формул — двойная, состоящая из номера главы и номера внутри данной главы.

Содержание работы

Во Введении кратко излагается история вопроса и описываются основные результаты диссертации.

В главе 1 диссертации изучается поведение функции Шеннона глубины схем над произвольным конечным базисом функций ifc-значной логики. В §1.1 вводятся основные понятия и определения, формулируются основные результаты этой главы, заключающиеся в трех следующих теоремах.

Теорема 1.1. При любом натуральном к, к > 2, для произвольного конечного базиса В функций k-значной логики существует такал положительная константа ав, что при п -> оо выполняется соотношение27

DB{n) ~ авп.

Теорема 1.2. При любом натуральном к, к > 2, для произвольного конечного базиса В константа ав из соотношения DB{n) ~ авп имеет вид = (logft 7"в)-1, где тв является алгебраическим числом.

Теорема 1.3. При любом натуральном к, к > 2, существует алгоритм нахождения по произвольному конечному базису В функций k-значной логики многочлена с целыми коэффициентами, максимальным действительным корнем которого является число тв.

Говоря содержательно, теорема 1.1 для произвольного конечного базиса В функций &-значной логики устанавливает существование асимптотики функции Шеннона глубины вида DB(n) ~ авп, линейной по числу п переменных реализуемых функций, а теоремы 1.2 и 1.3 дают «эффективное» в некотором естественном смысле решение проблемы нахождения константы ав в указанной асимптотике: по теореме 1.2 эта константа выражается в «замкнутой форме» через логарифм от алгебраического числа тд, которое по теореме 1.3 задается как корень некоторого вычисляемого по базису В многочлена с целыми коэффициентами.

В §§1.2-1.3 приводится доказательство теоремы 1.1. Наметим основные шаги этого доказательства. Для любого конечного базиса В функций ¿-значной логики и произвольного натурального числа d вводится величина NB{d) как наибольшее число существенных переменных у функций,

27Как обычно, для последовательностей положительных чисел {а„} и {Ь„} асимптотическое равенство а(п) ~ Ь(п) означает, что lim f0- = 1.

допускающих над базисом В реализацию схемой глубины не более ± Устанавливается, что для любого конечного базиса В функций ¿-значной логики существует положительный предел

Иш

¿-юо а

Далее вводится константа ав, определеляемая равенством

^¿-юо а )

В §1.2 на основе мощностных соображений доказывается, что для любого е, е > 0, при всех достаточно больших п выполняется неравенство 1>в(п) > авп( 1 - е), причем доля функций ... ,хп), для которых ВвУ) < авп(1-е), стремится к 0 с ростом п. (Отметим, что с учетом этого теореме 1.1 можно придать даже более сильную форму — имеет место так называемый «эффект Шеннона»: почти все функции имеют почти одинаковую глубину, асимптотически равную значению функции Шеннона.) В §1.3 доказывается верхняя оценка функции Шеннона глубины

Дв(п) < авп + о(п),

где п -> оо. При доказательстве этой оценки используется некоторый аналог леммы О. Б. Лупанова об обобщенном разложении28.

Теорема 1.1 устанавливает лишь факт существования асимптотики указанного вида для функции Шеннона глубины над любым конечным базисом функций /с-значной логики. Возникает проблема нахождения по конечному базису В соответствующей константы ав из этой асимптотики. В §1.4 рассматривается ряд известных конечных базисов функций ^-значной логики, дающих конкретные примеры возможных асимптотик функций Шеннона глубины. Во всех указанных примерах константа ав в соответсвующей асимптотике имеет вид ав — (1оgkтв)~1, где тв является рациональным (и даже натуральным) числом. Далее, здесь же приводится пример конечного базиса В, для которого константа тв в представлении а в — тв)-1 является числом иррациональным. Последний пример указывает на принципиальное отличие й-эначных (к > 3) логик от двузначной: при к — 2 для любого конечного базиса В константа тв — натуральное число29. Теорема 1.2 показывает, что в общем случае для конечных базисов функций /с-зпачной логики число тв является алгебраическим.

28Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во Московского университета, 1984.

29Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 43-81.

Далее в §1.5 проводится доказательство теорем 1.2 и 1.3. Определяется объект, называемый Л-грамматикой, который по существу отличается от контекстно-свободной грамматики лишь отсутствием терминальных символов. Описывается алгоритм построения по произвольному конечному базису В функций й-значной логики некоторой Л-грамматики имек>-щей в некотором подходящем смысле хорошие свойства. Далее описывается алгоритм построения по получившейся Л-грамматике 1В многочлена с целыми коэффициентами, максимальным действительным корнем которого является число тв, фигурирующее в формулировке теоремы 1.2. Таким образом устанавливается справедливость утверждений теорем 1.2 и 1.3, дающих алгоритмическое решение проблемы нахождения по произвольному конечному базису В константы а в.

Глава 2 диссертации посвящена изучению поведения функции Шеннона глубины схем над произвольным бесконечным базисом функций й-значной логики. Основным результатом этой главы является следующее утверждение.

Теорема 1.4. При любом фиксированном к, к > 2, для любого бесконечного базиса В функций к-значной логики либо существует константа 7в > 1, такая, что Вв{п) = ув при всех достаточно больших п, либо существует константа /Зв > 0, такая, что при п оо имеет место соотношение Ов{п) ~ pв\ogin.

Сначала в §2.1 вводится понятие обобщенной р-степени базиса В. Для произвольного бесконечного базиса В и любого простого числа р определяется величина gdegpB, называемая обобщенной р-степенью базиса В и принимающая значения из расширенного множества натуральных чисел N и {оо} (подробное определение этого понятия и объяснение соответствующих обозначений см. в тексте диссертации). Устанавливается, что для любого бесконечного базиса В функций к-значной логики имеет место одна из двух взаимоисключающих возможностей: либо gdegqB = оо при любом простом д, либо существует единственное простое р, такое, что ё^р-В < оо. В первом случае базис В называется базисом бесконечной характеристики, во втором — базисом конечной характеристики. (В случае к = 2 введенное в диссертации понятие обобщенной р-степени базиса совпадает с известным понятием р-степени базиса функций двузначной логики30.)

Далее в §2.1 устанавливается, что для произвольного бесконечного ба-

30Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным базисом // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007. — № 1. — С. 18-21.

зиса В бесконечной характеристики при всех достаточно больших п выполняется равенство

DB{n) = iB,

где 7в — некоторая константа, зависящая от базиса В. В конце параграфа рассматриваются некоторые примеры базисов бесконечной характеристики. (Тривиальным примером такого базиса является бесконечный базис, состоящий из всех функций fc-значной логики.)

В §§2.2-2.3 исследуются бесконечные базисы конечной характеристики. Для произвольного бесконечного базиса В конечной характеристки вводится положительная константа кв как предел некоторой последовательности положительных чисел, зависящей от базиса В (подробнее см. в § 2.2). Сначала в §2.2 устанавливается нижняя оценка: доказывается, что для произвольного бесконечного базиса В конечной характеристики и любого є, є > 0, при всех достаточно больших п справедливо неравенство

DB(n) > («5і - є) 1 og2n.

В отличие от случая конечных базисов в случае бесконечных базисов конечной характеристики нижняя оценка устанавливается конструктивно: явно предъявляется последовательность функций fc-значной логики {/„} (где /„ зависит от тг переменных), удовлетворяющих при произвольном є,є > О, и всех достаточно больших п неравенству

DB{fn) > (квг - г) log2 п.

Далее в §2.3 доказывается верхняя оценка: устанавливается, что при п оо для произвольного бесконечного базиса В конечной характеристики выполняется соотношение

DB(n) < Kß1 log2 п + o(log2n).

Таким образом, устанавливается, что для любого бесконечного базиса В конечной характеристики выполняется соотношение

DB(n) ~ ßB log2 n,

где ßB = Кв1.

В §2.4 рассматриваются примеры бесконечных базисов конечной характеристики. В случае функций двузначной логики для любого бесконечного базиса В конечной характеристики асимптотика функции Шеннона

глубины может быть записана31 в виде £>в(п) ~ ]ogs п, где в (й > 2) — некоторое натуральное число, зависящее от базиса В. В §2.4 сначала для всякого к > 3 устанавливается существование бесконечных базисов функций &-значной логики с аналогичной асимптотикой функции Шеннона глубины при всех достаточно больших е. Далее приводится пример бесконечного базиса конечной характеристики, для которого функция Шеннона глубины не пред ставима в таком виде (в этом случае асимптотика функции Шеннона имеет вид йв[п) ~ к^п, где г — число иррациональное). Этот пример указывает на еще одно отличие &-эначных (при к > 3) логик от двузначной.

Отметим, что справедливость утверждений теорем 1.1-1.4 в случае двузначной логики вытекает из перечисленных ранее результатов других авторов. Случай к = 2 включен в формулировки теорем 1.1-1.4 лишь для полноты изложения. Результаты теорем 1.1 и 1.4 дают полную качественную картину асимптотического поведения функции Шеннона глубины над произвольным'базисом функций /с-значной логики при всех к > 2.

Благодарности

Автор выражает благодарность проф. О. М. Касим-Заде за постановку задач и постоянное внимание к работе.

Публикации автора по теме диссертации

1. Кочергин А. В. О глубине функций А;-значной логики в бесконечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. — 2011. — № 1. — С. 22-26.

2. Кочергин А. В. О глубине функций многозначной логики // Материалы XI Международного семинара аДискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, 18-23 июня 2012 г.). — М.: Изд-во механико-математического факультета МГУ, 2012. — С. 133-135.

3. Кочергин А. В. О глубине функций /с-значной логики в конечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. — 2013. — № 1. — С. 56-59.

Касим-Заде О. М. О глубине булевых функций над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Сер. 1. — 2007 — Т 14,

1. — С. 45-69.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж Ц о экз. Заказ № 50

ФГБОУ ВПО «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА»

На правах рукописи УДК 519.7

04201451673

Кочергин Алексей Вадимович О ГЛУБИНЕ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ 01.09 — дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук,

профессор О. М. Касим-Заде

Москва 2013

Оглавление

Введение 3

1. Случай конечных базисов 15

§ 1.1. Основные понятия. Постановка задачи.............15

§ 1.2. Нижняя оценка функции Шеннона глубины..........22

§ 1.3. Верхняя оценка функции Шеннона глубины..........26

§ 1.4. Примеры конечных базисов ...................38

§ 1.5. Нахождение асимптотики функции Шеннона глубины .... 40

2. Случай бесконечных базисов 57

§ 2.1. Базисы бесконечной характеристики..............57

§ 2.2. Базисы конечной характеристики. Нижняя оценка функции

Шеннона глубины.........................66

§ 2.3. Базисы конечной характеристики. Верхняя оценка функции

Шеннона глубины.........................71

§ 2.4. Примеры базисов конечной характеристики..........76

Список литературы 79

Введение

Настоящая работа относится к одному из важнейших направлений дискретной математики и математической кибернетики — теории синтеза и сложности управляющих систем. Согласно [49], основная задача синтеза управляющих систем в общем виде может быть описана таким образом. Имеется некоторое множество «простых» базисных элементов (например, проводящих контактов, формул, функциональных элементов, интегральных схем, подпрограмм и т. п.), реализующих некоторые функции. Известны правила построения из этих элементов более сложных объектов, называемых схемами. Также задан способ сопоставления схеме вычисляемой (реализуемой) ею функции. Задача заключается в нахождении (построении) для каждой функции схемы над заданным базисом, реализующей эту функцию. В такой постановке задача обычно имеет неоднозначное решение: одна и та же функция может быть реализована различными схемами, при этом каждая из схем, вообще говоря, имеет свои характеристики. Поэтому задачу построения схем естественно уточнить следующим образом: требуется построить для данной функции схему, которая была бы в некотором смысле наилучшей по своим характеристикам.

Возникает вопрос о том, каким образом измерять качество схемы. Этот вопрос, как правило, решается введением специальной численной характеристики схемы: меры сложности схем. В качестве меры сложности схем берется, например, число проводящих контактов, число элементов, вес (стоимость), глубина, задержка, площадь (объем), мощность, активность и др. (см., например, [58, 21, 29, 33, 13, 15, 2, 9]). Таким образом, ка-

ж дои схеме сопоставляется некоторое неотрицательное число, называемое сложностью этой схемы относительно заданной меры сложности. Считается, что чем меньше значение сложности, тем лучше схема (опять-таки относительно заданной меры). Следовательно, задачу можно переформулировать так: для каждой функции / из заданного множества требуется найти реализующую ее схему с минимально возможным значением сложности. Это минимальное значение называется сложностью функции.

В случае, когда множество базисных элементов конечно и всякая схема состоит из конечного числа элементов, у описанной задачи теоретически имеется тривиальное решение методом перебора всех схем определенной сложности. Однако практически им можно воспользоваться даже с применением современных вычислительных возможностей, как правило, только для малых значений сложности, так как с ростом числа элементов количество различных схем растет очень быстро. Подробнее см. [49].

Уточним постановку задачи. Пусть каждой схеме S над заданным базисом поставлено в соответствие неотрицательное число L(S) — сложность этой схеме. Для каждой функции / определяется ее сложность L(f) следующим образом L(f) = min L(S), где минимум берется по всем схемам S, реализующим функцию /. Задача состоит в построении для каждой рассматриваемой функции / схемы S, удовлетворяющей равенству L(/) = L(S). Однако такая задача, как правило, оказывается очень трудной. В связи с этим часто рассматривают задачу построения схем, в том или ином смысле близких к оптимальным (например, асиптотически оптимальных схем). Вводится функция L(F) = maxL(/), где максимум берется по всем функциям / из некоторого класса F (класс F предполается конечным и состоящим из функций, допускающих реалицию в заданном классе схем). Требуется найти метод синтеза схем, позволяющий для произвольной функции / из класса F, построить схему 5, которая реализует функцию / и для которой значение L(S) близко к величине L(F). Например, если Fn — класс всех функций fc-значной логики от п переменных,

L(S) — схемная сложность (число элементов) схем из функциональных элементов над фиксированным конечным функционально полным базисом (см. ниже), то для каждой функции / из класса Fn требуется построить схему 5, реализующую функцию /, для которой величина L(S) асимптотически не превосходит величины L(n) = L{Fn). Функцию L(n) часто называют функцией Шеннона в честь К. Э. Шеннона, который в 1949 г. предложил [58] такой подход при изучении задачи синтеза контактных схем.

Начиная со второй половины 1950-х годов О.Б. Лупановым были разработаны асимптотически оптимальные методы синтеза и получены асимптотически точные оценки сложности для многих важнейших классов управляющих систем: вентильных схем глубины 2 и контактно-вентильных схем [21], контактных схем [23], схем из функциональных элементов над произвольным конечным базисом булевых функций [22], формул над произвольным конечным базисом булевых функций [24] и др. [26, 27, 28, 29, 32].

Впоследствии для различных классов функций, различных видов управляющих систем и различных мер сложности многими авторами были установлены асимптотически точные (или точные по порядку роста) оценки функций Шеннона (см., например, [48, 36, 47, 55, 16, 14, 6, 8, 45]).

В данной работе рассматривается реализация функций в одном из наиболее важных модельных классов управляющих систем — классе схем из функциональных элементов (см, например, [27]).

Будем рассматривать реализацию функции fc-значной логики (к > 2) схемами из функциональных элементов над произвольным базисом. Здесь и далее под базисом понимается произвольное функционально полное множество функций £;-значной логики, т. е. такое, что суперпозициями функций этого множества можно реализовать любую функцию fc-значной логики. Базис называется бесконечным, если для любого натурального числа га существует функция из этого базиса, существенно зависящая более чем

от т переменных. В противном случае базис называется конечным. Вообще говоря, при этом формально число функций в конечном базисе может быть бесконечным. Однако, по-существу, конечный базис с точностью до введения и изъятия несущественных переменных содержит лишь конечное число различных функций. Далее будем считать, что конечный базис задается как конечное множество функций /г-значной логики.

Изучаемая в работе мера сложности — глубина схемы. Под глубиной схемы понимается максимальное число элементов в ориентированных цепях, ведущих от какого-либо из входов схемы к ее выходу. Глубиной функции /г-значной логики / над базисом В называется минимальная глубина схем, реализующих функцию / над базисом В. В работе для произвольного базиса В исследуется поведение функции Шеннона глубины DB(n), характеризующей максимальную глубину функций от п переменных и определяемой равенством Db(ti) = тахДв(/), где максимум берется по всем функциям fc-значной логики /, зависящим от п переменных.

С содержательной точки зрения рассматриваемое в данной работе понятие глубины связано с представлениями о задержке (или времени работы) схемы. Подробнее об этих понятиях и их взаимосвязях см., например, [29, 44]. Время работы является одной из наиболее существенных характеристик современных вычислительных устройств.

Отметим, что в ряде работ [25, 30, 53, 20] под «глубиной» (или «глубиной альтернирования») схемы понимается максимальное число перемен типов элементов в цепях, ведущих от входов схемы к ее выходу. Это понятие существенно отличается от изучаемого в данной работе, и в данной работе не рассматривается.

Отметим также, что в данной работе исследуется глубина функций к-значной логики только над функционально полными системами. Однако глубина функций изучалась и над функционально неполными системами функций двузначной и fc-значной (к > 3) логики (см., например, работы А. Б. Угольникова [41, 42], А. А. Андреева [1]). В ряде работ также

получены соотношения, связывающие глубину и формульную сложность функций (см., например, работы Ф. М. Спиры [61], В. М. Храпченко [43], И. Вегенера [62], А. Б. Угольникова [40], М. Е. Рагаца [57], Р. Ф. Сафи-на [38]). В данной работе в качестве меры сложности рассматривается только глубина схем, а ее взаимосвязи с другими мерами сложности, как и сами другие меры сложности, не рассматриваются.

В 1970 г. О. Б. Лупановым [29] было установлено, что в случае двузначной логики (к = 2) для любого конечного базиса В выполняется соотношение

Е>в(п) ~ Сп,

где С = (к^2га)-1, а га — максимальное число существенных переменных у функций из базиса В. (Символ «~» обозначает асимптотическое равенство; определения асимптотического равенства и других асимптотических соотношений приведены в §1.1.) В случае классического базиса В0 двузначной логики, состоящего из конъюнкции двух переменных, дизъюнкции двух переменных и отрицания, эта оценка для функции Шеннона глубины 1>в0(п) уточнялась в работах Ф. М. Спиры [60], У. Ф. Мак-Колла и М. С. Патерсона [54], С. Б. Гашкова [5], С. А. Ложкина [18]. Наиболее точная верхняя оценка была получена С. А. Ложкиным в работе [18], в которой была установлена справедливость следующего неравенства:

Dвo{n) < \п - 1о§2 п + Ь(п)~1, где Ъ{п) = о(1) при п —> оо. Нижняя оценка вида

О во (га) > ~ 1°§2 п + а(п)1 >

где а(п) = о(1) при п —> оо, вытекает из стандартных мощностных соображений (см., например, [5]).

В 1996 г. С. А. Ложкиным [19] было показано, что для произвольного конечного базиса В функций двузначной логики справедливо равенство

Ов{п) = С{п - 1о§2 п) + с(п),

где c(n) = 0(1).

Результатов о поведении функции Шеннона глубины в случае бесконечных базисов функций двузначной логики до появления работ [10, 11, 12] было известно немного. Асимптотики роста (или хотя бы порядки роста) были найдены только для небольшого числа базисов. При этом во всех известных примерах функция Шеннона либо была ограничена сверху константой (в частности, для базиса, состоящего из всех функций двузначной логики, или для базиса функций двузначной логики, состоящего из всех пороговых функций [31]), либо росла по порядку как log2n (например, для базиса функций двузначной логики, состоящего из конъюнкции двух переменных и всех линейных функций — фактически это следует из результатов работы [17]).

В 2007 г. О. М. Касим-Заде [10] было установлено, что для любого бесконечного базиса В функций двузначной логики порядок роста функции Шеннона глубины DB(n) при п —У оо равен либо 1, либо log2n. В работах [11, 12] О. М. Касим-Заде этот результат усилил: было показано, что для любого бесконечного базиса В функций двузначной логики либо существует константа а, 1 < а < б, такая, что DB(n) = а при всех достаточно больших п, либо существуют целочисленная константа Ъ > 2, такая, что |"logbn] < -Dß(n) < flogen] + 5 при всех п.

При к > 3 задача о поведении функции Шеннона глубины функций fc-значной логики при реализации схемами из функциональных элементов до последнего времени оставалась практически неисследованной. Можно указать, по-видимому, только на некоторые тривиальные результаты, являющиеся очевидными обобщениями на А:-значные логики случая двузначной логики. Например, для конечного базиса В*, состоящего из всех функций fc-значной логики от двух переменных, легко показать, что порядок роста функции Шеннона глубины DB* (п) при п —у оо равен п. Отсюда очевидным образом следует, что и для любого конечного базиса В функций /с-значной логики функция Шеннона глубины DB{n) при п —> оо по

порядку растет как п. В то же время вопрос о точном виде асимптотики функции Шеннона глубины функций А;-значной логики при к > 3 над произвольным конечным базисом до самого последнего времени, по-видимому, оставался открытым. В случае бесконечных базисов при к > 3 оставался открытым даже вопрос о возможных порядках роста функции Шеннона глубины, в частности, оставалось неизвестным, конечно или бесконечно их число.

Основной целью данной диссертации является изучение асимптотического поведения функции Шеннона глубины схем из функциональных элементов над произвольным базисом функций &-значной логики при всех к > 3 и получение асимптотических выражений для указанной функции Шеннона.

Диссертация состоит из Введения, двух глав, разделенных в совокупности на 9 параграфов, и списка литературы. Основные утверждения работы формулируются в виде теорем. Утверждения нумеруются парой чисел, где первое число обозначает номер главы, а второе — номер утверждения внутри главы. Во Введении принята отдельная нумерация теорем; после номера каждой теоремы в скобках следует номер, который соответствующее утверждение имеет в тексте диссертации.

В первой главе диссертации изучается поведение функции Шеннона глубины схем над произвольным конечным базисом функций /с-значной логики. В начале первой главы (§1.1) вводятся основные понятия и определения, формулируются основные результаты этой главы, заключающиеся в трех следующих теоремах.

Теорема 1 (1.1). При любом натуральном к, к > 2, для произвольного конечного базиса В функций к-значной логики существует такая положительная константа ав, что при п —У оо выполняется соотношение

Ов(п) ~ авп.

Теорема 2 (1.2). При любом натуральном к, к > 2, для произвольного

конечного базиса В константа ав из соотношения Дв(?г) ~ авп имеет

Теорема 3 (1.3). При любом натуральном к, к > 2, существует алгоритм нахождения по произвольному конечному базису В функций к-значной логики многочлена с целыми коэффициентами, максимальным действительным корнем которого является число Тв-

Говоря содержательно, теорема 1 для произвольного конечного базиса В функций &-значной логики устанавливает существование асимптотики функции Шеннона глубины вида Ов(п) ~ а^п, линейной по числу п переменных реализуемых функций, а теоремы 2 и 3 дают «эффективное» в некотором естественном смысле решение проблемы нахождения константы ав в указанной асимптотике: по теореме 2 эта константа выражается в «замкнутой форме» через логарифм от алгебраического числа тв, которое по теореме 3 задается как корень некоторого вычисляемого по базису В многочлена с целыми коэффициентами.

В §§1.2-1.3 приводится доказательство теоремы 1. Наметим основные шаги этого доказательства. Для любого конечного базиса В функций к-значной логики и произвольного натурального числа с? вводится величина А^в(^) как наибольшее число существенных переменных у функций, допускающих над базисом В реализацию схемой глубины не более (1. Устанавливается, что для любого конечного базиса В функций /с-значной логики существует положительный предел

В §1.2 на основе мощностных соображений доказывается, что для любого е, е > 0, при всех достаточно больших п выполняется неравенство Вв(п) > авп( 1 — е), причем доля функций /(#1,..., жп), для которых

вид ав = (к^тв) 1, где тв является алгебраическим числом.

¿—юо д,

Далее вводится константа а в, определеляемая равенством

Ищ

Ав(/) < &вп( 1 — е), стремится к 0 с ростом п. (Отметим, что с учетом этого теореме 1 можно придать даже более сильную форму — имеет место так называемый «эффект Шеннона»: почти все функции имеют почти одинаковую глубину, асимптотически равную значению функции Шеннона.) В §1.3 доказывается верхняя оценка функции Шеннона глубины

£>я(п) < авп + о(п),

где п —У оо. При доказательстве этой оценки используется некоторый аналог леммы О. Б. Лупанова об обобщенном разложении из [33].

Теорема 1 устанавливает лишь факт существования асимптотики указанного вида для функции Шеннона глубины над любым конечным базисом функций А;-значной логики. Возникает проблема нахождения по конечному базису В соответствующей константы а в из этой асимптотики. В §1.4 рассматривается ряд хорошо известных конечных базисов функций &-значной логики, дающих конкретные примеры возможных асимптотик функций Шеннона глубины. Во всех указанных примерах константа ав в соответсвующей асимптотике имеет вид а в = (logk тв)~г, где тв является рациональным (и даже натуральным) числом. Далее, здесь же приводится пример конечного базиса В, для которого константа тв в представлении ав = (logьТв)~1 является числом иррациональным. Последний пример указывает на принципиальное отличие /с-значных (к > 3) логик от двузначной: при к — 2 для любого конечного базиса В константа тв — натуральное число [29]. Теорема 2 показывает, что в общем случае для к