Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.12.2023

Просмотров: 541

Скачиваний: 6

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

б) отношение перпендикулярности двух прямых?28. Доказать, что отношение {((x1, y1), (x2, y2)) | x2 1+ y2 1= x2 2+ y2 2} являет- ся отношением эквивалентности на множестве R2. Определить классы этой эквивалентности.29. Доказать, что отношение {(a, b) | (a − b) — рациональное число} явля- ется отношением эквивалентности на множестве вещественных чисел.30. Пусть на множестве ω определено отношение 6, задаваемое следую- щим правилом:m 6 n ⇔ m делит n.Считая, что 0 делит 0, показать, что 6 — частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, n} и sup{m, n}относительно указанного порядка.31. Для обычных отношений 6 и < на множестве ω показать, что< ◦ < 6= <, 6 ◦ < = < и 6 ◦ > = ω2 32. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего.33. Рассмотрим на множестве R2отношение Парето Π:(x1, y1) Π (x2, y2) ⇔ x1 6 x2и y1 6 y2.Для точек A(a1, a2) и B(b1, b2) найти множество нижних и верхних гра- ней множества {A, B}. Чему равен inf{A, B} и sup{A, B}?34. Построить линейный порядок на множестве комплексных чисел.35. Составить матрицу отношения полного порядка, при котором нумера- ция элементов ведется: а) по возрастанию; б) по убыванию. 50Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ36. Проверить, являются ли частичными порядками бинарные отношения со следующими матрицами:а)1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1; б)1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1; в)1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1;г)1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1; д)1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1; е)1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1;ж)1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1; з)1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1; и)1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1;к)1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1; л)1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1; м)1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1Построить диаграммы Хассе для заданных порядков. Есть ли в со- ответствующих частично упорядоченных множествах наименьшие или наибольшие элементы? Какие из этих частичных порядков линейные?37. Построить всевозможные попарно неизоморфные четырехэлементые ч.у.м. hA; 6i. Какие из этих ч.у.м. самодвойственны, т. е. изоморфныhA; >i? Глава 2АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ§ 2.1.Определения и примерыЧасто объектом изучения в математике и ее приложениях служит мно- жество вместе с определенной на нем структурой. Читателю уже известны поля, формирующие основу обычной арифметики, линейные пространства,обеспечивающие связь геометрических объектов с операциями над числами,множества с введенными на них бинарными отношениями. Все эти струк- туры образуют алгебраические системы, представляющие собой некоторые миры с определенными в них законами. Перейдем к точному определению алгебраической системы.Рассмотрим непустое множество A. В § 1.2 было введено понятиеn-местной операции на множестве A (f : An→ A). Отметим, что, поскольку операция f является функцией, для любого набора (x1, . . . , xn) ∈ Anре- зультат применения операции f (x1, . . . , xn) однозначно определен. Так как область значений операции f лежит в множестве A, то будем говорить, что операция f замкнута на множестве A.Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. При этом множе- ства предикатных и функциональных символов не пересекаются. 0-Местный функциональный символ называется константным символом или простоконстантой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). n-Местные предикатные и функциональ- ные символы часто будем обозначать соответственно через P(n)и f(n). Если в рассматриваемой сигнатуре используются стандартные символы, такие,например, как + для операции сложения, 6 для отношения порядка, | для 52Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫотношения делимости, 0 для константного символа и другие, то мы просто пишем Σ = {6}, Σ = {6, +, ·, 0}, Σ = {+, −, |, 0, 1} и т. д.Алгебраической системой A = hA; Σi сигнатуры Σ называется непустое множество A, где каждому n-местному предикатному (функциональному)символу из Σ поставлен в соответствие n-местный предикат (соответственно операция), определенный на множестве A. Множество A называется носите-лем или универсумом алгебраической системы hA; Σi. Предикаты и функ- ции, соответствующие символам из Σ, называются их интерпретациями.Обозначать интерпретации будем теми же буквами, что и соответствую- щие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A.Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами), а их носители — соответствующи- ми латинскими буквами A, B, . . . (с соответствующими индексами). Иногда мы будем отождествлять носитель с алгебраической системой.Мощностью алгебраической системы A называется мощность ее носите- ля A. В дальнейшем будем часто опускать слово “алгебраическая” и назы- вать A системой или структурой.Непустая сигнатура Σ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система A на- зывается алгеброй (моделью или реляционной системой), если ее сигнатура функциональна (предикатна).Пример 2.1.1. 1. Набор hω; +, ·i является алгеброй с двумя двухмест- ными операциями.2. Набор hω; 6, +, ·,0, 0, 1i является системой с бинарным отношением 6(µ(6) = 2), двухместными операциями +, · (µ(+) = µ(·) = 2), одноместной операцией0: n 7→ n + 1 (µ(0) = 1) и двумя нуль-местными операциями(константами) 0, 1 (µ(0) = µ(1) = 0).3. Набор hZ; +, :,√2i не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 /∈ Z), а элемент√2 не принадле- жит Z.4. Набор hP(U); ∩, ∪, , 0, 1i с двухместными операциями ∩, ∪, одномест- ной операцией : A 7→ A, константами 0 = ∅ и 1 = U является алгеброй,называемой алгеброй Кантора.5. Алгеброй является любое кольцо.6. Пара­{f (x) | f : R → R};ddx®(гдеddx— операция дифференцирова- ния) не является алгеброй, поскольку не всякая функция дифференцируема, 2.1. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ53но если рассмотреть множество A = {f (x) | f (x) дифференцируема беско- нечное число раз}, то отображение дифференцированияddx: f 7→dfdxявляется операцией на A и пара­A;ddx®образует алгебру. ¤Заметим, что частичную операцию f , отображающую Anв A, можно рассматривать как (n + 1)-местное отношениеRf­ {(x1, x2, . . . , xn, y) | (x1, . . . , xn) ∈ Anи y = f (x1, . . . , xn)}.Поэтому в последнем примере пару­{f (x) | f : R → R};ddx®можно считать алгебраической системой, если рассматриватьddxкак бинарное отношение©(f, g) | g =dfdxªАлгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группоидом.Единственная здесь операция f обычно обозначается символом ·: A = hA; ·i.Если A — конечное множество, действия операции · можно задать квадрат- ной таблицей, в которой для каждой пары (ai, aj) ∈ A2записан результат действия ·(ai, aj). Такая таблица называется таблицей Кэли группоида A.Группоид A называется полугруппой, если · — ассоциативная операция, т. е.для всех элементов x, y, z ∈ A верно x · (y · z) = (x · y) · z. Полугруппа A на- зывается моноидом, если существует элемент e ∈ A, называемый единицей,такой, что e · x = x · e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов.Пример 2.1.2. Пусть W (X) — множество слов алфавита X. Определим на W (X) операцию конкатенации ˆследующим образом: если α, β ∈ W (X),то αˆβ = αβ, т. е. результатом является слово, полученное соединением словα и β (например, xyzˆzx = xyzzx). Операция ˆ ассоциативна, т. е. для лю- бых слов α, β, γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, система hW (X);ˆiявляется полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α,где Λ — пустое слово, то Λ удовлетворяет свойству единицы. Таким образом,система hW (X);ˆi является моноидом. ¤Моноид A = hA; ·i называется группой, если для любого элементаx ∈ A существует элемент x−1∈ A, называемый обратным к x, такой, чтоx · x−1= x−1· x = e. Группа A называется коммутативной или абелевой,если x · y = y · x для всех x, y ∈ A.Пример 2.1.3. 1. Если hK; +, ·i — кольцо, то hK; +i — абелева группа.2. Система hGLn(K); ·i, где GLn(K) ­ {A | A — матрица порядка nнад полем K, и det A 6= 0} является группой, которая некоммутативна приn > 2. ¤ 54Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ§ 2.2.МорфизмыПусть даны алгебраические системы A = hA; Σi и B = hB; Σi. Отобра- жение ϕ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия:1) для любого функционального символа f(n)∈ Σ, соответствующих функций fAи fBв системах A и B и любых a1, a2, . . . , an∈ A выполня- етсяϕ(fA(a1, a2, . . . , an)) = fB(ϕ(a1), ϕ(a2), . . . , ϕ(an));2) для любого предикатного символа P(n)∈ Σ, соответствующих преди- катов PAи PBв системах A и B и любых a1, a2, . . . , an∈ A выполняется(a1, a2, . . . , an) ∈ PA⇒ (ϕ(a1), ϕ(a2), . . . , ϕ(an)) ∈ PB.Если ϕ: A → B — гомоморфизм, то будем его обозначать черезϕ: A → B.При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую.Пример 2.2.1. Рассмотрим системы A = hZ; +, 6i и B = hZ2; +, 6i, где в системе B сложение задается по правилу(a1, b1) + (a2, b2) = (a1+ a2, b1+ b2),а отношение порядка —(a1, b1) 6 (a2, b2) ⇔ a1 6 a2и b1 6 b2.Отображение ϕ: Z → Z2, при котором ϕ(a) = (a, 0), является гомоморфиз- мом. Действительно, для любых a, b ∈ Z имеемϕ(a + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + ϕ(b),и если a 6 b, то (a, 0) 6 (b, 0), т. е. ϕ(a) 6 ϕ(b). ¤Гомоморфизм ϕ: A → B, являющийся инъекцией, называется мономор-физмом. Гомоморфизм ϕ: A → B, являющийся сюръекцией, называетсяэпиморфизмом, и при этом система B называется гомоморфным образом 2.2. МОРФИЗМЫ55системы A. Гомоморфизм ϕ: A → A называется эндоморфизмом. Сюръек- тивный мономорфизм ϕ: A → B, для которого ϕ−1— гомоморфизм, называ- ется изоморфизмом A на B и обозначается через ϕ: A ∼→ B. Если существует изоморфизм ϕ: A ∼→ B, то системы A и B называются изоморфными и обо- значается это так: A ' B.Таким образом, условие A ' B означает, что существует биекцияϕ: A ↔ B, удовлетворяющая следующим условиям:1) для любого функционального символа f(n)∈ Σ, соответствующих функций fAи fBв системах A и B и любых a1, a2, . . . , an∈ A выполня- етсяϕ(fA(a1, a2, . . . , an)) = fB(ϕ(a1), ϕ(a2), . . . , ϕ(an));2) для любого предикатного символа P(n)∈ Σ, соответствующих преди- катов PAи PBв системах A и B и любых a1, a2, . . . , an∈ A выполняется(a1, a2, . . . , an) ∈ PA⇔ (ϕ(a1), ϕ(a2), . . . , ϕ(an)) ∈ PB.Изоморфизм ϕ: A ∼→ A называется автоморфизмом системы A. Заметим,что, поскольку изоморфизм ϕ: A ∼→ B является биекцией A ↔ B, изоморф- ные системы равномощны.Утверждение 2.2.1. 1. idA: A ∼→ A.2. Если ϕ: A ∼→ B, то ϕ−1: B ∼→ A.3. Если ϕ: A1∼→ A2и ψ: A2∼→ A3, то ϕ ◦ ψ: A1∼→ A3. ¤Таким образом, отношение изоморфизма ' является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгеб- раических систем не является множеством, поскольку не существует множе- ства всех множеств). Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство”. Это да- ет возможность переносить изучение свойств с одной системы на другую,изоморфную ей. Так, используя факт изоморфизма геометрического вектор- ного пространства пространству строк, работу с геометрическими объекта- ми можно свести к действиям с наборами чисел, что позволяет применять компьютеры.Пример 2.2.2. 1. Рассмотрим множество векторов E3геометрическо- го векторного пространства с операциями сложения векторов и умножения 56Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫвекторов на вещественные числа. Получим систему A = hE3; +, {λ·}λ∈Ri бес- конечной сигнатуры, где одноместные функции λ· ставят в соответствие век- тору a вектор 1   2   3   4   5   6   7   8   9   ...   29

