Министерство образования и науки Хабаровского края

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

«Хабаровский промышленно-экономический техникум»

ФОНД ОЦЕНОЧНЫХ СРЕДСТВ

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

ЕН.02 Дискретная математика с элементами математической логики

___________________________________________________________

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

09.02.07  Информационные системы и программирование

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

Хабаровск, 2020

Составитель: преподаватель КГБ  ПОУ  ХПЭТ М.С. Серганова __________

Рассмотрен и одобрен на заседании цикловой комиссии ______________________

протокол №___ от  «___»  ____________ 2020 г.

ФОС разработан на основе Федерального государственного образовательного стандарта среднего профессионального образования по специальности  09.02.07  «Информационные системы и программирование», утвержденного приказом Министерства образования и науки РФ от 10 января 2018 г. N 2.

СОДЕРЖАНИЕ

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

2. Паспорт фонда оценочных средств по дисциплине                                                   4

3. Комплект контрольно-оценочных средств для текущего контроля                         6

4. Комплект контрольно-оценочных средств для промежуточной аттестации          33

5.Перечень рекомендуемой учебной литературы, методических пособий и             37

Интернет-ресурсов                                                                                                          

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

В результате освоения дисциплины обучающийся осваивает следующие общие и профессиональные компетенции:

ОК 01 Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам

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

ОК 04 Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.

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

ОК 09 Использовать информационные технологии в профессиональной деятельности

ОК 10 Пользоваться профессиональной документацией на государственном и иностранном языках.

Умения:

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

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

Знания:

Основные принципы математической логики, теории множеств и теории алгоритмов.

Формулы алгебры высказываний.

Методы минимизации алгебраических преобразований.

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

Основные принципы теории множеств.

2. ПАСПОРТ

ФОНДА ОЦЕНОЧНЫХ СРЕДСТВ

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

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

наименование учебной дисциплины

3. Комплект контрольно-оценочных средств для текущего контроля  

Тема 1.1 Алгебра высказываний

Задание 1 для письменного ответа:

1) С помощью таблицы истинности проверить справедливость следующего тождества:

а)

б)

в)

г)

2) Составить таблицы истинности для следующих выражений:

а)

б)

в)

г)

Критерии оценивания ответа:

Правильное решение 7-8 заданий соответствует оценке «5»

Правильное решение 5-6 заданий соответствует оценке «4»

Правильное решение 4 заданий соответствует оценке «3»

Правильное решение 0-3 заданий в соответствует оценке «2»

Задание 2 для письменного ответа:

1) Заполните пропуски:

а)Логика (от греческого слова «logos» - ________________________) – совокупность наук о ________________ и __________________ мышления, о наиболее общих законах _________________.

б) Начало исследования в области формальной логики было положено работами ____________________ в ______________

в) Логика оперирует __________________________________________

г) Математическая логика применяет для анализа рассуждений __________________________________________________________________

д) Основоположник алгебры логики ____________________________

е) Высказывание — повествовательное предложение, о котором можно сказать, ______________ оно или ______________

ж) Алгебра логики занимается исследованием ___________________

____________________________

2) Закончите предложения:

а) Суждение – это ____________________________________________
__________________________________________________________________

б) Умозаключение – это_______________________________________
__________________________________________________________________

в)Логическое выражение – это _________________________________

__________________________________________________________________

3) Какие из приведенных высказываний являются истинными, а какие ложными? Перечислите через запятую в строках таблицы.

а) Земля – это звезда

б) 5>3

в) 4-1=10

г) Париж – это столица Англии

д) Москва – столица России

е) Корова – млекопитающее.

4) Поставить в соответствие определение логических операций и их названий:

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

б) Сложное высказывание ложно тогда и только тогда, когда А и В ложны одновременно.

в) Если высказывание А истинно, то В ложно, и наоборот.

г) Сложное высказывание АʌВ истинно тогда и только тогда, когда оба высказывания истинны одновременно.

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

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Задание 3 для письменного ответа:

Максимально упростите выражение, с помощью равносильных преобразований Затем, с помощью таблицы истинности, сравните Ваше упрощенное выражение с исходным:

1)

2) 

3) 

4) 

5)

Критерии оценивания ответа:

Правильное решение 5 заданий соответствует оценке «5»

Правильное решение 4 заданий соответствует оценке «4»

Правильное решение 3 заданий соответствует оценке «3»

Правильное решение 0-2 заданий в соответствует оценке «2»

Тема 1.2 Булевы функции

Тест

1. Булевой функцией от n переменных называют

А)Набор ,где 
Б)функциюА, принимающую значения 0 и 1
В) функцию А, принимающую одно из двух значений 0 или 1
Г) функцию А

2. Обозначение операции Штрих Шеффера

А) 

Б) x+y

В) 

Г) ()

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

