В.П. Воронин - Дополнительные главы дискретной математики (1127085)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиКафедра Математической КибернетикиД ОПОЛНИТЕЛЬНЫЕ ГЛАВЫДИСКРЕТНОЙ МАТЕМАТИКИлектор — старший преподаватель В. П. Воронинсоставитель — А. Д. ПоспеловМосква — 2002Содержание1 КомбинаторикаБинарное отношение . . . . . .

. . . . . . . . . . . . . . . . .1.1 Простейшие комбинаторные числа . . . . . . . . . . . . . . .Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . .Принцип включения и исключения . . . . . . . . . . . . . . .Перестановки с ограничениями .

. . . . . . . . . . . . . . . .Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 Производящие функции . . . . . . . . . . . . . . . . . . . . .Разбиения множества . . . . . . . . . . . . . .

. . . . . . . .Рекуррентные соотношения и производящие функции . . . .Основные свойства обычных производящих функций . . . .Основные преобразования обычных производящих функцийПримеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . .

. . . . . . . . . . . . . . . . .1.3 Простейшие перечислительные задачи . . . . . . . . . . . .Вводные замечания . . . . . . . . . . . . . . . . . . . . . . .Основные леммы . . . . . . . . . . . . . . . . . . . . . . . . .Теорема Пойа . . . . . . . . . . . . . . . . . . . . . . . . . .Примеры .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .1.4 Частично упорядоченные множества . . . . . . . . . . . . . .Основные понятия . . . . . . . . . . . . . . . . . . . . . . . .Цепи Анселя . . . . . . . . . .

. . . . . . . . . . . . . . . . .Алгебры инцидентности . . . . . . . . . . . . . . . . . . . . .Решетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .............................................................................................................224578111618182227282933343435373842424246515460612 Конечнозначные логики2.1 Функции конечнозначной логики . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Реализация функций формулами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Первая и вторая формы . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Операция замыкания, свойства замыкания, замкнутые классы . . . . . . . . . . . . . . . . . . . . .Полные системы, примеры полных систем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Теорема о полноте системы Поста .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Функция Вебба . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Теоремы о функциональной полноте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Теорема об алгоритмической разрешимости проблемы распознавания полноты в k-значной логикеТеорема Кузнецова о функциональной полноте . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Существенные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Леммы о существенных функциях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Теоремы о существенных функциях . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .2.4 Особенности многозначных логик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Представление функции k-значной логики полиномами . . . . . . . . . . . . . . . . . . . . . . . . .Теоремы о замкнутых классах в Pk при k > 3 . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................................................................626262646465687070717677777778788081828383838486.......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................2ГЛАВА 1.

КОМБИНАТОРИКАГлава 1КомбинаторикаОсновным объектом изучения комбинаторики является как правило конечное (хотя, возможно, и счетное) множество,из элементов которого составляются различные комбинаторные конфигурации. Основными вопросами при этом являются существование требуемых конфигураций, алгоритмы их построения, оптимизация алгоритмов (если таковыесуществуют), а также задачи перечислительного характера (например, количество конфигураций с требуемыми свойствами).Одним из наиболее популярных примеров комбинаторной постановки может служить задача о магическом квадрате. Она ставится следующим образом: для данного натурального n расположить числа от 1 до n2 в целочисленныхточках квадрата плоскости Oxy : 1 6 x 6 n, 1 6 y 6 n так, чтобы сумма всех чисел, расположенных в любом столбце,была равна сумме всех чисел, расположенных в любой строке и равнялась сумме всех чисел, стоящих на каждой издиагоналей.

К положительным достижениям в решении этой задачи относится, например, факт существования алгоритма, строящего магический квадрат для любого заданного n. В то же время открытым остается вопрос о количестверазличных магических квадратов для n > 5. Примером магического квадрата для n = 3 может выступать следующий:29475361 .8Другим известным примером является задача о шести офицерах, которая ставится следующим образом: имеетсяшесть полков, в каждом полку имеется шесть офицеров, причем все имеют разные звания.

Вопрос заключается в том,возможно ли расположить всех этих офицеров в квадрате 6 × 6 так, чтобы на любой линии стояли офицеры из разныхполков и с разными званиями. Задача обобщается на случай n = 4k + 2 полков и званий. Доказано, что при k = 1решения не существует, а при k > 2 решение имеется.Бинарное отношение.Определение 1.0.1. Декартовым произведением множеств X и Y называется множествоX ×Y = {(x, y) | x ∈ X, y ∈ Y }.Определение 1.0.2. Любое подмножество декартова произведения ρ ⊆ X ×Y называется бинарным отношением.Примерами бинарного отношения могут служить равенство x = y, предшествование x 6 y и другие. Областью определения бинарного отношения ρ называется множествоDρ = {x ∈ X| ∃ (x, y) ∈ ρ}.Областью значений бинарного отношения ρ называется множествоRρ = {y ∈ Y | ∃ (x, y) ∈ ρ}.Из определения следует, что пустое множество ∅ также считается бинарным отношением.Бинарное отношение может задаваться также в виде прямоугольной (вообще говоря, бесконечной) 0, 1-матрицы:ij...· · · 1 · · ·...

