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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ  
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС» 

 

 
 
 

 

 

 

 
 

 

№ 2229 

Кафедра инженерной кибернетики

Ю.Ю. Прокопчук 
А.И. Широков 
В.А. Грузман 

Дискретная математика

Основные теоретико-множественные 
конструкции 

Часть VI 

Учебное пособие 

Под редакцией профессора Н.В. Крапухиной 

Допущено учебно-методическим объединением 
по образованию в области прикладной математики 
и управления качеством в качестве учебного пособия 
для студентов высших учебных заведений, обучающихся 
по направлению 231300 – Прикладная математика 

Москва  2013 

УДК 591.45 
 
П78 

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

Прокопчук, Ю.Ю. 
П78  
Дискретная 
математика : основные 
теоретико-множественные конструкции. Ч. VI : учеб. пособие / Ю.Ю. Прокопчук, 
А.И. Широков, В.А. Грузман ; под ред. Н.В. Крапухиной. – М. : 
Изд. Дом МИСиС, 2013. – 183 с. 
ISBN 978-5-87623-708-8 

Пособие представляет собой VI часть раздела «Основные теоретикомножественные конструкции дискретной математики».  
В гл. XI рассматриваются следующие понятия: композиции функций (§1); 
функции, обратные к данной (§2), и отображения (§3). В главе ХII рассматриваются многоместные функции. В §1 изучаются произвольные многоместные, 
в частности, n-местные функции, где n∈N+; свойства таких функций и построенные на их основе «функциональные» конструкции (такие как суперпозиция, парциальные подфункции и т.д.). В §2 исследуются многоместные алгебраические операции и их свойства, а также понятия «группоид» и его «главные элементы»; §3 посвящен лаконичному обзору бинарных алгебраических 
операций и построенных на их базе основных видов группоидов. В §4 рассматриваются задачи анализа и синтеза группоидов и иллюстрируются их решения.  
К каждому параграфу приведены упражнения, решения большинства 
из которых подробно разобраны. 
Содержание пособия соответствует программе курсов «Основы математической логики» и «Алгоритмы дискретной математики».  
Предназначено для студентов специальностей 220700, 230100, 230400, 
230700 и 231300. 

УДК 591.45 

ISBN 978-5-87623-708-8 
 
© Ю.Ю. Прокопчук, 
А.И. Широков, 
В.А. Грузман, 2013 

ОГЛАВЛЕНИЕ 

От авторов .............................................................................................5 
Введение................................................................................................6 
Примечания .......................................................................................7 
ГЛАВА XI. ФУНКЦИОНАЛЬНЫЕ КОНСТРУКЦИИ.........................8 
§1. Композиция функций.....................................................................8 
1. Теорема о значении композиции функций.................................8 
2. Теорема о тождественных композициях ....................................9 
Упражнения.......................................................................................9 
Примечания .....................................................................................17 
§2. Функции, обратные к данной ......................................................18 
1. Обратные, обратимые и необратимые объекты.......................18 
2. Инъекции .....................................................................................21 
3. Определение функций, обратных к данной..............................22 
4. Количественные и качественные  характеристики функций, 
обратных к данной..........................................................................23 
Упражнения.....................................................................................24 
Примечания .....................................................................................39 
§3. Отображения .................................................................................39 
1. Операции над отображениями, порожденные операциями над 
графиками........................................................................................40 
2. Ретракции и иссечения ...............................................................43 
*3. Теоремы о композициях отображений  с заданными 
свойствами.......................................................................................46 
Упражнения.....................................................................................47 
Примечания .....................................................................................63 
ГЛАВА XII. МНОГОМЕСТНЫЕ ФУНКЦИИ.....................................65 
§1. Определение многоместных функций и их свойства................65 
1. Кортежные графики и соответствия .........................................65 
2. Основные понятия и термины, относящиеся к многоместным 
функциям .........................................................................................67 
3. Свойства n-местных функций....................................................69 
4. Суперпозиция функций..............................................................71 
5. Частные, или парциальные, подфункции функции .................74 
Упражнения.....................................................................................77 
§2. Многоместные алгебраические операции..................................83 
1. Определение n-местных алгебраических операций. Группоиды. 
Терминология..................................................................................83 

