Дискретная математика : основные теоретико-множественные конструкции. Ч.II

УДК 591.45 
 
П78 

Р е ц е н з е н т  
д-р техн. наук, проф. МГГА Л.П. Рябов 

Прокопчук Ю.Ю., Широков А.И. 
П78  
Дискретная математика: Основные теоретико-множественные 
конструкции. Ч.II: Учеб. пособие /Под ред. Г.И. Светозаровой и 
А.Г. Дьячко. – М.: МИСиС, 2004. – 147 с. 

Пособие представляет собой вторую часть раздела «Основные теоретикомножественные конструкции» учебного курса «Дискретная математика». В 
него входит описание такого фундаментального понятия современной математики, как график, и его отдельных видов: n-график и семейства множеств, а также относящийся к ним логический и математический аппарат. 
Содержание пособия соответствует программе курса «Дискретная математика». 
Предназначено для студентов специальностей 220200 и 351400, изучающих учебные дисциплины «Математическая логика и теория алгоритмов» и 
«Дискретная математика». 

© Московский государственный институт

стали и сплавов (Технологический  
университет) (МИСиС), 2004 

ОГЛАВЛЕНИЕ 

От авторов .................................................................................................5 
Введение....................................................................................................6 
Глава III. Графики.....................................................................................8 
§ 1. Определение графика. Отношения между графиками и 
операции над ними ...............................................................................8 
1. Теоретико-множественные отношения между графиками и 
операции над ними ...........................................................................8 
2. График над множеством. Области определения и значений 
графика. Диагональный график. Диагональное множество.........9 
3. Инвертирование..........................................................................10 
4. Присоединение............................................................................11 
Упражнения.....................................................................................12 
Примечания.....................................................................................21 
§ 2. Графики, состоящие из кортежей одинаковой длины .............23 
1. Определение n-графиков............................................................23 
2. Графовое описание диаграммы n-графиков.............................24 
3. Проектирование n-графиков......................................................26 
4. Компонирование n-графиков.....................................................30 
5. Кообразы множества относительно n-графика........................32 
6. *Пучки множеств относительно n-графика .............................34 
Упражнения.....................................................................................38 
Примечания.....................................................................................44 
§ 3. Способы задания n-графиков. Декартово произведение 
множеств..............................................................................................44 
1. О классах n-графиков при n=0,1,2.............................................44 
2. Способы задания n-графиков ....................................................45 
3. Декартово произведение множеств. Степень множества .......48 
Упражнения.....................................................................................50 
Примечания.....................................................................................54 
Приложение 1. О включении n-графиков в декартовы 
произведения множеств .................................................................55 
Упражнения к приложению 1........................................................58 
Примечания к приложению 1........................................................59 
§ 4. Свойства n-графиков. Задачи анализа и синтеза ......................59 
1. Определение функционального графика..................................59 
2. Определение инъективного графика ........................................63 
3. Определение биективного графика...........................................64 

4. Задачи анализа и синтеза объектов...........................................65 
Упражнения.....................................................................................68 
Примечания.....................................................................................73 
Приложение 2. Циклические свойства n-графиков.....................74 
П. 2. 1. Зависимость и однозначность.......................................74 
П. 2. 2. Функциональность.........................................................76 
П. 2. 3. Инъективность ...............................................................80 
П. 2. 4. Биективность..................................................................83 
Упражнения к приложению 2........................................................84 
Примечания к приложению 2........................................................89 
Глава IV. Бинарные графики. Семейства множеств ...........................90 
§ 1. Бинарные графики.......................................................................90 
1. Определения. Терминология .....................................................90 
2. Способы задания графиков........................................................91 
3. Образ и полный прообраз множества относительно 
графика ............................................................................................93 
4. Компонирование.........................................................................95 
5. Диаграммы результатов операций над графиками..................96 
6. Функциональные, инъективные и биективные графики ........98 
7. *Многоместные графики и многоместные алгебраические 
графики..........................................................................................103 
Упражнения...................................................................................104 
Примечания...................................................................................129 
§ 2. Семейства множеств..................................................................129 
1. Семейства. Терминология........................................................130 
2. Операции над семействами множеств....................................130 
3. Виды семейств множеств.........................................................132 
Упражнения...................................................................................135 
Примечания...................................................................................139 
Библиографический список.................................................................141 
Приложение 3. Указатель знаков и обозначений ......................143 
Приложение 4. Указатель терминов ...........................................145 
 

