ПРОГРАММА Дисциплина: « ДИСКРЕТНАЯ МАТЕМАТИКА С ЭЛЕМЕНТАМИ МАТЕМАТИЧЕСКОЙ ЛОГИКИ» Специальность: «Информационные системы и программирование»рабочая программа

ПРОГРАММА Дисциплина: «ЕН.02 ДИСКРЕТНАЯ МАТЕМАТИКА С ЭЛЕМЕНТАМИ МАТЕМАТИЧЕСКОЙ ЛОГИКИ» Специальность: 09.02.07 «Информационные системы и программирование»
рабочая программа

Настоящая образовательная программа учебной дисциплины ЕН.02 «Дискретная математика с элементами математической логики» предназначена для ее изучения в учреждении профессионального образования КГБ ПОУ ХПЭТ, реализующего образовательную программу среднего (полного) общего образования, при подготовке специалистов среднего звена по специальности среднего профессионального образования 09.02.07 «Информационные системы и программирование» (далее – ПООП СПО, программа). Программа разработана на основе федерального государственного образовательного стандарта среднего профессионального образования (ФГОС СПО) по специальности 09.02.07 «Информационные системы и программирование», утвержденного приказом Министерства образования и науки от 9 декабря 2016 года № 1547 (зарегистрирован Министерством юстиции Российской Федерации 26 декабря 2016г. , регистрационный № 44936 ) (далее – ФГОС СПО).

ПООП СПО определяет рекомендованный объем и содержание среднего профессионального образования по специальности 09.02.07 «Информационные системы и программирование», планируемые результаты освоения образовательной программы, примерные условия образовательной деятельности.

ПООП СПО разработана для реализации образовательной программы на базе среднего общего образования.

Образовательная программа, реализуемая на базе основного общего образования, разрабатывается образовательной организацией на основе требований федерального государственного образовательного стандарта среднего общего образования и ФГОС СПО с учетом получаемой специальности 09.02.07 «Информационные системы и программирование» и настоящей ПООП.

1.2. Нормативные основания для разработки ПООП:

Федеральный закон от 29 декабря 2012 г. №273-ФЗ «Об образовании в Российской Федерации»;
Приказ Минобрнауки России от 28 мая 2014 г. № 594 «Об утверждении Порядка разработки примерных основных образовательных программ, проведения их экспертизы и ведения реестра примерных основных образовательных программ»;
Приказ Минобрнауки России от 9 декабря 2017 года № 1547 «Обутверждении федерального государственного образовательного стандарта среднего профессионального образования по специальности 09.02.07 «Информационные системы и программирование» (зарегистрирован Министерством юстиции Российской Федерации 26 декабря 2016 г. , регистрационный № 44936 );
Приказ Минобрнауки России от 14 июня 2013 г. № 464 «Об утверждении Порядка организации и осуществления образовательной деятельности по образовательным программам среднего профессионального образования» (зарегистрирован Министерством юстиции Российской Федерации 30 июля 2013 г., регистрационный № 29200) (далее – Порядок организации образовательной деятельности);
Приказ Минобрнауки России от 16 августа 2013 г. № 968 «Об утверждении Порядка проведения государственной итоговой аттестации по образовательным программам среднего профессионального образования» (зарегистрирован Министерством юстиции Российской Федерации 1 ноября 2013 г., регистрационный № 30306);
Приказ Минобрнауки России от 18 апреля 2013 г. № 291 «Об утверждении Положения о практике обучающихся, осваивающих основные профессиональные образовательные программы среднего профессионального образования» (зарегистрирован Министерством юстиции Российской Федерации 14 июня 2013 г., регистрационный № 28785).
Приказ Министерства труда и социальной защиты Российской Федерации от 18 ноября 2013 года № 679н, "Об утверждении профессионального стандарта 06.001 Программист" (зарегистрирован Министерством юстиции Российской Федерации 18 декабря 2013 года, рег.№ 30635);
Приказ Министерства труда и социальной защиты Российской Федерации от 17 сентября 2014 года № 225н "Об утверждении профессионального стандарта 06.004 Специалист по тестированию в области информационных технологий" (зарегистрирован Министерством юстиции Российской Федерации 9 июня 2014 года, рег.№ 32623);
Приказ Министерства труда и социальной защиты Российской Федерации от 11 апреля 2014 года № 647н "Об утверждении профессионального стандарта 06.011 Администратор баз данных" (зарегистрирован Министерством юстиции Российской Федерации 24 ноября 2014 года, рег.№ 34846);
Приказ Министерства труда и социальной защиты Российской Федерации от 8 сентября 2014 года № 629н "Об утверждении профессионального стандарта 06.013 Специалист по информационным ресурсам" (зарегистрирован Министерством юстиции Российской Федерации 26 сентября 2014 года, рег.№ 34136);
Приказ Министерства труда и социальной защиты Российской Федерации от 18 ноября 2014 года № 896н "Об утверждении профессионального стандарта 06.015 Специалист по информационным системам" (зарегистрирован Министерством юстиции Российской Федерации 24 декабря 2014 года, рег.№ 35361);
Приказ Министерства труда и социальной защиты Российской Федерации от 8 сентября 2014 года № 612н "Об утверждении профессионального стандарта 06.019 Технический писатель" (зарегистрирован Министерством юстиции Российской Федерации 3 октября 2014 года, рег.№ 34234);
приказ Министерства труда и социальной защиты Российской Федерации от 18 января 2017 г. № 44н "Об утверждении профессионального стандарта 06.035 Разработчик web и мультимедийных приложений"(зарегистрирован Министерством юстиции Российской Федерации 31 января 2017 года, рег.№ 45481).