А) они входят в него точно один раз либо со знаком отрицания, либо без него.

Б) каждая из этих переменных входит в него либо со знаком отрицания, либо без него.

В) каждая из этих переменных входит в него точно один раз либо со знаком отрицания, либо без него.

Г) каждая из этих переменных входит в него точно один раз

4. Полином Жигалкина- это

А) представление булевой функции с помощью констант, операции конъюнкции и двоичного сложения

Б) представление булевой функции с помощью констант, операции дизъюнкции и двоичного сложения

В) представление булевой функции с помощью операции дизъюнкции и двоичного сложения

Г) представление булевой функции с помощью констант, операции конъюнкции

5. Для того, чтобы система булевых функций была полной необходимо и достаточно, чтобы для каждого из классов Т0, Т1, S,L,M нашлась функция, не принадлежащая этому классу

А) важное свойство суммы Жигалкина

Б) теорема о замкнутых классах

В) теорема Буля

Г) теорема Поста

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

А) Т0, Т1, S,K,M

Б) Т0, Т, S,L,M

В) Т0, S,L,N, M

7. Определить к какому замкнутому классу относится булева функция 

А) Т1, S,M

Б) Т0, Т1

В) Т1, L,M

Г) Т1,M

8. Определить к какому замкнутому классу относится булева функция

А) Т0, Т1

Б) Т1, S,M

В) Т1,M

Г) Т1, L,M

9. Определить к какому замкнутому классу относится булева функция 0

А) Т0,L,M

Б) Т1, S,M

В) Т1, S,L

Г) Т0,S,M

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

А) Т1, S,M

Б) Т1, L,M

В) Т1,M

Г) Т1, L,S

11. Определить к какому замкнутому классу относится булева функция x

А) Т0, Т1,L,M

Б) Т0, S,L,M

В) Т0, Т1, S,L,M

Г) Т0, Т1, S,L

12. Определить к какому замкнутому классу относится булева функция 

А) Т0, S

Б) Т0, Т1, S

В) S,L,M

Г) S,L

13. Определить к какому замкнутому классу относится булева функция x+y

А) Т0, L

Б) ни к какому

В) ко всем

Г) S,L,M

Критерии оценивания ответа:

Ответы на 12-13 вопросов соответствуют оценке «5»

Ответ на 9-11 вопросов соответствуют оценке «4»

Ответ на 7-9 вопросов соответствуют оценке «3»

Ответ на 0-6 вопросов соответствуют оценке «2»

2. Теория множеств.

Задания для письменного ответа:

1.  Закончите предложения:

а) Множество- это любая определенная ___________________________________          ______________.

б) Объекты, из которых состоит множество, называются его __________________ или ____________________.

в)  Если а элемент множества А, то пишут _________________________________

г) Если А и В состоят из одних и тех же элементов, то говорят, что они _________________, и пишут _________________.

д) Подмножеством множества А называется такое множество В, каждый элемент которого ___________________   ________________.

2. Вставьте пропущенное слово:

а) ___________________  множества А называется такое множество В, каждый элемент которого принадлежит множеству А

б) ___________________ множеств А и В называется множество, содержащее все элементы множества А и множества В, которые принадлежат хотя бы одному из множеств

в) ___________________ множеств А и В называется множество, содержащее те элементы множества А и множества В, которые входят одновременно в оба множества,

г) ___________________ множеств А и В называется множество, состоящее из тех элементов,  которые лежат в А, но не лежат в В.

д) ___________________ множества А называется множество , состоящее из всех элементов, которые не принадлежат А

3 Поставьте в соответствие каждой диаграмме Эйлера название операции над множествами:

1             2                          

         3                                                                           4                        

а) разность;  б) пересечение;  в) объединение;  г) дополнение

4. Закончите запись:

а) Пусть А и В множества, а∈А, b∈B, запишем их в определенные пары и обозначим (a,b), такая пара элементов называется ____________________.

б) Множество всех упорядоченных пар множеств A и B называется ____________.

в) Любое подмножество прямого произведения А×В называется _______________.

г) Если А=В, то прямое произведение  называется _________________.

5. Найдите:

Дано множество V={1,2,…,13}, и два его подмножества А={2,3,5,6,8,10},B={1,3,4,6,10,12}

Найти:  

______________________________________________________________________

______________________________________________________________________

6. Закрасьте

ту область на диаграмме Эйлера, которая соответствует выражению:

а)                                                                 б)

7. Составьте выражение, соответствующее диаграмме Эйлера:

а)                                                                                      б)

а)____________________                                     б)____________________

Критерии оценивания ответа:

Решение 6-7 заданий соответствуют оценке «5»

Решение 5 заданий соответствуют оценке «4»

Решение 3-4 заданий соответствуют оценке «3»

