КОС по дисциплине «Элементы математической логики» для специальности 090204


Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени С.М.КИРОВА»
____________________________________________________________________

КОНТРОЛЬНО-ОЦЕНОЧНЫЕ СРЕДСТВА ПО УЧЕБНОЙ ДИСЦИПЛИНЕ
Элементы математической логики
основной профессиональной образовательной программы (ОПОП)
по специальностям СПО
09.02.04 Информационные системы (по отраслям)

Санкт-Петербург
2016
РАССМОТРЕН и ОДОБРЕН
на заседании цикловой комиссии общеобразовательных, естественнонаучных и общетехнических дисциплин
Протокол №от «»2016 г.
Председатель ЦК/В.П. Казакова/
СОГЛАСОВАНО:
Председатель Методического совета/_____________/
«____» ____________2016 г.

Разработчики:_________/ К.В. Слюсаренко/
«____»____________2016 г.
1. Общие положения
Контрольно-оценочные средства (КОС) предназначены для контроля и оценки образовательных достижений обучающихся, освоивших программу учебной дисциплины Элементы математической логики.
КОС включают контрольные материалы для проведения текущего контроля и промежуточной аттестации в форме дифференцированного зачета.
КОС разработаны на основании положений:
основной профессиональной образовательной программы по специальности СПО
09.02.04 Информационные системы (по отраслям)
рабочей программы учебной дисциплины Элементы математической логики.

2. Результаты освоения дисциплины, подлежащие проверке
Результаты обучения
(освоенные умения, усвоенные знания) Основные показатели оценки результатов
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Составление таблиц истинности для формул
Приведение формул к совершенным нормальным формам
Упрощение формул логики до минимальной ДНФ
Решение задач алгебры Буля
Представление булевых функций в виде полинома Жегалкина
Определение полноты системы функций
Определение значения истинности высказываний.
Построение составных высказываний.
Доказательство тавтологий
Выполнение операции над множествами
Нахождение мощности множеств
Решение задач при помощи кругов Эйлера
Вычисление кортежей и декартового произведения множеств
Выполнение логических операций над предикатами
Выполнение операций с кванторами
Применение логики предикатов
Вычисление произведений подстановок. Разложение подстановок в произведение циклов
Составление алгоритмов
Применение метода математической индукции в доказательствах
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Формулировка основных операций: отрицание, конъюнкция и дизъюнкция.
Союзы языка и логические операции (язык и логика).
Формулировка определений: импликанция, эквиваленция, сумма по модулю два, штрих Шеффера, стрелка Пирса.
Таблицы истинности.
Формулировка определений тавтологии, высказывания и высказывательных форм.
Перечисление аксиом классической логики.
Формулировка правил вывода классической логики.
Классификация множеств.
Мощность множеств.
Кортежи и декартово произведение множеств.
Приложение кругов Эйлера к решению логических задач.
Описание бинарных отношений и их свойств.
Описание соответствия между множествами.
Формулировка понятий отображения и подстановки.
Описание элементов теории алгоритмов.
Формулировка определения алгоритма,
Перечисление задач теории шифрования и областей ее применения
Формулировка метода математической индукции.
З2 Знание формул алгебры высказываний. Классификация формул алгебры логики.
Перечисление последовательности действий при решении логических задач.
З3 Знание методов минимизации алгебраических преобразований. Приложение алгебры высказываний к логико-математической практике.
Приложение нормальных форм для формул алгебры высказываний.
З4 Знание основ языка и алгебры предикатов. Союзы языка и логические операции
Формулировка основных понятий, связанных с предикатами
Перечисление последовательности действий кванторных операции над предикатами
Описание процессов применения логики предикатов к логикоматематической практике.