Читайте так же:

Бесплатные программы для удаления троянов и вирусов

Программа содержит: паспорт примерной программы учебной дисциплины, структуру и примерное содержание учебной дисциплины, содержание учебной дисциплины, тематический план на 36 часов, контроль и оценку результатов освоения учебной дисциплины. При освоении специальности 09.02.07 «Информационные системы и программирование» дисциплина «Дискретная математика с элементами математической логики» изучается как профильный (базовый) учебный предмет в объеме 36 часов.

Программа ориентирована на достижение следующих целей:

Освоение системы базовых знаний, отражающих вклад элементов математической логики в формирование современной научной картины мира;
Овладение умениями применять, анализировать, формулировать задачи логического характера и применять средства математической логики для их решения , в том числе при изучении других дисциплин;
Развитие познавательных интересов, интеллектуальных и творческих способностей путем освоения и использования методов математической логики при изучении различных учебных предметов;
Воспитание ответственного отношения к выполнению поставленных задач.

Основу программы составляет содержание, согласованное с требованиями федерального компонента государственного стандарта среднего (полного) общего образования базового уровня.

Содержание программы представлено темами:

Раздел 1 Основы математической логики

Раздел 2 Элементы теории множеств

Раздел 3 Логика предикатов

Раздел 4 Элементы теории графов

Раздел 5 Элементы теории алгоритмов

Каждая тема включает в себя теоретический и практико-ориентированный материал, реализуемый в форме практических работ.

При усвоении программы у обучающихся формируется информационно-коммуникационная компетентность – знания, умения, навыки по решению задач по дискретной математике с элементами математической логики, необходимые для изучения других общеобразовательных предметов, для их использования в ходе изучения специальных дисциплин профессионального цикла, в практической деятельности и повседневной жизни.

Выполнение практических работ обеспечивает формирование у обучающихся умений собирать данные для анализа использования и функционирования компьютерных систем и комплексов, взаимодействовать со специалистами смежного профиля при разработке методов, средств и технологий применения объектов профессиональной деятельности для профессионального роста.

В программе учтены особенности содержания обучения по профессиям и специальностям в учреждении.

Программа содержит примерную тематику учебных проектов для организации самостоятельной деятельности обучающихся в процессе изучения дискретной математики с элементами математической логики.

В программе учреждение уточняет последовательность изучения учебного материала, виды самостоятельной работы обучающихся, профессионально значимый материал, распределение учебных часов с учетом профиля получаемого профессионального образования.

