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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Брянский государственный технический университет

УТВЕРЖДАЮ

Ректор университета

__________О.Н. Федонин “____”___________2014 г.

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания к выполнению

практических заданий и задачи для студентов

I курса очной формы обучения по направлениям подготовки

230400 «Информационные системы и технологии», 090900 «Информационная безопасность», 040100 «Социология», 090303 «Информационная безопасность автоматизированных систем»

I семестр

Брянск 2014

УДК 511

Дискретная математика [Текст]+[Электронный вариант]: методические указания к выполнению практических заданий и задачи для студентов I курса очной формы обучения по направлениям подготовки 230400 «Информационные системы и технологии», 090900 «Информационная безопасность», 040100 «Социология», 090303 «Информационная безопасность автоматизированных систем» II семестр. – Брянск, М.: БГТУ, 2014. – 60с.

Разработали: Андросенко В.А., ст.преп.

Сенько К.А., асс.

Рекомендовано кафедрой «Высшая математика» БГТУ

(протокол № 4 от 19. 12. 13)

Научный редактор А.Г. Белоусов

Редактор издательства Л.И. Захарова

Компьютерный набор А.П. Левкина

Темплан 2014г., п.254

Подписано в печать Формат 60´84 1/16. Бумага офсетная. Офсетная печать. Усл. печ. л. 3,49 Уч.-изд. л. 3,49 Тираж 30 экз. Заказ Бесплатно ____

Издательство Брянского государственного технического университета

241035, г. Брянск, бульвар 50 лет Октября, 7, тел 58-82-49

Лаборатория оперативной полиграфии БГТУ.

ПРЕДИСЛОВИЕ

Современная математика уже не такая, какой она была в начале XX века. В ней появилось большое количество новых дисциплин, широко применяющихся на практике. Например, дисциплины, объединенные под общим названием «Дискретная математика».

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

Предлагаемое пособие призвано познакомить студентов с важнейшими разделами дискретной математики, такими как:

1. Элементы теории множеств и комбинаторики.

2. Теория графов.

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

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

ТЕМА 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

И КОМБИНАТОРИКИ

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

Запись АÌВ означает, что множество А содержится в множестве В, т.е. является подмножеством.

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

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

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

АÈВ={ a: a ÎA или а ÎВ}

y ZXYueG1sTM5BTsMwEAXQPRJ3sAaJTUWdhqa0IZMKVWIDi0LhAE4yJBH2OMRu6t4edwXL0R/9/4pt MFpMNLreMsJinoAgrm3Tc4vw+fF8twbhvOJGacuEcCYH2/L6qlB5Y0/8TtPBtyKWsMsVQuf9kEvp 6o6McnM7EMfsy45G+XiOrWxGdYrlRss0SVbSqJ7jQqcG2nVUfx+OBuFl/zY7p2E1+3nIql2Y1jq8 Oo14exOeHkF4Cv7vGS78SIcymip75MYJjXC/jHKPsNmAuMSLJAVRIWTLDGRZyP/+8hcAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQADbxcf8wEAAOsDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQBEE+CL3QAAAAcBAAAPAAAAAAAAAAAAAAAAAE0EAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>А В

Пересечением множеств А и В называется множество АÇВ, элементами которого являются все элементы, одновременно принадлежащие множеству А и множеству В.

АÇВ={ a: a ÎA и а ÎВ}.

А В

Разностью множеств А и В называется множество А\В, элементами которого являются все элементы множества А, не содержащиеся во множестве В.

А\ В={ a: a ÎA и а ÏВ}.

А В

Симметрической разностью множеств А и В называется множество АDВ=(А\ В)È(В\А)

