Департамент образования города Москвы

Государственное бюджетное профессиональное образовательное учреждение города Москвы

«Западный комплекс непрерывного образования»

Образовательная программа

среднего профессионального образования

Комплект

контрольно-оценочных средств

по учебной дисциплине

ОП.08 Дискретная математика

программы подготовки специалистов среднего звена

09.02.01 Компьютерные системы и комплексы

для промежуточной аттестации

Москва, 2016 год

Согласовано:

Цикловая комиссия по специальности

«Компьютерные системы, сети и телекоммуникации (КСТ)»

Протокол № ____

от «____» ______________ 2016 г.

Утверждаю:

Зав. отделением СПО

_______________/И.Н. Мордвинова/

«____»________________2016 г.

Председатель цикловой комиссии

__________________/Журкин М.С./

Составитель: Кирсанова Н.Ю. преподаватель первой квалификационной категории ГБПОУ ЗКНО

1. Общие положения

Контрольно-оценочные средства (КОС) являются составной частью образовательной программы среднего профессионального образования по подготовке специалистов среднего звена 09.02.01 Компьютерные системы и комплексы и предназначены для контроля и оценки образовательных достижений обучающихся, освоивших программу учебной дисциплины «Дискретная математика».

КОС включают контрольные материалы для проведения промежуточной аттестации в форме зачета.

КОС разработаны на основании:

Положения о Фонде оценочных средств (ФОС);

Рекомендаций по разработке контрольно-оценочных средств (КОС);

Рабочей программы учебной дисциплины.

2. Результаты освоения дисциплины, подлежащие проверке

КОС для промежуточной аттестации направлены на проверку и оценивание результатов обучения, знаний и умений:

Результаты освоения дисциплины «Дискретная математика»

Результаты обучения

(освоенные умения, усвоенные знания)

Коды формируемых профессиональных и общих

компетенций

Основные показатели оценки

№ заданий, включенных в КОС

У1

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

ОК 1 - ОК 9

ПК1.1, ПК 1.3

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

ТЗ 1 - 4

ПЗ 1 - 6

У2

Применять законы алгебры логики

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Умение правильно применять законы алгебры логики для решения задач

ТЗ 5 - 9

ПЗ 7 - 10

У3

Определять типы графов и давать их характеристики

ОК 1 - ОК 9

ПК1.1, ПК 1.3

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

ТЗ 28 - 33

ПЗ 37 - 48

У 4

Строить простейшие автоматы

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Умение строить простейшие автоматы

разными способами: теоретико-множественное, графовое, табличное и матричное представление автоматов

ТЗ 38 - 40

ПЗ 51 - 53

З1

Знание основных понятий и приемов дискретной математики

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание основных понятий и приемов дискретной математики

ТЗ 1, 2, 4, 5, 10, 11, 20,21, 23, 28,34, 38

З2

Знание логических операций, формул логики, законов алгебры логики

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание логических операций, формул логики, законов алгебры логики

ТЗ 2 - 19, 23 - 27

ПЗ 1 - 9, 15 - 18

З 3

Знание основных классов функций, полноты множества функций, теоремы Поста

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Уверенное знание специальных классов булевых функций, полноты множества функций, теоремы Поста о функциональной полноте

ТЗ 10, 34 - 37

ПЗ 49 - 51, 49 - 51

З4

Знание основных понятий теории множеств, теоретико-множественных операций и их связи с логическими операциями

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание основных понятий теории множеств, теоретико-множественные операции и их связь с логическими операциями

ТЗ 11 - 17

ПЗ 10 - 14

З5

Знание логики предикатов, бинарных отношений и их видов

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание законов логики предикатов, бинарных отношений и их видов

ТЗ 23 - 27

ПЗ 15 - 16

З6

Знание элементов теории отображений и алгебры подстановок

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание элементов теории отображений и алгебры подстановок,

операций над подстановками

ТЗ 17 - 19

ПЗ 51

З7

Знание метода математической индукции

Хорошее знание метода математической индукции, базы индукции, индукционного перехода, полной и неполной индукции

ТЗ 20

ПЗ 19

З8

Знание алгоритмического перечисления основных комбинаторных объектов

Хорошее знание основных правил комбинаторики, методов алгоритмического перечисления (генерации) основных комбинаторных объектов, комбинаций элементов с повторениями

ТЗ 21 - 22

ПЗ 20 - 34

З9

Знание основных понятий теории графов, характеристик и видов графов

ОК 1 - ОК 9

ПК1.1, ПК 1.3

Хорошее знание основных понятий теории графов, характеристик и видов графов,

сетевых моделей представления информации

ТЗ 28 - 33

ПЗ 37 - 48

З10

Знание элементов теории автоматов

ОК 1 - ОК 9

ПК1.1, ПК 1.3

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

ТЗ 38 - 40

ПЗ 51 - 53

3. Распределение КОС по темам учебной дисциплины

Контрольно-оценочные средства представляют собой перечень теоретических вопросов и практических заданий.

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

Содержание учебного материала

по программе

№ заданий

теоретические

практические

Введение.

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

Тема 1.1.Логические операции

1

2 - 4

1 - 6

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

Тема 1.2. Булевы функции. Многочлены Жегалкина

5 - 10

7 - 9

Раздел 2.Множества и отображения

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

11- 14

10 - 14

Раздел 2. Множества и отображения

Тема 2.2. Отношения.

Отображения. Функции

15 - 19

15 - 18

Раздел 3. Математическая индукция

Тема 3.1. Метод математической индукции

20

19

Раздел 4.Комбинаторика

Тема 4.1 Перечислительная комбинаторика (теория перечислений)

