8908

F ≡ А3 Б5 В2 Г1 Е4 ≡ 1. Откуда получаем А3 ≡ 1, Б5 ≡ 1, В2 ≡ 1,

Г1 ≡ 1; Е4 ≡ 1, что и дает ответ задачи.

Задача 7.

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

которого фамилия Фридрих, есть фамилия того мальчика, имя которого – фа-

милия Карла.

Решение. Поставим в соответствие каждому мальчику символ ХУ , где Х

– имя, а Y – фамилия мальчика. Тогда по условию задачи ложны высказывания:

АА , КК , Д Д , ФФ , Д А , но есть мальчик YX такой, что истинна конъюнкция

ХФ YХ КY ≡ 1.

Очевидно, что Х¹Ф, Х¹К, Y¹Ф, Y¹К. Тогда возможны два случая:

1)Х=А и Y=Д,

2)Х=Д и Y=А.

Но первый случай невозможен, так как здесь YX = Д А, а по условию

Д А ≡ 0 . Следовательно, имеет место второй случай. Значит, Дидрих имеет фа-

милию Фридрих, Альберт имеет фамилию Дидрих, Карл имеет фамилию Аль-

берт, а Фридрих имеет фамилию Карл.

Задачи для раздела 5.

Задача 1.

Булеву функцию трех переменных

F (х1, х2 , х3 ) = (х1 « х2 ) ® (х1 Ú х3 ) Ù х2 представить логической формулой – в

виде СДНФ.

111

Искомая СКНФ логической функции:

F (x1, x2 , x3 ) = (х1 х2 x3 ) (x1 х2 x3 ) (x1 х2 x3 ) .

Задача 3.

Для формулы А≡ х у (х у) построить СКНФ с помощью равносиль-

ных преобразований.

112

Решение. КНФ А ≡ (х у) (х х у) , СКНФ А≡ (х у) (х у) .

Задача 4

Представим в виде полинома Жегалкина дизъюнкцию f (x1, x2 ) º x1 Ú x2 .

f (x1, x2 ) º x1 Ú x2 º х1 Ù x2 Å x1 Ù х2 Å x1 Ù x2 º

º(х1 Å1) Ù x2 Å x1 Ù (х2 Å1) Å x1 Ù x2 º x1 Ù x2 Å х2 Å x1 Ù x2 Å х1 Å x1 Ù x2 º

ºx1 Ù x2 Å х1 Å х2 .

Задача 5.

Будет ли формула А ≡ (х → у) → х у у тождественно истинной, тож-

дественно ложной или выполнимой?

Решение. Приведем формулу А к ДНФ.

(х → у) → х у у ≡ х у → х у у ≡ х у х у у ≡ х у х у у.

Полученная ДНФ не является тождественно ложной, так как каждая эле-

ментарная конъюнкция не содержит переменную и ее отрицание. Следователь-

но, исходная формула тождественно истинна или выполнима.

Преобразуем данную формулу к КНФ: (х ® у) ® х Ù у Ú у º

º х Ù у Ú х Ù у Ú у º (х Ù у Ú у) Ú х Ù у º у Ú х Ù у º ( у Ú х) Ù ( у Ú у) º у Ú х.

Полученная КНФ не является тождественно истинной, так как элемен-

тарная дизъюнкция не содержит переменную и ее отрицание.

Следовательно, данная формула А выполнима.

113

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

4.1 Общие рекомендации для самостоятельной работы

Самостоятельная работа студентов является основным способом овладе-

ния учебным материалом в свободное от обязательных учебных занятий время.

Целями самостоятельной работы студентов являются:

- систематизация и закрепление полученных теоретических знаний и прак-

тических умений студентов;

-углубление и расширение теоретических знаний;

-формирование умений использовать нормативную, правовую, справоч-

ную документацию и специальную литературу;

-развитие познавательных способностей и активности студентов:

-формирования самостоятельности мышления, способностей к саморазви-

тию, самосовершенствованию и самореализации.

Запланированная в учебном плане самостоятельная работа студента рас-

сматривается как связанная либо с конкретной темой изучаемой дисциплины,

либо с подготовкой к курсовой, дипломной работе, а также к защите ВКР. В

