Дискретная математика : основные теоретико-множественные конструкции. Ч. VII
Покупка
Тематика:
Дискретная математика
Издательство:
Издательский Дом НИТУ «МИСиС»
Под ред.:
Крапухина Нина Владимировна
Год издания: 2010
Кол-во страниц: 128
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-87623-300-8
Артикул: 752833.01.99
Доступ онлайн
В корзину
Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое фундаментальное понятие современной математики, как n-местное (в частности, бинарное) отношение на множестве, а также излагается относящийся к нему логический и математический аппарат. Содержание пособия соответствует программам учебных курсов «Математическая логика и теория алгоритмов» и «Дискретная математика». Предназначено для студентов, обучающихся по специальностям 230401, 230102 и 080801 и изучающих данные учебные курсы.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.03: Механика и математическое моделирование
- 01.03.04: Прикладная математика
- 03.03.01: Прикладные математика и физика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ № 1221 Кафедра инженерной кибернетики Кафедра автоматизированных систем управления А.В. Козловский Ю.Ю. Прокопчук А.И. Широков Дискретная математика Основные теоретико-множественные конструкции Часть VII Учебное пособие Под редакцией профессора Н.В. Крапухиной Допущено УМО по образованию в области Прикладной математики и управления качеством в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 230400 «Прикладная математика» специальности 230401 «Прикладная математика» Москва Издательский Дом МИСиС 2010
УДК 510.8 К59 Р е ц е н з е н т д-р техн. наук, проф. Л.П. Рябов (МГГУ) Козловский А.В., Прокопчук Ю.Ю., Широков А.И. К59 Дискретная математика: Основные теоретико-множественные конструкции. Ч. VII: Учеб. пособие / Под ред. проф. Н.В. Крапухиной. – М.: Изд. Дом МИСиС, 2010. – 128 с. ISBN 978-5-87623-300-8 Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое фундаментальное понятие современной математики, как n-местное (в частности, бинарное) отношение на множестве, а также излагается относящийся к нему логический и математический аппарат. Содержание пособия соответствует программам учебных курсов «Математическая логика и теория алгоритмов» и «Дискретная математика». Предназначено для студентов, обучающихся по специальностям 230401, 230102 и 080801 и изучающих данные учебные курсы. УДК 510.8 ISBN 978-5-87623-300-8 © Козловский А.В., Прокопчук Ю.Ю., Широков А.И., 2010
ОГЛАВЛЕНИЕ Введение....................................................................................................5 Упражнения к разделу «Введение» ................................................7 Примечания.......................................................................................9 Глава XIII. Бинарные отношения на множествах................................10 § 1. Основные понятия...........................................................................10 1. Определение n-местного отношения, где n∈N+, на множестве...................................................................................10 2. Определение бинарного отношения на множестве. Терминология и обозначения........................................................11 3. Способы задания отношений.....................................................14 4. Свойства отношений и связи между ними...............................18 5. Действия над отношениями.......................................................19 Упражнения к § 1 главы XIII.........................................................28 Примечания.....................................................................................42 § 2. Простые, или элементарные, отношения ......................................43 1. Отношения, порожденные свойствами соответствий (корреспондентные отношения)....................................................43 2. Отношения типа рефлексивности .............................................44 3. Отношения типа симметричности ............................................48 4. Совершенные и связанные отношения.....................................50 5. Отношения типа транзитивности..............................................54 Упражнения к § 2 главы XIII.........................................................57 Примечания.....................................................................................87 Глава XIV. Сложные бинарные отношения. Задачи анализа и синтеза отношений .................................................................................89 § 1. Составные, или сложные, бинарные отношения..........................89 1. Введение......................................................................................89 2. Эквивалентность.........................................................................90 3. Толерантность.............................................................................93 4. Порядки .......................................................................................96 Упражнения к § 1 главы XIV.........................................................99 Примечания...................................................................................105 § 2. Задачи анализа и синтеза отношений ..........................................108 1. Анкета отношения. Задачи анализа отношений ....................108 2. Задачи синтеза отношений ......................................................111 Упражнения к § 2 главы XIV.......................................................111 Библиографический список.................................................................115
Приложение 1. Математические конструкции, построенные из бинарных графиков ..............................................................................117 1. Бинарные графики, или графики.............................................117 2. Понятия, связанные с понятием «композиция графиков»....118 Упражнения...................................................................................123 Примечания...................................................................................123 Приложение 2. Указатель знаков и обозначений ..............................124 Приложение 3. Указатель терминов ...................................................125
ВВЕДЕНИЕ 1. Как и многие элементы речи, слово «отношение» (или его синонимы «реляция», «связь» и т.д.) представляет собой полисем [13, с. 57–62]. В различных научных областях оно служит термином [7, с. 594, ст. «Термин»] для понятий, объемы и содержания [14, с. 7] которых вообще говоря различны, хотя и могут иметь общие черты. В философии и логике [2, с. 264, ст. «Отношение»; 7, с. 418, ст. «Отношение»] понятие «отношение» является категорией [14, с. 8], в которой в самом общем виде отражены взаимосвязи и взаимозависимости как между отдельными предметами, процессами, явлениями, так и их сторонами. Наличие отношений между объектами любой сферы действительности взаимообуславливает их существование и развитие. По мнению великого греческого мыслителя Аристотеля (384–332 до Р.Х.), человеческое познание состоит главным образом в выявлении необходимых связей между предметами [6, с. 216, ст. «Необходимость»; с. 217, ст. «Необходимые и достаточные условия»]. 2. Число n, где n∈N+, всех предметов, находящихся в данном отношении, называют его местностью, или арностью, а само отношение – n-местным, или n-арным. Приведем несколько примеров. При n = 1 реляцию называют унарной, или свойством. Предметы разносторонне характеризуются своими свойствами. Они выражают отношение предмета «к самому себе», независимо от того, в каких связях находится он с другими предметами. Так, свойство натурального числа «быть четным» не является следствием, вытекающим, например, из тех фактов, что другие являются четными или нет, хотя какие-то связи между четными числами имеют место – см. раздел «Упражнения к разделу «Введение»». При n = 2 отношение называют двухместным, или бинарным. Примерами таких отношений между людьми служат родственные (отец–сын), производственные (начальник–подчиненный), социальные (партия–партия) и т.д. связи. При n = 3 связь называют трехместной, или тернарной. Например, отношения между людьми «отец–мать–сын» и «начальник–его заместитель–подчиненные» – тернарные. 3. В математике изучаются как отношения между математическим объектами [14, с. 11], так и различного рода связи между отношениями. Примерами математических свойств являются следующие: быть простым – для натуральных чисел [20, гл. VII, § 1, Примечание 2; с. 76],
быть конечным – для множеств [20, гл. VII, § 3, п. 1; с. 45], быть пустым – для кортежей [17, гл. II, § 1, п. 3; с. 75] и т.д. Образцами бинарных реляций служат такие: быть не меньше, чем – для чисел, включаться – для множеств [17, гл. I, § 2, п. 4; с. 25], быть равными – для кортежей [17, гл. II, § 1, п. 4; с. 76]. Представителем тернарного отношения служит реляция находиться между для точек х,y,z∈R, где R – числовая прямая [20, гл. VII, с. 80]. Это отношение можно определить, например, так: Р(х,y,z) ≡df [(точка) y находится правее (точки) х и левее (точки) z], (1) что формально можно записать следующим образом: x < y < z. Это знакосочетание по определению равносильно такому соотношению: (x < y) ∧ (y < z), которое свидетельствует о том, что некоторые трехместные соотношения могут быть заменены комбинациями двухместных. Приведем, наконец, пример n-местной реляции. Ею служит отношение, изображаемое n-местной формулой [15, гл. II, § 1, п. 4; с. 61] Σi∈[1;n]mi ≥ 0, (2) где (∀i: 1 ≤ i ≤ n)(mi∈Z)1). 4. Как мы уже говорили в [21, Введение, п. 3; с. 5–6], современной математике присущ э к с т е н с и о н а л ь н ы й , или о б ъ е м н ы й , п о д х о д , который характеризуется тем, что некоторые понятия из различных наук уточняются, или эксплицируются [6, с. 367, ст. «Экспликация»], посредством определенных теоретико-множественных объектов2). Это позволяет иметь дело только с последними, а для них уже применимы все известные математические методы [14, с. 9, 1-й абзац]. Данный труд посвящен, в основном, изучению математической, а именно, теоретико-множественной модели общенаучного понятия отношение и его разновидностям.
5. Понятия множество и кортеж, изученные нами в главах I и II пособия [17], являются категориями [14, с. 8] современной математики, на основе которых могут быть «построены» теоретикомножественные конструкции «любой степени сложности». Простейшие среди них – множества кортежей (то есть графики) и кортежи множеств – подробно изучены в главах III и IV пособия [18]. 6. Сделаем краткий обзор представленного пособия. В главе XIII читатель получает сведения об отношениях на множествах. В её первом параграфе вводится в рассмотрение определение понятия n-местное отношение на множестве и его важнейшего частного вида – бинарного отношения, которое ниже мы называем просто отношением. Здесь же описываются способы задания отношений, а также связи между отношениями и операции над ними. В § 2 определяются основные элементарные, или простые, свойства отношений, и выявляются логические связи между этими свойствами. Первый параграф главы XIV посвящен изучению наиболее важных с прикладной точки зрения классов сложных, или производных, отношений: эквивалентности, толерантности и порядка. В соответствующем месте мы будем говорить о них более детально. И, наконец, в § 2 этой главы рассматриваются вопросы анализа и синтеза отношений. 7. Авторы благодарят Р.Е. Гун за большую помощь в работе над пособием. Упражнения к разделу «Введение» 1. Приведите несколько примеров логических связей между свойствами типа «n – четное число», где n∈N, и другими свойствами. Решение (1) а) Утверждение если n – четное число, а m∈N, то n⋅m – четное число (I) – верное. *Таким образом, множество Nч, состоящее только из всех натуральных четных чисел, представляет собой идеал алгебры <N, ⋅> [10, с. 107].* б) Обратное к утверждению (I) предложение любое четное число, например r, может быть представлено в виде: r = n⋅m, m∈N, где по меньшей мере одно из чисел m,n – четное – справедливое.
Доказательство Поскольку r – четное число, то в силу своего определения оно может быть представлено в виде: r = 2⋅t, где t∈N. (2) а) Утверждение если m и n – четные числа, то (m + n), (m ⋅ n) и (m ÷ n) – четные числа – правильное. Таким образом, множество Nч замкнуто [21, с. 89, Определение 2] относительно бинарных операций сложения, умножения и частичного вычитания3) натуральных чисел. б) Утверждение если r – четное число, то существуют такие четные числа m и n, что r = m + n и r = m ÷ n – верное. *Оно свидетельствует о том, что бинарные операции + и ÷ типа Nч × Nч → Nч – сюръективные [19, с. 33, Определение 1].* Доказательство Пусть r∈Nч. Тогда верно равенство r = r + 0 = r ÷ 0, но 0 – число четное. в) Утверждение если r – четное число, то существуют такие ч е т н ы е ч и с л а m и n, что r = m ⋅ n (II) – выполнимое и опровержимое. Доказательство Пусть r – четное число. Тогда r = 2⋅q, где q∈N. Если q – четное число, то утверждение (II) – верное, так как q = 2⋅s, где s∈N, и поэтому r = 2⋅(2⋅s). Если же q – нечетное число, то утверждение (II) – ложное. *Таким образом, операция умножения типа Nч × Nч → N не является, вообще говоря, сюръективной [19, с. 33, Определение 1].* (3) Утверждение каждое натуральное число, например, n, может быть представлено в виде n = 2m⋅r, где m∈N, (III) – верное, так как n = 20⋅n. Обратное к утверждению (III) предложение любое число вида 2m⋅r, где m∈N+, а r∈N, – натуральное
– очевидно, справедливое. (4) Утверждение каждое натуральное положительное число n может быть представлено в виде n = 2m⋅p, где m∈N, а р – п р о с т о е ч и с л о (IV) – неверное, поскольку, например, число 18 = 2⋅32 не имеет указанного представления. Конверсия утверждения (IV): любое число указанного вида – натуральное – очевидно, справедливая. (5) Утверждение (∀n∈N)[(n – четное число) ⊕ (n – нечетное число)] – несомненно правильное. Примечания 1) Отметим, что хотя для любого n∈N+ существует n-местное отношение – см., например, формулу (2), «Евклид ХХ века» Н. Бурбаки считает, что при построении современных математических теорий можно ограничиться рассмотрением (по-видимому, в качестве исходных) только бинарных отношений [3, с. 35]. Например, отношение Р(x, y, z), изображенное правой частью определения (1), может быть представлено так: (x < y) ∧ (y < z), то есть через конъюнкцию бинарных соотношений x < y и y < z. 2) Так, логическое понятие «свойство» отождествляется с вполне определенной совокупностью, а именно – его областью определения – см. [17, гл. I, Приложение 1; с. 42–43]. 3) Бинарная операция частичного вычитания на множестве N, обозначаемая знаком ÷, определяется так: m n, если m n, m n 0, если m n. − ≥ ⎧ ÷ = ⎨ < ⎩
ГЛАВА XIII. БИНАРНЫЕ ОТНОШЕНИЯ НА МНОЖЕСТВАХ § 1. Основные понятия 1. Определение n-местного отношения, где n∈N+, на множестве Напомним необходимые в этой главе понятия, обстоятельно проанализированные нами в пособии [19, гл. V, § 1, с. 6–8]. Определение 1. Пусть n∈N+, а Y =df (Xi)i∈[1,n] (1) – кортеж множеств. Пару вида 〈Φ, Y〉, где Φ⊆Пi∈[1,n]Xi, называют n-местным, или n-арным, отношением (syn. n-местной, или n-арной, реляцией) на кортеже множеств (1), или между множествами кортежа (1). Реляцию обычно обозначают строчной буквой из второй половины греческого алфавита. Допустим, что ϕ =df 〈Φ, Y〉 (2) – реляция. Кортеж множеств (1) называют её носителем, а n-график Φ [18, с. 23, Определение 1], – графиком. Он представляет собой вполне определенную совокупность (быть может, пустую), кортежей длины n, или энок [17, гл. II, § 1, п. 3; с. 75]. Примеры n-местных реляций между множествами кортежей приведены в упр. 1 из п. 1 раздела «Упражнения к § 1 главы XIII». Если для компонент кортежа (1) выполнено условие (∀i∈[1;n])(Хi = Х), то Пi∈[1;n]Xi = Xn – см. [18, гл. III, § 3, п. 3; с. 49], а дефиниция (2) приобретает такой вид: ϕ =df <Φ, Xn>, или, допуская вольность в обозначениях, ϕ =df 〈Φ, X〉, (3)
где Φ⊆Xn. Определение 2. Отношение (реляцию) вида (3) называют nместным, или n-арным отношением (syn. n-местной, или n-арной реляцией) на множестве Х. 2. Определение бинарного отношения на множестве. Терминология и обозначения Из формулы (3) в п. 1 при n = 2 получаем: ϕ =df < Φ, X>, (1) где Φ⊆X2. Определение 1. Отношение, или реляцию, вида (1) называют бинарным, или двухместным, отношением (syn. бинарной, или двухместной, реляцией) на множестве Х1). Пример 1. Следующие реляции получаются при интерпретации, или конкретизации [16, гл. III, § 2, п. 1; с. 26], отношения (1) путем фиксирования его графика: 1) OX =df 〈∅, X〉; 2) EX =df 〈ΔX 2, X〉; 3) NEX =df 〈X2\ΔX 2, X〉; 4) PX =df 〈X2, X〉. Они носят следующие имена соответственно: 1) пустая; 2) равенства, или диагональная, или тождественная; 3) неравенства, или антидиагональная; 4) полная, или универсальная. Бинарные отношения, или реляции, на множестве являются основным предметом изучения в этой и следующей главах. Поэтому на всем протяжении последних именно их, для краткости речи и пренебрегая полисемией [13, с. 57], мы будем называть просто отношениями, или реляциями, и только о них вести разговор2). Легко видеть, что понятие реляция является отдельным видом понятия соответствие [19, с. 8]. Поэтому относящиеся к нему обозначения и терминология [19, с. 8] могут быть использованы и для наименования объектов, разносторонне характеризующих реляцию, разумеется, с учетом ее специфики. Познакомимся с ними. Итак, в силу Определения 1 из п. 1, отношение, или реляция, – это пара [17, с. 75], например, вида (1). Её первая компонента есть часть
декартова произведения [18, с. 48] второй компоненты (необходимо являющейся множеством) на себя (декартового квадрата множества Х). Множество Φ, представляющее собой бинарный график [18, с. 90], называют графиком реляции (1), а множество Х (Х, пр1Φ и пр2Φ) – её областью отправления, или носителем (соответственно, областью прибытия, областью определения и областью значений) и обозначают через Дотпр(ϕ) (соответственно, Дпр(ϕ), Допр(ϕ) и Дзн(ϕ)). Пусть Ф – график реляции (1), а х,у∈Х. Если принадлежность <x, y>∈Ф (2) – верная, то говорят, что (объект) х находится в отношении ϕ (с объектом) y. Пример 2. См. пример 1. Любой элемент х∈Х находится в отношениях равенства (самому себе) и полного, так как справедливы принадлежности <x,x>∈ 2 x Δ и <x,x>∈Х2 соответственно. При условии, что х∈пр1Ф, высказываются так: (реляция) ϕ определена для (предмета) х, и этот факт обозначают знакосочетанием !ϕ(х), или !Фϕ(х), или просто !Ф(х), когда из контекста ясно, о какой реляции идет речь. Ситуацию, когда у∈пр2Ф, выражают предложением (объект) у есть значение, принимаемое (реляцией) ϕ, которое стенографируют так: !ϕ–1(y), или !Фϕ –1 (y), или просто !Ф–1(y) [18, с. 90–91]3). Таким образом, !ϕ(х) ≡df (х∈пр1Ф), !ϕ–1(у) ≡df (у∈пр2Ф). Определение 2. Множество ε<x,y>{<x,y>∈X2: <x,y>∈Ф} (ε<x,y>{<x,y>∈X2: <x,y>∉Ф}), состоящее только из всех пар, принадлежащих (соответственно, не принадлежащих) графику Ф, называют областью истинности (со
Доступ онлайн
В корзину