Паспорт программы учебной дисциплины «ЕН.02. Дискретная математика с элементами математической логики»

Область применения учебной программы

Программа учебной дисциплины является частью подготовки математического и общего естественнонаучного цикла в соответствии с ФГОС по специальностям 09.02.07 «Информационные системы и программирование»

Место дисциплины в структуре основной профессиональной образовательной программы.

Учебная дисциплина «Дискретная математика с элементами математической логики» принадлежит к математическому и общему естественнонаучному циклу (ЕН.00), изучается как базовая учебная дисциплина при освоении специальности технического профиля 09.02.07 «Информационнрые системы и программирование» в учреждениях в 4 семестре на 2 курсе, обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом, содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления.

Цель и планируемые результаты освоения дисциплины:

ОК 01 Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам

ОК 02 Осуществлять поиск, анализ и интерпретацию информации, необходимой для выполнения задач профессиональной деятельности

ОК 04 Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.

ОК 05 Осуществлять устную и письменную коммуникацию на государственном языке с учетом особенностей социального и культурного контекста.

ОК 09 Использовать информационные технологии в профессиональной деятельности

ОК 10 Пользоваться профессиональной документацией на государственном и иностранном языках.

Применять логические операции, формулы логики, законы алгебры логики.

Формулировать задачи логического характера и применять средства математической логики для их решения .

Основные принципы математической логики, теории множеств и теории алгоритмов.

Лекция 14. Предмет дискретной математики. Место и роль дискретной математики в системе математических наук и в решении задач, связанных с обеспечением информационной безопасности

В последние годы инженеры-математики, занимающиеся прикладными исследованиями, все больше используют аппарат дискретной математики. Это объясняется необходимостью создания и эксплуатации современных ЭВМ, средств передачи и обработки информации, автоматизированных систем управления и проектирования.

С прикладной точки зрения интерес к функциям алгебры логики основан на том, что вся современная электроника (в т. ч. компьютерная) – цифровая 0-1 электроника. Успехи, достигнутые в этой области, позволили применять 0-1 электронику и там, где, казалось, должна была вечно господствовать континуальная электроника – в радиовещании и телевидении. Аудио и видеозапись высокого качества, в том числе и системы телевидения высокого разрешения, лазерные проигрыватели и т. п. – это тоже системы 0-1 электроники.

Читайте так же:

Блокировка сайтов для детей программа

В настоящее время в учебных планах различных инженерных специальностей появилась дисциплина “Дискретная математика“.

Дискретная математика – самостоятельное направление современной математики. Она изучает математические модели объектов, процессов, зависимостей, существующих в реальном мире, с которыми имеют дело в технике, информатике и других областях знаний.

Дискретная математика, или дискретный анализ – область математики, которая занимается исследованием структур и задач на конечных множествах. Поэтому в качестве синонима иногда используется термин «конечная математика». Можно считать общепринятым деление математики на непрерывную и дискретную. Последняя представляет собой важное направление, имеющее характерные для него предмет исследований, методы и задачи. Специфика задач дискретной математики в первую очередь предполагает отказ от основных понятий классической математики – предела и непрерывности. Поэтому для задач дискретной математики обычные средства классического анализа являются вспомогательными.

Дискретная и непрерывная математика взаимно дополняют друг друга. Понятия и методы одной часто используются в другой. Один и тот же объект может рассматриваться с двух точек зрения и в зависимости от этого выбирается непрерывная или дискретная математика.

При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются дискретные методы формализованного представления, являющиеся предметом рассмотрения в дискретной математике. К ним относятся методы, основанные на теоретико-множественных представлениях, графы, алгоритмы, математическая логика и др.

Дискретная математика предлагает:

· универсальные средства (языки) формализованного представления;

· способы корректной переработки информации, представленной на этих языках;

· возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей.

Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специалистам в области информатики.

