С.В. Яблонский - Введение в дискретную математику, страница 2

Предлагаемые к публикации в серии «Высшая математика» избранные учебники по математике реализуют указанный выше подход. Они написаны в основном профессорами Московского государственного университета им. М.В. Ломоносова. Книга С.В. Яблонского «Введение в дискретную математику» является учебным пособием по основному курсу дискретной математики, читающемуся на факультете вычислительной математвки и кибернетики и механико- математическом факультете Московского государственного университета им. М.В. Ломоносова. Она посвящена нгсзп ' иччгс области математики, бурно развивающейся в последние годы и ставшей сердцевиной современной математической кибернетики.

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

В данной серии уже изданы учебники Г.И. Архипова, В.А. Садовничего, В.Н. Чубарикова «Лекции по математическому анализу», И.М. Виноградова «Элементы высшей математики (Аналитическая геометрия. Дифференциальное исчисление. Основы теории чисел)», И.И. Привалова «Введение в теорию функций комплексного переменного», В.А. Садо вничего «Теория операторов», С.Б.

Гашкова, В.Н. Чубарикова «Арифметика. Алгоритмы. Сложность вычислений», В.И. Нечаева «Элементы криптографии (основы теории защиты информации)»„ И.А. Виноградовой, С.Н. Олехника, В.А. Садовничего «Задачи и упражнения по математическому анализу» (тома 1 и 2), Н.С. Бахвалова, А.В. Лапина, Е.В. Чижонкова «Численные методы в задачах и упражнениях». Надеюсь, что данные книги положат начало новой серии базовых учебников по высшей математике для вузов с повьппенным уровнем математической подготовки. Кроме практической ценности эта серия призвана подвести некоторые итоги работы российских ученых и педагогов-математиков по созданию базовых учебников по математике на рубеже второго и третьего тысячелетий.

Серия не ограничивается указанными книгами. В дальнейшем предполагается продолжить отбор и издание как современных, так и классических учебников, которые отвечают изложенной выше концепции, не потеряли своей новизны и актуальности и пользуются заслуженной популярностью и авторитетом у студентов и педагогов. Академик Российской академии наук В.А. Садовничий ЧАСТЬ ( ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ Теория функциональных систем занимается научением функций, описывающих работу дискретных преобразователей. Здесь рассматриваются важнейшие классы функций: булевы функции, функции )г-анечкой логики, автоматные (о.-д.) функции н вычислимые функции.

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

Данные объекты в книге расположены так, что каждый последующий объект является «расширением» предыдущего. Это позволяет переносить ревультаты с простых систем на более сложные. При этом обращается внимание на аналогии и на существвнныв различия. Роль теории функциональных систем в дискретной математике можно сравнить с ролью математического анализа в непрерывной математике. Глава т АЛГЕБРА ЛОГИКИ 3 $. Функции алгебры логики Пусть У = (и„и„..., и, ..) — исходный алфавит переменных (аргументов) . Будем рассматривать функции ~(и... и;„..., и«„) (и1ъ~ и;„при т «ь и), аргументы которых определены на множестве Е, (О, (), и такие, что 1(ан аи ..., а„)жЕи когда а~жЕ» (( (, 2..., ..., п).

Эти функцни будем называть функциями аггебРы логики илп булевыми функциаии, Чтобы избежать 10 Ч. 1. ФУНКЦИОНАЛЪНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ сложяых обозначений для индексов переменных, мы будем употреблять в качестве метаобозначений (обозначений для произвольных символов алфавита с)) символы х, у, з, ..., а также эти символы с индексами. Таким образом, запись 1(хи х„..., хв) понимается как запись функции, зависящей от произвольных фиксированных аРгумэнтов Н11в Ивы ° ° ° в И1„, ГДЕ Ц;, т= И1В ПРН У Ф )А. Таблица 1 Г(Л1 в Ла 11 Ла) Л1 -' Ла-1 Ла 1(0, ..., О, О) у(О, ..., О, 1) т(0, ..., в, 0) 0 ...

0 0 О ... О в 0 ... 1 0 Поэтому естественно интерпретировать символ ~ как символ, обозначающий это отображение, а х„х„..., х„— как названия столбцов. В этом случае функции 1(хвв Яав ° ° в Яв), 1(У» Ув ° °, Ув) будут задавать одно и то же отображение, и их таблицы будут отличаться только, быть может, названиями столбцов. Обозначим через Р, систему всех функций алгебры логики над алфавитом У, содержащую также константы О и 1. Если зафиксировать п переменных х„х„..., е„, то различные таблицы будут отличаться лишь значениями Из определения функции 1(хо х„..., хв) следует, что для ее задания достаточно указать, какое значение функции соответствует каждому из наборов значений аргументов, т.

е. выписать таблицу (см. табл. 1). Легко видеть, что п переменных принимают 2" различных аначений. Для удобства мы употребляем стандартное расположение наборов: если набор рассматривать как запись числа в двоичном исчислении, то расположение наборов соответствует естественному порядку следования чисел О, 1, ..., 2" — 1. Далее мы видим, что каждая функция 1(хв ха °, хв) определяет отображение Еа Х Еа Х ...

Х Еа-в. Е,. а рав ГЛ. Ь, АЛГЕБРА ЛОГИКИ правого столбца. Поэтому справедливо следующее утверждение. Теорема 1. Число ра(п) всех функйий из Р,, вависящ х от и переменных х„х„..., х„, равно 2 ". Здесь следует обратить внимание на два обстоятельства. 1. Число функций алгебры логики, зависящих от заданных п аргументов, конечно. Поэтому, если нужно выяснить, обладают ли функции из этого конечного множества каким-либо свойством, достаточно осуществить просмотр (или, как говорят, впереборэ) функций из данного множества. Однако числа р,(п) с ростом п быстро растут: ра(1) 4< ра(2) = 16, ра(3) = 256< ра(4) = 65536< Следовательно, уже при сравнительно небольшпх значениях и (и > 6) перебор становится практически невозможным даже с использованием вычислительной техники.

2. С ростом числа аргументов таблица, аадающая функцию, сильно усложняется. Так, например, уже прп не очень большом числе аргументов, скажем при и 10, таблица становится громоздкой (имеет 1024 строки), а прп и 20 — практически необозримой. Введенное выше понятие функции несовершенно, поскольку оно не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа аргументов. Для устранения этого недостатка введем следующее определение.

Определение. Функция ~(х„..., х«, х<, х<+„... ..., х„) из Р, зависит существенныль образом от аргумента х<, если существуют такие значения а„..., а< „ а„„..., а„переменных х„..., х, „х,+„..., х„, что Дан..., а< „О, сь „, ..., а.) вь /(ан ..., а«, 1, а<+<, ... а,). В этом случае переменная х< называется существенной. Если х, не является существенпой переменной, то она называется несущественной илн фиктивной. Пусть для функции /(х„..., х.) переменая х, является фиктивной.

