Дискретная математика : основные теоретико-множественные конструкции. Ч.II
Покупка
Тематика:
Дискретная математика
Издательство:
Издательский Дом НИТУ «МИСиС»
Год издания: 2004
Кол-во страниц: 147
Дополнительно
Доступ онлайн
В корзину
Пособие представляет собой вторую часть раздела «Основные теоретикомножественные конструкции» учебного курса «Дискретная математика». В него входит описание такого фундаментального понятия современной математики, как график, и его отдельных видов: nграфик и семейства множеств, а также относящийся к ним логический и математический аппарат. Содержание пособия соответствует программе курса «Дискретная математика». Предназначено для студентов специальностей 220200 и 351400, изучающих учебные дисциплины «Математическая логика и теория алгоритмов» и «Дискретная математика».
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
- 03.03.01: Прикладные математика и физика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
ОГЛАВЛЕНИЕ От авторов .................................................................................................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], то
(G1⊗G2)−1= 1 1 G− ⊗ 1 2 G− . (перестановочность операций инвертирования и ⊗)3) (7) Определение 3. График G называют симметричным, если G⊆G-1. (8) Несложно доказать, что для симметричного графика G верно: G=G-1. (9) Это равенство рассматривают иногда как определение симметричного графика. Пример 1. Для графиков L1 и L2 из примера 1 в п. 2 имеем: L 1 1 − ={Λ, <0>, <2,1>, <1,2>, <4,3,3>}, а L 1 2 − ={Λ, <0>, <<2>, <1,2>>}. Ясно, что они не симметричны. С другой стороны, любой график, состоящий только из кортежей длины, меньшей 2, а так же, например, график {<a,b,c,b,a>} – симметричные. Очевидно, что (график G – диагональный) ⇒ (график G – симметричный). (10) 4. Присоединение Определение 1. Соединением графиков G1 и G2, р а с с м а т р и в а е м ы х в у к а з а н н о м п о р я д к е , называют и через [G1,G2] обозначают множество, состоящее только из всех с о е д и н е н и й вида [z1,z2], где z1∈G1, а z2∈G2 – см. [19, гл. II, § 2, п. 3, с. 89]. Таким образом, [G1,G2]=df εx{x: (∃z1∈G1, z2∈G2)(x=[z1,z2])}. (1) Очевидно, что [G1,G2] – график. Определение 2. Одноместную операцию, относящую паре <G1,G2> графиков G1 и G2 их соединение [G1,G2], называют присоединением графика G2 к графику G1 справа, или просто присоединением графиков, если из контекста ясно, о какой паре идет речь. *Несложно убедиться, что эта операция определена для любой пары графиков, функциональна, но вообще говоря, не инъективна [17, гл. I, § 4, п. 4, с. 36].* Операция присоединения графиков обладает какими-то свойствами и находится в определенных связях с другими операциями. Перечислим некоторые из них. Пусть G1, G2, G3 и G4 − графики. Тогда
[G1,{Λ}]=[{Λ},G1]=G1; (график {Λ} есть двусторонний нейтральный элемент относительно операции [,]) (2) [G1,∅]=[∅,G1]=∅; (пустой график есть двусторонний аннулятор относительно операции [,]) (3) [[G1,G2],G3]=[G1,[G2,G3]]; (ассоциативность операции [,]). (4) Ассоциативность позволяет нам вместо термов [[G1,G2],G3] и [G1,[G2,G3]] использовать их код [G1,G2,G3], вместо термов [[G1,G2], [G3,G4]] и [G1,[G2,[G3,G4]]] – их код [G1,G2,G3,G4] и т.д.; ([G1,G2] = [G1,G3]) ⇒ (G2=G3); (сократимость слева) (5) ([G2,G1] = [G3,G1]) ⇒ (G2=G3); (сократимость справа) (6) [G1,G2]-1=[G 1 2 − ,G 1 1 − ]; (антиперестановочность операций инвертирования и [,])3) (7) Обобщение равенства (7) – см. равенство (VI) из примечания 3 – может быть доказано методом математической индукции [14, с. 17 – 19]. Упражнения 1. Используя определение (1) из п. 1, докажите, что ∅ есть график. Доказательство Подставляя в указанное определение (G – график) ≡df (∀z∈G)(z – кортеж) константу ∅ на место свободной переменной G, получаем: (∅ – график)≡(∀z∈∅)(z – кортеж). Правая часть этой равносильности – соотношение, верное тривиальным образом. Стало быть, и ее левая часть: (∅ – график) – также верное соотношение. 2. Докажите, что всякий надграфик графика есть его расширение. Верно ли обратное утверждение? Доказательство В силу определения понятий надграфик и расширение графика первое есть частный вид второго. Обратное утверждение формулируется так:
любое расширение графика есть его надграфик. Оно неверно – см. ниже ответ к упр. 3. 3. Приведите пример расширения графика, не являющегося графиком. Ответ. Если G=df{Λ, 〈1〉, 〈1,2〉}, то множество H=df(G∪{1,2}) – расширение графика G, но не график, и поэтому не надграфик G. 4. Приведите примеры кографиков графика G=df{Λ, 〈0〉, 〈1,2〉, 〈〈1〉,〈2〉,3〉}. Ответ. Подграфики графика G таковы: G1=df∅, G2=df{Λ}, G3=df{〈1,2〉, 〈〈1〉,〈2〉,3〉} и т.д., а надграфики графика G следующие: G1=df(G∪{Λ}), G2=df(G∪{〈1,3〉, 〈2,4〉}) и т.п. Любой элемент из совокупности {G1, G2, G3, G1, G2} есть кографик графика G. 5. Может ли какой-либо график быть элементом некоторого графика? Ответ. Нет, не может, так как элементами любого графика служат кортежи, а не графики. 6. Приведите пример множества, содержащего некоторый график: 1) в качестве элемента; 2) в качестве подмножества. Ответ. Множество X=df{{〈a,b〉}, 〈a〉, 〈b,c〉, 〈a,b,c〉} содержит в качестве элемента график {〈a,b〉}, а в качестве подмножества – график {〈a〉, 〈b,c〉, <a,b,c〉}. 7. Покажите, что булеан графика не является графиком. Ответ. Элементами булеана графика являются множества, но отнюдь не кортежи. 8. Перечислите одинаковые и различные признаки понятий «множество» и «график». Ответ. Сходные признаки: оба понятия представляет собой множества. График является множеством отдельного вида. Таким образом, объем понятия «график» является частью объема понятия «множество». 9. Запишите на ЛМЯ определение графика над множеством, используя понятие к о р т е ж н а д м н о ж е с т в о м [19, гл. II, § 1, п. 3, с. 75]. Ответ: (G – график над множеством Х)≡df ≡df (∀z∈G)(z – кортеж над множеством Х). 10. 1) Докажите импликацию: (G=∅) ⇒ (G – график над ∅). (I)
2) Верно ли обратное утверждение? 11. 1) Верно ли утверждение: (G – график над множеством X) ⇒ (Допр(G), Дзн(G)⊆X)? (I) 2) Верно ли утверждение, обратное к (I)? Решение 1) Утверждение (I), вообще говоря, неверное – см. определения (1) и (2) из п. 2. Так, если G=df{Λ, 〈1,1〉}, то G – график над N, так как 〈1,1〉 – кортеж над N, а Λ есть по определению кортеж над любым множеством, в том числе и над ∅. Однако Допр(G)=Дзн(G)={Λ, 1}, но ⎤({Λ, 1}⊆N). 2) Утверждение, обратное к утверждению (I), таково: (Допр(G), Дзн(G)⊆X) ⇒ (G – график над множеством X). (II) Оно опровержимо. В самом деле, если G=df{〈1,∅,1〉} и X=N, то Допр(G)=Дзн(G)={1} и 1∈N, но <1,∅,1> не является кортежем над N, так как пр2〈1,∅,1〉=∅, а ∅∉N. 12. Покажите, что график L2={Λ, 〈0〉, 〈〈1,2〉, 〈2〉〉} не является графиком над N. 13. Докажите, что любой график есть график над некоторым множеством. Ответ. Любой график есть график над своим объемом, который является множеством. 14. Задайте о п и с а н и е м [19, гл. I, § 2, п. 3, с. 24] области определения и значений графика G длины, большей 1. Ответ: Допр(G)=εx{x: (∃z∈G)(пр1z=x)}, Дзн(G)=εy{y: (∃z∈G) (прl(z)z=y)}. 15. 1) Докажите, что у равных графиков области определений и значений равны. 2) Верно ли обратное утверждение? Ответ. 1) Первое утверждение, очевидно, верно. *Оно свидетельствует о том, что одноместные соответствия типов G→Допр(G) и G→Дзн(G) функциональны.* 2) Обратное утверждение формулируется так: если графики имеют одинаковые области определения и значений, то они равны. Оно опровержимо. В самом деле, пусть G1=df {〈a,b,a〉}, G2=df{〈a,c,a〉} и b≠c. Тогда Допр(G1) = Допр(G2)=Дзн(G1) = Дзн(G2)={a}, но G1≠G2. *Это утверждение говорит о том, что указанные выше одноместные функции не являются инъективными.*
Доступ онлайн
В корзину