21 - 22

20 - 33

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

Тема 5.1. Предикаты

23 -27

34, 35

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

Тема 6.1. Основные понятия теории графов

28 -29

36 - 41

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

Тема 6.2. Операции над графами. Типы графов

30 - 33

42 - 47

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

Тема 7.1. Теория алгоритмов

34 - 37

48 - 50

Раздел 8. Элементы теории автоматов

Тема 8.1. Конечные автоматы

38 - 40

51 - 53

4. Содержание КОС

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

4.1. Теоретические задания (ТЗ):

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

2. Составные высказывания. Простейшие связки. Логические отношения.

3. Варианты импликации.

4. Основные законы, определяющие свойства логических операций.

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

6. Свойства элементарных булевых функций.

7. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний.

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

9. Многочлены Жегалкина.

10. Специальные классы булевых функций: функции, сохраняющие единицу, функции, сохраняющие нуль, самодвойственные функции, линейные функции, монотонные функции. Теорема Поста о функциональной полноте.

11. Понятие множества. Способы задания множества. Подмножества. Операции над множествами.

12. Соотношения между множествами и составными высказываниями.

13. Соотношение между высказываниями и соответствующими им множествами истинности.

14. Абстрактные законы операций над множествами.

15. Кортежи и декартово произведение множеств. Степень множества.

16. Бинарные отношения в множестве и их свойства.

17. Отношения строгого и нестрогого порядка.

18. Отображение множеств. Функции.

19. Определенность и неопределенность функций. Композиция отображений.

20. Метод математической индукции. База индукции. Индукционный переход. Полная и неполная индукция.

21. Основные правила комбинаторики. Методы алгоритмического перечисления (генерации) основных комбинаторных объектов: перестановка, сочетание, размещение.

22. Комбинация элементов с повторениями. Бином Ньютона.

23. Предикаты. Применение предикатов в алгебре.

24. Булева алгебра предикатов.

25. Кванторы. Формулы логики предикатов.

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

27. Исчисления предикатов.

28. Основные понятия теории графов. Степень вершины. Маршрут, цепи, циклы. Связность графа.

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

30. Изоморфизм графов.

31. Плоские графы. Операции над графами.

32. Способы задания графов. Некоторые типы графов.

33. Сети. Сетевые модели представления информации. Применение графов и сетей.

34. Вычислимые функции и алгоритмы.

35. Рекурсивные функции.

36. Нормальный алгоритм Маркова.

37. Машины Тьюринга.

38. Понятия конечного автомата. Определения и способы задания конечного автомата.

39. Примеры конечных автоматов.

40. Канонические уравнения автомата.

4.2. Практические задания (ПЗ):

1. Докажите тождественную истинность формулы →(Х→У).

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f₁= X٨ (Y→Z) и f₂= (٨Y) ٧ (X٨Z).

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

а) Х↔Х, б)Х↔, в)(Х٧У)↔(Х٨У), г)(Х→)→(У→), д)(X→Y)٨(Y→Z)٨, е)(Х→У)→Х, ж)((Х→У)→Х

4. Доказать закон отрицания конъюнкции ()

5. Найти значение и убедиться, что при всех значениях A и B - это истинное значение.

6. С помощью основных равносильностей доказать закон обобщенного склеивания .

7. Составьте таблицу истинности булевой функции трех переменных f(х_1, х_2, х₃) = х₁ х₂→٧х₁ | )٨) и найдите ее двоичный набор.

8. Докажите эквивалентность функции: f_{(x, y, z)} = x٨(x٧z)٨(y٧z) и f_{(x, y, z)} = (x٨y)٧(x٨z).

9. Найдите СДНФ и СКНФ функции f_{(x, y, z)}, заданной следующей таблицей истинности:

х₁

х₂

х₃

f(х_1, х_2, х₃)

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

10. Опрос 100 студентов выявил следующие данные о числе студентов, изучающих различные иностранные языки: английский - 28; немецкий - 30; французский - 42, английский и немецкий - 8; английский и французский - 10; немецкий и французский - 5; все три языка - 3.

1) Сколько студентов не изучают ни одного иностранного языка?

2) Сколько студентов изучают один французский язык?

3) Сколько студентов изучают немецкий язык в том и только в том случае, если они изучают французский язык?

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

Ответ: 1) 20; 2) 30; 3) 38.

11. Изобразите с помощью диаграмм Эйлера-Венна множества:

1) и ; 2); и А \ В = ; 3); и С=;

4)В; и ; 5)(А \ В)(В \ А).

12. Воспользовавшись диаграммой Эйлера-Венна, определите, какие из следующих высказываний истинны: а)Х; б) Х; в) Х г) X→(Y→X); д)X.

13. Пусть А = {1, 2}. Выписать все элементы декартова произведения А×А.

14. Рассмотрим два множества А = {a, b, c, d, e, f, g, h} и В = {1, 2, 3, 4, 5, 6, 7, 8}.

15. Проверьте на линейность функцию f(х_1, х_2, х₃), если ее двоичный набор F= 11100001.

16. Найдите правую и левую области отношения R = {‹1, 5› ; ‹1, 6› ; ‹1, 7›}.

17. Если А = {2, 3,4, 5, 6, 7, 8}, запишите бинарное отношение R = {‹х, у› : х, у А, х делит у, и х 3}.

18. Являются ли следующие отношения функциями:

1. {‹1, 2› ; ‹2, 3› ; ‹3, 2›}; 2) {‹1, 2› ; ‹1, 3› ; ‹2, 3›};

3) {х,х² - 2х - 3 : }?

19. Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый - с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?