данном разделе рассматривается только самостоятельная работа первого вида.

Самостоятельная работа выполняется в два этапа: планирование и реали-

зация.

Планирование самостоятельной работы включает:

-уяснение задания на самостоятельную работу;

-подбор рекомендованной литературы;

-составление плана работы, в котором определяются основные пункты предстоящей подготовки.

Составление плана дисциплинирует и повышает организованность в рабо-

те.

На втором этапе реализуется составленный план. Реализация включает в

себя:

- изучение рекомендованной литературы;

114

-составление плана (конспекта) по изучаемому материалу (вопросу);

-взаимное обсуждение материала.

Необходимо помнить, что на лекции обычно рассматривается не весь ма-

териал. Оставшийся восполняется в процессе самостоятельной работы. В связи с этим работа с рекомендованной литературой обязательна.

Работа с литературой и иными источниками информации включает в себя две группы приемов: техническую, имеющую библиографическую направлен-

ность, и содержательную. Первая группа – уяснение потребностей в литерату-

ре; получение литературы; просмотр литературы на уровне общей, первичной оценки; анализ надежности публикаций как источника информации, их отно-

симости и степени полезности. Вторая – подробное изучение и извлечение не-

обходимой информации.

Для поиска необходимой литературы можно использовать следующие спо-

собы:

-поиск через систематический каталог в библиотеке;

-просмотр специальных периодических изданий;

-использование материалов, размещенных в сети Интернет.

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

монографий, научных статей, следует учитывать, что учебник и учебное посо-

бие предназначены для студентов и магистрантов, а монографии и статьи ори-

ентированы на исследователя. Монографии дают обширное описание пробле-

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

тора или его конкретные достижении в исследовании какой-либо научной про-

блемы.

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

вается речь.

При необходимости студенту следует обращаться за консультацией к пре-

115

подавателю.

Составление записей или конспектов позволяет составить сжатое пред-

ставление по изучаемым вопросам. Записи имеют первостепенное значение для самостоятельной работы студентов. Они помогают понять построение изучае-

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

Ведение записей способствует превращению чтения в активный процесс. У

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

шие при самостоятельной работе.

Можно рекомендовать следующие основные формы записи: план, кон-

спект, тезисы, презентация.

План – это схема прочитанного материала, краткий (или подробный) пере-

чень вопросов, отражающих структуру и последовательность материала. Под-

робно составленный план вполне заменяет конспект.

Конспект – это систематизированное, логичное изложение материала ис-

точника. Объем конспекта не должен превышать 10 страниц. Шрифт Times New Roman, кегль 14, интервал 1,5. Список литературы должен состоять из 5-8

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

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

мают одну страницу формата А4 или одну – две страницы в ученической тетра-

ди. В конце тезисов студент должен сделать собственные выводы.

Презентации по предложенной теме составляются в программе Power Point

или Impress. Количество слайдов должно быть не менее 15 и не превышать 20

слайдов. Кроме текста на слайдах можно создавать схемы и таблицы. Шрифт должен быть читаемым, например, шрифт черного цвета на светлом фоне или светлый шрифт на темном фоне. Также шрифт не должен быть слишком мел-

116

ким. В слайдах указываются только основные тезисы, понятия и нормы.

4.2Темы для самостоятельного изучения

1.Понятие об автомате и его математическое описание.

2.Проверка правильности логических выводов. Метод резолюций.

3.Теория нечетких множеств и отношений.

4.Нечеткая логика и нечеткий вывод.

5.Задача о кратчайшем пути: замена оборудования, составление распи-

сания движения транспортных средств, размещение пунктов скорой помощи, размещение телефонных станций.

6.Связность графов и сетей: проектирование кратчайшей коммуникаци-

онной сети, синтез структурно-надежной сети циркуляционной связи,

анализ надежности стохастических сетей связи.

7.Раскраска в графах: распределение памяти в компьютере, проектиро-

вание сетей телевизионного вещания.

8.Задача о максимальном потоке: анализ пропускной способности ком-

муникационной сети, организация движения в динамической сети, оп-

тимальный подбор интенсивностей выполнения работ, задача о рас-

пределении работ.

9.Задача об упаковках и покрытиях: оптимизация структуры ПЗУ (по-

стоянного запоминающего устройства), размещение диспетчерских пунктов городской транспортной сети.

10.Изоморфизм графов и сетей: структурный синтез линейных избира-

тельных цепей, автоматизация контроля при проектировании БИС

(больших интегральных схем).

117

4.3Учебно-методическое обеспечение самостоятельной работы

1.Шевелев Ю.П. Дискретная математика. математика: учеб. пособие для студентов вузов по направлению и спец. "Приклад. математика и информати-

ка": Учеб. пособие. СПб: Лань, 2008.

2. Галушкина И. Конспект лекций по дискретной математике с упражне-

ниями и контрольными работами. – М.: ЮНИТИ, 2006.

3. Алексеев В.Е. Элементы теории графов. Пособие для студентов заоч-

ного отделения. – Н.Новгород, ННГУ, 2002.

4.Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962.

5.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной матема-

тике. – М.: Наука, 1977.

6.Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях : учебное пособие / Г.И. Москинова. – М. : Логос, 2004. – 240 с.

7.Новиков Ф.А. Дискретная математика для программистов. СПб: Питер,

2001.

8.Оре О. Теория графов. 2-е изд. – М.: Наука. 1980. – 336 с.

9.Шапорев С.Д. Дискретная математика. Курс лекций и практических за-

нятий: Учеб. пособие. СПб: БХВ-Петербург, 2005. – 416 с.

10.Яблонский, С.В. Введение в дискретную математику: учебное пособие

/ С.В. Яблонский. – 3- е изд. стер. – М. : Высш. шк., 2002. – 384 с.

4.4 Задания для самостоятельной работы

Раздел 1. Теория множеств и отношений.

2.Какие из следующих утверждений верны:

1){1,2} {{1,2,3}{, 1,3},1,2}

1)аÎ В

2)А В

3)аÎ А È В

4)аÎ А Ç В

5)аÎ А \ В

6)аÎ А ¸ В

7)а Í А

8){а} А

4.Известно, что {а} В. Является ли число 2 элементом множеств:

A = {1,3,5,6}, B = {− 3,0,1,2,4}, C = {x x2 = 4x − 4}

5.Перечислите все элементы следующих множеств:

3) множество всех двузначных натуральных чисел, делящихся на 5, но не

делящихся на 10.

6. Перечислите все элементы следующих множеств:

119

3) множество всех двузначных натуральных чисел, делящихся на 5, но не

делящихся на 10.

7.Перечислить все элементы множества: а) {x x Í {}1 }; б) {x x Í {1,2,3}}.

8.Перечислите все подмножества множества {{1,2}, {3},1}, {{}1 , {2},1,2}.

9.Докажите, что {{1,2}, {2,3}} ¹ {1,2,3}.

10.Проверьте, что А и 2 А имеют общий элемент, если А = {1,2, {1,2}}.

11. Пусть А = {1,4,5}, В = {2,4,6}. Найдите А È B, А Ç B, А \ B, B \ А, А ÷ B, 2 А .

12.Соедините знаком включения следующие пары множеств:

1)A = {x Î R lg x = 2 - lg5}, B = {20,30};

2)A = {x Î R x2 - 7x +12 = 0}, B = {x Î R x3 - 7x2 + 12x = 0}.

13. Пусть U – множество сотрудников некоторой фирмы. А – множество всех сотрудников старше 35 лет. В – множество сотрудников, имеющих стаж работы более 10 лет, С – множество менеджеров фирмы каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:

а) B ; б) А Ç В Ç С ; в) А È В Ç С ; г) В \ С ; д) С \ В.

14. В результате поиска в Интернете выданы адреса Web-страниц www.cont1,

www.cont2, www.cont3, www.st1, www.st2, www.st3, www.inf.ru,

«electronic_libraries». Известно, что страницы с адресами www.cont1,

www.cont3, www.st1, www.st2, www.inf.au содержат информацию о книгах

по техническим наукам, страницы www.st1, www.st2, www.st3, www.inf.ru, www.inf.au – сведения о периодических изданиях, адрес www.inf.au

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