КОС по дисциплине "Дискретная математика с элементами математической логики"
учебно-методический материал

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

Краевое государственное бюджетное

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

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

КОМПЛЕКТ ОЦЕНОЧНЫХ СРЕДСТВ

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

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

___________________________________________________________

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

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

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

Хабаровск, 2020

Составитель: преподаватель КГБ  ПОУ  ХПЭТ _____________________________

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

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

СОДЕРЖАНИЕ

1 Паспорт комплекта оценочных средств                                                 3

2. Комплект оценочных средств                                                                5

3. Критерии оценки за ответ на теоретические вопросы                        10

4. Критерии оценки за выполнение практической работы                     10

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

пособий и Интернет-ресурсов

1 Паспорт комплекта контрольно-оценочных средств

Контрольно-оценочные средства (КОС) предназначены для оценки результатов освоения учебной дисциплины «Дискретная математика с элементами математической логики»

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

В результате освоения учебной дисциплины ЕН.02 Дискретная математика с элементами математической логики обучающийся должен обладать предусмотренными ФГОС СПО по специальности 09.02.07 Информационные системы и программирование, следующими общими компетенциями и знаниями и умениями:

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

2 Комплект оценочных средств

2.1 Методы оценки результатов обучения для текущего контроля:

2.1.1 Теоретические задания для устного и письменного опроса

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

1. Понятие высказывания.

2. Основные логические операции.

3. Формулы логики.

4. Таблица истинности и методика её построения.

5. Законы логики.

6. Равносильные преобразования.

7. Понятие булевой функции.

8. Способы задания ДНФ, КНФ

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

10. Основные классы функций.

11. Полнота множества.

12.  Теорема Поста.

Раздел 2 Элемент теории множеств

1. Общие понятия теории множеств.

2. Способы задания.

3. Основные операции над множествами и их свойства.

4. Мощность множеств.

5. Графическое изображение множеств на диаграммах Эйлера-Венна.

6. Декартово произведение множеств.

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

8. Теория отображений.

9. Алгебра подстановок.

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

1. Понятие предиката.

2. Логические операции над предикатами.

3. Кванторы существования и общности.

4. Построение отрицаний к предикатам, содержащим кванторные операции.

5. Нахождение области определения и истинности предиката.

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

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

2. Виды графов: ориентированные и неориентированные графы.

3. Способы задания графов.

4. Матрицы смежности и инциденций для графа.

5. Эйлеровы и гамильтоновы графы.

6. Деревья.

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

1. Основные определения.

2. Машина Тьюринга.

2.1.2 Практические задания для устного и письменного опроса

Задачи по разделам 1-5

2.1.3 Темы индивидуальных проектов

1. История развития математической логики

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

3        Логические операции. Законы алгебры логики.

4        Формы представления Булевых функций. Многочлены Жегалкина.

5        Логика предикатов

6        Алгебра вычетов.

7. История теории графов.

8. Маршруты, цепи, циклы.

9. Матрица смежности, матрица инцидентности.

10. Решение задач по теме: «Ориентированные, упорядоченные и бинарные деревья».

11        Представление деревьев в ЭВМ

12 Элементы теории автоматов»

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

1. Формулы логики. Упрощение формул логики с помощью равносильных преобразований.
2. Булевы функции.
3. Множества и основные операции над ними.
4. Нахождение области определения и истинности предиката. Построение отрицаний к предикатам, содержащим кванторные операции.
5. Матрицы смежности и инциденций для графа.
6. Графы
7. Работа машины Тьюринга

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

2.2.1 Задания для экзамена по дисциплине: «Дискретная математика с элементами математической логики»

2.2.1 Теоретические задания для подготовки к  экзамену

Вопросы к экзамену:

1. Что такое множество, элементы множества, подмножество, равные множества?

2. Дайте определения для операций над множествами объединения, пересечения.

3. Дайте определения для отношений эквивалентности и порядка.

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

5. Дайте определения для логических операций конъюнкция, импликация.

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

7. Дайте определения для понятий граф, смежность и инцидентность вершин и ребер графа.

8. Дайте определения для свойств бинарных отношений рефлексивность и транзитивность.

9. Дайте определения для маршрута, цепи, цикла, простой цепи и простого цикла в графе.

10. Дайте определения для матрицы смежности и матрицы инциденций.

11. Дать определение булевой функции.

12. Дайте определения для операций над множествами разности, дополнения.

13. Дайте определения для операций над высказываниями дизъюнкция, эквивалентность.

14. Дать определение предиката, области определения предиката, множества истинности предиката.

15. Дайте определения для свойств бинарных отношений симметричность и антирефлексивность.

16. Дать определение тривиальному графу, какой граф является деревом?

2.2.2 Практические задания для подготовки к экзамену

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

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

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

1. 4х + 5 = -3
2. Луна это спутник Земли
3. х2 – 2х + 1 = 0
4. х3 – 2х + 1
5. х + 2 < Зх – 4
6. (х + 2) – (3х – 4)
7. х2 - 4 > 0

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

5. Определить, является ли данное отношение эквивалентностью, или порядком:

 R={(x,y)/x,y∈R,x2=y2}

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

V1                                     e1                                       V2

V4                                       e3                                  V3

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

        а)

б)

8. Проверить, сравнимы ли числа по данному модулю:

а)        б)      в)  

г)            д)    е)  

9. Записать 6 сравнений по mod 37.

10. Дан граф:        

Указать одну простую цепь, одну цепь, один простой цикл, один цикл,

указать один маршрут.

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

Найти:  , , A\B, B\A, A2

12. Дан граф:        

Составьте матрицу смежности для данного графа

13. Дан граф:

e2

e3

e7

e8

Составить для данного графа матрицу инциденций.

14. Составить таблицу истинности для следующего высказывания:

15. Даны матрица смежности:

M(G[I,j])     0  1  1  1        

                    1  0  1  0                          

                    1  1  0  1                            

                    1  0  1  0                          

матрица инциденций:

H(G[I,j])    1  0  0  1  1                    

                   1  1  0  0  0                                        

                   0  1  1  0  1                                      

                   0  0  1  1  0                                      

Воссоздать по ним граф.

16. Описать классы вычетов по mod 6

3. Критерии оценки за ответ на теоретические вопросы

4 Критерии оценки за выполнение практической работы

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/Математический