20. Из 4 первокурсников, 5 второкурсников и 6 третьекурсников надо выбрать 3 студента на конференцию. Сколькими способами можно осуществить этот выбор, если среди выбранных должны быть студенты разных курсов?

21. Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различны?

22. Сколькими способами можно рассадить 5 человек за круглым столом (рассматривается только расположение сидящих относительно друг друга)?

23. Сколькими способами можно распределить 15 выпускников по 3 районам, если в одном из них имеется 8, в другом - 5 и в третьем - 2 вакантных места?

24. Известно, что 7 студентов сдали экзамен по дискретной математике на хорошо и отлично. Сколькими способами могли быть поставлены им оценки?

25. Группа студентов изучает 10 различных дисциплин. Сколькими способами можно составить расписание занятий в понедельник, если в этот день должно быть 4 разных занятия?

26. Из 60 вопросов, входящих в экзаменационные билеты, студент знает 50. Найти вероятность того, что среди трех наугад выбранных вопросов студент знает: а) все вопросы, б) два вопроса.

27. Во взводе три сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

28. В барабане револьвера 7 гнезд, из них в 5 заложены патроны. Барабан приводится во вращение, потом нажимается спусковой курок. Какова вероятность того, что, повторив такой опыт 2 раза подряд: а) револьвер оба раза не выстрелит, б) оба раза револьвер выстрелит.

29. Решить уравнение: 5

30. Решить уравнение:

31. Решить уравнение:

32. Решить уравнение: + = 15(х-1)

33. Решить уравнение: =

34. Записать предложение: «прямая а параллельна прямой b» с помощью предиката.

35. Записать с помощью предиката: «Аксиома: через две различные точки проходит единственная прямая» (Если две точки принадлежат двум прямым, то эти прямые совпадают).

36. Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

37. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

38. К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города.

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

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

40. В городе Н от каждой площади отходит ровно пять улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно пяти.

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

42. Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

1)2)

43. Составить матрицу инцидентности данного орграфа:

4544. Составить матрицу смежности данного орграфа:

45. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

46. Из пункта А в пункт В выехали пять машин одной марки разного цвета: белая, черная, красная, синяя, зеленая. Черная едет впереди синей, зеленая - впереди белой, но позади синей, красная впереди черной. Какая машина едет первой и какая последней?

47. Пусть даны графы G₁(X, E) и G₂(Y, E). Установите, изоморфны ли данные графы

48. Найдите функции g и h в рекурсивной формуле для двухместной функции f(x,y)=x y , если рекурсия проводиться по переменной х.

49. Найдите функции g и h в рекурсивной формуле для трехместной функции f(x,y,z) = x y+z, если рекурсия проводится по переменной y.

50. Примените оператор минимизации к функции

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

52. Для автомата, заданного диаграммой Мура, выпишите соответственную таблицу и систему булевых функций

53. Для автомата, заданного каноническими уравнениями, постройте диаграмму Мура и соответствующую таблицу .

5. Описание процедуры проведения промежуточной аттестации

Зачет проводится за счет часов, отведенных на дисциплину, в учебное время по вопроснику, согласованному на ЦК и утвержденному заведующим отделением СПО.

Обучающийся получает одно теоретическое и одно практическое задания. На подготовку к ответу обучающемуся отводится до 20 минут. Обучающийся предъявляет ответы в смешанной форме: устно раскрывает теоретические вопросы; решение задач представляется в письменном виде с устными комментариями (пояснениями).

6. Эталоны ответов.

6.1. Эталоны ответов на устные вопросы:

1. Математика стала частью нашей культуры. Человек не может считать себя широкообразованным, не имея представления современной математике, ее роли в повседневной жизни, в науке. Основу составляют такие разделы математики, как комбинаторный анализ, теории множеств, элементы математической и классической логики. Дискретная математика для программистов относится к числу общепроффесиональных предметов, формирующих базовый уровень знаний, необходимых для изучения других дисциплин, таких, как «Математическая статистика», «архитектура ЭВМ, систем сетей», «Базы данных», «Компьютерное моделирование», «Автоматизированные системы», «Технология разработки программных продуктов», «Основы алгоритмизации и программирования». Предложенный вариант учебной дисциплины можно назвать «Курсом на межпредметной основе». Для этого математические знания были увязаны с общенаучными и учтены современные представления о функциональной роли математического образования. Курс формирует у учащихся систему умений и навыков самостоятельного избирательного восприятия информации и ее переработки. Его задача - научить систематизации, обобщению, структурированию знаний, а так же их адекватному применению как в предметных областях, так и в практической деятельности. Сочетание фундаментальных теоретических знаний с их функциональной направленностью призвано показать учащимся использование универсального математического аппарата применительно к различным предметным областям и разнообразным видам деятельности. Акцент делается на знакомство с разными приемами систематизации знаний и предоставлении информации в сжатом виде.

2. Составные высказывания. Простейшие связки. Логические отношения.

3. Варианты импликации.

4. Основные законы, определяющие свойства логических операций.

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

6. Свойства элементарных булевых функций.

7. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний.

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

9. Многочлены Жегалкина.

10. Специальные классы булевых функций: функции, сохраняющие единицу, функции, сохраняющие нуль, самодвойственные функции, линейные функции, монотонные функции. Теорема Поста о функциональной полноте.

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

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

Теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.

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

Теорема. Множество всех монотонных функций является замкнутым классом.

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

Следствие. Класс монотонных функций является замыканием системы функций

Проверка булевой функции на принадлежность к замкнутым классам, на

полноту.

Теорема. Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.

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

.

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

б) Системы (штрих Шеффера) и (стрелка Пирса) являются функционально полными.