2. Виды n-местных алгебраических операций и задание их 
двухстрочными таблицами ............................................................85 
3. Свойства алгебраических операций..........................................87 
*3.2.1 Нейтральные элементы группоидов..................................92 
*3.2.2. Аннулирующие элементы группоида.................................95 
Упражнения.....................................................................................98 
Примечания ...................................................................................114 
§3. Виды группоидов........................................................................117 
1. Идемпотентные группоиды .....................................................117 
2. Ассоциативные группоиды, или полугруппы. Ассоциаторы. 
Моноиды........................................................................................119 
3. Коммутативные группоиды.....................................................122 
4. Сократимые группоиды ...........................................................124 
5. Обратимые группоиды.............................................................129 
6. Примеры алгебраических структур.........................................135 
Упражнения...................................................................................138 
Примечания ...................................................................................171 
§4. Задачи анализа и синтеза группоидов ......................................172 
1. Анкета группоида. Задача анализа группоидов.........................172 
2. Задачи синтеза группоидов......................................................176 
Упражнения...................................................................................176 
Библиографический список.............................................................177 
Приложение 1....................................................................................179 
Приложение 2....................................................................................180 
 
 

 

 

 

 

 

 

 

 

Памяти 
Николая Евгеньевича 
Емельянова 

От авторов 

Данное пособие авторы посвящают светлой памяти Николая 
Евгеньевича Емельянова, профессора Московского института 
стали и сплавов (МИСиС), скончавшегося после тяжелой и продолжительной болезни 14 октября 2010 г. 
Н.Е. Емельянов работал на кафедре инженерной кибернетики 
(КИК) МИСиС с 1978 г. в должностях старшего преподавателя, 
доцента, а с 1989 до 2010 г. – профессора. На протяжении большого периода времени Николай Евгеньевич возглавлял (в частности, на кафедре ИК) научное направление, носящее название 
«Модели, методы и средства построения информационных систем». За цикл работ по этому направлению и их массовому внедрению Н.Е. Емельянов был удостоен в 1990 г. Государственной 
премии Совета Министров СССР. 
В период преподавания в МИСиС им было подготовлено более 1000 специалистов, работающих в отечественных и зарубежных организациях. Под его непосредственным руководством защищено шесть кандидатских диссертаций. Приказом министра 
образования России В.М. Филиппова от 18 ноября 2002 г. 
Н.Е. Емельянову было присвоено звание «Почетный работник 
высшего профессионального образования» и вручен нагрудный 
знак «За заслуги в области образования». 
Профессор Н.Е. Емельянов – автор более 180 научных и учебных публикаций, в том числе 4 монографий, 10 учебных пособий 
и 6 изобретений. 
Авторы данного труда работали рядом с Николаем Евгеньевичем в течение нескольких десятилетий. У них навсегда сохранились самые теплые воспоминания о нем как об эрудированном 
специалисте, прекрасном педагоге и, что особенно важно, в высшей степени доброжелательном товарище. 

Введение 

В серии наших трудов по дискретной математике [10020] впервые логически строгое определение одного из основных научных 
понятий – функции было сформулировано в пособии [17, стр.39]. 
Под функцией мы понимали соответствие [17, стр.13] с бинарным функциональным графиком [16, стр.98]. Это определение остается в силе и во всех последующих работах указанной серии. 
В публикации [17, стр.34] даны дефиниции основных классов 
функций, как-то: отображения, сюръекции, инъекции и биекции, 
и установлены некоторые связи между ними1). 
В книге [18] на базе понятий «инъекция», «биекция» и «упорядоченное множество», то есть множество, рассматриваемое вместе 
с заданным на нем отношением порядка [20, стр.96], вводится в рассмотрение и анализируется «количественная характеристика» множества – его мощность [18, стр.16-17]. Здесь же устанавливаются 
мощности множеств, наиболее часто используемых в математике 
и ее приложениях. В работе [19] начинается разностороннее и более 
глубокое, чем в перечисленных выше изданиях,  исследование видов 
и классов функций, которое продолжается и в данном пособии. Познакомимся с ним более подробно. 
В гл. XI дается представление об «основных функциональных конструкциях», то есть сложных математических объектах, главными составляющими которых являются функции. А именно, в §1 мы получаем результаты, разносторонне характеризующие уже известный нам предмет – 
композицию функций [17, стр.25]. На ее основе в §2 вводится 
в рассмотрение и обстоятельно анализируется такое важное математическое понятие как функция, обратная к данной (обратная функция). 
И, наконец, в §3 детально исследуется отдельный класс функций – отображения, который в классической математике2) [3, стр.398] отождествляется с совокупностью, состоящей только из всех функций3). Отметим, что в многотомном курсе «Основы математики» Н.Бурбакú, которого называют Эвклидом XX-го века, именно отображения, а не функции являются, с одной стороны, базовым предметом математики, а с 
другой – основным средством, при помощи которого исследуются математические объекты [12, стр.11]. 
Если в вышеупомянутой литературе изучаются только так называемые одноместные функции, то есть функции, «зависящие» лишь 
от одного аргумента [13, стр.44], то в гл. ХII рассматриваются их 