Памяти 
Анатолия Павловича 
Демьяновского 

От авторов 

Данное пособие авторы посвящают памяти Анатолия Павловича 
Демьяновского, доцента Московского государственного института 
стали и сплавов (МИСиС), скончавшегося после тяжелой и продолжительной болезни 22 мая 1990 г. 
А.П. Демьяновский работал на кафедре инженерной кибернетики 
(КИК) МИСиС, возглавляемой академиком РАН С.В. Емельяновым, 
с осени 1969 года, и на кафедре автоматизированных систем управления (АСУ), руководимой доктором технических наук, профессором А.Г. Дьячко, с 9 сентября 1987 года по день кончины. На протяжении всего времени работы в МИСиС Анатолий Павлович возглавлял развиваемое им на обеих кафедрах научное направление, носящее название «Автоматизированные системы управления производством» (АСУП). Его теоретические курсы, практические занятия и 
лабораторные работы были направлены в основном на изложение 
методов и моделей АСУП, многие из которых были разработаны и 
внедрены в практику Анатолием Павловичем и его сотрудниками. 
Актуальность и плодотворность этого направления подтвердились 
тем, что большое число студентов выполнили по нему научноисследовательские курсовые и дипломные работы. Кроме того, под 
научным руководством А.П. Демьяновского было подготовлено и 
защищено восемь кандидатских диссертаций. По теме АСУП Анатолий Павлович вместе со своими сотрудниками выпустил в свет несколько печатных изданий: учебников, учебных пособий и лабораторных практикумов. 
Авторы пособия работали рядом с Анатолием Павловичем более 
двух десятилетий. У них до сих пор остались самые искренние и теплые чувства к Анатолию Павловичу как эрудированному специалисту, прекрасному педагогу и верному товарищу. 

ВВЕДЕНИЕ 

1. Понятия множество и кортеж, рассмотренные нами в предыдущих главах [19, гл. I – II], являются к а т е г о р и я м и  современной математики [16, с. 8], на основе которых могут быть «построены» теоретико-множественные конструкции «любой степени сложности». Простейшие из них – множества кортежей, или графики, – 
систематически изучаются в данном пособии. Обратимся к его содержанию. 
Глава III посвящена исследованию понятия «график». Ознакомимся вкратце с ее составляющими. В § 1 вводится понятие графика как 
множества, состоящего исключительно из кортежей. В своем первоначальном виде оно появилось в математике под именем пробег предиката [8, с. 30, 121] в одной из ранних работ выдающегося немецкого 
философа, логика и математика Готтлоба Фреге (1848 – 1925). Это понятие равнообъемно [16, с. 7] широко используемому в настоящее 
время понятию бинарного графика, область задания (значений) которого есть область определения какого-то одноместного соотношения 
[17, гл. II, § 2, п. 4] (соответственно, множество {модальность «истина», модальность «ложь»}), то есть довольно незначительной части 
объема понятия «график». Сравнение объемов понятий «пробег предиката» и «график» свидетельствует о существенном обобщении исторически исходного понятия в современном варианте [16, с. 4]. 
В § 2 в рассмотрение вводится весьма важный в приложениях отдельный вид графиков – n-графики, где n∈N. К нему относятся все 
графики, каждый из которых состоит только из кортежей одинаковой 
длины n. Далее изучаются связанные с n-графиками конструкции и 
операции. 
В § 3 читатель знакомится с некоторыми способами задания nграфиков. Здесь же рассматривается частный вид n-графиков – прямые, или декартовы, произведения множеств и их отдельный класс 
– степени множеств. Между двумя последними понятиями и графиками устанавливаются в приложении 1 некоторые связи. 
В § 4 речь идет о таких важных с теоретической точки зрения 
свойствах n-графиков, как (линейные) функциональность, инъективность и биективность. В приложении 2 изучаются аналоги указанных свойств n-графика: (циклические) функциональность, инъективность и биективность. Характеризуемые ими n-графики находят 

