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

Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиКафедра Математической КибернетикиД ОПОЛНИТЕЛЬНЫЕ ГЛАВЫДИСКРЕТНОЙ МАТЕМАТИКИлектор — старший преподаватель В. П. Воронинсоставитель — А. Д. ПоспеловМосква — 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-арные отношения.