обобщения – многоместные функции, то есть такие, аргументами 
которых служат кортежи [13, стр.70]. Ознакомимся вкратце с ее содержанием. В §1 гл.ХII формулируются определения основных понятий, вводится соответствующая терминология, описываются способы 
задания многоместных функций и формулируются некоторые вспомогательные результаты. В §2 изучаются функции, относящиеся 
к отдельному виду многоместных функций – многоместным 
алгебраическим операциям, главным образом, к n-местным алгебраическим операциям, где n∈N+\{1}, то есть отображения типа 
Хn→Х, где Х – непустое множество [17, стр.13]. В §3 из гл.XII приведен лаконичный обзор бинарных алгебраических операций и построенных на их базе основных видов группоидов. И, наконец, в §4 
интерпретируются задачи анализа и синтеза группоидов, и иллюстрируются их решения. 
В каждом параграфе приведены упражнения, решения большинства из которых подробно разобраны. 
Некоторые фрагменты, отмеченные в начале и конце звездочками (*), содержат более трудный материал. Их включение в текст преследовало по меньшей мере следующие цели: а) сделать содержание 
книги более интересным для читателей с разными уровнями подготовки, например для тех, которые могли бы получить сведения, приведенные в этих фрагментах, из других источников; б) познакомить 
читателей с иными подходами и точками зрения на излагаемый материал. Указанные фрагменты можно пропустить при беглом чтении 
без ущерба для понимания последующего. 

Примечания 

1) Отметим, что совокупность указанных классов хотя и является 
строгой, но не представляет собой ни покрытия, ни попарно дизъюнктного семейства области, состоящей только из всех функций 
[16, стр.132 – 135]. 
2) Характерной чертой объектов, изучаемых в классической математике, является однозначность (с точностью до изоморфизма) 
их структур [3, стр.397, п.7]. 
3) Очевидно, что класс отображений является собственным подмножеством совокупности всех функций, так как каждое отображение является функцией, но отнюдь не всякая функция является отображением. Например, значение функции (1/х) типа R→R при х = 0 
не определенó. 

ГЛАВА XI. ФУНКЦИОНАЛЬНЫЕ 
КОНСТРУКЦИИ 

В этой главе мы детально проанализируем некоторые вопросы, связанные с двухместной операцией компонирования одноместных функций, 
и понятиями «обратная функция» и «отображение». При изложении мы 
будем использовать в основном материалы из монографий [3, стр.93–98] 
и [21, стр.209–212; 218–225], а также наших пособий [10–20]. 

§1. Композиция функций  

1. Теорема о значении композиции функций  

Пусть 

 
f=df<F,X,Y> 
(1) 

и 

 
g=df<G,U,V> 
(2) 

– функции [19, стр.9]. Из равенства (11) в п.3 §3 гл.V пособия 
[17, стр.26] следует, что соотношение  

 
(∀x∈X)[!(f°g({x})) ∧ !(g(f({x})) ⇒ ((f°g)({x})=g(f({x}))]1)  
(3) 

– верное. Из него и «условного равенства» вытекает следующая 
теорема: 

Теорема 1 (о значении композиции функций). 
Для любых функций вида (1) и (2) верно: 

 
(∀x∈X)[ (f°g)(x)=g(f(x)) ]2) 
(I) 

