|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ДИСЦИПЛИНЕ "ДИСКРЕТНАЯ МАТЕМАТИКА" ( для студентов специальности 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 ![]() ![]() В случае, если приходится рассматривать некоторое множество не самостоятельно, а как часть другого, более широкого множ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 . Так как в сочетание входят к элементов, то число таких сочетаний равно ![]() Т.к. в каждое из ![]() Отметим, что ![]() ![]() Пользуясь формулой можно подсчитать ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Т.к. ![]() 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 курса... |
![]() | Федеральное агентство по образованию Российской Федерации южно-российский государственный технический университет Методические указания предназначены для студентов Шахтинского института (филиала) юргу (нпи) обучающихся по специальности «Триботехника»... |