.

Таким образом, система сводится к системе , а система - к системе .

в) Система (умножение по модулю 2, сложение по модулю 2 - см. пункт 1 лекции № 8)) является функционально полной. Поскольку , данная система сводится к .

11. Понятие множества. Способы задания множества. Подмножества. Операции над множествами.

12. Соотношения между множествами и составными высказываниями.

13. Соотношение между высказываниями и соответствующими им множествами истинности.

14. Абстрактные законы операций над множествами.

15. Кортежи и декартово произведение множеств. Степень множества.

16. Бинарные отношения в множестве и их свойства.

17. Отношения строгого и нестрогого порядка.

Исследование бинарных отношений на рефлексивность, симметричность и транзитивность; выделение классов эквивалентности.

Определение 1. Отношение называется отношением нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным.

Определение 2. Отношение называется отношением строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным.

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

Определение. Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Эта система обладает следующими свойствами:

1. она образует разбиение множества , то есть классы попарно не пересекаются;

2. любые два элемента из одного класса эквивалентны;

3. любые два элемента из разных классов не эквивалентны.

Все эти свойства прямо следуют из определения отношения эквивалентности.

18. Отображение множеств. Функции.

19. Определенность и неопределенность функций. Композиция отображений.

20. Метод математической индукции. База индукции. Индукционный переход. Полная и неполная индукция.

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

Переход индукции: если верно какое-то утверждение ряда (неважно, какое именно), то верно и следующее за ним утверждение ряда.

Решение задач на выполнение операций в алгебре вычетов

Для степени y=2ⁿ(n-натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии. Как известно, натуральные степени числа 2 оканчиваются цифрами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2. Определим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2ⁿ:

n

2ⁿ

Последняя

цифра 2^т

1

2

2

2

4

4

3

8

8

4

16

6

5

32

2

6

64

4

7

128

8

8

256

6

f: N®{2, 4, 8, 6},

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Последнее равенство означают, что для любого п нужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).

Но это задача на делении с остатком числа nна 4:

n=4k+m, k-частное, т - остаток.

Очевидно, последняя цифра числа 2" зависит от остатка, полученного при делении показателя n степени 2 ⁿ на 4.

Отразим этот факт в записи функции: f(n)= f (nmod 4)

Из этой формулы можно установить, если f (nmod 4) = 0, то

При делении чисел на 4 "nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 ⁿ для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

21. Основные правила комбинаторики. Методы алгоритмического перечисления (генерации) основных комбинаторных объектов: перестановка, сочетание, размещение.

22. Комбинация элементов с повторениями.

23. Предикаты. Применение предикатов в алгебре.

24. Булева алгебра предикатов.

25. Кванторы. Формулы логики предикатов.

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

27. Исчисление предикатов.

28. Основные понятия теории графов. Степень вершины. Маршрут, цепи, циклы. Связность графа.

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

30. Изоморфизм графов.

31. Плоские графы. Операции над графами.

32. Способы задания графов. Некоторые типы графов.

33. Сети. Сетевые модели представления информации. Применение графов и сетей.

34. Вычислимые функции и алгоритмы.

35. Рекурсивные функции.

36. Нормальный алгоритм Маркова.

37. Машины Тьюринга.

38. Понятия конечного автомата. Определения и способы задания конечного автомата.

39. Примеры конечных автоматов.

рис. 7.7

40. Канонические уравнения автомата.

6.2. Эталоны ответов на практические задания:

1. Докажите тождественную истинность формулы →(Х→У).

Решение. Составим таблицу истинности:

X

Y

Х→У

→(Х→У).

0

0

1

1

1

0

1

1

1

1

1

0

0

0

1

1

1

0

1

1

Ответ: последний столбец состоит из 1, следовательно, доказана тождественная истинность формулы.

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f₁= X٨ (Y→Z) и f₂= (٨Y) ٧ (X٨Z).

Решение.

X

Y

Z

Y→Z

f₁

٨Y

X٨Z

f₂

0

0

0

1

1

0

0

0

0

0

0

1

1

1

0

0

0

0

0

1

0

1

0

0

1

0

1

0

1

1

1

1

0

1

0

1

1

0

0

0

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

0

0

0

0

0

0

0

1

1

1

0

1

1

0

1

1

Ответ: так как значения для высказываний f_{1 и} f₂ в таблице истинности не совпадали, то они не эквивалентны.

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

а) Х↔Х, б) Х↔, в) (Х٧У)↔(Х٨У), г) (Х→)→(У→),

д) (X→Y)٨(Y→Z)٨, е) (Х→У)→Х, ж) ((Х→У)→Х.

Решение.

X

Y

Х↔Х

Х↔

Х٧У

Х٨У

(Х٧У)↔(Х٨У)

0

0

1

1

0

0

0

1

0

1

1

1

0

1

0

0

1

0

1

0

0

1

0

0

1

1

1

0

0

1

1

1

а)

б)

в)

Вывод: а) - логически истинное, б) - противоречивое, в) - ни то, ни другое.

Х

У

Х→

У→

(Х→)→(У→)

0

0

1

1

1

1

0

1

0

1

1

1

1

0

1

1

1

1

1

1

0

0

0

1

г)

г) - логически истинное

Х

У

Z

Х↔У

У↔Z

(X→Y)٨(Y→Z)

Х→Z

(X→Y)٨(Y→Z)٨

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

0

1

0

0

1

0

0

0

1

1

1

1

1

1

0

0

1

0

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

0

1

1

0

1

0

0

0

1

0

1

1

1

1

1

1

1

0

0

д)

д) - противоречиво

Х

У

Х→У