Множество — это одно из основных понятий математики, как дискретной, так и непрерывной. Оно не определяется через другие понятия. Содержательно, под множеством понимается некоторая совокупность элементов. Основное отношение между элементами и множеством — это отношение принадлежности элемента множеству. Оно обозначается знаком означает, что элемент x принадлежит множеству A. означает, что элемент x не входит в множество A. означает, что каждый элемент множества A является также элементом множества B. В этом случае множество A называетсяподмножеством множества B. Если и то A=B, т.е. множества A и B равны. Если и то A называется собственным подмножеством множества B, и в этом случае пишем Множество, не содержащее элементов, называется пустым и обозначается .

Обычно множества обозначаются с помощью пары фигурных скобок, в которые заключены их элементы. Небольшие множествазадаются прямым перечислением всех элементов. Например, множество простых чисел, не превосходящих 10, это <2, 3, 5, 7>; множество (имен) летних месяцев: <июнь, июль, август>. В описаниях "больших" конечных множеств используют многоточие. В них часто указывается несколько первых элементов и последний элемент множества. Например, множество целых неотрицательных чисел, не превосходящих 100, записывают как <0, 1, 2, . , 100>, множество всех месяцев года — как < январь, февраль, . декабрь>. Такое задание требует определенной аккуратности. Например, если некоторое множество Aзадано как <3, 5, 7, . , 19>, то не ясно, является ли A множеством нечетных чисел, лежащих в интервале от 3 до 19, или это множество простых чисел из того же интервала (возможны и другие его расшифровки). Перечисления элементов бесконечных множеств начинаются несколькими начальными элементами, а завершаются многоточием. При этом часто указывают общий вид элемента задаваемого множества. Основное бесконечное множество, рассматриваемое в дискретной математике, этомножество всех натуральных чисел N= <1, 2, 3, . >. Множество всех квадратов этих чисел можно задать, например, так: <1, 4, 9, . n 2 , . >.

Как мы уже отметили, большие множества не всегда можно точно определить, используя перечисление с многоточием. Основной способ их описания имеет вид: < Elem | условие на Elem>, где Elem — это общий вид элемента определяемого множества, а после вертикальной черты описано условие, которому этот элемент должен удовлетворять. Например, — это множество целых чисел в интервале от 10 до 1000, — множество квадратов натуральных чисел, — множество всех простых чисел.

Множества, элементами которых являются другие множества, часто называют семействами или классами. Семейство ( множество ) всех подмножеств множества A обозначается через 2 A , т.е. Например, если A=< 0, 1, <2,3>>, то а дляпустого множества семейство его подмножеств

Читайте так же:

В какой программе нарисовать схему помещения

Битовые операции

«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.

В булевой логике: <displaystyle land data-lazy-src=

» width=»» height=»» />

В языке C: &

Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.

«(Логическое) НЕ» (not), инвертирование — аналог

Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.

«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.

В булевой логике: <displaystyle lor data-lazy-src=

» width=»» height=»» />

В языке C: |

Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.

Исключающее ИЛИ

«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.

В булевой логике: <displaystyle oplus data-lazy-src=

» width=»» height=»» />

В языке C: ^

Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся .

В Операции от многих аргументов

Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).

Прочие бинарные операции

«ИЛИ-НЕ» (nor), она же «стрелка Пирса».

В булевой логике: <displaystyle downarrow data-lazy-src=

» width=»» height=»» />

Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.

«И-НЕ» (nand), она же «штрих Шеффера».

В булевой логике: <displaystyle mid data-lazy-src=

» width=»» height=»» />

Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое <displaystyle leq data-lazy-src= » width=»» height=»» /> (меньше или равно).

Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.

Сводная таблица истинности булевых операций

Операции над битовыми векторами

Обобщение операций на булеву алгебру

Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов (в программировании их называют регистрами), например, , где N — количество битов в регистре.

Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операция от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т.д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в Битовые сдвиги

К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.

Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).

Арифметический сдвиг (правый)

Циклический сдвиг через перенос

Логический сдвиг

При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.

Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.

Арифметический сдвиг

Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.

Циклический сдвиг

При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).