3. Распределение основных показателей оценки результатов по видам контроля
Наименование элемента умений или знаний Виды аттестации
Текущий контроль Промежуточная аттестация
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Оценка выполнения расчетного задания
Теоретические и практические вопросы
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов.
Оценка по результатам устного опроса, расчетного задания Теоретические и практические вопросы
З2 Знание формул алгебры высказываний.
З3 Знание методов минимизации алгебраических преобразований.
Оценка по результатам устного опроса, расчетного задания
Оценка по результатам устного опроса, расчетного задания
Теоретические и практические вопросы
Теоретические и практические вопросы
З4 Знание основ языка и алгебры предикатов. Оценка по результатам устного опроса, расчетного задания Теоретические и практические вопросы
4. Распределение типов контрольных заданий по элементам знаний и умений.
Содержание
учебного материала
по программе УД Тип контрольного задания
У1 З1 З2 З3 З4
Раздел 1. Булевы функции и формулы логики Расчетное задание 6.1 Расчетное задание 6.1
Устный опрос 6.2 Расчетное задание 6.1 Раздел 2. Исчисление высказываний Расчетное задание 6.3 Устный опрос 6.4 Расчетное задание 6.3
Устный опрос 6.12 Расчетное задание 6.3 Раздел 3. Исчисление предикатов Расчетное задание 6.5 Расчетное задание 6.5 Расчетное задание 6.5
Раздел 4. Основные операции над множествами Расчетное задание 6.6 Расчетное задание 6.6 Раздел 5. Бинарные отношения Расчетное задание 6.6 Расчетное задание 6.6 Раздел 6. Отображения. Подстановки Расчетное задание 6.8 Устный опрос 6.7 Раздел 7. Элементы теории алгоритмов Расчетное задание 6.9 Расчетное задание 6.9 Раздел 8. Некоторые элементы теории шифрования Устный опрос 6.10 Раздел 9. Метод математической индукции Расчетное задание 6.11 Устный опрос 6.10 5. Распределение типов и количества контрольных заданий по элементам знаний и умений, контролируемых на промежуточной аттестации.
Форма промежуточной аттестации – дифференцированный зачет. Зачетные вопросы имеют теоретическую (Т) - содержит вопросы - и практическую (П) – содержит расчетные задания - части (см. Перечень вопросов к зачету).
Содержание
учебного материала
по программе УД Тип контрольного задания
У1 З1 З2 З3 З4
Раздел 1. Булевы функции и формулы логики П-1-2,4,7 Т-1-12,15 Т-13-14 Раздел 2. Исчисление высказываний П-3,5,10 Т-18 Т-16-17 Раздел 3. Исчисление предикатов П-6 Т-20-21
Раздел 4. Основные операции над множествами П-8 Т-19,22 Раздел 5. Бинарные отношения Т-23-25 Раздел 6. Отображения. Подстановки П-9 Т-26-29 Раздел 7. Элементы теории алгоритмов П-12 Т-30-31 Раздел 8. Некоторые элементы теории шифрования Т-32-35 Раздел 9. Метод математической индукции П-11Т-36 6. Структура контрольного задания
6.1 Расчетное задание
6.1.1 Текст задания
Вариант 1.
Составьте таблицу истинности для:
(A∨B)∧BПриведите равносильными преобразованиями формулу к дизъюнктивной нормальной форме .
Для формулы алгебры высказываний найдите СДНФ с помощью таблицы истинности и минимизируйте ее.
Для формулы алгебры высказываний найдите СКНФ с помощью таблицы истинности и минимизируйте ее.
Для булевой функции найдите представляющий ее полином Жегалкина.
Докажите, что все следующая функция линейна .
Применяя равносильные преобразования, приведите формулу к возможно более простой форме.
Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?
Вариант 2.
Составить таблицу истинности для:
(A∧B)∨AПриведите равносильными преобразованиями формулу к дизъюнктивной нормальной форме ..
Для формулы алгебры высказываний найдите СДНФ с помощью таблицы истинности и минимизируйте ее.
Для формулы алгебры высказываний найдите СКНФ с помощью таблицы истинности и минимизируйте ее.
Для булевой функции найдите представляющий ее полином Жегалкина .
Докажите, что все следующая функция линейна .
Применяя равносильные преобразования, приведите формулу к возможно более простой форме.
Является ли полной система булевых функций, состоящая из дизъюнкции и конъюнкции?
6.1.2 Время на выполнение: 90 мин.
6.1.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Составление таблиц истинности для формул
Приведение формул к совершенным нормальным формам
Упрощение формул логики до минимальной ДНФ
Решение задач алгебры Буля
Представление булевых функций в виде полинома Жегалкина
Определение полноты системы функций 8 баллов
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Союзы языка и логические операции.
Таблицы истинности. З2 Знание формул алгебры высказываний.
Перечисление последовательности действий при решении логических задач. За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.2 Устный ответ.
6.2.1 Текст задания.
Дать определение операций: конъюнкция, дизъюнкция, отрицание.
Перечислить союзы языка и логические операции.
Дать определения: импликанция, эквиваленция, сумма по модулю два, штрих Шеффера, стрелка Пирса.
Зачем нужны таблицы истинности?
6.2.2 Время на выполнение:15 мин.
6.2.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Формулировка основных операций: отрицание, конъюнкция и дизъюнкция.
Союзы языка и логические операции.
Формулировка определений: импликанция, эквиваленция, сумма по модулю два, штрих Шеффера, стрелка Пирса.
Таблицы истинности. 4 балла
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.3 Расчетное задание.
6.3.1 Текст задания.
Вариант 1
Докажите, что следующая формула является тавтологией, преобразовав равносильным образом .
Проверить является ли формулой ИВ выражение:
(A & B)→C
Методом резолюций доказать теорему
⊨A→(A→B)Вариант 2
Докажите, что следующая формула является тавтологией, преобразовав равносильным образом .
Проверить являются ли формулами ИВ выражения:
(A→B)→(C→D)
Методом резолюций доказать теорему:

