Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Контрольно-оценочные средства для промежуточной аттестации по "Дискретной математике" и "Элементам высшей математке"

Контрольно-оценочные средства для промежуточной аттестации по "Дискретной математике" и "Элементам высшей математке"

  • Математика

Поделитесь материалом с коллегами:

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

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

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






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

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







Комплект

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

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

ОП.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. Докажите тождественную истинность формулыhello_html_29ad3803.gif →(Х→У).

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f1= X٨ (YZ) и f2= (hello_html_29ad3803.gif٨Y) ٧ (X٨Z).

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

а) Х↔Х, б)Х↔hello_html_29ad3803.gif, в)(Х٧У)↔(Х٨У), г)(Х→hello_html_m57b5b6b8.gif)→(У→hello_html_29ad3803.gif), д)(XY)٨(YZ)٨hello_html_7e63f044.gif, е)(Х→У)→Х, ж)((Х→У)→Х

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

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

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

7. Составьте таблицу истинности булевой функции трех переменных f1, х2, х3) = х1 hello_html_6ce33.gifх2hello_html_26d5b52f.gif٧х1 | )hello_html_77225543.gif٨hello_html_2cedf75d.gif) и найдите ее двоичный набор.

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

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

х1

х2

х3

f1, х2, х3)

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)hello_html_m32788729.gif и hello_html_m32dba535.gif; 2)hello_html_m32788729.gif; hello_html_m32dba535.gif и А \ В = hello_html_m6c410134.gif; 3)hello_html_m32788729.gif; hello_html_m32dba535.gif и С=hello_html_f71043a.gif;

4)hello_html_m3eccf2ef.gifВ; hello_html_m32dba535.gif и hello_html_m359b528b.gif; 5)(А \ В)hello_html_69c8c4a6.gif(В \ А).


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

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

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

15. Проверьте на линейность функцию f1, х2, х3), если ее двоичный набор F= 11100001.

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

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

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

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

3) {х,х2 – 2х – 3 : hello_html_50e8285f.gif}?

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. Решить уравнение: 5hello_html_3c20e34c.gif

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


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

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



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


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


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

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


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


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

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

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

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



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


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

1)hello_html_m64a73a0e.gif2)


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

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









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

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

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


hello_html_m6da9fbf8.png




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

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

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

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

hello_html_69360b25.png

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

hello_html_4c459f6d.png

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


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

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

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

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

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

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

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

hello_html_m45c92f56.pnghello_html_69b7362a.pnghello_html_m1c68040.pnghello_html_211a5036.pnghello_html_m3a629e4f.pnghello_html_m1c6ee096.pnghello_html_m686b0a4f.pnghello_html_ab07cc2.pnghello_html_mfdd1e89.pnghello_html_m26f26b91.pnghello_html_418d950b.png3. Варианты импликации.

hello_html_m424463df.png

hello_html_3df60d06.pnghello_html_512a03bb.pnghello_html_4abbfd10.png

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

hello_html_m209c481e.pnghello_html_m76f62bbe.pnghello_html_m726cfcc7.pnghello_html_m441a6f16.pnghello_html_1862aab5.png


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

hello_html_64a4c617.pnghello_html_47c3a21b.pnghello_html_m477dfb76.pnghello_html_m1bce0007.pnghello_html_m329791f2.pnghello_html_58832b21.pnghello_html_mcbfb001.png

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

hello_html_m70c70344.pnghello_html_77bfeda.pnghello_html_me672f9b.pnghello_html_415f6322.pnghello_html_m2d93be17.png

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

hello_html_70bed47a.pnghello_html_m2fbbf349.png

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

hello_html_489880e0.pnghello_html_324faaec.pnghello_html_m7c3843ed.pnghello_html_675dd399.pnghello_html_m4d334037.pnghello_html_m73beb27f.png

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

hello_html_m6cd50c88.png

hello_html_1467296f.pnghello_html_m1f9571de.png

hello_html_208d9f41.pnghello_html_m37308630.png

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


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

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

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

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

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

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

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

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

полноту.

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

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

hello_html_m20832c5c.gif.

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

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

hello_html_m72525465.gif.

Таким образом, система hello_html_4d679d30.gif сводится к системе hello_html_m37dec2af.gif, а система hello_html_m282421f4.gif - к системе hello_html_m4ee1814c.gif.