Также различают циклический сдвиг через бит переноса — при нем первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.

2-адическая интерпретация

Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории . Множество целых 2-адических чисел (т.е. произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в Практические применения

Физическая реализация битовых операций

Наиболее распространены транзисторно-транзисторная логика и Схемы аппаратной логики

Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет Использование в программировании

Благодаря реализации в схеме языках низкого уровня , а также в Примечания

Дискретная математика

Дискретная математика. Часть 1: Учебное пособие. − Томск: Томский межвузовский центр дистанционного образования, 2000. − 106 с.

Учебное пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем управления ТУСУР 17 мая 1999 г.

Томский межвузовский центр дистанционного образования, 2000

1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ.

1.1 Основные определения.

1.2 Операции над множествами.

1.3 Отношения на множествах.

1.4 Экстремальные элементы множеств.

1.5 Отображения множеств.

1.6 Задачи и упражнения.

2 ОСНОВЫ ТЕОРИИ ГРАФОВ.

2.1 Основные определения.

2.1.1 Общие понятия.

2.1.2 Ориентированные и неориентированные графы .

2.1.3 Цепи, циклы, пути и контуры графов.

2.1.4 Конечный и бесконечный графы.

2.1.5 Частичные графы, подграфы, частичные подграфы.

2.1.6 Связность в графах .

2.1.7 Изоморфизм. Плоские графы.

2.2 Отношения на множествах и графы.

2.3 Матрицы смежности и инциденций графа.

2.4 Операции над графами.

2.5 Степени графов.

2.5.1 Степени неориентированных графов.

2.5.2 Степени ориентированных графов.

2.6 Характеристики расстояний в графах.

2.7 Определение путей и кратчайших путейв графах.

2.7.1 Алгоритм определения пути в графе .

2.7.2 Алгоритм определения кратчайших путей в графе.

2.8.1 Эйлеровы цепи, циклы, пути, контуры.

2.8.2 Гамильтоновы цепи, циклы, пути, контуры.

2.9 Характеристики графов.

2.10 Задачи и упражнения.

3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.

3.1 Алгебра высказываний.

3.2 Булевы функции.

3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формы

3.4 Полнота системы булевых функций.

3.5 Минимизация дизъюнктивных нормальных форм.

3.5.1 Основные определения.

3.5.2 Этапы минимизации ДНФ .

3.5.3 Минимизация ДНФ методом Квайна.

3.6 Автоматные описания.

3.7 Синтез комбинационных схем.

3.8 Логика предикатов.

3.8.1 Предикаты и операции квантирования.

3.8.2 Равносильные формулы логики предикатов

3.9 Задачи и упражнения. .

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА». Часть 1

Для создания и эксплуатации сложных автоматизированных систем обработки информации и их компонент в области экономики, математи-ческого и программного обеспечения вычислительной техники, сетей передачи данных и многих других сферах деятельности человека необходимо знание дискретной математики.

Дискретная математика – часть математики, которая зародилась в глубокой древности. Как говорит само название, главной ее особенностью является дискретность, т.е. антипод непрерывности. В ней отсутствует понятие предельного перехода, присущее классической, «непрерывной» математике. Дискретная математика занимается изучением дискретных структур, которые возникают как внутри математики, так и в ее приложениях.

Цель дисциплины «Дискретная математика» − знакомство с основными разделами зтой науки: теорией множеств, математической логикой, теорией графов, теорией алгоритмов, комбинаторным анализом как аппаратом для построения моделей дискретных систем.

Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дисциплинах: «Информатика», «Программирование», «Структуры и алгоритмы обработки данных в ЭВМ», «Базы данных» и т.д.

Настоящее пособие представляет собой курс лекций, читаемый в Томском государственном университете систем управления и радиоэлектроники студентам специальностей «Программное обеспечение вычислительной техники и автоматизированных систем» и «Информационные системы в экономике».

Пособие рассчитано на изучение в течение двух семестров и в соответствии с этим разбито на две час-

В первой части излагаются основы теории множеств, теории графов, элементы алгебры высказываний, теории булевых функций и логики предикатов.

Вторая часть посвящена изложению основ построения формальных теорий, знакомству с основными разделами теории алгоритмов: аппаратом рекурсивных функций, машинами Тьюринга, нормальными алгоритмами Маркова. Завершает вторую часть раздел, дающий представление о задачах и основных построениях комбинаторного анализа.

В конце каждого раздела приведены задачи и упражнения, которые необходимо выполнить для закрепления теоретического материала.

1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

1.1 Основные определения

Понятие множества является фундаментальным неопределяемым понятием. Интуитивно под множеством понимают совокупность вполне определенных различаемых объектов, рассматриваемых как единое целое.

Природа объектов может быть самой различной. Так, можно говорить о множестве стульев в комнате, людей, живущих в Томске, студентов в группе, о множестве натуральных чисел, букв в алфавите, состояний системы и т.п. Но нельзя, например, говорить о множестве капель в стакане воды, так как невозможно четко и ясно указать каждую отдельную каплю, капли неразличимы между собой.

Отдельные объекты, из которых состоит множество, называют его элементами .

Для обозначения конкретных множеств принято использовать прописные буквы A, S, X, . . Для обозначения элементов множества используют строчные буквы a, s, x, . . Множество X, элементами которого являются x 1 , x 2 , x 3 , обозначают X = . Это один способ задания множества − перечисление всех его элементов. Он удобен при рассмотрении конечных множеств, содержащих небольшое число элементов. Второй способ задания множества − описательный − состоит в том, что указывается характерное свойство, которым обладают все элементы множества. Так, если M − множество студентов группы, то множество X отличников этой группы записывается в виде

что читается следующим образом: множество X состоит из элементов x множества M таких, что x является отличником группы. Множество простых чисел записывается как X = . Для указания того, что элемент x принадлежит множеству X, используется запись x X. Запись x X означает, что элемент x не принадлежит множеству X.

Множество называется конечным , если оно содержит конечное число элементов, и бесконечным , если число его элементов бесконечно. Множество, не содержащее ни одного элемента, называется пустым . Пус-

тое множество обозначается , например:

где С — множество целых чисел. Пустое множество условно относится к конечным множествам.

Два множества X и Y равны в том и только в том случае, когда они состоят из одних и тех же элемен-

тов, т.е. X = Y, если x X, то x Y и если y Y, то y X.

Множество X является подмножеством множества Y, если любой

элемент множества X принадлежит

множеству Y. Этот факт записывается как X Y.

n-строчкой или кортежем . В n-

Последовательность из n элементов множества называется

строчке каждый элемент занимает определенное место, тогда как во множестве порядок расположения элементов роли не играет.

Для сокращения записи в теории множеств используются некоторые логические символы. Это кванторы общности и существования , а также символы следствия (импликации) и логической эквивалентности . Смысл этих обозначений следующий:

— «любой», «каждый», «для всех»;- «существует», «найдется», «хотя бы один»;- «влечет», «имеет следствием»;

— «тогда и только тогда», «необходимо и достаточно».

Использование логических символов, например, для определения подмножества, которое может быть сформулировано в виде: для любого x утверждение «x принадлежит X» влечет за собой утверждение «x принадлежит Y», приводит к записи:

Запись X Y и Y X X = Y означает: для того, чтобы X было равно Y необходимо и достаточно, чтобы X Y и Y X.

1.2 Операции над множествами

Над множествами можно производить действия, которые во многом напоминают действия сложения и умножения в элементарной алгебре. Для графической иллюстрации операций над множествами будем использовать так называемые диаграммы Эйлера, в которых произвольному множеству X ставится в соответствие множество точек на плоскости внутри некоторой замкнутой кривой.

Объединением (суммой) множеств X и Y называют множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X, Y (рис.1.1).

Объединение двух множеств символически записывают как X Y или Y X. Объединение множеств X i (i = 1, 2, . N) есть множество элементов, каждый из которых принадлежит хотя бы одному из множеств X i . Соответствующее обо-

голоса

Рейтинг статьи