Решение 0-2 заданий соответствуют оценке «2»

Тема 2.2 Отношения. Бинарные отношения и их свойства.

Тест

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

2. Множество решений уравнения записывается:
а) {-2,3}
б) (2;-3)
в) {2,-3}

3. Мощность множества B={0,1,2,3,5,9,27,38} равна:
а) 8
б) 18
в) 4

4. Правильная запись предложения «Y – множество действительных чисел, больших 3» – это:
а) Y={y/yєR, y>3}
б) Y={R/ y>3}
в) Y={yєR/y>3}

5. Декартово произведение множеств A={0,-3} и B={-1,2} – это:
а) AB={(0,-1),(-3,2)}
б) AB={(0,-1),(-3,-1),(0,2),(-3,2)}
в) AB={0,-1}

6. Не пересекаются множества чисел:
а) простых и четных
б) простых и нечетных
в) простых и составных

7. Пересечение множеств равносторонних и прямоугольных треугольников – это множество треугольников:
а) пустое множество
б) равнобедренных
в) прямоугольных

8. Пересечение множеств прямоугольников и ромбов – это множество:
а) параллелограммов
б) прямоугольников
в) квадратов

9. Пересекаются множества чисел:
а) четных и нечетных
б) простых и четных
в) простых и составных

10. Мощность множества A={-3,0,2,5,13} равна:
а) 5
б) 15
в) 2

Критерии оценивания ответа:

Правильный ответ на 9-10 вопросов соответствует оценке «5»

Правильный ответ на 7-8 вопросов соответствует оценке «4»

Правильный ответ на 5-6 вопроса соответствует оценке «3»

Правильный ответ на 0-3 вопросов соответствует оценке «2»

Задание для письменного ответа:

 Вставьте пропущенные слова:

1) Бинарное отношение р, заданное на множестве А, называется ________________, если ∀a∈A,(a,a)∉p

2) Бинарное отношение р, заданное на множестве А, называется ________________, если для любых элементов a,b∈A,(a,b)∧(b,a)∈p⇒a=b;(a,b)∈p∧a≠b ⇒(a,b)∉p

3) Бинарное отношение р, заданное на множестве А, называется _______________, если для любых элементов a, b, c∈Aвыполняется (a,b)∈p∧(b,c)∈p

4) Бинарное отношение р, заданное на множестве А, называется _______________, если для любых элементов a, b ∈ Aиз того, что (a,b)∈p⇒ (b,a)∈p

5) Бинарное отношение р, заданное на множестве А, называется ________________, если для любых элементов a,b∈A,a=b∨(a,b)∈p∨(b,a)∈p

6) Бинарное отношение р, заданное на множестве А, называется _______________, если элемент этого множества находится в данном отношении сам с собой

Критерии оценивания ответа:

Решение 6 заданий соответствуют оценке «5»

Решение 5 заданий соответствуют оценке «4»

Решение 3-4 заданий соответствуют оценке «3»

Решение 0-2 заданий соответствуют оценке «2»

Тест

Установите соответствие между отношением, заданным на множестве, и его свойствами:

1. Два целых числа a и b находятся в отношении ρ тогда и только тогда, когда

разность a−b делится нацело на 5

Данное отношение обладает следующими свойствами: 

Варианты ответов

1. Транзитивность
2. Симметричность
3. Антисимметричность
4. Антирефлексивность
5. Рефлексивность

2. Два целых числа a и b находятся в отношении ρ тогда и только тогда, 

когда a меньше или равно b

Данное отношение НЕ ОБЛАДАЕТ следующими свойствами: 

Варианты ответов

1. Антисимметричность
2. Рефлексивность
3. Транзитивность
4. Симметричность
5. Антирефлексивность

3. Каковы свойства отношения "больше в 2 раза", заданного на множестве  

M={2; 4; 6; 8; 12} ? 

Варианты ответов

1. Симметричность
2. Транзитивность
3. Антисимметричность
4. Рефлексивность
5. Антирефлексивность

4. На множестве K={1; 2; 3; 4; 5; 6; 7; 8; 9; 10} задано отношение "иметь один и тот же остаток при делении на 3". 

Какими свойствами НЕ ОБЛАДАЕТ данное отношение, заданное на этом множестве? 

Варианты ответов

1. Антисимметричность
2. Антирефлексивность
3. Симметричность
4. Рефлексивность
5. Транзитивность

5. На множестве окружностей плоскости задано отношение " окружность x лежит

 внутри окружности y"

Варианты ответов

1. Транзитивность
2. Симметричность
3. Антисимметричность
4. Антирефлексивность
5. Рефлексивность

 6. На множестве  B={213; 37; 21; 87; 82} задано отношение "иметь в записи одинаковые цифры". Какими свойствами обладает это отношение?

Варианты ответов