λa. Рассмотрим также систему B = hR3; +, {λ·}λ∈Ri, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору a ∈ E3его координатную строку (x, y, z) в некотором фиксированном базисе e1, e2, e3, является биекцией (ϕ: E3↔ R3), при кото- рой сохраняются действия операций: ϕ(a+b) = ϕ(a)+ϕ(b) и ϕ(λ·a) = λ·ϕ(

1) является ли граф, соответствующий рассматриваемой принципиаль- ной схеме, планарным?2) если граф планарен, то как получить его изображение без пересечения ребер?На первый вопрос принципиальный ответ дает теорема Понтрягина—Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б. Н. Деньдобренько, А. С. Малика [7].Если граф G непланарен, то для его геометрической реализации удаля- ют отдельные ребра (переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ре- бер на следующую плоскость и т. д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G1, G2, . . ., Gm(разбиение ведется по множеству ребер), называется толщиной графа G.Таким образом, толщина планарного графа равна 1.Пример 4.15.2. Каждый из графов K5и K3,3имеет толщину 2. ¤Задачи и упражнения1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.2. Составить матрицу инцидентности для мультиграфа, изображенного на рис. 4.51.3. Найти все неизоморфные подграфы и части графа K3 4. Представить в геометрической и матричной формах графы G1∪ G2,G1∩ G2, G1⊕ G2(рис. 4.52).5. Для графов G1и G2из предыдущей задачи найти G1× G2, G1[G2] и G2[G1]. ЗАДАЧИ И УПРАЖНЕНИЯ163•••••¡¡¡¡¡¡@@@@@@R ?¾-±°²¯••••¡¡¡¡¡¡µ¸?YK*¼g±°²¯Рис. 4.50Рис. 4.516. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент.7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа(рис. 4.55).9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:а) графа K5; б) графа K3,3; в) графа, изображенного на рис. 4.56.•••¢¢¢¢¢¸AAAAAU1 23G1••••¾AAAAAU¢¢¢¢¢®1 23 4G2••••@@@I¡¡¡µ?@@@Rh1 23 4Рис. 4.52Рис. 4.53•••••••¡¡¡¡@@@@@@•••••½½½½>ZZZZ?-@@@@@@R¡¡¡¡¡¡µ¾6K®1 23 54(3)(4)(6)(2)(1)(2)(2)(3)(−2)(−5)Рис. 4.54Рис. 4.55 164Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ•••••••¶¶¶¶¶¶³³³³³³³³´´´´PPPPPPPPQQQQEEEEEEEE¢¢¢¢¢¢¡¡¡•••••••¶¶¶¶¶¶@@@´´´´@@@@@@EEEEEEEESSSSSS¡¡¡¡¡¡¢¢¢¢¢¢(2)(2)(3)(3)(1)(2)(2)(4)(3)(1)Рис. 4.56Рис. 4.57••••••••••••••••@@R¡¡ª¡¡ª ??¡¡ª@@R@@R@@R@@R¡¡ª¡¡ª¡¡ª¡¡ª@@R¡¡ª1 23 45 67 89 10 11 12 13 14 15 16•••••••JJJJ1 23 45 97 86 10Рис. 4.58Рис. 4.5911. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.12. Найти остов минимального веса взвешенного графа (рис. 4.57).13. Найти упорядоченный лес, соответствующий бинарному дереву, изображен- ному на рис. 4.58.14. Найти матрицы фундаментальных циклов и фундаментальных разрезов гра- фа (рис. 4.59).15. Найти хроматическое число графа (рис. 4.60).16. Найти толщину графа (рис. 4.61).•••••••¡¡¡@@@@@@@@@SSSSSS¦¦¦¦¦¦¦¦••••••¡¡¡¡@@@@HHHHHHHHHHHHHH©©©©©©©©©©©©©©Рис. 4.60Рис. 4.61 Глава 5КОМБИНАТОРИКАКомбинаторика — раздел математики, посвященный решению задач вы- бора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множе- ства, называемой комбинаторной конфигурацией. Поэтому целями комби- наторного анализа являются изучение комбинаторных конфигураций, алго- ритмов их построения, оптимизация таких алгоритмов, а также решение за- дач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения. При подсчете комбинаторных конфигураций используются правила суммы, произведения и степени, сформулированные в § 1.4.§ 5.1.Перестановки и подстановкиПусть дано множество M = {a1, a2, . . . , an}. Перестановкой элементов множества M называется любой кортеж (ai1, ai2, . . . , ain), состоящий из nразличных элементов множества M.Перестановки отличаются друг от друга только порядком входящих в них элементов. Покажем, что число Pnвсех перестановок множества Mравно n!. Действительно, на первое место в кортеже можно подставить лю- бой из n элементов, на второе место — любой из n − 1 оставшихся и т. д. Для последнего места остается единственный элемент. Поэтому получаем всегоn(n − 1)(n − 2) . . . 2 · 1 = n! перестановок. 166Глава 5. КОМБИНАТОРИКАПример 5.1.1. 1. Расставить на полке 10 книг можно P10= 10! == 3 628 800 различными способами.2. Список студентов группы, состоящей из 25 человек, можно составитьP25= 25! способами. ¤Напомним, что биекция σ: M ↔ M называется подстановкой множе- ства M. Пусть σ — подстановка множества M = {1, 2, . . . , n}. Тогдаσ(k) = sk, где 1 6 sk6 n, k = 1, 2, . . . , n, {s1, s2, . . . , sn} = {1, 2, . . . , n},и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк:[σ] ­µ1 2 . . . ns1s2. . . sn¶.Ясно, что если в матрице [σ] переставить столбцы, то полученная матрица будет также определять подстановку σ. Множество всех подстановок мно- жества {1, 2, . . . , n} обозначается через Sn. Для подстановок σ, τ ∈ Snможно определить произведение σ · τ как произведение двух функций. Зная матри- цы подстановок[σ] =µ1 2 . . . ns1s2. . . sn¶и [τ ], переставив столбцы матрицы [τ ] так, чтобы ее первая строка совпала со второй строкой матрицы [σ]:µs1s2. . . snt1t2. . . tn¶,получаем[στ ] =µ1 2 . . . ns1s2. . . sn¶ µs1s2. . . snt1t2. . . tn¶=µ1 2 . . . nt1t2. . . tn¶.Пример 5.1.2. Если [σ] =µ1 2 3 4 2 1 4 3¶, [τ ] =µ1 2 3 4 3 1 4 2¶, то[στ ] =µ1 2 3 4 2 1 4 3¶ µ2 1 4 3 1 3 2 4¶=µ1 2 3 4 1 3 2 4¶. ¤Теорема 5.1.1. Алгебра hSn; ·i является группой. При n > 3 она неком-мутативна. 5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ167Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка εс матрицей [ε] =µ1 2 . . . n1 2 . . . n¶и для любой подстановки σ с матрицей[σ] =µ1 2 . . . ns1s2. . . sn¶существует обратная подстановка σ−1, соответству- ющая матрицеµs1s2. . . sn1 2 . . . n¶Если n > 3, то рассмотрим подстановки σ и τс матрицами[σ] =µ1 2 3 4 . . . n2 1 3 4 . . . n¶и [τ ] =µ1 2 3 4 . . . n3 2 1 4 . . . n¶Имеем [στ ] =µ1 2 3 4 . . . n2 3 1 4 . . . n¶, [τ σ] =µ1 2 3 4 . . . n3 1 2 4 . . . n¶, т. е.στ 6= τ σ. Таким образом, группа hSn; ·i некоммутативна. ¤Группа hSn; ·i называется симметрической группой степени n. Число элементов этой группы |Sn| равно Pn­ n!.Подстановка σ называется циклом длины r, если матрицу [σ] переста- новкой столбцов можно привести к видуµs1s2s3. . . sr−1srsr+1. . . sns2s3s4. . .srs1sr+1. . . sn¶.Очевидно, что в этом случае σ задает биекцию, в которой s17→ s2,s27→ s3, . . ., sr7→ s1, а остальные элементы неподвижны. Описанный цикл σобозначается через (s1s2. . . sr).Пример 5.1.3. Подстановка с матрицейµ1 2 3 4 5 6 1 5 6 4 3 2¶является циклом (2 5 3 6), а подстановка с матрицейµ1 2 3 4 5 6 4 5 2 1 6 3¶циклом не яв- ляется, так как из нее можно выделить два цикла (1 4) и (2 5 6 3). ¤Циклы (s1s2. . . sr) и (t1t2. . . tp) называются независимыми, если{s1, s2, . . . , sr} ∩ {t1, t2, . . . , tp} = ∅.Теорема 5.1.2. Каждую подстановку можно однозначно, с точностьюдо порядка сомножителей, представить в виде произведения независимыхциклов. ¤ 168Глава 5. КОМБИНАТОРИКАВ примере 5.1.3 имеемµ1 2 3 4 5 6 1 5 6 4 3 2¶= (2 5 3 6) иµ1 2 3 4 5 6 4 5 2 1 6 3¶= (1 4)(2 5 6 3).Двухэлементный цикл (i j) называется транспозицией. При транспози- ции i-й и j-й элементы меняются местами, а остальные сохраняют свое по- ложение.Теорема 5.1.3. Каждая подстановка есть произведение транспозиций.Доказательство. По теореме 5.1.2 достаточно установить, что любой цикл (s1s2. . . sr) можно представить в виде произведения транспозиций,но легко проверяется, что (s1s2. . . sr) = (s1s2)(s1s3) . . . (s1sr). ¤Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤§ 5.2.Размещения и сочетанияПусть M — множество, состоящее из n элементов, m 6 n. Размещениемиз n элементов по m или упорядоченной (n, m)-выборкой, называется любой кортеж (ai1, ai2, . . . , aim), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функциюf : {1, 2, . . . , m} → M, для которой f (j) = aijПример 5.2.1. Для множества M = {a, b, c} пары (a, b) и (b, a) являются размещениями из 3 по 2, тройка (a, c, b) — размещением из 3 по 3, а тройка(b, a, b) размещения не образует. ¤Число размещений из n по m обозначается через Amnили P (n, m). Пока- жем, чтоAmn=n!(n − m)!= n(n − 1) . . . (n − m + 1)(5.1)(напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n − 1) способами. Если продолжить этот процесс, 5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ169то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1).Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A3 10вариантов расстановок, где A3 10=10!7!= 10 · 9 · 8 = 720. ¤Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкойназывается любое подмножество множества M, состоящее из m элементов.Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤Число сочетаний из n по m обозначается через Cmn,¡nm¢или C(n, m).Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({ai1, ai2, . . . , aim}) ­­ {(b1, b2, . . . , bm) | {b1, b2, . . . , bm} = {ai1, ai2, . . . , aim}}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, Amn= m!·Cmn,т. е. Cmn=Amnm!. Таким образом,Cmn=n!(n − m)! m!.Пример 5.2.4. Из десяти чисел четыре можно выбрать C4 10=10!6!4!==7·8·9·10 4!=7·8·9·10 1·2·3·4= 210 способами. ¤Число Cmnобладает следующими свойствами:1) Cmn= Cn−mn;2) Cmn+ Cm+1n= Cm+1n+1(правило Паскаля);3) (a + b)n=nPm=0Cmnambn−mдля любых a, b ∈ R, n ∈ ω (бином Ньютона).В силу последнего свойства числа Cmnназываются биномиальными коэф-фициентами.Пример 5.2.5. Из свойства 3 следует, что 2n=nPm=0Cmn. Действительно,2n= (1 + 1)n=nPm=0Cmn1m1n−m=nPm=0Cmn. ¤ 170Глава 5. КОМБИНАТОРИКА§ 5.3.Размещения и сочетания с повторениемРазмещением с повторением из n элементов по m или упорядоченной(n, m)-выборкой с возвращениями называется любой кортеж (a1, a2, . . . , am)элементов множества M, для которого |M| = n.Поскольку в кортеж (a1, a2, . . . , am) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениямиˆP (n, m) равно n · n · . . . · n|{z}m раз= nm:ˆP (n, m) = nm.Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆP (4, 3) = 4 3= 64трехзначных числа. ¤Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m:(a1, a2, . . . , am) ∼ (b1, b2, . . . , bm) ⇔ для любого c ∈ M число элементов ai,равных c, совпадает с числом элементов bi, равных c.Сочетанием с повторением из n элементов по m или неупорядоченной(n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов поm. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно.Число сочетаний с повторениями из n элементов по m обозначается через ˆC(n, m) и вычисляется по формулеˆC(n, m) = Cmn+m−1=(n + m − 1)!m!(n − 1)!.Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆC(6, 2) = C2 7= 21. ¤§ 5.4.РазбиенияПусть M — множество мощности n, {M1, M2, . . . , Mk} — разбиение мно- жества M на k подмножеств, |Mi| = mi, m1+ m2+ . . . + mk= n. Кортеж(M1, . . . , Mk) называется упорядоченным разбиением множества M. 5.4. РАЗБИЕНИЯ171Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m1и m2элементов, определяется сочетанием(без повторений) из n элементов по m1или из n по m2(m2= n − m1). Следо- вательно, число разбиений R(m1, m2) равно биномиальному коэффициентуCm1n= Cm2n. Таким образом,R(m1, m2) =n!m1!(n − m1)!=n!m1! m2!.В общем случае число R(m1, m2, . . . , mk) упорядоченных разбиений(M1, M2, . . . , Mk), для которых |Mi| = mi, равноn!m1! m2! . . . mk!, а числоR0(n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- мулеR0(n, k) =Xm1+ ... +mk=n,mi>0R(m1, m2, . . . , mk).Числа R(m1, m2, . . . , mk) называются полиномиальными коэффициентами,поскольку для всех a1, a2, . . . , ak∈ R справедливо соотношение(a1+ a2+ . . . + ak)n=Xm1+ ... +mk=n,mi>0n!m1! . . . mk!· am1 1am2 2. . . amkk.Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование?Пусть M — множество студентов в группе, M1— множество студентов,проголосовавших за выдвинутую кандидатуру, M2— множество студентов,проголосовавших против, M3— множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M1| = 12, |M2| = 10, |M3| = 3, (M1, M2, M3) —упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно25!12!10!3!= 1487285800. ¤Число ˆR(l1, l2, . . . , lr; m1, m2, . . . , mr) разбиений исходного множества Mна k подмножеств, неупорядоченных между собой, среди которых liмножеств 172Глава 5. КОМБИНАТОРИКАимеет мощность mi, i = 1, . . . , r, l1+ . . . + lr= k, m1l1+ . . . + mrlr= n,вычисляется по формулеˆR(l1, . . . , lr; m1, . . . , mr) =n!l1! . . . lr!(m1!)l1. . . (mr!)lr,а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равноXl1+...+lr=k,m1l1+ ... +mrlr=n,mi>0приli>0ˆR(l1, . . . , lr; m1, . . . , mr).1   ...   14   15   16   17   18   19   20   21   ...   29

B ∩ C = ∅.
4. P
1
= {ha, 2i, ha, 3i, ha, 4i, hb, 3i, hc, 1i, hc, 4i},
P
2
= {h1, 1i, h2, 3i, h2, 2i, h3, 4i, h1, 4i, h2, 4i, h4, 2i}.
5. P ⊆ (Z
+
)
2
, hx, yi ∈ P ⇔ x
2
> y,
где Z
+
= {x ∈ Z | x > 0}.
6. hC \ R; +, ·, :i.
7. B = hC; +,
.
ıi, X = R.
8. β = [5, 7, 11, 2], a = 43, b = 74, x = [3, 2, 5, 1].
9. G
1
: •
•
•
•
h h
h
?
@
@
@
R ?
¡
¡
¡
ª
1 2
4 3
G
2
: •
•
•
h h
h
-
A
A
A
3 2
1 10. G:
¡
¡
¡
¡
¡
¡
©©
©©
©©
@
@
@
•
•
•
•
•
•
•
•
11. x ↔ y ∧ (y → x), x ∨ (y ⊕ z ↓ x | y).
12. x → y ↓ z и (x → y) ↓ (x → z).
13. (x ↔ y → z) | y.
14. f (0, 1, 1) = f (0, 1, 0) = f (1, 0, 1) = f (1, 1, 1) = 1.
15. (0011 1101 0010 1100).
16. J = {x ∨ y, x ↔ y}.
17. A \ (B \ C) = (A \ B) \ C.

Указатель терминов
Автоморфизм, 55
Аксиома бесконечности, 44
выбора, 45
замены, 44
математической индукции, 24
множества всех подмножеств, 44
регулярности, 45
суммы, 44
существования пары, 44
пустого множества, 44
экстенсиональности, 44
Аксиомы
Дедекинда—Пеано, 24
Цермело—Френкеля, 44
метрики, 131
Алгебра, 52
Кантора, 52
булева, 65
булевых функций, 186
компьютерная, 88
отношений, 70
реляционная, 71
Алгебраическая система, 52
Алгоритм
Дейкстры, 134
Евклида, 96
Форда—Беллмана, 133
последовательной раскраски, 160
Алфавит, 40
Антидизъюнкция, 182
Антиконъюнкция, 182
Аргумент, 20
Арифметика многомодульная, 111
модулярная, 100
остатков, 100
по модулю M , 111
Ассоциативность, 14, 65, 186
композиции, 19
Атом, 66
Атомарная формула, 180
Базис, 205
индукции, 24
Биекция, 21
Бином Ньютона, 169
Бит, 88
Булеан, 12
Булева алгебра двойственная, 201
решетка, 64
функция, 183
Булева алгебра, 65
Булево кольцо, 67

УКАЗАТЕЛЬ ТЕРМИНОВ
263
В.у.м., 40
Валентность вершины, 136
Вектор, 37
значений булевой функции, 184
оснований, 110
остатков, 110
Вершина, 115
висячая, 136
графа, 115
достижимая, 127
изолированная, 136
концевая, 136
периферийная, 131
центральная, 132
взвешенная, 132
Вершины взаимно достижимые, 130
смежные, 118
Вес вершины, 120
дуги, 120
маршрута, 132
Ветвь остова, 152
Включение множества, 11
Восьмеричная система, 84
Вхождение переменной, 195
Выборка неупорядоченная, 169
с возвращениями, 170
упорядоченная, 168
с возвращениями, 170
Высказывание, 180
простое, 180
сложное, 180
Гомоморфизм, 54
естественный, 60
Граница, 157
Грань верхняя, 39
нижняя, 39
точная верхняя, 39
нижняя, 39
Граф, 115
ациклический, 140
бесконтурный, 127
бихроматический, 159
взвешенный, 120
гамильтонов, 139
двудольный, 159
неориентированный, 116
ориентированный, 116
планарный, 160
полный, 125
получаемый отождествлением вер- шин, 122
помеченный, 120
разреженный, 121
связный, 127
сильно связный, 127
Графы гомеоморфные, 160
изоморфные, 119
Группа, 53
абелева, 53
коммутативная, 53
симметрическая, 167
Группоид, 53

264
УКАЗАТЕЛЬ ТЕРМИНОВ
ДНФ, 189
Двоичная система, 83
Декартова степень множества, 16
Декартово произведение алгебр, 62
множеств, 16, 61
отношений, 70
Декомпозиция функции, 206
дизъюнктивная, 207
нондизъюнктивная, 207
простая, 208
функциональная итеративная, 210
множественная, 210
Делитель, 93
наибольший общий, 94
Дерево, 140
бинарное, 151
остовное, 141
упорядоченное, 149
Диагональ, 18
Диаграмма
Хассе, 42
Эйлера—Венна, 13
Диаметр графа, 131
Дизъюнкт, 188
Дизъюнктивная нормальная форма, 189
минимальная, 196
совершенная, 190
сокращенная, 195
тупиковая, 196
Дизъюнкция, 180
элементарная, 188
Дистрибутивность, 14
Длина маршрута, 126
слова, 40
Домен, 70
Дополнение графа, 123
множества, 13
функции, 186
элемента, 64
Дуга, 115
графа, 115
заходящая в вершину, 115
инцидентная вершине, 119
исходящая из вершины, 115
Дуги кратные, 116
Единица моноида, 53
решетки, 63
частично упорядоченного множества,
39
Задача коммивояжера, 140, 144
нахождения остова минимального веса, 142
о безопасном хранении ключа, 105
о кенигсбергских мостах, 137
Закон двойного отрицания, 14, 66, 186
де Моргана, 14, 66, 186
дистрибутивности, 14, 65, 186
идемпотентности, 14, 65
нуля и единицы, 14, 66

УКАЗАТЕЛЬ ТЕРМИНОВ
265
поглощения, 14, 66, 186
Значение терма, 58
функции, 20
Идеал, 68
главный, 68
Идемпотентность, 14, 186
Изображение графа, 115
плоское, 160
Изоморфизм, 55
частично упорядоченных множеств,
43
Изоморфные системы, 55
частично упорядоченные множества,
43
Импликанта простая, 195
формулы, 195
функции, 195
Импликация, 180
Инверсия, 180
Инвертор, 206
Индукционный шаг, 24
Интерпретация, 52, 181
Инфимум, 39
Инцидентор, 116
Инъекция, 20
Источник, 133
КНФ, 189
Кардинал, 26
Каркас графа, 141
Карта
Карно, 198
декомпозиции, 208
Квазипорядок, 37
Класс функций линейных, 203
монотонных, 203
самодвойственных, 202
эквивалентности, 35
Классы Поста, 202
Кограница, 157
Код двоичный, 82
Кольцевая сумма графов, 123
формул, 182
Кольцо булево, 67
вычетов по модулю m, 100
целых чисел, 76, 78
Комбинаторика, 165
Коммутативность, 14, 65, 186
Композиция графов, 125
отношений, 19
Компонента связности, 127
сильной, 127
сильная, 127
Компьютерная алгебра, 88
Конгруэнция, 59
единичная, 64
нулевая, 64
Конец ребра, 116
Конкатенация, 53

266
УКАЗАТЕЛЬ ТЕРМИНОВ
Константа, 22, 51, 52 0, 185 1, 185
Константный символ, 51
Конституента единицы, 190
нуля, 190
Контакт, 213
замыкающий, 213
размыкающий, 213
Континуум, 26
Контрпример, 220
Контур, 127
Конфигурация комбинаторная, 165
Конъюнкт, 188
Конъюнктивная нормальная форма,
189
минимальная, 197
совершенная, 190
Конъюнкция, 180
элементарная, 188
Координата, 16
слова, 40
Коранг, 141
Корень дерева, 143
упорядоченного, 149
характеристический, 174
Кортеж, 16
Коцикл, 154
Коэффициент биномиальный, 169
полиномиальный, 171
Л.у.м., 38
Лемма о рукопожатиях, 137
Лес, 140
упорядоченный, 149
Литера, 188
Литеры контрарные, 188
МДНФ, 196
МКНФ, 197
Маршрут, 126
кратчайший, 132
циклический, 126
Математика дискретная, 6
непрерывная, 6
прерывная, 6
Матрица
Квайна, 197
бинарного отношения, 31
весов, 120
достижимости, 129
инцидентности, 119
контрдостижимости, 130
программируемая логическая, 218
расстояний, 131
связности, 129
смежности, 118
соединений, 218
фундаментальных разрезов, 155
циклов, 152
Метод
Квайна, 196
бинарный, 102
Многообразие, 62

УКАЗАТЕЛЬ ТЕРМИНОВ
267
Многочлен характеристический, 174
Множества равномощные, 26
равные, 11
совпадающие, 11
эквивалентные, 26
Множество, 10
бесконечное, 26
континуальное, 26
счетное, 26
вполне упорядоченное, 40
вычетов, 99
действительных чисел, 81
коконечное, 69
комплексных чисел, 82
конечное, 26
коциклов фундаментальное, 155
линейно упорядоченное, 38
натуральных чисел, 23, 24
пустое, 12
рацинальных чисел, 79
строго включенное, 12
универсальное, 12
фундаментальных циклов, 152
целых чисел, 78
по модулю m, 99
циклов фундаментальное, 152
частично упорядоченное, 38
Множество-степень, 12
Модель, 52
Моноид, 53
Мономорфизм, 54
Мощность алгебраической системы, 52
множества, 26
Мультиграф, 116
неориентированный, 117
реберный, 159
эйлеров, 138
Мультиграфы изоморфные, 119
Мультиплексор, 217
Набор длины n, 16
остатков стандартный, 110
цепей, покрывающих граф, 139
Наибольший общий делитель, 94
Наименьшее общее кратное, 95
Неорграф, 116
ациклический, 126
связный, 127
соответствующий данному оргра- фу, 117
Неравенство
Бернулли, 25
треугольника, 131
Нормальная форма дизъюнктивная, 189
минимальная, 196
сокращенная, 195
тупиковая, 196
конъюнктивная, 189
минимальная, 197
Носитель алгебраической системы, 52
Нуль решетки, 63
частично упорядоченного множества,
39

268
УКАЗАТЕЛЬ ТЕРМИНОВ
Область значения, 18
определения, 18
Образ гомоморфный, 54
множества, 19, 22
Обратное отношение, 19
Обхват графа, 126
Обход графа по глубине, 143
по ширине, 143
Объединение графов, 123
конгруэнций, 64
отношений, 70
функций, 186
элементов решетки, 63
Объединение множеств, 12
Ограничение отображения, 22
Операция
n-арная, 22
n-местная, 22
бинарная, 22
возведения в степень, 27
выбора, 71
добавления вершины, 122
дуги, 122
кольцевого сложения, 68
кольцевого умножения, 68
конкатенации, 53
логическая, 180
на множестве ассоциативная, 53
отождествления вершин, 122
подразбиения ребра, 160
проекции, 72
сложения, 25, 27
соединения, 72
стягивания дуги, 122
удаления вершины, 122
дуги, 122
умножения, 25, 27
унарная, 22
Определение индукционное, 24
Орграф, 116
Ортогональные подпространства, 158
Основание счисления, 83
Остаток, 94
Остов графа, 141
Отношение, 17
n-местное, 17
Парето, 39
антирефлексивное, 33
антисимметричное, 33
асимметричное, 33
бинарное, 17
иррефлексивное, 33
на множестве, 17
обратное, 19
полное, 18
рефлексивное, 33
симметричное, 33
тождественное, 18
транзитивное, 33
унарное, 17
универсальное, 18
эквивалентности, 35

УКАЗАТЕЛЬ ТЕРМИНОВ
269
Отношения совместимые, 70
Отображение, 20
Отрицание, 180
ПЛМ, 218
Перевод дробных чисел, 87
целых чисел, 86
Переменная логическая, 180
Пересечение графов, 123
конгруэнций, 64
множеств, 12
отношений, 70
функций, 186
элементов решетки, 63
Перестановка, 165
Перешеек, 138
Период дроби, 81
Петля, 118
Плоское изображение графа, 160
Поглощение, 14
Подалгебра, 57
Подграф, 121
Поддерево левое, 151
правое, 151
упорядоченное, 149
Подмножество, 11
собственное, 12
Подмодель, 57
Подпространства ортогональные, 158
Подсистема, 57
порожденная множеством, 57
Подстановка множества, 21, 166
Покрытие множества, 15
Поле действительных чисел, 80
комплексных чисел, 82
конечное, 101
рациональных чисел, 79
характеристики нуль, 101
Полином Жегалкина, 203
линейный, 204
нелинейный, 204
Полное отношение, 18
Полугруппа, 53
Полустепень захода, 137
исхода, 137
Полюс, 212
входной, 213
выходной, 213
Пометка, 120
Порядок двойственный, 38
лексикографический, 40
линейный, 38
полный, 40
строгий, 38
частичный, 38
Последователь, 121
вершины, 118
Последовательность, 22
возвратная, 174
фундаментальная, 80
Поток в сети, 153
Правило

270
УКАЗАТЕЛЬ ТЕРМИНОВ
Паскаля, 169
произведения, 28
степени, 28
суммы, 28
Предикат, 17
на множестве, 17
Предпорядок, 37
Представление со смешанными основаниями, 112
Предшественник вершины, 118
Принцип двойственности для булевых функций, 201
математической индукции, 24
полного упорядочения, 45
полной индукции, 26
трансфинитной индукции, 45
Программируемая логическая матри- ца, 218
Проекция, 20
Произведение алгебр, 62
бинарных отношений, 19
векторов внутреннее, 157
графов, 123
множеств, 13
декартово, 16, 61
прямое, 16
остатков, 100
отношений декартово, 70
списков, 92
элементарное, 195
Прообраз множества, 19
Противоречие, 187
Путь, 127
Радиус взвешенный, 132
графа, 132
Разбиение множества, 15
упорядоченное, 170
Разложение Шеннона, 191
Размещение, 168
с повторением, 170
Разность множеств, 13
симметрическая, 13
отношений, 70
Разрез графа, 154
простой, 154
фундаментальный, 155
Ранг коциклический, 141
циклический, 141
Раскраска вершин графа, 158
ребер мультиграфа, 159
Распределение меток, 120
вершин, 120
дуг, 120
Расстояние, 131
взвешенное, 132
Реализация декомпозиционная, 206
Решение общее, 174
частное, 175
Решетка, 63
булева, 64

УКАЗАТЕЛЬ ТЕРМИНОВ
271
дистрибутивная, 64
конгруэнций, 64
подсистем, 63
элементов &, 218
Решето Эратосфена, 98
СДНФ, 190
СКНФ, 190
Свойство, 17
делимости, 94
евклидовости, 94
Связка, 180
Сегмент начальный замкнутый, 43
открытый, 43
Сеть, 153
k-полюсная, 212
Сигнатура, 51
предикатная, 52
функциональная, 52
Система, 52
Дедекинда—Пеано, 76
аксиом
ZFC, 45
алгебраическая, 52
булевых функций полная, 202
неотрицательная, 108
остатков наименьших по абсолютной ве- личине, 100
неотрицательных, 100
полная, 100
симметричная, 100, 110
симметричная, 108
счисления восьмеричная, 84
двоичная, 83
позиционная, 82
смешанная, 85
шестнадцатеричная, 84
числовая наименьшая неотрицательная,
110
наименьшая по абсолютной ве- личине, 110
Системы изоморфные, 55
Слово, 40
пустое, 40
Сложение логическое, 182
по модулю 2, 182
Сложность
(1, 1)-полюсника, 214
булевой функции, 214
схемы из функциональных элемен- тов, 216
функции, 217
Смешанная система счисления, 85
Соединение графов, 123
контактов параллельное, 213
последовательное, 213
Сомножитель, 96
Соответствие, 17
взаимно однозначное, 21
Соотношение рекуррентное, 174
Сочетание, 169

272
УКАЗАТЕЛЬ ТЕРМИНОВ
с повторением, 170
Список дуг, 121
над множеством, 90
пустой, 90
уступчатый, 150
Степень вершины, 136
Стрелка Пирса, 182
Структура, 52
смежности, 121
Сумма кольцевая, 182
множеств, 13
кольцевая, 13
остатков, 100
списков, 92
Суперпозиция функций, 185
Супремум, 39
Схема
X
n
-функициональная минимальная, 217
X
n
-функциональная, 216
из функциональных элементов, 215
контактов, 213
электрическая, 213
Сюръекция, 21
Таблица
Кэли, 53
истинности, 181, 184
Тавтология, 187
Теорема
Биркгофа, 62
Дедекинда—Пеано, 76
Жегалкина, 203
Кантора, 29
Кантора—Бернштейна, 27
Квайна, 196
Понтрягина—Куратовского, 161
Поста, 205
Стоуна, 66
Ферма малая, 102
Шеннона вторая, 192
первая, 191
арифметики основная, 97
о гомоморфизме, 60
о единственности неприводимого раз- ложения, 97
о сравнении множеств, 27
о существовании неприводимого раз- ложения, 97
о функциональной полноте, 192
о четырех красках, 162
об остатках китайская, 104
Терм сигнатуры Σ, 58
Тождественное отношение, 18
Тождество сигнатуры Σ, 62
Толщина графа, 162
Транспозиция, 168
Универсальное отношение, 18
Универсум, 12
алгебраической системы, 52
Уравнение линейное диофантово, 95
рекуррентное, 174
линейное неоднородное, 175
Утверждение двойственное, 67

УКАЗАТЕЛЬ ТЕРМИНОВ
273
Фактор-алгебра, 60
Фактор-множество, 35
Факториал, 25
Фильтр, 69
Фреше, 69
главный, 69
двойственный к идеалу, 69
Форма нормальная дизъюнктивная, 189
совершенная, 190
конъюнктивная, 189
совершенная, 190
Формула алгебры логики, 180
атомарная, 180
выполнимая, 187
общезначимая, 187
опровержимая, 187
представляющая функцию, 184
тождественно истинная, 187
тождественно ложная, 187
включений и исключений, 172
рекуррентная, 174
Формулы эквивалентные, 186
Функция, 20
n-местная, 22
алгебры логики, 183
биективная, 21
булева, 183
двоичная, 183
двойственная, 201
индикаторная, 29
инъективная, 20
линейная, 203
монотонная, 203
на, 21
переключательная, 183
проводимости, 213
разложимая, 205
разнозначная, 20
реализуемая
(1, k)-полюсником, 214
схемой, 216
самодвойственная, 201
сохраняющая единицу, 202
нуль, 202
ставящая в соответствие элементу элемент, 20
сюръективная, 21
частичная, 20
Характеристика поля, 101
Хорда, 152
Целая часть числа, 92
Центр графа, 132
Цепи покрывающие, 139
Цепь, 126
гамильтонова, 139
простая, 126
эйлерова, 139
Цикл, 126, 167
гамильтонов, 139
простой, 126
фундаментальный, 152
эйлеров, 138
Цифра, 83
Ч.у.м., 38

Смотрите также файлы