в) Система hello_html_b0b719e.gif (hello_html_m5c7206cc.gifумножение по модулю 2, hello_html_m4ea03aa7.gifсложение по модулю 2 – см. пункт 1 лекции № 8)) является функционально полной. Поскольку hello_html_mdca1466.gif, данная система сводится к hello_html_5322ca38.gif.


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

hello_html_m55402d44.pnghello_html_m373abe7e.pnghello_html_4bbb4f2f.pnghello_html_3a373f57.pnghello_html_m32f074ea.pnghello_html_79b1aa83.png

hello_html_m556843a0.png

hello_html_491c9f20.pnghello_html_43e46af5.png

hello_html_2b29ac5.pnghello_html_m67fbca29.png

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

hello_html_m147aab40.pnghello_html_d46ac49.pnghello_html_m6d9c9bfc.pnghello_html_7fcf176f.pnghello_html_m65fa2924.png

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

hello_html_6203e76a.pnghello_html_e96d490.pnghello_html_m3194551d.pnghello_html_616622a3.pnghello_html_41a39bf6.png

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

hello_html_m39ec94f6.pnghello_html_m329091ab.pnghello_html_m70d28079.pnghello_html_1809402e.pnghello_html_m567249f2.png

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

hello_html_m4565626c.pnghello_html_m3387de9e.pnghello_html_4af1fa3c.png

hello_html_2ed61b3c.pnghello_html_8302ad.png

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

hello_html_m2447a09.pnghello_html_m1ca58b0b.png

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

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

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


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


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

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

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

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

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

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


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

hello_html_fd22635.pnghello_html_m6fa76737.pnghello_html_329e2566.pnghello_html_99e9c1f.png

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

hello_html_m471472b3.pnghello_html_14f6845.pnghello_html_m38eea9aa.png

hello_html_6b81eb8a.png

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


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

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

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

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

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

n

2n

Последняя

цифра 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 n на 4.

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

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

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

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

hello_html_m75d80bb0.png

hello_html_ef0f66e.pnghello_html_m71977a96.pnghello_html_326ae540.png

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

hello_html_m10069926.pnghello_html_5abcf4dd.pnghello_html_5e305b28.pnghello_html_m55b0b8f5.pnghello_html_3a7d1cb.png

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

hello_html_m1af56d.pnghello_html_m4eb06a87.pnghello_html_12df07ff.pnghello_html_m41e1cbdc.png

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

hello_html_4eabcfbe.png

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

hello_html_655d7975.pnghello_html_m5e2110b6.pnghello_html_m7064c636.png

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

hello_html_m2aa69f5c.pnghello_html_7b71b905.pnghello_html_md7115a7.pnghello_html_11d6443b.pnghello_html_m3c35a6af.pnghello_html_m5f2a7e5d.pnghello_html_11f0a4ec.pnghello_html_m7caf3f60.pnghello_html_787dd75a.pnghello_html_75f8e331.pnghello_html_m692f3a76.pnghello_html_12eddd7.pnghello_html_6aab15f1.pnghello_html_m43313a0f.pnghello_html_67217e36.pnghello_html_m212d817.png

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

hello_html_m4dad8b7.pnghello_html_m59547ec1.pnghello_html_m44688c4.pnghello_html_m39ca4ce8.png

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

hello_html_m114e6e2b.pnghello_html_m5cf5699f.pnghello_html_m3550fbdb.pnghello_html_3b6a9f00.pnghello_html_m35aa7404.pnghello_html_m44c0f552.png

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

hello_html_m334f200c.pnghello_html_3fe1b691.png

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


hello_html_65b4a58f.pnghello_html_m36bd8961.pnghello_html_m4078cd4d.pnghello_html_m330b518a.png

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

hello_html_10be155a.pnghello_html_5be1208b.pnghello_html_2b8ae3fd.png

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

hello_html_m1f021b9a.pnghello_html_1f8c6a79.pnghello_html_m538ce0d9.pnghello_html_39656bee.pnghello_html_m2dac2d41.pnghello_html_m6c933426.pnghello_html_m45d827fa.pnghello_html_m7b2b2e59.pnghello_html_78bb967f.pnghello_html_m58030028.pnghello_html_1f00eeee.pnghello_html_m76dd1143.pnghello_html_m189cf639.png

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

hello_html_1508e9f2.pnghello_html_m4ba03b80.png

hello_html_m7b1cc442.pnghello_html_678dc2da.png

hello_html_m7697769.png

hello_html_1ea17976.png

hello_html_6b1c93e9.pnghello_html_m66af6881.png

hello_html_m3e1bb8bd.png