1. Рефлексивность
2. Транзитивность
3. Антирефлексивность
4. Антисимметричность
5. Симметричность

Критерии оценивания ответа:

Ответы на 6 вопросов соответствуют оценке «5»

Ответ на 4-5 вопросов соответствуют оценке «4»

Ответ на 3 вопроса соответствуют оценке «3»

Ответ на 0-2 вопроса соответствуют оценке «2»

Задание 2 для письменного ответа:

Выберите из перечисленных свойств бинарных отношений те, которые необходимы (возможны неоднократные повторения)

(Рефлексивно, антирефлексивно, симметрично, антисимметрично, транзитивно, связано, не связанное.)

1) Бинарное отношение R, заданное на множестве А, называется отношением эквивалентности, если оно _________________, _______________, _____________.

2) Бинарное отношение R, заданное на множестве А, называется отношением порядка, если оно ________________, __________________

3) Бинарное отношение R, заданное на множестве А, называется отношением строгого порядка, если оно ___________________, ________________, ___________________.

4) Бинарное отношение R, заданное на множестве А, называется отношением не строгого порядка, если оно ____________________, ___________________, ___________________.

5) Бинарное отношение R, заданное на множестве А, называется отношением линейного порядка, если оно __________________, __________________, ____________________.

6) Бинарное отношение R, заданное на множестве А, называется отношением частичного порядка, если оно ______________________.

Критерии оценивания ответа:

Решение 6 заданий соответствуют оценке «5»

Решение 5 заданий соответствуют оценке «4»

Решение 3-4 заданий соответствуют оценке «3»

Решение 0-2 заданий соответствуют оценке «2»

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

Вопросы для устного ответа:

1. Что такое предикат?

2. Примеры 1, 2, 3 местных предикатов.

3. Область определения предиката.

3. Множество истинности предиката.

4. Является ли линейное уравнение предикатом?

5. Является ли линейное неравенство предикатом?

6. Область определения предиката х + 2 < Зх – 4?

7.  - как читается квантор?

8. - как читается квантор?

9. Множество истинности предиката х + 5 = 1?

 Критерии оценивания ответа:

Ответы на 8-9 вопросов соответствуют оценке «5»

Ответ на 6-7 вопросов соответствуют оценке «4»

Ответ на 4-5 вопросов соответствуют оценке «3»

Ответ на 0-3 вопросов соответствуют оценке «2»

Тема 4.1 Основы теории графов

Тест

1) Кто считается родоначальником теории графов?

а) Куратовский

б) Леонард Эйлер

в) Аппель

2) Кто  решил задачу о трех колодцах?

а) Куратовский

б) Леонард Эйлер

в) Аппель

3) Совокупность конечного числа точек, называемых вершинами, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами, это –

а) инцидентность

б) смежность

в) граф

4) Если ребра – упорядоченные пары, то такой граф называется:

а) псевдографом

б) ориентированным

в) неориентированным

5) В каком графе могут быть кратные ребра?

а) псевдографом

б) мультиграфом

в) неориентированным

6) Смежными в графе называются вершины:

а) совпадающие

б) изоморфные

в) инцидентные одному ребру

7) Ребра, инцидентные одной вершине, называются:

а) смежными;

б) совпадающими;

в) изоморфными

Критерии оценивания ответа:

Ответы на 7 вопросов соответствуют оценке «5»

Ответ на 5-6 вопросов соответствуют оценке «4»

Ответ на 4 вопроса соответствуют оценке «3»

Ответ на 0-3 вопроса соответствуют оценке «2»

Задания для письменного ответа

        рис.1

1) Перечислить все пары смежных вершин, смежных ребер, инцидентные ребра и вершины графа на рис.1

В графе, диаграмма которого приведена на рис.1, найти:

2) маршрут, но не цепь;

3) цепь, но не простая цепь;

4) простая цепь;

5) цикл, но не простой цикл;

6) простой цикл.

Критерии оценивания ответа:

Правильное решение 6 заданий соответствует оценке «5»

Правильное решение 4-5 заданий соответствует оценке «4»

Правильное решение 3 заданий соответствует оценке «3»

Правильное решение 0-2 заданий в соответствует оценке «2»

Вопросы для устного ответа:

1. Какие два графа называются изоморфными?

2. Какой граф называется двудольным?

3. Какой граф называется тривиальным?

4. Какой граф называется турниром?

5. Какой граф называется сетью?

6. Какая вершина называется четной (нечетной)?

7. Что такое инвариант графа?

8. Какой граф называется полным?

Критерии оценивания ответа:

Ответы на 7-8 вопросов соответствуют оценке «5»

Ответ на 5-6 вопросов соответствуют оценке «4»

Ответ на 4 вопроса соответствуют оценке «3»

Ответ на 0-3 вопроса соответствуют оценке «2»