применение, например, в разделе «Структуры данных» научной дисциплины «Информатика». 
Глава IV посвящена наиболее изученному к настоящему времени 
подклассу n-графиков – бинарным, или 2-графикам, то есть графикам, состоящим лишь из кортежей длины 2, или пар [19, гл. II, § 3 
п. 1]. Именно 2-графики находят самое разнообразное применение в 
таких фундаментальных «сложных» понятиях современной математики, как соответствия (в частности, функции), отношения на 
множестве и т.д. [7, с. 55 – 62]. 2-графики (обладающие или нет указанными в предыдущем абзаце свойствами) выступают в качестве их 
основных составляющих. В § 1 вводятся и исследуются основные 
понятия и объекты, связанные с бинарными графиками. 
В § 2 изучается отдельный вид бинарных функциональных графиков – семейства множеств (СМ), которые широко применяются во 
всех разделах «Теории множеств». Использование СМ позволяет, 
например, уточнить многие введенные ранее понятия и обобщить 
полученные в предыдущих главах результаты. 
2. Некоторые места текста имеют целью уберечь читателя от 
серьезной ошибки, которую он рискует совершить. Они помечены 
знаком Z («опасный поворот») [5, с. 20]. 
3. Авторы благодарят М.С. Кузьмина за помощь в компьютерной 
верстке. 

ГЛАВА III. ГРАФИКИ 

Понятия м н о ж е с т в о  и к о р т е ж ,  рассмотренные в гл. I и II 
пособия [19], являются к а т е г о р и я м и  современной математики 
[16, с. 8], на основе которых могут быть «построены» теоретикомножественные конструкции «любой степени сложности»1). Простейшие среди последних - множества кортежей и производные от 
них понятия - систематически изучаются в данной главе. 

§ 1. Определение графика. Отношения между 
графиками и операции над ними 

1. Теоретико-множественные отношения 
между графиками и операции над ними 

Определение 1. Любое множество, состоящее только из кортежей, называют графиком.  
Таким образом, 

 
(G - график) ≡df (∀z∈G)(z - кортеж). 
(1) 

Графики, будучи множествами, могут находиться между собой в 
некоторых теоретико-множественных отношениях, например, в бинарных отношениях =, ⊆, ⊂ и т. д. [19, гл. I, § 2, пп. 2 – 5, с. 20 – 30]. 
На графики, фактически находящиеся в них, переносят соответствующую терминологию. Например, всякую часть графика G называют его подграфиком, а любое множество, включающее G в себя, – 
его расширением. Расширение графика G, являющееся г р а ф и к о м , 
называют надграфиком G. Ясно, что каждая часть надграфика графика G есть график, но им не является всякое подмножество расширения G. Подграфики и надграфики данного графика называют его 
кографиками. 
Располагая некоторым запасом графиков, мы можем получать множества, представляющие собой их объединения, пересечения, разности, 
симметрические разности и т.д. [19, гл. I, § 3, пп. 3 – 6, с. 45 – 50]. 
Z Легко понять, что результаты одних теоретико-множественных 
операций над графиками суть графики, а других – отличные от них 
объекты. Так, объединения, пересечения, разности и симметрические 
разности графиков - графики, а булеаны графиков - нет. 

Тот факт, что графики представляют собой множества к о р т е ж е й , позволяет ввести в рассмотрение предметы и действия, индуцированные объектами и операциями, связанными с кортежами. Ниже мы познакомимся с некоторыми из них. 

2. График над множеством. Области 
определения и значений графика. Диагональный 
график. Диагональное множество 