3 bnJldi54bWxMj8FOwzAQRO9I/IO1SFyq1iFSQhPiVKgSFzgAhQ9wkm0SYa9D7Kbu37Oc4Dg7o9k3 1S5aIxac/ehIwd0mAYHUum6kXsHnx9N6C8IHTZ02jlDBBT3s6uurSpedO9M7LofQCy4hX2oFQwhT KaVvB7Tab9yExN7RzVYHlnMvu1mfudwamSZJLq0eiT8MesL9gO3X4WQVPL++rS5pzFff91mzj8vW xBdvlLq9iY8PIALG8BeGX3xGh5qZGneizgvDOisKjioochDsp1nCUxoFOR9kXcn/A+ofAAAA//8D AFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9U eXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9y ZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAPzIJTT1AQAA6wMAAA4AAAAAAAAAAAAAAAAALgIAAGRy cy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAFcskO3dAAAACAEAAA8AAAAAAAAAAAAAAAAATwQA AGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABZBQAAAAA= " strokecolor="black [3040]"/>y ZXYueG1sTM5BTsMwEAXQPRJ3sAaJTUWdhqa0IZMKVWIDi0LhAE4yJBH2OMRu6t4edwXL0R/9/4pt MFpMNLreMsJinoAgrm3Tc4vw+fF8twbhvOJGacuEcCYH2/L6qlB5Y0/8TtPBtyKWsMsVQuf9kEvp 6o6McnM7EMfsy45G+XiOrWxGdYrlRss0SVbSqJ7jQqcG2nVUfx+OBuFl/zY7p2E1+3nIql2Y1jq8 Oo14exOeHkF4Cv7vGS78SIcymip75MYJjXC/jHKPsNmAuMSLJAVRIWTLDGRZyP/+8hcAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQAG3duj8wEAAOsDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQBEE+CL3QAAAAcBAAAPAAAAAAAAAAAAAAAAAE0EAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>А В

Часто складывается ситуация, когда все рассматриваемые множества содержатся в некотором едином множестве W, называемом универсальным множеством. Дополнением множества А (до универсального) называется множество =W\А.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Пусть А={1,2,3,4,5,6,7}; В={4,5,6,7,8,9,10}; С={2,4,6,8,10}; И={1,2,3,4,5,6,7,8,9,10}. Определить следующие множества: .

Решение.

АÇВ={4,5,6,7}

={1,2,3,8,9,10}.

Задача 2. Для множества используйте диаграммы Эйлера-Венна и заштрихуйте те ее части, которые изображают заданное множество: (АÈВÈС)\ (АÇВÇС).

Решение.

1) 2)

l di54bWxMj81OwzAQhO9IvIO1SFwq6uBCEoU4FarEBQ6UwgM48ZJE+CfEbuq+PcsJbrszo9lv622y hi04h9E7CbfrDBi6zuvR9RI+3p9uSmAhKqeV8Q4lnDHAtrm8qFWl/cm94XKIPaMSFyolYYhxqjgP 3YBWhbWf0JH36WerIq1zz/WsTlRuDRdZlnOrRkcXBjXhbsDu63C0Ep5f96uzSPnqu7hvd2kpTXoJ Rsrrq/T4ACxiin9h+MUndGiIqfVHpwMzEgpxR0nSixwY+WJT0tCSILIN8Kbm/z9ofgAAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQBrhwyC8gEAAOwDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQD7oatE3gAAAAkBAAAPAAAAAAAAAAAAAAAAAEwEAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>u cmV2LnhtbEzOQU7DMBAF0D0Sd7AGiU1FnYamtCGTClViA4tC4QBOMiQR9jjEbureHncFy9Ef/f+K bTBaTDS63jLCYp6AIK5t03OL8PnxfLcG4bziRmnLhHAmB9vy+qpQeWNP/E7TwbcilrDLFULn/ZBL 6eqOjHJzOxDH7MuORvl4jq1sRnWK5UbLNElW0qie40KnBtp1VH8fjgbhZf82O6dhNft5yKpdmNY6 vDqNeHsTnh5BeAr+7xku/EiHMpoqe+TGCY1wv4xyj7DZgLjEiyQFUSFkywxkWcj//vIXAAD//wMA UEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEA5CHuvvQBAADrAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJz L2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEARBPgi90AAAAHAQAADwAAAAAAAAAAAAAAAABOBAAA ZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFgFAAAAAA== " strokecolor="black [3040]"/>А В