Тема 4.2 Матрица смежности, матрица инциденций.

Вопросы для устного ответа:

1. Определение матрицы смежности.

2. Определение матрицы инциденций для неориентированного графа.

3.  Определение матрицы инциденций для ориентированного графа.

4. Свойства матрицы смежности

5. Свойства матрицы инциденций.

6. Определение списка инцидентности.

7. Преимущества и недостатки использования списка инцидентности и матрицы смежности и инцидентности.

Критерии оценивания ответа:

Ответы на 7 вопросов соответствуют оценке «5»

Ответ на 5-6 вопроса соответствуют оценке «4»

Ответ на 4 вопроса соответствуют оценке «3»

Ответ на 0-3 вопроса соответствуют оценке «2»

Тема 4.3 Деревья.

Задания для письменного ответа

1. Привести 4 диаграммы различных свободных деревьев с 8 вершинами

2. Записать 3 цепи для дерева:

        v1        

        v4

                         v2              v3

           v6                                   v5

3. Привести 3 диаграммы различных ориентированных деревьев с 6 узлами

4. Изобразить дерево в виде диаграммы

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Тема 5 Элементы теории алгоритмов

Задания для письменного ответа

1. Дано число n в десятичной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 7. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 2. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

3) На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 4. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

4)  Составить коды для всех сообщений данных а) бинарного дерева б) тринарного дерева

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 1

Тема: «Формулы логики. Упрощение формул логики с помощью равносильных преобразований»

Цель: Научиться производить логические операции и действия с объектами.

Вариант 1

Задание 1. С помощью таблицы истинности проверить справедливость следующего тождества:

а); б)

Задание 2. Максимально упростите выражение, воспользовавшись законами логики Буля. Затем, с помощью таблицы истинности, сравните Ваше упрощенное выражение с исходным:

Задание 3: Составить таблицу истинности для высказывания:

а) ; б)

Вариант 2

Задание 1. С помощью таблицы истинности проверить справедливость следующего тождества:

а) ; б)

Задание 2. Максимально упростите выражение, воспользовавшись законами логики Буля. Затем, с помощью таблицы истинности, сравните Ваше упрощенное выражение с исходным:

Задание 3: Составить таблицу истинности для высказывания:

а) ; б)

Контрольные вопросы:

1. Что такое логика как наука?

2. Алгебра логики?

3. Высказывание?

4. Дизъюнкция?

5. Конъюнкция?

6. Импликация?

7. Эквивалентность?

Критерии оценивания ответа:

Правильное решение 5 заданий соответствует оценке «5»

Правильное решение 4 заданий соответствует оценке «4»

Правильное решение 3 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 2

Тема: Булевы функции

Цель: Научиться упрощать выражения с помощью законов логики Буля, определять, к какому из замкнутых классов принадлежит функция.

Вариант 1

Задание 1 С помощью таблицы истинности проверить справедливость следующего тождества:

Задание 2 Максимально упростите выражение, воспользовавшись законами логики Буля:

Задание 3Привести выражение к СДНФ: ( a – b) + c

Задание 4 К какому из замкнутых классов принадлежит функция:

f(x1,x2,x3) = x1-x2+x3

Вариант 2

Задание 1 С помощью таблицы истинности проверить справедливость следующего тождества:

Задание 2 Максимально упростите выражение, воспользовавшись законами логики Буля:

Задание 3 Привести выражение к СДНФ: ( a – b) - ( c – d)

Задание 4 К какому из замкнутых классов принадлежит функция f(x1,x2), такая, что:

Контрольные вопросы

1. Определение булевой функции

2. Замкнутые классы

4. Что такое СДНФ?

5. Что такое СКНФ?

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 3

Тема: Множества и основные операции над ними.

Цель: Научиться производить операции над множествами, определять бинарные отношения на множествах.

Вариант-1

Задание 1.Дано множество V={1,2,3,…,9} и два подмножества данного множества: A={1,3,4,7,9}, B={5,6,7,9}.

Найти: A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

Задание 2.Доказать тождество с помощью диаграммы Эйлера (A∩B)∪(C∩A)=A∩(B∪C)

Задание 3. Дана диаграмма Эйлера. По данной диаграмме записать тождества, используя операции над множествами.

Задание 4.Выяснить, является ли данное отношение эквивалентностью и порядком (определить каким)

R={(b,a)/b,a∈R, b-2a=4}

Вариант-2

Задание 1. Дано множество V={1,2,3,…,14} и два подмножества данного множества: A={1,3,7,10}, B={4,6,7,8,9}.

Найти: A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

Задание 2.Доказать тождество с помощью диаграммы Эйлера (A∪B)\(A∩B)=(A\B) ∪ (B\A)

Задание 3. Дана диаграмма Эйлера. По данной диаграмме записать тождества, используя операции над множествами.