hello_html_3e3ac701.png

hello_html_m326a8ebe.pnghello_html_mfdf8eff.pnghello_html_m717d2104.png

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

hello_html_e288bee.pnghello_html_m4dcfc3c3.png

hello_html_m87a6f95.pnghello_html_728f522f.pnghello_html_3577cb7f.pnghello_html_md5ee579.pnghello_html_66f2358a.pnghello_html_35594e45.png

hello_html_m14b19409.pnghello_html_6583e407.pnghello_html_m16a416e.png

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

hello_html_mc5d6394.pnghello_html_1e9d6922.pnghello_html_m57090353.pnghello_html_m5132dd31.pnghello_html_c5e8b6f.pnghello_html_m71762654.png

hello_html_59dad89b.pnghello_html_mc0dde53.png

hello_html_34282fd0.pnghello_html_m6bdacd2e.png

hello_html_m1b4d3327.png

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

hello_html_2f783f84.pnghello_html_1d29b38a.png

hello_html_m4b2291ff.png

hello_html_560b9a3f.pnghello_html_m36cc709d.pnghello_html_1ea4a2c.pnghello_html_1695a1df.pnghello_html_m4ab47637.pnghello_html_m6cb959e6.png

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

hello_html_m784ab17e.png

hello_html_m5ba4631.pnghello_html_7232b9af.png

hello_html_m1588ef70.pnghello_html_m3e67bf95.pnghello_html_m3239a835.png

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

hello_html_3812e440.pnghello_html_m1754d998.png

hello_html_445643d0.png

hello_html_m4db04ad5.pnghello_html_634e9926.pnghello_html_79f0d897.pnghello_html_m749dfae0.pnghello_html_1bddfa09.pnghello_html_m3cf514be.pnghello_html_760a0e84.png

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

hello_html_28182ee8.pnghello_html_m158717c5.pnghello_html_m6d5b0828.png hello_html_m21c9bfe4.png

hello_html_m6c7d74e0.pnghello_html_3c80f029.pnghello_html_m563fcd00.pnghello_html_m56505fcb.pnghello_html_559467a2.pnghello_html_72ea52a1.pnghello_html_3a0ddb1a.pnghello_html_m5ae7c907.pnghello_html_1020dfbe.pnghello_html_m67f64185.pnghello_html_m2a6af2a0.pnghello_html_2d8781a6.png hello_html_19917d7d.png hello_html_5169e57d.pnghello_html_m59c2028b.pnghello_html_mb191255.pnghello_html_60d19627.pnghello_html_fe1fc13.pngрис. 7.7

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

hello_html_69aa3411.pnghello_html_m63db633f.pnghello_html_23482e36.pnghello_html_m585eec5c.pnghello_html_45483d62.pnghello_html_m2bf4ef53.pnghello_html_b81f16b.png

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

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

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

X

Y

hello_html_29ad3803.gif

Х→У

hello_html_29ad3803.gif(Х→У).

0

0

1

1

1

0

1

1

1

1

1

0

0

0

1

1

1

0

1

1



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

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f1= X٨ (YZ) и f2= (hello_html_29ad3803.gif٨Y) ٧ (X٨Z).

Решение.

X

Y

Z

hello_html_29ad3803.gif

YZ

f1

hello_html_29ad3803.gif٨Y

X٨Z

f2

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



Ответ: так как значения для высказываний f1 и f2 в таблице истинности не совпадали, то они не эквивалентны.



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

а) Х↔Х, б) Х↔hello_html_29ad3803.gif, в) (Х٧У)↔(Х٨У), г) (Х→hello_html_m57b5b6b8.gif)→(У→hello_html_29ad3803.gif),

д) (XY)٨(YZ)٨hello_html_7e63f044.gif, е) (Х→У)→Х, ж) ((Х→У)→Х.

Решение.

X

Y

Х↔Х

hello_html_29ad3803.gif

Х↔hello_html_29ad3803.gif

Х٧У

Х٨У

٧У)↔(Х٨У)

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



а)


б)



в)

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

Х

У

hello_html_m57b5b6b8.gif

Х→hello_html_m57b5b6b8.gif

У→hello_html_29ad3803.gif

(Х→hello_html_m57b5b6b8.gif)→(У→hello_html_29ad3803.gif)

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

(XY)٨(YZ)

Х→Z

hello_html_2da23a35.gif

(XY)٨(YZ)٨hello_html_7e63f044.gif

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. Доказать закон отрицания конъюнкции (hello_html_m6f6c0f52.gif)

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

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