(см. упр.2). 
Пример 1. Пусть f и g – функции типа R→R, где R – множество, 
состоящее только из всех вещественных чисел [15, стр.14]. Согласно 
Теореме 1 композиция f°g функций f и g может быть задана конструктивной термальной формой (g(f(x)), где x∈R [13, стр.69]. 

f({x}) = 

{f(x)}, если x∈пр1F; 

∅, когда x∈Х\пр1F 

Таким образом, знакосочетания 

 
x→g(f(x)), y=g(f(x)) и h(x)= g(f(x)) 
 

задают в равной степени функцию f°g. 
Аналогичная картина имеет место и для бóльшего числа функций. 
Например, различные знакосочетания 

 
x→i(h(g(f(x)))), y=i(h(g(f(x)))) и z(x)=i(h(g(f(x)))) 
 

также изображают только одну функцию f°g°h°i, то есть являются 
синонимами [11, стр.48–49]. 
Пример 2. Терм y =df (log(sin(x2))) обозначает композицию f°g°h 
функций f(x)=x2, g(x)=sin(x) и h(x)=log(x). 
Несложно убедиться при помощи метода математической индукции [10, стр.16–18], что Теорема 1 верна и для любого конечного 
[18, стр.89–93], бóльшего двух, числа функций, а именно, имеет место следующее равенство:  

 
(f1° f2° … °fn)(x)=fn(…(f2(f1(x)))…),  
(4) 

где n∈(N+\{1}), доказательство которого приведено в упр.3. 

2. Теорема о тождественных композициях 

Чтобы доказать биективность функций, часто применяют следующую теорему3). 
Теорема 1 (о тождественных композициях). Пусть X и Y – множества, а f=df<F,X,Y>  и  g=df<G,Y,X> – функции. Если функции f°g 
и g°f – тождественные [19, стр.10], то f и g – биекции и 

 
g=f–1  
(1) 

(см. упр. 1). 

Упражнения 

Композиция функций  

1. Чем различаются соотношения  

 
(∀x∈X)(f°g)({x})=g(f({x})) 
 (I) 

и 

(∀x∈X)((f°g)(x)=g(f(x)))  
(II) 

[см. соотношение (3) из п.1 Теоретической части (ТЧ)]. 
Ответ. Если f и g – нефункциональные соответствия, то соотношение (I) осмысленно и верно, а соотношение (II) неосмысленно. 
Если же f и g – функции, то соотношения (I) и (II) осмысленны 
и равносильны. 
2. Докажите Теорему 1 (о значении композиции функций).  
Доказательство. Данная теорема формулируется так:  
Для любых функций вида (1) и (2) из ТЧ верно:  

 
(∀x∈X)[ (f°g)(x)=g(f(x)) ].  
(I) 

Любопытно, что существует ее доказательство, не опирающееся 
на соотношение (3) из ТЧ. Приведем его, считая, что пр2F=пр1G.  
В силу определений (1) и (2) из ТЧ имеем:  

 
f°g=< F°G, X, V >.  
(II) 

Пусть x∈X и !(f°g)(x). Предположим, что (f°g)(x)=z, то есть 

<x,z>∈F°G. Тогда существует такое y, что  

 
<x,y>∈F,  
(III) 

а 

 
<y,z>∈G. 
 (IV) 

Из принадлежности (III) получаем: f(x)=y, а из принадлежности 
(IV) – g(y)=z. Значит,  

 
g(f(x))=g(y)=z. 
 

С другой стороны, если x∈X и !g(f(x)), то положим, что g(f(x))=z. 
Очевидно, что из соотношения !g(f(x)) вытекает соотношение !f(x). 
Пусть f(x)=y. Тогда g(y)=g(f(x))=z. Отсюда легко выводятся принадлежности (III) и (IV), из которых и следует, что (f°g)(x)=g(f(x)), 

то есть <x,z>∈F°G.  
3. Докажите равенство (4) из п.1 ТЧ при помощи метода математической индукции [10, стр.16–18].  
Доказательство. Указанное равенство имеет вид:  

 
(f1° f2° … °fn)(x)=fn(…(f2(f1(x)))…),  
(I) 