А В

y ZXYueG1sTI9BTsMwEEX3SNzBGiQ2FbUbaDEhToUqsYFFoe0BnGRIIuxxiN3UvT3uCpZf8/T/m2Id rWETjr53pGAxF8CQatf01Co47F/vJDAfNDXaOEIFZ/SwLq+vCp037kSfOO1Cy1IJ+Vwr6EIYcs59 3aHVfu4GpHT7cqPVIcWx5c2oT6ncGp4JseJW95QWOj3gpsP6e3e0Ct62H7NzFlezn8dltYmTNPHd G6Vub+LLM7CAMfzBcNFP6lAmp8odqfHMpCzEIqEK7mUG7AI8PSyBVQqkFMDLgv//oPwFAAD//wMA UEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEAwpL7zfMBAADtAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJz L2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEA00oUbd4AAAAJAQAADwAAAAAAAAAAAAAAAABNBAAA ZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFgFAAAAAA== " strokecolor="black [3040]"/> С С

u cmV2LnhtbEzOQU7DMBAF0D0Sd7AGiU1FnYamtCGTClViA4tC4QBOMiQR9jjEbureHncFy9Ef/f+K bTBaTDS63jLCYp6AIK5t03OL8PnxfLcG4bziRmnLhHAmB9vy+qpQeWNP/E7TwbcilrDLFULn/ZBL 6eqOjHJzOxDH7MuORvl4jq1sRnWK5UbLNElW0qie40KnBtp1VH8fjgbhZf82O6dhNft5yKpdmNY6 vDqNeHsTnh5BeAr+7xku/EiHMpoqe+TGCY1wv4xyj7DZgLjEiyQFUSFkywxkWcj//vIXAAD//wMA UEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEAjbDvL/QBAADrAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJz L2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEARBPgi90AAAAHAQAADwAAAAAAAAAAAAAAAABOBAAA ZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFgFAAAAAA== " strokecolor="black [3040]"/>А В

y ZXYueG1sTI/BTsMwEETvSPyDtUhcKmongtCGOBWqxAUOlNIPcGKTRNjrELup+/dsT3DaGe1o9m21 Sc6y2Uxh8CghWwpgBluvB+wkHD5f7lbAQlSolfVoJJxNgE19fVWpUvsTfph5HztGJRhKJaGPcSw5 D21vnApLPxqk3ZefnIpkp47rSZ2o3FmeC1FwpwakC70azbY37ff+6CS8vu8W5zwVi5/Hh2ab5pVN b8FKeXuTnp+ARZPiXxgu+IQONTE1/og6MEs+ExlFSeQ0L4H1PYlGQiEE8Lri/z+ofwEAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQDhU8m28wEAAOsDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQB9Yz+f3QAAAAkBAAAPAAAAAAAAAAAAAAAAAE0EAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>

Задача 3. Доказать формулу АÇ(ВÈС)=(АÇВ)È(АÇС), пользуясь принципом "Х£У и У£ХÞХ=У".

Доказательство.

Пусть Х=АÇ(ВÈС), У=(АÇВ)È(АÇС).

1. Пусть а ÎХÞ(а ÎАÇ(ВÈС))Û (а ÎА) и (а Î(ВÈС))Û а ÎА и (а ÎВ или а ÎС))Û(а ÎА) и (а ÎВ)) или ((а ÎА) и (а ÎС)) Û (а Î(АÇВ)) или (а Î(АÇС)) Û(а Î(АÇВ) È (АÇС)) Û а ÎУÞХ£У.

2. Пусть а ÎУÞ(а Î(АÇВ)È(АÇС))Û (а Î(АÇВ)) или (а Î(АÇС))Û (а ÎА) и (а ÎВ)) или (а ÎА) и ((а ÎС)Û(а ÎА) и ((а ÎВ) или (а ÎС)) Û ((а ÎА) или (а Î(ВÈС)) Û(а ÎАÇ(ВÈС))Û а ÎХÞУ£Х.

Из 1. и 2. Þ Х=У.