A

B

hello_html_deaf6db.gif

hello_html_m6f11c5e9.gif

hello_html_m1d7af487.gif

hello_html_763e8747.gif

hello_html_bdcfd75.gif

И

И

И

Л

Л

Л

Л

И

Л

Л

И

Л

И

И

Л

И

Л

И

И

Л

И

Л

Л

Л

И

И

И

И

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

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

Решение.

A

B

hello_html_deaf6db.gif

hello_html_m6f11c5e9.gif

hello_html_m1d7af487.gif

hello_html_763e8747.gif

hello_html_bdcfd75.gif

hello_html_m6f6c0f52.gif

И

И

И

Л

Л

Л

Л

И

И

Л

Л

И

Л

И

И

И

Л

И

Л

И

И

Л

И

И

Л

Л

Л

И

И

И

И

И

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

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

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



7. Составьте таблицу истинности булевой функции трех переменных f1, х2, х3) =

х1 hello_html_6ce33.gifх2hello_html_26d5b52f.gif٧х1 | )hello_html_77225543.gif٨hello_html_2cedf75d.gif) и найдите ее двоичный набор.

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

f1 = х1hello_html_6ce33.gifх2; f 2 = hello_html_m795652cc.gif٨hello_html_m719892af.gif; f3 = х1 | f2; f4 = hello_html_2fc3d17.gif٧f3; f5 = f1f4.

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

х1

х2

х3

hello_html_m719892af.gif

hello_html_m795652cc.gif

hello_html_2fc3d17.gif

f1

f2

f3

f4

f5

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

Лексикографическое упорядочение наборов в таблице истинности булевой функции позволяет задать функцию двоичным набором длины 2n, который будет обозначаться буквой 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


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

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

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

х1

х2

х3

f1, х2, х3)

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

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

hello_html_m69dce421.gif٨hello_html_m6c5ea4e1.gif٧1٨hello_html_m795652cc.gif٨х3)٧(hello_html_m7d3b4ff8.gifх2٨х3)٧1٨х2٨х3),

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

(х1٧х2٧hello_html_m729c79d6.gif٨1٧hello_html_m55313fd8.gifх3)٨(hello_html_m719892af.gif٧х2٧х3)٨(hello_html_m719892af.gif٧hello_html_m795652cc.gif٧х3).

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

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

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

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

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

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

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

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

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

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

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

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

1)hello_html_m32788729.gif и hello_html_m32dba535.gif; 2)hello_html_m32788729.gif; hello_html_m32dba535.gif и А \ В = hello_html_m6c410134.gif; 3)hello_html_m32788729.gif; hello_html_m32dba535.gif и С=hello_html_f71043a.gif;

4)hello_html_m3eccf2ef.gifВ; hello_html_m32dba535.gif и hello_html_m359b528b.gif; 5)(А \ В)hello_html_69c8c4a6.gif(В \ А).

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

(А \ В)hello_html_69c8c4a6.gif(В \ А)

hello_html_7bb629d9.gif

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



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

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

hello_html_m470ffd2.gif


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

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}.

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

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

15. Проверьте на линейность функцию f1, х2, х3), если ее двоичный набор F= 11100001.

Решение. Применяем к функции f1, х2, х3) алгоритм проверки на линейность.

Вычисляем коэффициенты а0, а1, а2, а3 многочлена Жегалкина для данной функции:

а0 = f(0, 0, 0,) = 1; a1 = f(0, 0, 0)hello_html_6ce33.giff(1, 0, 0) = 1hello_html_6ce33.gif0 = 1; а2 = f(0, 0, 0)hello_html_6ce33.giff(0, 1, 0) = 1hello_html_6ce33.gif1 = 0; а3 = f(0, 0, 0)hello_html_6ce33.giff(0, 0, 1) = 1hello_html_6ce33.gif1 = 0.

Вычисляем многочлен: f1, х2, х3) = а0hello_html_6ce33.gifа1х1hello_html_6ce33.gifа2х2hello_html_6ce33.gifа3х3 = х1hello_html_6ce33.gif1.

Очевидно, что двоичный набор F = 11110000 многочлена f1, х2, х3) = х1hello_html_6ce33.gif1 не совпадает с двоичным набором булевой функции, следовательно, функция f1, х2, х3) не линейна.

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 = {‹х, у› : х, у hello_html_m2e28bbd1.gif А,

х делит у, и х hello_html_m54ea4251.gif3}.

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

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

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

  2. {х,х2 – 2х – 3 : hello_html_50e8285f.gif}?

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

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

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

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

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

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