где х – произвольная вещь4) из области определения функции f1. Докажем его методом математической индукции по переменной n∈N+, где 
n>1, обозначающей число компонируемых функций [10, стр. 16–18]. 
Итак, пусть х∈пр1F1, где F1 – график функции f1.  
1) При n=2 равенство (I) «принимает вид»:  

 
(f1°f2)(x) = (f2(f1(x))). 
(II) 

Оно верно в силу Теоремы 1 из п.1 ТЧ.  
2) Предположим, что при n=k, где k∈N и k≥2, равенство (I), принимающее вид 

 
(f1° f2° … °fk)(x)=fk(…(f2(f1(x)))…), 
 (III) 

верное, и покажем, что равенство  

 
(f1° f2° … °fk°fk+1)(x)=fk+1(…(f2(f1(x)))…) 
 (IV) 

также верное.  
Введем обозначение 

 
g =df (f1°f2°…°fk). 
 (V) 

Тогда равенство (IV) «принимает» такой вид: 

 
(g°fk+1)(x) = fk+1(g(x)).  
(VI) 

В этом уравнении «фигурируют» две функциональные переменные 
[13, стр.52]: g и fk+1. В силу справедливости соотношения (II) указанное 
уравнение - верное. Заменяя в формуле (VI) букву g на правую часть знакосочетания (V) и имея в виду правую часть равенства (III), получаем, что 
соотношение (IV) – верное, что и требовалось доказать. 
*4. Найдите критерий ( то есть необходимые и достаточные условия [2, т.3, стр.963, ст. «Необходимые и достаточные условия»]), 
которому должен удовлетворять фн-график F [16, гл.IV, стр.98], чтобы график F°F-1 был фн-графиком.  
Ответ. Для того чтобы композиция F°F-1 фн-графика F со своей 
инверсией F-1 являлась фн-графиком, необходимо и достаточно, 
чтобы график F был ин-графиком [16, Теорема 2, стр.101].  
Доказательство 
Необходимость. Предположим, что композиция F°F-1 фн-графика 
F со своей инверсией есть фн-график, и покажем, что F – фн-график. 
Допустим, что F не является ин-графиком. Это означает, что существуют такие предметы а,b∈пр1F и с∈пр2F, что  

а≠b, 
 (I) 

но  

 
<а,c>, <b,c>∈F.  
(II) 

Из принадлежности (II) имеем: <c,а>,<c,b>∈F-1. Отсюда и снова 
из (II) получаем: <a,а>,<a,b>∈F°F-1. В силу неравенства (I) график 
F°F-1 не является фн-графиком, что противоречит условию утверждения, которое мы доказываем.  
Достаточность. Пусть фн-график F является инъективным. Тогда график F-1 представляет собой фн-график (и ин-график). Поэтому 
F°F-1 – фн-график.  
*5. Найдите Критерий (см. упр.4), которому должна удовлетворять функция f, чтобы соответствие f°f-1 было функцией.  
Ответ. См. ответ к упр.4. Для того чтобы соответствие f°f-1 
было функцией, необходимо и достаточно, чтобы функция f была 
инъективной. 
6. Докажите или опровергните следующее утверждение:  

 
Если H – ин-график, а F – фн-график, то H°F – фн-график.  
(I) 

Ответ. Утверждение (I) – опровержимое.  
Доказательство  
Пусть а, b, с, d и e – попарно различные объекты. Ясно, что множества H=df{<a,b>, <a,c>} и F=df{<b,d>, <c,e>} – ин-график 
и фн-график соответственно, но график H°F={<a,d>, <a,e>} 
фн-графиком не является.  
7. Докажите, что в том частном случае, когда H=F-1, компози-
ция F-1°F представляет собой фн-график (см. упр.6). 
Доказательство. Покажем, что F-1°F – фн-график. Для этого 
достаточно установить следующую импликацию: 

 
[(<a,b>∈(F-1°F) ∧ <a,с>∈(F-1°F)] ⇒ [b=c]. 
 

Имеем 

 
<a,b>∈(F-1°F) ≡ ∃x[(<a,x>∈F-1) ∧ (<x,b>∈F)] ≡ 
 

 
≡ ∃x[(<x,a>∈F) ∧ (<x,b>∈F)] ⇒[a=b],  
 

так как по условию график F – функциональный.