6.3.2 Время на выполнение: 45 мин.
6.3.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Определение значения истинности высказываний.
Построение составных высказываний.
Доказательство тавтологий
3 балла
З2 Знание формул алгебры высказываний.
Перечисление последовательности действий при решении логических задач. З3 Знание методов минимизации алгебраических преобразований.
Приложение алгебры высказываний к логико-математической практике.
Приложение нормальных форм для формул алгебры высказываний. За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.4 Устный ответ.
6.4.1 Текст задания.
Сформулировать определения тавтологии, высказывания и высказывательных форм.
Перечислить аксиомы классической логики.
Сформулировать правила вывода классической логики.
В чем заключается метод резолюций?
6.4.2 Время на выполнение:25 мин.
6.4.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Формулировка определений тавтологии, высказывания и высказывательных форм.
Перечисление аксиом классической логики.
Формулировка правил вывода классической логики.
. 4 балла
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.5 Расчетное задание.
6.5.1 Текст задания.
Вариант 1
Найдите множество истинности предиката, заданного над указанным множеством «», .
Из следующего предиката с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны () .
Изобразите на плоскости множество истинности одноместного предиката, заданного на .
Пусть означает « простое число», означает « четное число», означает « нечетное число», « делится на ». Переведите на русский язык следующие символические записи на языке логики предикатов, учитывая что и пробегают множество натуральных чисел
Докажите, что формулы из следующих пар равносильны между собой на одноэлементном множестве и .
Применяя равносильные преобразования, приведите формулу к предваренной нормальной форме, т.е. к форме у которой все кванторы стояли бы вначале формулы .
Какие из следующих формул тождественно истины?
x((x) P(x))(x(x) xP(x))
x((x) P(x))(x(x) xP(x))
Вариант 2
Найдите множество истинности предиката, заданного над указанным множеством «», .
Из следующего предиката с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны () .
Изобразите на плоскости множество истинности одноместного предиката, заданного на .
Пусть означает « простое число», означает « четное число», означает « нечетное число», « делится на ». Переведите на русский язык следующие символические записи на языке логики предикатов, учитывая что и пробегают множество натуральных чисел .
Докажите, что формулы из следующих пар равносильны между собой на одноэлементном множестве и .
Применяя равносильные преобразования, приведите формулу к предваренной нормальной форме, т.е. к форме у которой все кванторы стояли бы вначале формулы .
Какие из следующих формул тождественно истины?
x((x) P(x))(x(x) xP(x))
x((x) P(x)) ~ (x(x) xP(x))
6.5.2 Время на выполнение: 80 мин.
6.5.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Выполнение логических операций над предикатами
Выполнение операций с кванторами
Применение логики предикатов 7 баллов
З4 Знание основ языка и алгебры предикатов.
Союзы языка и логические операции
Формулировка основных понятий, связанных с предикатами
Перечисление последовательности действий кванторных операции над предикатами
Описание процессов применения логики предикатов к логикоматематической практике. З3 Знание методов минимизации алгебраических преобразований.
Приложение алгебры высказываний к логико-математической практике.
Приложение нормальных форм для формул алгебры высказываний. За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.6 Расчетное задание.
6.6.1 Текст задания.
Вариант 1.
Укажите множество действительных чисел, соответствующее записи
Даны множества . Найдите: а)
б) в) .
Докажите тождества, используя только определения операций над множествами .
В студенческом потоке 37 человек хорошо знают математику, а 25 человек – электронику, и 19 человек хорошо знают и математику и электронику. Если в потоке каждый из студентов знает хотя бы один из этих предметов, то сколько студентов в потоке?
Указать количество парных элементов, из которых состоит декартовое произведение А1 х А2 для множеств А1={a,b,c} и А2={1,2,3}.
Укажите количество подмножеств множества B={1, 2, 3}
Укажите мощность множества 
На множестве людей Земли введено бинарное отношение «быть родственником по крови». Будет ли это отношение отношением эквивалентности? 
Вариант 2.
Укажите множество действительных чисел, соответствующее записи
Даны множества . Найдите: а)
б) в) .
Докажите тождества, используя только определения операций над множествами .
В студенческом потоке 37 человек хорошо знают математику, а 25 человек – электронику, и 19 человек хорошо знают и математику и электронику. Если в потоке каждый из студентов знает хотя бы один из этих предметов, то сколько студентов в потоке?
Указать количество парных элементов, из которых состоит декартовое произведение А1 х А2 для множеств А1={a,b,4} и А2={1,2,3}.
Укажите количество подмножеств множества B={1, 2, 4}
Укажите мощность множества букв русского алфавита 
На множестве людей Земли введено бинарное отношение «быть родственником по крови». Будет ли это отношение отношением эквивалентности? 
6.6.2 Время на выполнение: 90 мин.
6.6.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Выполнение операции над множествами
Нахождение мощности множеств
Решение задач при помощи кругов Эйлера
Вычисление кортежей и декартового произведения множеств 7 баллов
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Классификация множеств.
Мощность множеств.
Кортежи и декартово произведение множеств.
Приложение кругов Эйлера к решению логических задач.
Описание бинарных отношений и их свойств.
Описание соответствия между множествами. За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.7 Устный ответ.
6.7.1 Текст задания.
Дать определение понятий функция, образ множества, прообраз множества
Дать определения инъективного и биективного отображения. Привести примеры.
Дать определение понятия подстановки.
Как осуществляется произведение подстановок?
Дать определение понятия цикла и длины цикла.
6.7.2 Время на выполнение: 10 мин.
6.7.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Формулировка понятий отображения и подстановки. 5 баллов
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.8 Расчетное задание.
6.8.1 Текст задания.
Вариант 1.
Определить четность подстановок.
Найти разложение подстановок в циклы.
Найти произведение подстановок:
F1=1 2 3 4 5 6 75 4 7 6 2 1 3, F2=1 2 3 4 5 6 72 7 3 6 1 4 5Вариант 2.
Определить четность подстановок.
Найти разложение подстановок в циклы.
Найти произведение подстановок:
F1=1 2 3 4 5 6 7 83 5 8 2 7 4 6 1, F2=1 2 3 4 5 6 7 88 2 6 5 3 4 7 16.8.2 Время на выполнение: 30 мин.
6.8.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Вычисление произведений подстановок. Разложение подстановок в произведение циклов 3 балла
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.9 Расчетное задание.
6.9.1 Текст задания.
Вариант 1.
1.Остановится ли когда-нибудь машина Тьюринга, заданная следующей программой
Q
А
П Л
1 П П Л
2413635745363000если она начнет перерабатывать слово, начав в состоянии обозревать ячейку, в которой записана самая левая буква перерабатываемого слова 11111 ?
2.Составить программу машины Тьюринга, которая заданное слово 001 преобразует в слово 0011
Вариант 2.
1.Остановится ли когда-нибудь машина Тьюринга, заданная следующей программой:
Q
А
П Л
1 П П Л
2413635745363000если она начнет перерабатывать слово, начав в состоянии обозревать ячейку, в которой записана самая левая буква перерабатываемого слова ?
2.Составить программу машины Тьюринга, которая заданное слово 111 преобразует в слово 0001
6.9.2 Время на выполнение: 45 мин.
6.9.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Составление алгоритмов
2 балла
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Описание элементов теории алгоритмов.
Формулировка определения алгоритма. За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.10 Устный ответ.
6.10.1 Текст задания.
Перечислите задачи теории шифрования.
Перечислите области применения шифрования.
Как работают шифры замена?
Как работают перестановочные шифры?
Как работают блочные шифры?
В чем заключается метод математической индукции?
6.10.2 Время на выполнение: 30 мин.
6.10.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
У1. Умение формулировать задачи логического характера и применять средства математической логики для их решения. Перечисление задач теории шифрования и областей ее применения
Формулировка метода математической индукции. 6 баллов
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.11 Расчетное задание.
6.11.1 Текст задания.
Доказать методом математической индукции:
11∙3+13∙5+…+1(2n-1)(2n+1)=n2n+1Доказать методом математической индукции:
1∙2+2∙3+3∙4+…+n(n+1)=n(n+1)(n+2)36.11.2 Время на выполнение: 20 мин.
6.11.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
З1 Знание основных принципов математической логики, теории множеств и теории алгоритмов. Применение метода математической индукции в доказательствах 6 баллов
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
6.12 Устный ответ.
6.12.1 Текст задания.
Указать, на какие типы подразделяются формулы алгебры высказываний.
Сформулировать определение выполнимой формулы.
Сформулировать определение опровержимой формулы.
Сформулировать определение тавтологии.
Сформулировать определение тождественно ложной формулы.
Перечислить последовательность действий при решении логических задач.
6.12.2 Время на выполнение: 30 мин.
6.12.3 Перечень объектов контроля и оценки
Наименование объектов контроля и оценки Основные показатели оценки результата Оценка
З2 Знание формул алгебры высказываний.
Классификация формул алгебры логики.
Перечисление последовательности действий при решении логических задач. 6 баллов
За правильный ответ на вопросы или верное решение задачи выставляется положительная оценка – 1 балл.
За неправильный ответ на вопросы или неверное решение задачи выставляется отрицательная оценка – 0 баллов.
Перечень вопросов к дифференцированному зачетупо дисциплине «Элементы математической логики»
Теоретическая часть.
Булевы векторы. Понятие булевой функции.
Способы задания булевой функции, описание.
Логическое отрицание (определение, таблица истинности)
Конъюнкция (определение, таблица истинности)
Дизъюнкция (определение, таблица истинности).
Импликация (определение, таблица истинности).
Эквивалентность (определение, таблица истинности).
Приоритеты логических операций. Логическая функция.
Алгоритм построения таблицы истинности.
Законы алгебры логики для дизъюнкции.
Законы алгебры логики для конъюнкции.
Законы алгебры логики для конъюнкции.
ДНФ (определение, алгоритм построения), СДНФ (определение, переход от ДНФ к СДНФ).
КНФ (определение, алгоритм построения), СКНФ (определение, переход от КНФ к СКНФ).
Теорема Поста. Описание замечательных классов функций.
Тавтологии, противоречия, основные аксиомы исчисления высказываний.
Правила вывода в исчислении высказываний.
Способы доказательства тавтологий.
Мощность множества. Булеан.
Предикаты (определение, примеры).
Кванторы.
Основные операции над множествами.
Бинарные отношения. Свойства бинарных отношений.
Отношение линейного порядка, частичного порядка, отношение эквивалентности.
Операции над бинарными отношениями.
Отображение, образ, прообраз.
Инъективные, биективные, сюръективные отображения.
Подстановки. Умножение подстановок. Знак подстановки.
Алгоритм разложения подстановки в цикл.
Алгоритм. Свойства алгоритмов. Простейшие функции. Рекурсивные функции
Машина Тьюринга. Основные определения.
Задачи теории шифрования и области ее применения.
Перестановочные шифры.
Шифры замены.
Блочные шифры.
Метод математической индукции.
Практическая часть.
Найти ДНФ и СДНФ аналитически и по таблице истинности для формулы
a∙(b∙c→a∙b)Найти КНФ и СКНФ аналитически и по таблице истинности для формулы
a∙(b∙c→a∙b)Является ли высказывание тавтологией (доказать по таблице истинности и аналитически с помощью законов алгебры логики):
(p∙p→q)→qДля булевой функции найдите представляющий ее полином Жегалкина .
Проверить является ли формулой ИВ выражение:
(A & B)→C
Из следующего предиката с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны () .
Проверить на полноту систему:
⋁,1Показать на диаграммах Венна:
(A∩B)∪(A∩B)(C\A)∩(C\B)(A∩B∩B∩C)\AОпределить четность подстановок, найти их разложение в циклы, найти произведение подстановок:
F1=1 2 3 4 5 6 75 4 7 6 1 2 3, F2=1 2 3 4 5 6 77 2 3 6 1 4 5Построить таблицы истинности для следующих высказываний:
(p→q)↔(q→p)(p⋀q⋁r)→(p→q)⋁(p→r)(p→q⋀q→r)→(r→p)Доказать методом математической индукции:
13+23+33+…+n3=n(n+1)22Составить программу машины Тьюринга, которая заданное слово 111 преобразует в слово 0011
Зачет формируется из одного теоретического вопроса и двух практических заданий. Время выполнения - 90 минут.
7. Шкала оценки образовательных достижений
Процент результативности (правильных ответов) Оценка уровня подготовки
балл (отметка) вербальный аналог
90 ÷ 100 5 отлично
80 ÷ 89 4 хорошо
70 ÷ 79 3 удовлетворительно
менее 70 2 неудовлетворительно
8. Перечень материалов, оборудования и информационных источников, используемых в аттестации
Основные источники:
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М., Энергоатомиздат, 1988.
Марков А. А.. Элементы математической логики. М., изд-во МГУ, 1984.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., Наука, 1984.
Дополнительные источники:
Новиков П. С. Элементы математической логики. 2-ое изд. М., Наука, 1973.
Новиков Ф.А. Дискретная математика для программистов. Спб., Питер, 2001.
Фомичев В.М. Дискретная математика и криптология. М., Диалог-МИФИ, 2003.

Приложенные файлы

  • docx file6
    Размер файла: 133 kB Загрузок: 20