Задание 4.Выяснить, является ли данное отношение эквивалентностью и порядком (определить каким)

R={(a,b)/a,b∈N, b/a}

Контрольные вопросы:

1. Что такое множество?
2. Что такое подмножество?
3. Изобразите с помощью диаграмм Эйлера объединение , пересечение, разность множеств А и В, дополнение к множеству А.
4. Опишите свойства бинарных отношений: рефлексивность, симметричность, транзитивность.
5. Опишите отношение эквивалентности и порядка.

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 4

Тема: Логика предикатов

Цель: научиться записывать предикатные функции, проверять истинность и ложность клауз.

Вариант 1

Задание 1     Записать по одной предикатной функции 0,1,2,3 местной.

Задание 2        Какие из клауз истины, а какие ложны? Ответ обосновать

        а)

б)

Задание 3        Составьте таблицу истинности для клаузы

Задание 4 Определите, что из перечисленного является предикатом, у предикатов определите область определения и множество истинности

а) 2х + 5 = 11

б) х2 – 2х + 1 = 0

в) Париж – столица Франции

г) х + 7 < 3х – 1

д)(х + 10) – (3х – 4)

Вариант 2

Задание 1    Записать по одной предикатной функции 0,1,2,3 местной.

Задание 2        Какие из клауз истины, а какие ложны? Ответ обосновать

        а)

б)

Задание 3        Составьте таблицу истинности для клаузы

Задание 4

а) 2х - 15 = 11

б) х2 – 4х + 4 = 0

в) Солнце - звезда

г) 4х + 5 < 2х – 1

д) (х + 10) – (3х – 4)

Контрольные вопросы

1. Что такое предикат?

2. Область определения предиката?

3. Множество истинности предиката?

4. Является ли квадратное уравнение предикатом?

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 5

Тема: Матрица смежности, матрица инцидентности

Цель: Научиться составлять матрицу смежности, матрицу инциденций по данным графам, научиться восстанавливать графы по данным матрицам.

Вариант 1

Задание1: Составьте: а) матрицу смежности для графа G,  орграфаD.

б) матрицу инциденций для графа G,  орграфа D

Орграф D

Граф G

Задание 2 Восстановите граф и орграф по матрице смежности и матрице инциденций.

M(G[I,j])                                      M(D[I,j])  

H(G[I,j])                                                      H(D[I,j])

Вариант 2

Задание1 Составьте: а) матрицу смежности для графа G, орграфаD.

 б) матрицу инциденций для графа G, орграфа D.

граф G

Орграф D

        V4

Задание 2 Восстановите граф и орграф по матрице смежности и матрице инциденций.

M(G[I,j])                              M(D[I,j])  

H(G[I,j])                                                        H(D[I,j])

Контрольные вопросы:

1. Определение матрицы смежности.
2. Определение матрицы инциденций.
3. Определение смежных вершин, смежных ребер.
4. Определение инцидентных вершин и ребер.

Критерии оценивания ответа:

Правильное решение 4 заданий соответствует оценке «5»

Правильное решение 3 заданий соответствует оценке «4»

Правильное решение 2 заданий соответствует оценке «3»

Правильное решение 0-1 заданий в соответствует оценке «2»

Практическая работа 6 

Тема: Графы

Цель: Научиться строить диаграммы различных деревьев, записывать цепи по данным диаграммам.

2 вариант

1.Привести 4 диаграммы различных свободных деревьев с 9 вершинами

2.Записать 3 цепи для дерева:

           V5                

        V1        V2        V3

V4

        V6

3. Привести 3 диаграммы различных ориентированных деревьев с 4 узлами

4. Изобразить дерево в виде диаграммы

5.        Привести 2 различные диаграммы упорядоченных деревьев с 10 вершинами, чтобы они были изоморфны как свободные деревья.

Практическая работа 10

Тема Решение задач по теории автоматов

Цель: Научиться применять теорию автоматов при решении задач

Вариант 1        

1. Дано число n в десятичной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 9. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 3. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 2        

1. Дано число n в десятичной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 8. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 5. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 4. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Контрольные вопросы:

1. Что такое дискретные автоматы?
2. Связь теории автоматов и теории алгоритмов.
3. Анализ автоматов.
4. Синтез автоматов.

Критерии оценивания ответа:

Правильное решение 3 заданий соответствует оценке «5»

Правильное решение 2 заданий соответствует оценке «4»

Правильное решение 1 заданий соответствует оценке «3»

Правильное решение 0 заданий в соответствует оценке «2»

4. КОС для промежуточной аттестации

Экзаменационный тест

            1 вариант

1. Как называется операция над множествами, характеризующаяся логически словами: Элемент (Х С А)V(XCB) x принадлежит множеству А или множеству В