0...n×mгде n — мощность множества X, а m — мощность множества Y могут, вообще говоря, равняться счетной бесконечности.Считается, что все элементы каждого из множеств X и Y пронумерованы натуральными числами. Элемент матрицы синдексом (i, j) равняется единице тогда и только тогда, когда пара (xi , y j ) ∈ ρ, где xi — элемент из X, занумерованныйчислом i, а y j — элемент из Y , занумерованный числом j; и равняется нулю в противном случае.3Бинарное отношение можно задать в виде двудольного орграфа:`` i` H` ` ` `HCj`` CW` ` H`` Hj`X`Yпри этом дуга из элемента из X с номером i идет к элементу из Y с номером j тогда и только тогда, когда (xi , y j ) ∈ ρ.Такое задание бинарного отношения позволяет рассматривать его как многозначное отображение.Определение 1.0.3.

Обратным бинарным отношением к ρ называется бинарное отношениеρ −1 = {(y, x) | (x, y) ∈ ρ} .Определение 1.0.4. Композицией бинарных отношений ρ1 и ρ2 называется бинарное отношениеρ = ρ2 ◦ ρ1 = {(x, z) | ∃y : (x, y) ∈ ρ1 , (y, z) ∈ ρ2 } .Очевидны простейшие свойства этих операций:ρ −1и−1=ρ(ρ2 ◦ ρ1 )−1 = ρ1−1 ◦ ρ2−1 .В дальнейшем будем рассматривать частный случай бинарного отношения — X = Y — бинарное отношение на декартовом квадрате. Введем для него следующие аксиомы.1.

Аксиома рефлексивности: для любого x ∈ X выполняется xρ x. Иными словами в матрице, задающей это бинарное отношение, на диагонали стоят единицы.2. Аксиома симметричности: для любых x, y ∈ X выполняется xρ y ⇒ yρ x. Иными словами, матрица, задающая этобинарное отношение, является симметрической.3. Аксиома транзитивности: для любых x, y, z ∈ X выполняется xρ y & yρ z ⇒ xρ z.4.

Аксиома антисимметричности: для любых x, y ∈ X выполняется xρ y & yρ x ⇒ x = y.Определение 1.0.5. Аксиомы 1, 2 и 3 определяют отношение эквивалентности. Такое отношение разбивает множество X, на котором оно задано, на классы эквивалентности, множество которых в свою очередь называется фактормножеством.Часто в комбинаторных постановках требуется узнать по заданному основному множеству и отношению эквивалентности на нем число классов эквивалентности. Отношение эквивалентности можно задавать группой перестановок. Вэтом случае возможен вопрос о числе элементов в множестве по известной группе перестановок.Определение 1.0.6.

Аксиомы 1, 3 и 4 определяют бинарное отношение частичного порядка. Примером может.служить упорядочение множества натуральных чисел по делимости: y | x или x..y означает, что y является делителемчисла x. Множество с заданным на нем частичным порядком называется частично упорядоченным.Частично упорядоченное по делимости множество натуральных чисел обозначается (N, |). Бинарные отношениячастичного порядка удобно изображать с помощью диаграмм Хассе.

Диаграмма Хассе представляет собой ориентированный ациклический граф, множеством вершин которого является исходное множество, а дуга между вершинами xи y рисуется тогда и только тогда, когда xρ y и @z : xρ z & zρ y. Например, частичный порядок наборов из нулей и единиц,определяющий монотонность функций алгебры логики, будет выглядеть на диаграмме Хассе следующим образом:(111)6@I@@@ (011)(110)(101)6I@@6I@@@@@(100)(010) @ (001)I@6@@@(000)4ГЛАВА 1. КОМБИНАТОРИКАВ некоторых случаях можно обойтись без дуг, располагая элементы множества по ярусам. Так, например, вышеописанное частично упорядоченное множество (N, |) можно изобразить так:``8 ` 12 ` 30 `L\ L\L\L \4 ` 6 ` 9 ` 10L` 15\` , ,, , ,, , , , , ` 7 `` 3 ,` 5 `2,l \ Ll \ Ll \Ll\Lll\L`1````квадраты простых, простое·простое``простыекубы простых, простое2 ·простое,простое·простое·простоеединицаТакже в случае X = Y граф, описывающий частично упорядоченное множество, не обязательно будет двудольным иможет выглядеть по-другому:``````По индукции можно определить также n-арные отношения.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги