9968
.pdfF А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
|
|
|
х |
|
|
|
|
|
|
|
|
х1 х3 |
|
х х |
|
х |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
х |
х |
2 |
|
х |
2 |
|
х |
х |
|
|
|
F(х , х |
, х |
) |
|
|
|
|
|
|
|
|
|
|
|
||||||
1 |
|
3 |
|
|
|
|
|
( |
1 |
3 |
) |
2 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
|
1 2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
0 0 |
|
0 |
1 |
|
|
|
0 |
|
|
0 |
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
||||||||||||||||||
0 0 |
|
1 |
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
|||||||||||||||||
0 |
1 |
|
0 |
0 |
|
|
|
1 |
|
|
0 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 |
|
1 |
0 |
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
||||||||||||||||||
1 |
0 |
|
0 |
1 |
|
|
|
1 |
|
|
1 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
1 |
|
|
|
1 |
|
|
1 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 |
|
0 |
0 |
|
|
|
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
||||||||||||||||||
1 1 |
|
1 |
0 |
|
|
|
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
х1 х2 х3 |
Искомая СДНФ логической функции
F(х1, х2 , х3) х1 х2 х3 х1 х2 х3 х1 х2 х3 х1 х2 х3 х1 х2 х3 .
Задача 2.
Булеву функцию трех переменных
F(х1, х2 , х3 ) = (х1 х2 ) (х1 х3) х2 представить логической формулой – в виде СКНФ.
х |
х |
|
х |
|
|
|
|
х х |
|
х1 х3 |
|
х1 |
х3 |
|
х |
F(х , х |
|
, х ) |
|
|
|
|
|
|
|
|
||
2 |
|
х |
2 |
|
|
( |
) |
2 |
|
|
|
|
|
|
|
|
||||||||||||
1 |
|
3 |
|
|
|
1 |
2 |
|
|
|
|
2 |
1 |
3 |
|
|
|
|
|
|
|
|
||||||
0 |
0 |
|
0 |
1 |
|
|
|
0 |
|
|
0 |
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
1 |
1 |
|
|
|
0 |
|
|
1 |
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
0 1 |
|
0 |
0 |
|
|
|
1 |
|
|
0 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
|||||||||||||||
0 |
1 |
|
1 |
0 |
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 0 |
|
0 |
1 |
|
|
|
1 |
|
|
1 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
|||||||||||||||
1 0 |
|
1 |
1 |
|
|
|
1 |
|
|
1 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
х1 х2 х3 |
|||||||||||||||
1 |
1 |
|
0 |
0 |
|
|
|
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
1 |
0 |
|
|
|
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
Искомая СКНФ логической функции:
F(x1, x2, x3) (х1 х2 x3) (x1 х2 x3) (x1 х2 x3) .
Задача 3.
Для формулы А х у (х у) построить СКНФ с помощью равносиль-
ных преобразований.
112
Решение. КНФ А (х у) (х х у) , СКНФ А (х у) (х у) .
Задача 4
Представим в виде полинома Жегалкина дизъюнкцию f (x1, x2 ) x1 x2 .
х1 |
х2 |
x1 x2 |
|
|
|
|
|
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
|
х1 x2 |
|||
|
|
|
|
|
|
|
|
1 |
0 |
1 |
х1 х2 |
||||
1 |
1 |
1 |
|
х1 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. Теория множеств и отношений.
1. Сколько элементов в каждом из множеств:
1) |
1,2,3 , 1,3 ,1,2 |
4) |
1, 1 , 2, 1,2,3 ,1,2, 3 |
2) |
1,2,3 ,1,2, 3 |
5) |
1, 1 , 2, 1, 2,3 , |
3) |
1, 1,2,3 ,1,2, 3 |
6) |
|
|
|
7) |
|
|
|
118 |
|
8) , |
9) , |
2.Какие из следующих утверждений верны:
1)1,2 1,2,3 , 1,3 ,1,2
2) |
b a,b |
|
6) |
b a, b |
10) |
|
3) |
b a,b |
|
7) |
b a, b |
11) |
|
4) |
b a,b |
|
8) |
b a, b |
12) |
|
5) |
b a,b |
|
9) |
b a, b |
13) |
|
3. Известно, что |
А В и |
а А. Какие из |
следующих |
утверждений |
||
верны: а В |
|
|
|
|
|
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.Перечислите все элементы следующих множеств:
1) x R |
|
x 2 3x 2 0 ; |
2) x R |
|
x 2 1 0 ; |
|
|
3) множество всех двузначных натуральных чисел, делящихся на 5, но не делящихся на 10.
6. Перечислите все элементы следующих множеств:
1) x R |
|
x 2 3x 2 0 ; |
2) x R |
|
x 2 1 0 ; |
|
|
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 lg 5 , 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, www.inf.au, содержащих комбинацию ключевых слов
«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
указывает на страницу с информацией об электронных библиотеках Австралии. Используя операции над множествами, найти множество всех адресов, указывающих на страницы, содержащие информацию о