(Х→У) →Х

((Х→У) →Х) →Х

0

0

1

0

1

0

1

1

0

1

1

0

0

1

1

1

1

1

1

1

е)

ж)

е) - ни то, ни другое; ж) - логически истинно

Ответ: а) - логически истинное, б) - противоречивое, в) - ни то, ни другое, г) - логически истинное, д) - противоречиво, е) - ни то, ни другое; ж) - логически истинно.

4. Доказать закон отрицания конъюнкции ()

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

Найдем значения для ии сравним их.

A

B

И

И

И

Л

Л

Л

Л

И

Л

Л

И

Л

И

И

Л

И

Л

И

И

Л

И

Л

Л

Л

И

И

И

И

Ответ: значения выражений совпадают, следовательно, закон доказан.

5. Найти значение и убедиться, что при всех значениях A и B - это истинное значение.

Решение.

A

B

И

И

И

Л

Л

Л

Л

И

И

Л

Л

И

Л

И

И

И

Л

И

Л

И

И

Л

И

И

Л

Л

Л

И

И

И

И

И

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

6. С помощью основных равносильностей доказать закон обобщенного склеивания .

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

7. Составьте таблицу истинности булевой функции трех переменных f(х_1, х_2, х₃) =

х₁ х₂→٧х₁ | )٨) и найдите ее двоичный набор.

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

f₁ = х₁х₂; f ₂ = ٨; f₃ = х₁ | f₂; f₄ = ٧f₃; f₅ = f₁→f₄.

Последовательно составляются таблицы истинности всех указанных функций.

х₁

х₂

х₃

f₁

f₂

f₃

f₄

f₅

0

0

0

1

1

1

0

1

1

1

1

0

0

1

1

1

0

0

1

1

1

1

0

1

0

1

0

1

1

0

1

1

1

0

1

1

1

0

0

1

0

1

1

1

1

0

0

0

1

1

1

0

1

1

1

1

0

1

0

1

0

1

0

1

1

1

1

1

0

0

0

1

0

0

1

1

1

1

1

1

0

0

0

0

0

1

1

1

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

8. Докажите эквивалентность функции: f_{(x, y, z)} = x٨(x٧z)٨(y٧z) и f_{(x, y, z)} = (x٨y)٧(x٨z).

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

x

y

z

x٧z

y٧z

x٨(x٧z)

x٨(x٧z)٨(y٧z)

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

1

0

0

1

0

0

0

1

0

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

x

y

z

x٨y

z٨x

(x٨y)٧(x٨z)

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

0

1

1

1

1

0

1

0

1

1

1

1

1

1

1

Получаем F₁ = 00000111 и F₂ = 00000111. Значит, функции эквивалентны.

Ответ: функции эквивалентны.

9. Найдите СДНФ и СКНФ функции f_{(x, y, z)}, заданной следующей таблицей истинности:

х₁

х₂

х₃

f(х_1, х_2, х₃)

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

Решение. По теореме о функциональной полноте СДНФ имеет вид:

٨٧(х₁٨٨х₃)٧(х₂٨х₃)٧(х₁٨х₂٨х₃),

СКНФ имеет вид:

(х₁٧х₂٧٨(х₁٧х₃)٨(٧х₂٧х₃)٨(٧٧х₃).

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

А) Если в конъюнкцию входит некоторая переменная со своим отрицанием, то мы удаляем эту конъюнкцию из ДНФ;

Б) Если конъюнкцию одна и та же переменная входит несколько раз, то все они удаляются, кроме одной;

В) Если в конъюнкцию не входят некоторые переменные, то для каждой из них к конъюнкции добавляется соответствующая формула вида (х٧);

Г) Если в полученной ДНФ имеется несколько одинаковых конъюнкций, т оставляем только одну из них. В результате получается СДНФ.

10. Опрос 100 студентов выявил следующие данные о числе студентов, изучающих различные иностранные языки: английский - 28; немецкий - 30; французский - 42, английский и немецкий - 8; английский и французский - 10; немецкий и французский - 5; все три языка - 3.

1) Сколько студентов не изучают ни одного иностранного языка?

2) Сколько студентов изучают один французский язык?

3) Сколько студентов изучают немецкий язык в том и только в том случае, если они изучают французский язык?

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

Ответ: 1) 20; 2) 30; 3) 38.

11. Изобразите с помощью диаграмм Эйлера-Венна множества:

1) и ; 2); и А \ В = ; 3); и С=;

4)В; и ; 5)(А \ В)(В \ А).

Решение. Изобразим с помощью диаграмм Эйлера-Венна множество

(А \ В)(В \ А)

Это множество является объединением двух разностей, называется симметрической разностью и обозначается , т.е. (А \ В)(В \ А) = .

12. Воспользовавшись диаграммой Эйлера-Венна, определите, какие из следующих высказываний истинны: а) Х; б) Х; в) Х г) X→(Y→X); д)X.

Решение. Множество истинности высказывания X→Y совпадает с заштрихованной областью на диаграмме:

Т.к.эта заштрихованная область включает в себя множество В, то мы видим, что из Y следует X→Y.

13. Пусть А = {1, 2}. Выписать все элементы декартова произведения А×А.

Решение. А×А = {‹1, 1› ; ‹1, 2› ; ‹2, 1› ; ‹2, 2›}.

14. Рассмотрим два множества А = {a, b, c, d, e, f, g, h} и В = {1, 2, 3, 4, 5, 6, 7, 8}.

Составьте множество пар ‹х, у› А×В. Что это множество представляет?

Ответ: множество клеток шахматной доски.