Определение 1. Если все элементы графика G являются к о р т е ж а м и  н а д  м н о ж е с т в о м  X  [19, гл. II, § 1, п. 3, с. 75], то G 
называют графиком над множеством Х.  П о  о п р е д е л е н и ю  
с ч и т а ю т , что пустой график, то есть ∅, и {Λ} – суть графики над 
любым, в том числе и пустым множеством. 
Пример 1. Множество L1 =df {Λ, <0>, <1,2>, <2,1>, <3,3,4>} – 
график над N, а график L2 =df {Λ, <0>, <<1,2>, <2>>} – нет. 
Определение 2. Совокупность, состоящую только из первых (последних) проекций всех элементов графика G, называют его областью определения (соответственно, значений) и обозначают через 
Допр(G) (соответственно, Дзн(G)). 
Таким образом, 

 
Допр(G) =df εх{x: (∃z∈G)(x=пр1z)}, 
(1) 

 
Дзн(G) =df εх{x: (Λ∈G⇒x=Λ)∨(∃z∈G)(l(z)>0⇒x=прl(z)z)}. 
(2) 

Пример 2. Ясно, что Допр(∅)=Дзн(∅)=∅, а Допр({Λ})=Дзн({Λ})={Λ}. 
Если L1 и L2 - графики из примера 1, то Допр(L1)={Λ, 0, 1, 2, 3} и 
Дзн(L1)={Λ, 0, 1, 2, 4}, а Допр(L2)={Λ, 0, <1,2>} и Дзн(L2)={Λ, 0, <2>}. 
Определение 3. Объемом графика G называют и через V(G) обозначают множество, состоящее только из всех компонент всех кортежей из G. 
Таким образом, 

 
V(G)=df ∪z∈G(∪1≤i≤l(z){прiz}). 
(3) 

Пример 3. См. пример 1. Легко понять, что V(L1)={Λ, 0, 1, …, 4}, 
а V(L2)={Λ, 0, <1,2>, <2>}. 
Определение 4. График, состоящий только из д и а г о н а л ь н ы х  
к о р т е ж е й  [19, гл. II, § 1, п. 3, с. 76], называют диагональным. 
Пример 4. Графики G1=df{<a,a>, <b,b>} и G2=df{<a,a,a>, <b,b,b,b>, 
<c,c>} - диагональные, а график G3=df {<a>, <a,b>} при a ≠ b – нет. 

Определение 5. Диагональю высоты m, где m∈N+, множества X, 
называют и через ∆m
X обозначают совокупность, состоящую только 
из всех д и а г о н а л ь н ы х  к о р т е ж е й  длины m н а д  м н о ж е с т в о м  X [19, гл. II, § 1, п. 3, с. 76]. 
Пример 5. Если X=df{a, b, с}, то ∆1
x={<a>, <b>, <с>},..., 
∆4
x={<a,a,a,a>, <b,b,b,b>, <с,с,с,с>} и т. д. 

3. Инвертирование 

Определение 1. Инверсией графика G называют и через G-1 обозначают множество, содержащее только инверсии всех элементов из G. 
Таким образом, 

 
(G–1 – инверсия графика G) ≡df (∀z)((z∈G–1)⇔(z–1∈G)). 
(1) 

Ясно, что G-1 есть график, который называют иногда графиком, 
обратным к G. 
Определение 2. Операцию, относящую графику его инверсию, 
называют инвертированием графиков. 
*Несложно убедиться, что эта одноместная операция определена 
для любого графика, функциональна и инъективна, то есть является 
одноместным биективным соответствием на всяком классе графиков, 
замкнутом относительно него2) [17, гл. I, § 4, п. 4, с. 36].* 
Операция инвертирования обладает какими-то свойствами и находится в определенных связях с другими операциями. Перечислим 
некоторые из них. Пусть G, G1 и G2 – графики. Тогда 

 
V(G)=V(G–1); 
(2) 

 
|G|=|G–1|; 
(3) 

 
(G–1)−1=G; (инволютивность операции инвертирования) 
(4) 

(G1⊆G2)⇒(G
1
1
− ⊆G
1
2
− ); (монотонность отношения нестрогого включения относительно операции инвертирования) 
(5) 

 
Допр(G)=Дзн(G–1), Дзн(G)=Допр(G–1). 
(6) 

Если ⊗ – теоретико-множественная ф у н к ц и о н а л ь н а я  п е р е м е н н а я  с  н о м е н к л а т у р о й  {∪, ∩, \, ∆} [17, гл. I, § 5, п. 7, 
с. 52], то