Возьмем таблицу для функции Г(х„... ..., х„) и по ней построим новую таблицу путем вы- 12 ч. 1. Функцпонлльные системы с ОпеРАциями черкиванпя всех строк вида (сс„..., сс~ „1, а „, ..., и.) п вычеркивания столбца для аргумента хь Полученная таблица будет определять некотору1о функцию у(х„... ..., х, „х„.„..., х„). Будем говорить, что функция У(хо ..., х, „х;„, ..., х„) полУчена из 1(хо ..., х„) путел1 удаления фиктивной переменной хь а также, что фупкция ~(хи ..., х„) получается пз у(х„..., х, „ х,+„..., х„) путем введения фиктивной переменной х. Определение. Функции (, и 1, называются равньыщ, если функцию ~, можно получить из 1, путем добавления и изъятия фиктивных аргументов.

В дальнейшем всюду функции рассматриваются с точностью до фиктивных переменных, т. е. Мы считаем, что если ладана функция ~„то аадана и любая равная ей функция ~,. Это накладывает некоторые естественные ограничения на классы функций, которые будут здесь рассматриваться. В частности, класс функций, обладающих определенными свойствами, будет рассматриваться только в том случае, если зтп своиства инвариантны относительно операций введения и удаления фиктпвных переменных. Существуют два типа функций, которые не имеют существенных переменных: функции первого типа тождественно равны О, а второго — 1. Ввиду етого целесообразно включить в нашп рассмотрения константы О и (рассматривая их как функции от пустого множества переменных) .

Для иллюстрации сказанного рассмотрим два класса симметрических функций. О и р е д е л е н и е. Булева функция ~(х„..., х„) навывается симметрической относительно переменных х„..., х„(2 < /с ~ и), если для любой подстановки ( ') $...ь~ ) имеет место равенство 1," ° ) / (х„..., хь, хА+„..., х„) = ~(х>,, ..., хло хе+„..., х„). Аналогично вводится понятие функцпп, симметрической относительно произвольных переменных х1,, ..., х, Очевидно, что функции, тождественно равные константам О и 1, явля1отся симметрнческимп относительно любой совокупности своих переменных.

Пример 1. а) Класс функций, симметрпческпх относительно всех своих переменных. Это свойство не яв- Гл, ь Алгевва логнк11 ляется инварпантным относительно операции введения несущественной переменной, так как любая функция, отличная от константы и обладающая этим свойством, существенно зависит от всех своих переменных (зависимость хотя бы от одной переменной следует из того, что функция принимает оба значения О и 1, а зависимость от всех переменных — из симметрии). Такие классы дальше рассматриваться не будут. б) Класс функций, симметрических относительно всех своих существенных переменных.