15. Проверьте на линейность функцию f(х_1, х_2, х₃), если ее двоичный набор F= 11100001.

Решение. Применяем к функции f(х_1, х_2, х₃) алгоритм проверки на линейность.

Вычисляем коэффициенты а₀, а₁, а₂, а₃ многочлена Жегалкина для данной функции:

а₀ = f(0, 0, 0,) = 1; a₁ = f(0, 0, 0)f(1, 0, 0) = 10 = 1; а₂ = f(0, 0, 0)f(0, 1, 0) = 11 = 0; а₃ = f(0, 0, 0)f(0, 0, 1) = 11 = 0.

Вычисляем многочлен: f(х_1, х_2, х₃) = а₀а₁х₁а₂х₂а₃х₃ = х₁1.

Очевидно, что двоичный набор F = 11110000 многочлена f(х_1, х_2, х₃) = х₁1 не совпадает с двоичным набором булевой функции, следовательно, функция f(х_1, х_2, х₃) не линейна.

16. Найдите правую и левую области отношения R = {‹1, 5› ; ‹1, 6› ; ‹1, 7›}.

Решение. D_пр. = {5, 6, 7}; D_лев = {1}.

Ответ: D_пр. = {5, 6, 7}; D_лев = {1}.

17. Если А = {2, 3,4, 5, 6, 7, 8}, запишите бинарное отношение R = {‹х, у› : х, у А,

х делит у, и х 3}.

Ответ: R = {‹2, 2› ; ‹2, 4› ; ‹2, 6› ; ‹2, 8› ; ‹3, 3› ; ‹3, 6›}.

18. Являются ли следующие отношения функциями:

2. {‹1, 2› ; ‹2, 3› ; ‹3, 2›}; 2) {‹1, 2› ; ‹1, 3› ; ‹2, 3›};

3. {х,х² - 2х - 3 : }?

Решение. Отношение 1) - функция; отношение 2)- не является функцией;

отношение 3) -функция, которая обычно обозначается у = х² - 2х - 3.

19. Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый - с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?

Решение. Пусть на мяче число белых лоскутов х штук, а чёрных будет (32 - х) штук. Тогда, границ белых лоскутов с чёрными: 5(32-х) =3х, значит х= 20 и белых лоскутов 20 штук.

Ответ: 20 лоскутов белого цвета.

20. Из 4 первокурсников, 5 второкурсников и 6 третьекурсников надо выбрать 3 студента на конференцию. Сколькими способами можно осуществить этот выбор, если среди выбранных должны быть студенты разных курсов?

Решение .××= 4*5*6 = 120

Ответ: 120 способов.

21. Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различны?

Решение. Размещения с возвращением: 9⁴=6561

Ответ: 6561 чисел.

22. Сколькими способами можно рассадить 5 человек за круглым столом (рассматривается только расположение сидящих относительно друг друга)?

Решение. Р₄= 4! = 24

Ответ: 24 способа.

23. Сколькими способами можно распределить 15 выпускников по 3 районам, если в одном из них имеется 8, в другом - 5 и в третьем - 2 вакантных места?

Решение. С₁₅^8* С₇^{5 *} С₂^{2 =} 135135.

Ответ: 135135 способов.

24. Известно, что 7 студентов сдали экзамен по дискретной математике на хорошо и отлично. Сколькими способами могли быть поставлены им оценки?

Решение.= 2⁷=128 Ответ: 128 способов.

25. Группа студентов изучает 10 различных дисциплин. Сколькими способами можно составить расписание занятий в понедельник, если в этот день должно быть 4 разных занятия?

Решение. А₁₀⁴=10*9*8*7 = 5040 Ответ: 5040 способов.

26. Из 60 вопросов, входящих в экзаменационные билеты, студент знает 50. Найти вероятность того, что среди трех наугад выбранных вопросов студент знает:

а) все вопросы, б) два вопроса.

Решение. а) р = = 0,573; б) р = = 0,36.

Ответ: а) 0,573; б) 0,36.

27. Во взводе три сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

Решение. С₃¹*С₃₀³= 3!/1!2!* 30!/3!27! = 30*29*14 = 12180.

Ответ: 12180 способов.

28. В барабане револьвера 7 гнезд, из них в 5 заложены патроны. Барабан приводится во вращение, потом нажимается спусковой курок. Какова вероятность того, что, повторив такой опыт 2 раза подряд: а) револьвер оба раза не выстрелит, б) оба раза револьвер выстрелит.

Решение: а) Р = = 4/49; б) Р = = 20/49. Ответ: 4/49; 20/49.

29. Решить уравнение: 5 Ответ: х = 14; х = 3.

30. Решить уравнение: Ответ: х = 10; х= - 8.

31. Решить уравнение: _{Ответ: х = 19/3.}

32. Решить уравнение: + = 15(х-1) Ответ: х = -10; х = 9.

33. Решить уравнение: = Ответ: х= 1; х = 9,5.

34. Записать предложение: «прямая а параллельна прямой b» с помощью предиката.

Решение. Предметная область - множество прямых.

Введем предикат Р (х), х - прямая. Предикат параллельности х||у .

Тогда предложение можно записать в виде: Р (а) Р(b) (а||b) .

35. Записать с помощью предиката: «Аксиома: через две различные точки проходит единственная прямая» (Если две точки принадлежат двум прямым, то эти прямые совпадают).

Решение. Введем предикаты: Т (х), х - точка; Р (х), х - прямая; J(x,y) - x у.

Тогда можно записать:

Т (А)Т (В)_{(А ≠ В)}Р (а)Р(b)J(A,a)J(B,а)J(A,b)J(B,b) (a=b).

36. Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

Решение: Составим схему-граф маршрутов:

