Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 3

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

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 104 >> Следующая

Второе издание книги отличается от первого наличием дополнительной части по комбинаторному анализу, некоторой переработкой остальных частей и устранением всех аамеченных погрешностей. В этой работе автору помогли замечания многих математиков, которым автор весьма призпателен. Особую благодарность автор выражает редакторам первого и второго изданий Б, П. Липатову и В. М. Храпченко, проделавшим большую работу по улучшению изложения материала.
С. В, Яблонский
ЧАСТЬ I
ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Теория функциональных систем занимается изучением функций, описывающих работу дискретных преобразователей. Здесь рассматриваются важнейшие классы функций: булевы функции, функции ймзначной логики, автоматные (о.-д.) функции и вычислимые функции. С каждым из этих классов естественным образом связываются операции, позволяющие из одних функций данного класса строить другие функции этого же класса. Такими операциями являются операция суперпозиции, операция обратной связи, операция примитивной рекурсии и ji-операцня. В результате этого мы приходим к функциональным системам с операциями — некоторым классам алгебр. Данные объекты в книге расположены так, что каждый последующий объект является «расширением» предыдущего. Это позволяет переносить результаты с простых систем на более сложные. При этом обращается внимание на аналогии и на существенные различия.
Роль теории функциональных систем в дискретной математике можно сравнить с ролью математического анализа в непрерывной математике.
Глава 1
АЛГЕБРА ЛОГИКИ
§ 1, Функции алгебры логики
Пусть U -= {и1( иг, ..., ит, ..— исходный алфавит переменных (аргументов). Будем рассматривать функции и igi • * * 1 п ) (uiv ф при v ф ц), аргумен-
ты которых определены на множестве Es =» {0, 1), и такие, что /(аь аз, an)eEz, когда ai^E2 (i** 1, 2,
..., п). Эти функции будем называть функциями алгебры логики или булевыми функциями. Чтобы избежать
til ‘I I (T'VItliHЦ( 111 \.ЧI.ЦЫI' ППГ.ТКМЫ С ОПЕРАЦИЯМИ
ецьыплч fiiHiiiHii'H'imit для индексов переменных, мы будем уши роблнть и качестве метаобозначений (обозначения дли произвольных символов алфавита U) символы
л, у, s л также эти символы с индексами. Таким
оГфтюм, запись f(xu х2, ..гп) понимается как запись функции, зависящей от произвольных фиксированных аргументов щ1, щ2, . .щп, где при v#=n.
Таблица 1
*1- ХТ1— 1 *п /(*!. ** Хп—1» Хп)
0 . . 0 0 /(0 , .. .. 0, 0)
0- . . 0 1 /(0, .. 0, 1)
0 . . 1 0 /(0, .. и 0)
1 . .. 1 1 /(1, .. м 1. 1)
На определения функции /(ж,, т2, ..хп) следует, чиї для во задания .достаточно указать, какое значение функции соответствует каждому из наборов значений н|ну Минтон, т. е. выписать таблицу (см. табл. 1), Легко вицотк, что п переменных принимают 2П различных зна-чпинП. Для удобства мы употребляем стандартное расположение наборов: если набор рассматривать как запись числа в двоичном исчислении, то расположение наборов соответствует естественному порядку следования чнгвд О, 1, ..., 271 — І. Далее мы видим, что каждая функция /(,Ги Яи, ..хп) определяет отображение
Е2х Е2х ... X Е2 -> Е2.
п раз
Поэтому естественно интерпретировать символ / как символ, обозначающий это отображение, а хи л’2,_________, хп —
к«к названия столбцов. В этом случае функции
%2і • • Хц) , $ (Уі, У г, > ? ?) У ті)
будут задавать одно и то же отображение, и их таблицы будут отличаться только, быть может, названиями столбцов. Обозначим через Р2 систему всех функций алгебры логики над алфавитом {7, содержащую также константы 0 и 1.
Если зафиксировать п переменных хи х2, ..., хп, ло различные таблицы будут отличаться лишь значениями
ГЛ. I. АЛГЕБРА ЛОГИКИ
11
правого столбца. Поэтому справедливо следующее утверждение.
Теорема 1. Число р2(п) всех функций из Р2, зависящих от п переменных хи х2, ..хп, равно 22П-
Здесь следует обратить внимание на два обстоятельства.
1. Число функций алгебры логики, зависящих от заданных п аргументов, конечно. Поэтому, если нужно выяснить, обладают ли функции из этого конечного множества каким-либо свойством, достаточно осуществить просмотр (или, как говорят, «перебор») функций из данного множества. Однако числа рз(я) с ростом п быстро растут:
рг(1) = 4, р,(2)= 10, ра(3) = 256, ра(4) = 65536, ...
Следовательно, уже при сравнительно небольших значениях п (п > 6) перебор становится практически невозможным даже с использованием вычислительной техники.
2. С ростом числа аргументов таблица, задающая функцию, сильно усложняется. Так, например, уже при не очень большом числе аргументов, скажем при п — 10, таблица становится громоздкой (имеет 1024 строки), а прп п = 20 — практически необозримой.
Введенное выше понятие функции несовершенно, поскольку оно не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа аргументов. Для устранения этого недостатка введем следующее определение.
Определение. Функция f(xu . . Xi-U Х{, Xi+u • ? ? ..., хф) из Р2 зависит существенным, образом от аргумента Xi, если существуют такие значения а,, ..., cti-i, ai+u ..., а« переменных xlt ..., Xi~,, xi+1, ..., хп, что
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed