Ф. УР-33 ГАПОУ СО «Уральский радиотехнический колледж им. А.С. Попова»
ОДОБРЕНЫ	УТВЕРЖДАЮ
ЦМК «ЕНД»	Заместитель директора по учебной работе _________ Д.В. Колесников
Протокол от «____» ___ 20 ___ г. № ___
Председатель ЦМК __________ Алферьева О.В.	«____» ___________20___ г.

Порядок, условия проведения и содержание экзамена

по учебной дисциплине ЕН 02 «Элементы математической логики»

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

программа базовой подготовки

Семестр 3

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

Последовательность и условия выполнения задания:

1. Тестирование.

2. Решение задач из экзаменационного билета.

3. Устный опрос на знание основных формул и определений.

Вы можете воспользоваться: -при сдаче на оценку «удовлетворительно» справочным материалом

Максимальное время выполнения задания – 45 мин.

Теоретические вопросы

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. Ядро отношения.

Типовые практические задания

1. Выберите высказывания, которые является истинными, если высказывание P-истинно, а высказывание Q -ложно?

PÙQ, PÚQ, P®Q, P«Q.

2. Выберите высказывания, которые является истинными, если высказывания P и Q ложны?

PQ, PÚQ, Q®P, P«Q.

3. Выберите высказывания, которые является истинными, если высказывания P и Q истинны?

PÙQ, PÚQ, Q®P, PQ.

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

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

6. Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.

7. Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.

8. Пусть Р(х) — предикат: «х — делится на два ». Выразите словами высказывания $хР(х), "хР(х).

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

a) ,

b) ,

c) ,

d) ,

e) ,

где

P(x): x – отрицательное число,

Q(x,y): x > y,

R(x,y) : студент x изучает дисциплину y.

10. Q(x,y): студент x учится в колледже y. Запишите на естественном языке высказывания и определите их истинность:

a) ,

b) ,

c) ,

d) ,

e) ,

f) .

11. По каналу связи передаются 3 сообщения, каждое из которых может быть правильно принято, независимо от других. Запишите с помощью формул алгебры логики высказывания:

a) «все сообщения будут искажены»;

b) «будет искажено только первое сообщение»;

c) «одно сообщение будет искажено»;

d) «хотя бы одно сообщение будет искажено».

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

-первый элемент вышел из строя;

-первый элемент вышел из строя;

-первый элемент вышел из строя;

-первый элемент вышел из строя.

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

-первый элемент вышел из строя;

-первый элемент вышел из строя;

-первый элемент вышел из строя;

-первый элемент вышел из строя.

14. Записать предикат с помощью символики:

a) Среди чисел а, b, с есть хотя бы одна пара взаимно противоположных.

b) Данные числа х, у являются координатами точки, лежащей в первой координатной четверти.

c) Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).

d) Число d является корнем только одного из уравнений и .

15. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

16. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

17. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

18. Даны два множества A = {§, ©, ª}, B = {©, ¨, ·}. Что представляет собой множества А\В, А È В, АÇВ, В\А, ВΔА?

19. Найдите (BÈ А)\C, AÇ (B\C), (CÇ А)È B, если , , .

20. Три множества A, В и С изображены кругами Эйлера. Запишите множество, которое соответствует закрашенной области:

a) b)

21. Изобразите множества кругами Эйлера:

a) , если , ,;

b) , если , ,;

c) , если , ,.

22. Определите мощность множества .

23. Из 105 опрошенных человек 38 любят смотреть по телевизору фильмы ужасов, 29 − мелодрамы, 65 − комедии, смотрят фильмы ужасов или мелодрамы − 56, смотрят комедии или мелодрамы − 81, смотрят фильмы ужасов или комедии − 91, не смотрят телевизор вообще 4 человека. Сколько человек смотрят только комедии?

24. На экзамене по дискретной математике из 45 человек группы первое задание выполнили 17 человек, второе – 20, третье – 20, первое и второе – 5, второе и третье – 7, первое и третье – 6, все три – 4. Сколько студентов не выполнили ни одного задания?

25. Пусть , . Найдите , , .

26. Определите свойства отношения R, если, A –множество всех людей, .

27. Определите свойства отношения R, если A –множество действительных чисел, .

28. Пусть , , , , , , . Найдите композицию отношений и .

29. Пусть , , . Задайте отношение R перечислением пар, постройте матрицу отношения, изобразите отношение графом. Найдите и ядро отношения Ker R.

30. Пусть , , . По матрице отношения R, запишите отношение R перечислением пар, изобразите отношение графом. Определите свойства отношения.

Методика и критерии оценки

Оценка за экзамен выставляется по сумме набранных баллов за выполнение заданий:

Тестирование – 18-30 баллов (по 3 баллу за каждый правильный ответ).

Решение двух задач из экзаменационного билета – 16-30 баллов за каждую задачу.

Устный опрос на знание основных формул и определений –10 баллов, при правильном ответе на все вопросы, 5 баллов при 1-2ошибках).

Оценка	Количество набранных баллов
Отлично	86-100
Хорошо	71-85
Удовлетворительно	55-70
Неудовлетворительно	Менее 55 баллов

Преподаватель: О.В. Алферьева

Рецензенты: Шутова Н.Н. преподаватель дисциплины «Основы алгоритмизации и программирования», «Основы теории информации»,

Поликарпова С.В., преподаватель дисциплины «Архитектура аппаратных средств».