Читать онлайн «Элементы дискретнои? математики : учебное пособие»

ЭЛЕМЕНТЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Учебное пособие Министерство образования и науки Российской Федерации Уральский федеральный университет имени первого Президента России Б. Н. Ельцина Элементы дискретной математики Рекомендовано методическим советом УрФУ в качестве учебного пособия для студентов, обучающихся по направлениям подготовки 231300 — Прикладная математика 141100 — Энергетическое машиностроение 140400 — Электроэнергетика и электротехника 140100 — Теплоэнергетика и теплотехника 141403 — Атомные станции: проектирование, эксплуатация и инжиниринг 280700 — Техносферная безопасность Екатеринбург Издательство Уральского университета 2015 УДК 519. 1(075. 8) ББК 22. 176я73 Э45 Рецензенты: кафедра высшей и прикладной математики Уральского государственно- го университета путей сообщения (завкафедрой, д-р физ. -мат. наук проф. Г. А. Тимофеева); д-р физ. -мат. наук, зам. директора ИММ УрО РАН В. Т. Шевалдин Научный редактор — д‑р физ. -мат. наук проф. А. Н. Сесекин     Элементы дискретной математики : учебное пособие / Д. С. Ананичев, Э45 И. Ю. Андреева, Н. В. Гредасова, К. В. Костоусов. — Екатеринбург : Изд-во Уральского университета, 2015. — 108 с. ISBN 978-5-7996-1387-7 В учебном пособии рассматриваются элементы дискретной математики: ло- гические исчисления, предикаты, булевы функции, комбинаторика, теория гра- фов, автоматы и алгоритмы. Приведено решение типовых задач. Предназначается для студентов всех форм обучения всех специальностей. УДК 519. 1(075. 8) ББК 22. 176я73 ISBN 978-5-7996-1387-7 © Уральский федеральный университет, 2015  1. Логические исчисления Множество, отношения, функции Множества Множество — совокупность объектов (элементов). Множества A, B, … Элементы a, b, c, ... а О А а — элемент А (а принадлежит А). а П А а — не элемент А (а не принадлежит А). Основное свойство множеств Для любых а и А выполняется ровно одно из двух условий: а О А, а П А. Способы задания множеств 1. Перечисление элементов: А = {0, 1, 2, 3, …, 9}. B = {красный, синий, зеленый}. C = {борода, шляпа, очки}. Можно задать лишь конечные множества. 2. Определяющие свойства: А = {x | x — десятичная цифра}. N = {x | x — натуральное число}. Z = {x | x — целое}. N0 ={x | x О Z, x ≥ 0}. m Q = { | m О Z, n О N}. n R ={x | x — действительное число}. C ={x | x — комплексное число}. (2,3) = {x | x О R, x - 5 x + 6 < 0 }. 2 3 Элементы дискретной математики Пример 1 О{1, 2, 3} — верно. 1 О{{1},{2},{3}} — не верно.