Ответ: от З до М добраться нельзя.

37. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10. Ответ: 10.

38. К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города.

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

Решение:

Решить эту задачу удалось в 1736 г. Леонарду Эйлеру . В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке.)

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

Ответ: нельзя.

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

Решение. Построим граф, вершины которого А, Б, В, 1, 2, 3 соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку - ребро графа, не пересекающее остальные ребра, провести нельзя.

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).
Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»

Ответ: нельзя.

40. В городе Н от каждой площади отходит ровно пять улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно пяти.

Решение. Из теоремы о том, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.

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

Решение. Пусть существует некоторый город А. Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А). Тогда всего городов не более 1+3+6=10. Значит всего городов не более 10. Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.

Ответ: не более 10.

42. Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

1)2)

Ответ: 1) можно, так как только две нечетные вершины; 2) нельзя, так как нечетных вершин - четыре.

43. Составить матрицу инцидентности данного орграфа:

Решение.

X1

X2

X3

X4

X5

X6

V1

1

-1

0

0

-1

0

V2

-1

0

1

0

1

0

V3

0

0

-1

1

0

-1

V4

0

1

0

-1

0

1

4544. Составить матрицу смежности данного орграфа:

Решение.

V1

V2

V3

V4

V1

0

0

0

1

V2

1

0

0

1

V3

0

1

0

1

V4

0

0

1

0

45. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

Решение. Участников этой компании изобразим вершиной графа, а отношение знакомства между двумя учасниками - ребром. Изобразим графы, которые могут соответствовать такой компании.

46. Из пункта А в пункт В выехали пять машин одной марки разного цвета: белая, черная, красная, синяя, зеленая. Черная едет впереди синей, зеленая - впереди белой, но позади синей, красная впереди черной. Какая машина едет первой и какая последней?

Решение. Решаем задачу, построив ориентированный граф для отношения f :

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

47. Пусть даны графы G₁(X, E) и G₂(Y, E). Установите, изоморфны ли данные графы

48. Найдите функции g и h в рекурсивной формуле для двухместной функции f(x,y)=x y , если рекурсия проводиться по переменной х.

49. Найдите функции g и h в рекурсивной формуле для трехместной функции f(x,y,z) = x y+z, если рекурсия проводится по переменной y.

50. Примените оператор минимизации к функции

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

Решение.

52. Для автомата, заданного диаграммой Мура, выпишите соответственную таблицу и систему булевых функций

Решение.

53. Для автомата, заданного каноническими уравнениями, постройте диаграмму Мура и соответствующую таблицу .

Решение.

7. Критерии оценки:

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

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

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

9. Приложение: перечень вопросов к зачету

Государственное бюджетное профессиональное образовательное учреждение города Москвы

«Западный комплекс непрерывного образования

Рассмотрено на ЦК

по специальности

«Компьютерные системы, сети и телекоммуникации (КСТ)»

Протокол № ___

от ______________ 2016г.

Председатель ЦК

___________ /Журкин М.С./

ВОПРОСЫ К ЗАЧЕТУ

по дисциплине

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

Специальность 09.02.01 Компьютерные системы и комплексы

Семестр: 4

Утверждаю:

Зав. отделением СПО

_________/И.Н. Мордвинова/

« ___ » __________ 2016 г.

Теоретические задания:

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

2. Составные высказывания. Простейшие связки. Логические отношения.

3. Варианты импликации.

4. Основные законы, определяющие свойства логических операций.

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

6. Свойства элементарных булевых функций.

7. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний.

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

9. Многочлены Жегалкина.

10. Специальные классы булевых функций: функции, сохраняющие единицу, функции, сохраняющие нуль, самодвойственные функции,линейные функции, монотонные функции. Теорема Поста о функциональной полноте.

11. Понятие множества. Способы задания множества. Подмножества. Операции над множествами.

12. Соотношения между множествами и составными высказываниями.

13. Соотношение между высказываниями и соответствующими им множествами истинности.

14. Абстрактные законы операций над множествами.

15. Кортежи и декартово произведение множеств. Степень множества.

16. Бинарные отношения в множестве и их свойства.

17. Отношения строгого и нестрогого порядка.

18. Отображение множеств. Функции.

19. Определенность и неопределенность функций. Композиция отображений.

20. Метод математической индукции. База индукции. Индукционный переход. Полная и неполная индукция.

21. Основные правила комбинаторики. Методы алгоритмического перечисления (генерации) основных комбинаторных объектов: перестановка, сочетание, размещение.

22. Комбинация элементов с повторениями. Бином Ньютона.

23. Предикаты. Применение предикатов в алгебре.

24. Булева алгебра предикатов.

25. Кванторы. Формулы логики предикатов.

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

27. Исчисления предикатов.

28. Основные понятия теории графов. Степень вершины. Маршрут, цепи, циклы. Связность графа.

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

30. Изоморфизм графов.

31. Плоские графы. Операции над графами.

32. Способы задания графов. Некоторые типы графов.

33. Сети. Сетевые модели представления информации. Применение графов и сетей.

34. Вычислимые функции и алгоритмы.

35. Рекурсивные функции.

36. Нормальный алгоритм Маркова.

37. Машины Тьюринга.

38. Понятия конечного автомата. Определения и способы задания конечного автомата.

39. Примеры конечных автоматов.

40. Канонические уравнения автомата.

Практические задания:

1. Докажите тождественную истинность формулы →(Х→У).

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f₁= X٨ (Y→Z) и f₂= (٨Y) ٧ (X٨Z).

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