А) Пересечение Б) Объединение В) Разность Г) Дополнение

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

А) Пересечение

Б) Объединение

В) Разность

Г) Дополнение

3. Свойство бинарного отношения, когда любой элемент множества находится в этом отношении сам с собой:

А) Транзитивность Б) Симметричность В) Связанность

 Г) Рефлексивность

4. Каким будет отношение R, заданное на множестве А, если оно рефлексивно, транзитивно, симметрично:

А) Порядок Б) Строгий порядок В) Эквивалентность Г) Нестрогий порядок

5. Высказывание, которое принимает значение истины тогда и только тогда, когда А и В истинны:

А) Конъюнкция Б) Дизъюнкция В) Импликация Г) Эквивалентность

6. Закон коммутативности в логике Буля:

А) AV1=А Б) (AVB) Λ A=A B) AV B = BVA Г) АV A=A

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

А) T1 Б) Т0 В) S Г) М

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

А) Множество Б) Логическое высказывание В) Булевы функции

Г) Предикат

9. По какому модулю сравнимы числа 7 и 3?

А) По mod 7 Б) По mod 3 В) По mod 2 Г) По mod 5

10.  К какому классу вычетов по mod 5 принадлежат числа 17, -13?

          _      _      _      _

     А) 2 Б) 3 В) 1 Г) 4

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

А) Логика высказываний; Б) Алгебра вычетов; В) Теория множеств;

 Г) Комбинаторика.  

12. Сколько элементов  n должно содержать множество, чтобы число всех перестановок не превышало 30?

А) n<=5 Б) n<=3 В) n<= 6 Г) n<=4

13. С помощью какой формулы можно подсчитать число размещений из n элементов по m?

А) A   = n! Б) A   = n!/(n-m)! В) A  = n!/m!(n-m)! Г) A  = m!/(n-m)!

14. Какое из равенств верное?

А) С  = A  / P  Б) С  = AP  В) C  = P  / A  Г) С  = P  / P

15.  Какая из клауз верная:

А) xP(x) =>xP(x) Б) xP(x) =>xP(x) В) xP(x) =>xP(x)

Г) xP(x) =>xP(x)

16. Совокупность двух множеств V вершин и Е ребер V – непустое множество, а Е – множество неупорядоченных пар различных элементов V называется:

А) Граф Б) Смежность В) Инцидентность Г) Изоморфизм

17. Сколько в данном графе вершин, смежных с вершиной V1:

               V1                  V2                                А) 1 Б) 3 В) 4 Г) 2

                V4                    V3

18. Сколько в данном графе ребер, инцидентных вершине V3:

А) 1 Б) 2 В) 3 Г) 4

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

      А) Матрицей Б) Матрицей инциденций В) Матрицей смежности Г) Матиндукцией.

20.  Граф, состоящий из одной вершины, называется

         А) Орграфом Б) Тривиальным В) Деревом Г) Подграфом

21. В матрице смежности для графа, если вершины смежны, то это обозначается:

А) + Б) 1 В) 0 Г) –1

22. В матрице инцидентности для орграфа, если вершина инцидентна ребру и является его началом, это обозначается:

А) + Б) 1 В) 0 Г) –1

23. В дереве нет:

          А) циклов Б) вершин В) ребер Г) простых цепей

24. Ориентированное дерево это:

А) Подграф Б) Дополнение к графу В) Орграф, обладающий определенными свойствами Г) Объединение графов

 25. В цепи может повторяться:

          А) Ребро Б) Вершина В) Путь Г) Граф

2 вариант.

1.Как называется операция над множествами, характеризующаяся логически словами: Элемент (Х С А)(XCB) x принадлежит множеству А и множеству В

А) Объединение Б) Пересечение В) Разность Г) Дополнение

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

А) Объединение

Б) Пересечение

В) Разность

Г) Дополнение

3. Свойство бинарного отношения, такое, что если элемент множества

а  находится в этом отношении с элементом в, а элемент в находится в этом отношении с элементом с, то элемент а находится в этом отношении с элементом с:

А) Рефлексивность Б) Симметричность В) Связанность

Г) Транзитивность

4. Каким будет отношение R, заданное на множестве А, если оно  транзитивно, антисимметрично:

 А) Эквивалентность Б) Строгий порядок В) Порядок Г) Нестрогий порядок

5. Высказывание, которое принимает ложное значение  тогда и только тогда, когда А и В ложны:

А) Дизъюнкция Б) Конъюнкция В) Импликация Г) Эквивалентность

6. Закон поглощения в логике Буля:

А) AV1=1  Б) AV B = BVA B) (AVB) Λ A=A Г) АV A=A

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

А) T0 Б) Т1 В) S Г) М

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

А) Множество Б) Предикат В) Булевы функции

Г) Логическое высказывание