Решение .hello_html_44db748d.gif×hello_html_me56d9d2.gif×hello_html_6da1d5d8.gif= 4*5*6 = 120

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

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

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

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

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

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

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

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

Решение. С158* С75 * С22 = 135135.

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

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


Решение.hello_html_66461e6e.gif= 27=128 Ответ: 128 способов.



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

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


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

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

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

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



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

Решение. С31303= 3!/1!2!* 30!/3!27! = 30*29*14 = 12180.

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

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

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

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

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


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


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


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


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

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

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

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


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

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

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

Т (А)hello_html_3f84af95.gifТ (В)hello_html_3f84af95.gif(А ≠ В)hello_html_3f84af95.gifР (а)hello_html_3f84af95.gifР(b)hello_html_3f84af95.gifJ(A,a)hello_html_3f84af95.gifJ(B,а)hello_html_3f84af95.gifJ(A,b)hello_html_3f84af95.gifJ(B,b) hello_html_m6da0e660.gif(a=b).

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

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

hello_html_m1ce8c5b4.gif

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


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


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

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



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

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

Решение:

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

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

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

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

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

gr6_2

Проведенные в графе на рисунке ребра А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. Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.

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



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

1)hello_html_m64a73a0e.gif2)

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


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





Решение.


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



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








Решение.


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. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

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

hello_html_ma687363.pnghello_html_47ca1454.png

hello_html_45537e34.png

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

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

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

hello_html_6ddb44fb.pnghello_html_7376535e.png

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


hello_html_m6da9fbf8.pnghello_html_5525fdd0.png

hello_html_m5e6405e7.png

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

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

hello_html_4375adda.png

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

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

hello_html_69360b25.png

Решение. hello_html_m2d8c580d.pnghello_html_m7dc1572.png

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

hello_html_4c459f6d.pngРешение. hello_html_m3bb587e8.pnghello_html_51f76c6a.png

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

Решение.

hello_html_m68b3c96c.pnghello_html_489062f4.jpg
























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. Докажите тождественную истинность формулыhello_html_29ad3803.gif →(Х→У).

2. С помощью таблиц истинности проверить, являются ли эквивалентными высказывания: f1= X٨ (YZ) и f2= (hello_html_29ad3803.gif٨Y) ٧ (X٨Z).

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

а) Х↔Х, б)Х↔hello_html_29ad3803.gif, в)(Х٧У)↔(Х٨У), г)(Х→hello_html_m57b5b6b8.gif)→(У→hello_html_29ad3803.gif), д)(XY)٨(YZ)٨hello_html_7e63f044.gif, е)(Х→У)→Х, ж)((Х→У)→Х

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

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

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

7. Составьте таблицу истинности булевой функции трех переменных f1, х2, х3) = х1 hello_html_6ce33.gifх2hello_html_26d5b52f.gif٧х1 | )hello_html_77225543.gif٨hello_html_2cedf75d.gif) и найдите ее двоичный набор.

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

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

х1

х2

х3

f1, х2, х3)

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)hello_html_m32788729.gif и hello_html_m32dba535.gif; 2)hello_html_m32788729.gif; hello_html_m32dba535.gif и А \ В = hello_html_m6c410134.gif; 3)hello_html_m32788729.gif; hello_html_m32dba535.gif и С=hello_html_f71043a.gif;

4)hello_html_m3eccf2ef.gifВ; hello_html_m32dba535.gif и hello_html_m359b528b.gif; 5)(А \ В)hello_html_69c8c4a6.gif(В \ А).


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

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

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

15. Проверьте на линейность функцию f1, х2, х3), если ее двоичный набор F= 11100001.

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

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

х делит у, и х hello_html_m54ea4251.gif3}.

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

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

3) {х,х2 – 2х – 3 : hello_html_50e8285f.gif}?

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. Решить уравнение: 5hello_html_3c20e34c.gif

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


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

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


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


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


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

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


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


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

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

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

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



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


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

1)hello_html_m64a73a0e.gif2)

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

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









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

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

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


hello_html_m6da9fbf8.png




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

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

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

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

hello_html_69360b25.png

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

hello_html_4c459f6d.png

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















































Автор
Дата добавления 11.03.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров203
Номер материала ДВ-517937
Получить свидетельство о публикации
Похожие материалы

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