а) Х↔Х, б)Х↔, в)(Х٧У)↔(Х٨У), г)(Х→)→(У→), д)(X→Y)٨(Y→Z)٨, е)(Х→У)→Х, ж)((Х→У)→Х

4. Доказать закон отрицания конъюнкции ()

5. Найти значение и убедиться, что при всех значениях A и B - это истинное значение.

6. С помощью основных равносильностей доказать закон обобщенного склеивания .

7. Составьте таблицу истинности булевой функции трех переменных f(х_1, х_2, х₃) = х₁ х₂→٧х₁ | )٨) и найдите ее двоичный набор.

8. Докажите эквивалентность функции: f_{(x, y, z)} = x٨(x٧z)٨(y٧z) и f_{(x, y, z)} = (x٨y)٧(x٨z).

9. Найдите СДНФ и СКНФ функции f_{(x, y, z)}, заданной следующей таблицей истинности:

х₁

х₂

х₃

f(х_1, х_2, х₃)

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

10. Опрос 100 студентов выявил следующие данные о числе студентов, изучающих различные иностранные языки: английский - 28; немецкий - 30; французский - 42, английский и немецкий - 8; английский и французский - 10; немецкий и французский - 5; все три языка - 3.

1) Сколько студентов не изучают ни одного иностранного языка?

2) Сколько студентов изучают один французский язык?

3) Сколько студентов изучают немецкий язык в том и только в том случае, если они изучают французский язык?

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

Ответ: 1) 20; 2) 30; 3) 38.

11. Изобразите с помощью диаграмм Эйлера-Венна множества:

1) и ; 2); и А \ В = ; 3); и С=;

4)В; и ; 5)(А \ В)(В \ А).

12. Воспользовавшись диаграммой Эйлера-Венна, определите, какие из следующих высказываний истинны: а)Х; б) Х; в) Х г) X→(Y→X); д)X.

13. Пусть А = {1, 2}. Выписать все элементы декартова произведения А×А.

14. Рассмотрим два множества А = {a, b, c, d, e, f, g, h} и В = {1, 2, 3, 4, 5, 6, 7, 8}.

15. Проверьте на линейность функцию f(х_1, х_2, х₃), если ее двоичный набор F= 11100001.

16. Найдите правую и левую области отношения R = {‹1, 5› ; ‹1, 6› ; ‹1, 7›}.

17. Если А = {2, 3,4, 5, 6, 7, 8}, запишите бинарное отношение R = {‹х, у› : х, у А,

х делит у, и х 3}.

18. Являются ли следующие отношения функциями:

1. {‹1, 2› ; ‹2, 3› ; ‹3, 2›}; 2) {‹1, 2› ; ‹1, 3› ; ‹2, 3›};

3) {х,х² - 2х - 3 : }?

19. Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый - с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?

20. Из 4 первокурсников, 5 второкурсников и 6 третьекурсников надо выбрать 3 студента на конференцию. Сколькими способами можно осуществить этот выбор, если среди выбранных должны быть студенты разных курсов?

21. Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различны?

22. Сколькими способами можно рассадить 5 человек за круглым столом (рассматривается только расположение сидящих относительно друг друга)?

23. Сколькими способами можно распределить 15 выпускников по 3 районам, если в одном из них имеется 8, в другом - 5 и в третьем - 2 вакантных места?

24. Известно, что 7 студентов сдали экзамен по дискретной математике на хорошо и отлично. Сколькими способами могли быть поставлены им оценки?

25. Группа студентов изучает 10 различных дисциплин. Сколькими способами можно составить расписание занятий в понедельник, если в этот день должно быть 4 разных занятия?

26. Из 60 вопросов, входящих в экзаменационные билеты, студент знает 50. Найти вероятность того, что среди трех наугад выбранных вопросов студент знает: а) все вопросы, б) два вопроса.

27. Во взводе три сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

28. В барабане револьвера 7 гнезд, из них в 5 заложены патроны. Барабан приводится во вращение, потом нажимается спусковой курок. Какова вероятность того, что, повторив такой опыт 2 раза подряд: а) револьвер оба раза не выстрелит, б) оба раза револьвер выстрелит.

29. Решить уравнение: 5

30. Решить уравнение:

31. Решить уравнение:

32. Решить уравнение: + = 15(х-1)

33. Решить уравнение: =

34. Записать предложение: «прямая а параллельна прямой b» с помощью предиката.

35. Записать с помощью предиката: «Аксиома: через две различные точки проходит единственная прямая» (Если две точки принадлежат двум прямым, то эти прямые совпадают).

36. Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

37. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

38. К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города.

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

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

40. В городе Н от каждой площади отходит ровно пять улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно пяти.

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

42. Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

1)2)

43. Составить матрицу инцидентности данного орграфа:

4544. Составить матрицу смежности данного орграфа:

45. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

46. Из пункта А в пункт В выехали пять машин одной марки разного цвета: белая, черная, красная, синяя, зеленая. Черная едет впереди синей, зеленая - впереди белой, но позади синей, красная впереди черной. Какая машина едет первой и какая последней?

47. Пусть даны графы G₁(X, E) и G₂(Y, E). Установите, изоморфны ли данные графы

48. Найдите функции g и h в рекурсивной формуле для двухместной функции f(x,y)=x y , если рекурсия проводиться по переменной х.

49. Найдите функции g и h в рекурсивной формуле для трехместной функции f(x,y,z) = x y+z, если рекурсия проводится по переменной y.

50. Примените оператор минимизации к функции

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

52. Для автомата, заданного диаграммой Мура, выпишите соответственную таблицу и систему булевых функций

53. Для автомата, заданного каноническими уравнениями, постройте диаграмму Мура и соответствующую таблицу .