9. По какому модулю сравнимы числа 7 и 2 ?

А) По mod 7 Б) По mod 3 В) По mod 5 Г) По mod 2

10. К какому классу вычетов по mod 6 принадлежат числа 19, -11?

      _      _      _      _

А) 1  Б) 3 В) 2 Г) 4

11. Сколько элементов  n должно содержать множество, чтобы число всех перестановок не превышало 40?

А) n<=5 Б) n<=3 В) n<= 6 Г) n<=4

12. С помощью какой формулы можно подсчитать число сочетаний из n элементов по m?

А) C  = n! Б) С   = n!/ m!(n-m)! В) C  = n!/(n-m)! Г) C  = m!/(n-m)!

13. Какое из равенств верное?

А) P  = n!   Б) P  = n!/ m!(n-m)!  В) P  = n!/ (n-m)!   Г) P  = (n-m)!  

14.  Какая из клауз подтверждается примером: « Если все люди смертны, то человек  Сократ тоже смертен:

А) xP(x) =>xP(x) Б) xP(x) =>xP(x) В) xP(x) =>xP(x)

Г) xP(x) =>xP(x)

15. Любое … является предикатом:

А) выражение Б) предложение В) Сочетание Г) неравенство

16. Два ребра, инцидентные одной вершине, называются:

А) Графическими Б) Смежными В) Связанными Г) Изоморфными

17. Сколько в данном графе вершин, смежных с вершиной V2:

              V1         V2         А) 1 Б) 2 В) 4 Г) 3

             V4          V3

18. Сколько в данном графе ребер, инцидентных вершине V1:

А) 1 Б) 2 В) 3 Г) 4

19. Чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны:

А) Маршрут Б) Цепь В) Цикл Г) Простой цикл

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

А) Матрицей Б) Матрицей инциденций В) Матрицей смежности Г) Матиндукцией.

21. В матрице смежности для графа, если вершины  не смежны, то это обозначается:

А) + Б) 0 В) 1 Г) –1

22. В матрице инцидентности для орграфа, если вершина инцидентна ребру и является его концом, это обозначается:

А) + Б) –1  В) 0 Г) 1

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

А) Свободным Б) Бинарным В) Эквивалентным Г) Упорядоченным

24. Связный ациклический граф является:

А) Ордеревом Б) Упорядоченным ордеревом

В) Свободным деревом Г) Бинарным

25. Ориентированное дерево является:

        А) Тривиальным графом  Б) Матрицей  В) Упорядоченным деревом Г) Графом с циклами.

Критерии оценки выполнения задания:

- "Отлично" - если студент  глубоко и прочно усвоил весь программный материал в рамках указанных общих и профессиональных компетенций, знаний и умений. Исчерпывающе, последовательно, грамотно и логически стройно его излагает, тесно увязывает с условиями современного производства, не затрудняется с ответом при видоизменении задания, свободно справляется с задачами и практическими заданиями, правильно обосновывает принятые решения, умеет самостоятельно обобщать и излагать материал, не допуская ошибок. 24-25 правильных ответов из 25 (96-100%)

- "Хорошо" - если твердо студент знает программный материал, грамотно и по существу излагает его, не допускает существенных неточностей в ответе на вопрос, может правильно применять теоретические положения и владеет необходимыми умениями и навыками при выполнении практических заданий. 19-23 правильных ответов из 25 (76-95%)

- "Удовлетворительно" - если студент усвоил только основной материал, но не знает отдельных деталей, допускает неточности, недостаточно правильные формулировки, нарушает последовательность в изложении программного материала и испытывает затруднения в выполнении практических заданий. 13-18 правильных ответов из 25 (52-75%)

-  "Неудовлетворительно" - если студент   не знает значительной части программного материала, допускает существенные ошибки, с большими затруднениями выполняет практические задания, задачи. Меньше 13 правильных ответов из 25 (меньше 52%)

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

1. Лупанов О. Б. Курс лекций по дискретной математике. - М., 2018.
2. Новиков Ф.А. Дискретная математика для программистов - 2018 г.
3. Яблонский С.В. Введение в дискретную математику — М. Наука, 2017.
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. — М.: Наука, 2017.
5. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: учеб. пособ.- М.: Форум: ИНФРА-М, 2017.
6. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика -М., 2018 г.
7. Мендельсон Э. Введение в математическую логику. — М.: Наука, 2019.
8. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.: Издательство МАИ, 2013
9. Спирина М.С. Дискретная математика: учеб. – М.: Академия, 2018.
10. Харари Ф. Теория графов. –М., 2018 год.

Электронные ресурсы:

1. http://otherreferats.allbest.ru/
2. http://st.educom.ru/eduoffices/gateways/get_file.
3. http://umu.kemsu.ru/Content/userfiles/files/Математический