Методические указания по дисциплине "дискретная математика" ( для студентов специальности 22. 01 )
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ДИСЦИПЛИНЕ "ДИСКРЕТНАЯ МАТЕМАТИКА" ( для студентов специальности 22.01 ) Утверждено на заседании кафедры ЭВМ протокол № 6 от ХХ.ХХ.ХХХХ Донецк ХХХХ УДК 681.973МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»(для студентов специальности 22.01) в 2-х частях. Составители : А.Ю.Иванов А.Г.Кравченко Ответственный за выпуск: В.В.Лапко ЧАСТЬ 1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ=================================================== ТЕОРИЯ МНОЖЕСТВ.Понятию множества нельзя дать строгого определения. Более общего понятия чем множество в математике не существует. Это - "совокупность, собрание, класс, семейство". Часто множество - несколько обьектов, обьедененных общим признаком. Например: - множество стульев в комнате; - множество атомов на Луне; - множество точек на данной окружности. Георг Кантор определил: "Множество - многое, мыслимое нами как единое". Предметы, составляющие множeство, называются элементами. Для указания того, что множeство А состоит из элементов х, у ...z пишут А={ х,у.... }. Например: множество арифметических действий состоит из элементов { сложения, вычитания, умножения, деления }. Tо, что элемент х принадлежит множеству А, записывают x A. Если не принадлежит x A. Например: если А - множество натуральных чисел, то 6 А, а вот 1.3 А. Если нужно символически записать фразу «множество A состоит из элементов a, обладающих свойством f», то принято писать:  .Символ |A| обозначает количество элементов во множестве A. Если множество содержит конечное число элементов, то оно конечно. Если множество содержит бесконечное число элементов - оно бесконечно (множество точек на окружности). Существует 2 способа задания множеств : 1) перечисление всех элементов множества (полный список элементов). Множество студентов группы. Этот способ применим только к конечным множествам. Первый способ основывается на аксиоме, называемой принципом обьемности (экстенсиональности): всякое множество определяется своими элементами, т.е. два множесва равны в том случае если они состоят из одних и тех же элементом. Например: 1)А={ 2,4,6 } В={ 2,4,6 } А=В 2)Пусть А - множество четных чисел, В - множество всех чисел равных сумме двух нечетных чисел. А и В - бесконечны. Если из x принадлежит А x принадлежит В и наоборот то А=В. Докажем это: x A x B x B x A x=2m=(2m-1)+1 x (2p-1)+(2z-1)=2(p+z-1) Следовательно: А=В. 1) Если нельзя указать множество с помощью списка - задается характеристическое свойство справедливое для всех элементов множества и только для них. Второй способ задания множеств основан на аксиоме, называемой принципом абстрактности(свертывания). Задание характеристических свойств иногда приводит к сложностям: - когда различные характеристические свойства задают одно и то же множество. Например: множество толстокожих животных, имеющих 2 бивня, совпадает с множеством толстокожих животных, имеющих хобот (слон). - из-за недостаточной четкости языка, неоднозначности человеческой речи. Например, не слишком четко определено множество лиц бесплатно проезжащих в ж/д транспорте. К этому множеству относятся дети до 7 лет. А если 7 лет исполнится в пути ? Множество не содержащее ни одного элемента называется пустым и обозначается 0 ( множество лошадей на Луне, множество действительных корней уравнения  .Оно нужно, когда множество задано своим характеристическим свойством и не известно зарание есть хоть один элемент с этим свойством. До сих пор неизвестно: пусто ли множество всех натуральных n, таких, что для n>2  имеет положительное целочисленные решения (теорема Ферма ). Если в пределах  проблемы расматриваются только множества, составленные из элементов некоторого множества, то множество U называется универсальным. В случае, если приходится рассматривать некоторое множество не самостоятельно, а как часть другого, более широкого множeства, говорят о подмножестве. Множество В является подмножеством А, если каждый элемент х из В является и элементом множества А. Записывается В А или А В. Можно говорить также, что B включено в А. Тогда В  А. - Если А В и А В, то говорят что А строго включено в В, или А - собственное подмножество В. Для включения нестрогого выполнимы следующие свойства: 1) А А (рефлексивность); 2) А В, В С А С (транзитивность); 3) А В, В А А = В (антисиметричность). Строгое включение обладает только свойством транзитивности. Нельзя смешивать отношения включения и принадлежности, т.к.отношение принадлежности не обладает свойствами рефлексивности и транзитивности. Справедливо: 0 A U; 0 A A. Определим, сколько подмножеств имеет конечное множество (в число подмножеств включим и пустое множество и само множество)? Множество состоящее из одного элемента а, имеет два подмножества О и { а }. Множество состоящее из 2-х элементов а и в имеет уже четыре подмножества: О, { а },{ в },{ а,в }. Множество из 3-х элементов кроме четырёх названых имеет еще 4 подмножества { с },{ а,с },{ в,с },{ а,в,с }. Поэтому множество, состоящее из n элементов, имеет всего  подмножеств. Подмножества можно классифицировать по числу входящих в них элементов. Если множества содержат n элементов то его подмножества состоящие из к элементов называются сочетаниями из n по к  Так как общее число подмножеств равно то  Если предположить 1 К n, то  Поэтому число выбраных сочетаний равно  .Теперь подсчитаем сколько сочетаний из элементов a1, ... an по к не содержит элемент an. Эти сочетания из элементов a1, ... an-1 . Так как в сочетание входят к элементов, то число таких сочетаний равно  Т.к. в каждое из  сочетаний элемент An либо входит,либо не входит, то утверждение доказано. Отметим, что  при любом n 0, т.к. каждое множество имеет лишь одно пустое подмножество; аналогично,  Пользуясь формулой можно подсчитать при n = 0, 1, 2, ...Такая таблица записывается в виде треугольника Паскаля.           Т.к.  =1, то на сторонах треугольника стоят 1. Остальные числа вычисляем по формуле, учитывая, что каждое число равно сумме чисел стоящих в предыдущей строке слева и справа от него. В результате получаем : 1  1 1  1 2 1  1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 |
Похожие:
 | Методические указания для студентов специальности Э. 01. 03. 00 «Экономика и управление на предприятии» Вычислительная техника и программирование. Методические указания для студентов-заочников специальности А. 29. 10. 00 «Строительство... | | Методические указания к практическим занятиям по дисциплине «бухгалтерский учет» для студентов специальности Методические указания к практическим занятиям по дисциплине «Бухгалтерский учет» / Сост.: Н. А. Адамов, Г. А. Амучиева; гуу. – М.,... |
