Читать онлайн «Дискретная математика в тестах, упражнениях и задачах»

РОСЖЕЛДОР Государственное образовательное учреждение высшего профессионального образования «Ростовский государственный университет путей сообщения» (РГУПС) Самсонов Б. Б. , Филоненков А. И. ДИСКРЕТНАЯ МАТЕМАТИКА В ТЕСТАХ, УПРАЖНЕНИЯХ И ЗАДАЧАХ Учебное пособие Утверждено методическим советом университета Ростов-на-Дону 2008 УДК 519. 6 ББК 22. 1 Самсонов, Б. Б. Дискретная математика в тестах, упражнениях и задачах : учеб. по- собие / Б. Б. Самсонов, А. И. Филоненков ; Рост. гос. ун-т путей сообще- ния. – Ростов н/Д, 2008. – 163 с. : ил. , табл. , прил. – Библиогр. : 15 назв. В справочнике изложены теоретические сведения, тестовые задания, упражнения и задачи по дисциплине «Дискретная математика» согласно разделам Государственного образовательного стандарта (2000 г. ) для спе- циальностей 230101 и 230201. Предназначены для студентов, бакалавров и магистров компьютер- ных специальностей. Рецензенты: доц. Э. В. Тучков (СКЖД); д-р техн. наук, проф. С. М. Ковалёв (РГУПС) © Ростовский государственный университет путей сообщения, 2008 2  ВВЕДЕНИЕ В данной работе приведены справочные данные, тестовые задания, упражнения и задачи по всем разделам Государственного образовательно- го стандарта (2000 г. ) для специальности 230101. Более подробные сведения можно найти в [1–15]. Оглавление справочника соответствует названиям разделов ГОС. Более детальная рубрикация представлена в кодификаторе (прил. 1). Для контроля и самостоятельного изучения материала разработан 451 тест. Характеристики тестов приведены в прил. 2. Банк тестов разработан в соответствии с приказом проректора по учебной работе РГУПС. Кроме того, приведено более 600 вариантов задач и упражнений, которые можно использовать в курсовых и расчётно- графических работах. 1 МНОЖЕСТВА 1. 1 Элементы теории множеств Основные положения классической теории множеств приведены в табл. 1 и 2. В табл. 1 даны определения для отношений (, ) и операций с множествами ( , , , \, ). Здесь приняты следующие обозначения: x – произвольный элемент множества; А, В – некоторые множества; x A – элемент x принадлежит множеству A; xA – элемент x не принадлежит множеству A; → – логическое следование (импликация); ↔ – двустороннее следование (эквивалентность);  – логическое «И» (конъюнкция);  – логическое «ИЛИ» (дизъюнкция); В табл. 2 приводятся основные соотношения для операций булевой алгебры множеств ( , , U ). Здесь: 3  U – универсальное множество, содержащее все элементы;  – пустое множество, не содержащее ни одного элемента. Таблица 1 Отношения и операции на множествах Наимено- Сим- Соотношение Диаграмма вание вол Подмноже- A  B  ( x  A  x  B) ство  Равенство = A B A B B A Дополне- A x A  x A ние Пересече- x A  B  x A  x B ние  Объедине- x A  B  x A  x B ние  x  A \ B  x  A  x  B; Разность \ A\ B  AB x A  B  Симметри- ( x  A  x  B)  ческая  разность  ( x  B  x  A); A  B  ( A \ B)  ( B \ A) 4  Таблица 2 Свойства теоретико-множественных операций Свойство (закон) Соотношения Идемпотентность A  A  A, A  A  A Коммутативность A  B  B  A, A  B  B  A A  ( B  C )  ( A  B)  C, Ассоциативность A  ( B  C )  ( A  B)  C A  ( B  C )  ( A  B )  ( A  C ), Дистрибутивность A  (B  C )  ( A  B)  ( A  C ) Поглощение ( A  B )  A  A, ( A  B )  A  A Свойства  A    A, A     Свойства U A U U, A U  A Инволютивность A A Законы де Моргана A  B  A  B, A  B  A  B Свойства дополнения A  A U, A  A   Теоретико-множественные тождества, в частности, приведенные в табл. 1 и 2, доказываются по следующему алгоритму.