| Методические указания и контрольные задания по курсу «Бухгалтерская финансовая отчетность» для студентов специальности 080109 «Бухгалтерский учет, анализ и аудит» Методические указания предназначены для студентов дневной и вечерней форм обучения | | Методические указания к курсовому проектированию по дисциплине "инновационный менеджмент" для студентов специальности "Менеджмент организации" 061100 Выполнение курсового проекта по дисциплине “Инновационный менеджмент” является важнейшим практическим этапом изучения дисциплины... |
| Методические указания по подготовке курсовых работ Москва 2002 утверждено Методические указания подготовлены для студентов, обучающихся по специальности 350 800 "Документоведение и документационное обеспечение... | | Методические указания для самостоятельной работы студентов по курсу Методические указания для самостоятельной работы по курсу «Бухгалтерский финансовый учет» тема «Учет операций по налогообложению... |
| Южно-Российский государственный технический университет (Новочеркасский политехнический институт) Шахтинский институт (филиал) Методические указания предназначены для студентов специальности 071900 «Информационные системы в технике и технологии». Методические... | | Методические указания к выполнению курсовой работы для студентов специальности 100110. 65 «Домоведение» Экономика домашнего хозяйства и окружающего социума: методические указания к выполнению курсовой работы / сост.: к филос н., доцент... |
| Методические указания по выполнению лабораторных работ для студентов специальности 220100 «эвм, системы, комплексы и сети» по дисциплине «организация ЭВМ и систем» Целью лабораторных работ является изучение структуры и принципов функционирования 8 разрядного процессора типа кр580ВМ80 | | Молчанов Сергей Валентинович, ст преподаватель каф. «ФиХ»; Волкова Валентина Константиновна, ст преподаватель каф. «ФиХ»; Молчанова Наталья Александровна, врач-биолог муз гбсмп. М 54 методические указания Методические указания предназначены для студентов дневной формы обучения, изучающих общую химию, в особенности для студентов I курса... |
| Федеральное агентство по образованию Российской Федерации южно-российский государственный технический университет Методические указания предназначены для студентов Шахтинского института (филиала) юргу (нпи) обучающихся по специальности «Триботехника»... |