5.2.1. Задания для проведения текущего контроля включают: перечень вопросов (п. 5.1.), требующих ответов в устной или письменной форме согласно результатам обучения и содержанию тем дисциплины.
5.2.2. Задания промежуточной аттестации в виде экзамена включают: вопросы, требующие ответов в письменной форме, и задачу, требующую практического решения.
| № п/п | Задание |
| 1. | 1. Высказывание. Логические операции. 2. Теории первого порядка, их свойства. 3. Задача (тема – логика предикатов). |
| 2. | 1. Пропозициональные буквы, связки и формы. Таблицы истинности. 2. Обзор неклассических логик (основные понятия, применимость). 3. Задача (тема – дедуктивные теории). |
| 3. | 1. Тавтологии. Противоречия. Равносильность. 2. Подходы к определению алгоритма, неформальное определение. Алфавит, слова, вполне эквивалентные алгоритмы. 3. Задача (тема – логика предикатов). |
| 4. | 1. Основные законы алгебры логики. 2. Нормальные алгоритмы Маркова. 3. Задача (тема – сложность вычислений). |
| 5. | 1. Нормальные формы. Совершенные нормальные формы. 2. Функции, частично выводимые и вычислимые по Маркову. Замыкание и распространение нормального алгоритма. Операции над нормальными алгоритмами 3. Задача (тема – логика высказываний). |
| 6. | 1. Минимизация формул, диаграммы Вейча (карты Карно). 2. Машина Тьюринга. 3. Задача (тема – логика предикатов) |
| 7. | 1. Анализ и синтез схем цифровых схем из логических элементов. 2. Вычислимость по Тьюрингу. 3. Задача (тема – логика высказываний). |
| 8. | 1. Функционально полные базисы. Элементы «штрих Шеффера», «стрелка Пирса». 2. Связь между машинами Тьюринга и нормальными алгоритмами. 3. Задача (тема – дедуктивные теории). |
| 9. | 1. Понятие предиката. Формулы логики предикатов. 2. Основная гипотеза теории алгоритмов (тезис Черча) 3. Задача (тема – логика высказываний) |
| 10. | 1. Интерпретация и модель в логике предикатов. Общезначимые, выполнимые, равносильные формулы. 2. Проблема алгоритмической неразрешимости 3. Задача (тема – сложность вычислений). |
| 11. | 1. Кванторы. Правила преобразований формул с кванторами (перестановка, вынесение за скобки, перенесение отрицаний через кванторы). 2. Примитивно рекурсивные, общерекурсивные и частично рекурсивные функции. 3. Задача (тема – логика высказываний) |
| 12. | 1. Логическое следствие. Проблема дедукции. 2. Основные понятия лямбда-исчисления. 3. Задача (тема – сложность вычислений) |
| 13. | 1. Резольвента дизъюнктов логики высказываний. Метод резолюции 2. Теория естественного вывода 3. Задача (тема – логика высказываний). |
| 14. | 1. Метод насыщения уровня. Стратегия вычёркивания. Лок-резолюция. 2. Формальная арифметика (теория S). 3. Задача (тема – теория алгоритмов). |
| 15. | 1. Хорновские дизъюнкты. Метод резолюции для хорновских дизъюнктов. 2. Класс NP. NP-полные и NP-трудные задачи. 3. Задача (тема – логика высказываний) |
| 16. | 1. Преобразование формул логики предикатов. Сколемовская стандартная форма. 2. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций 3. Задача (тема – сложность вычислений) |
| 17. | 1. Дедуктивные теории и их свойства 2. Теоремы исчисления высказываний. 3. Задача (тема – теория алгоритмов) |
| 18. | 1. Полуформальные и формальные аксиоматические теории. 2. Полиномиальные алгоритмы и задачи, класс P. 3. Задача (тема – логика высказываний) |
| 19. | 1. Свойства выводимости. 2. Временная и емкостная сложность вычислений 3. Задача (тема – логика высказываний) |
| 20. | 1. Исчисление высказываний. 2. Многоленточные машины Тьюринга. Квантовый аналог машин Тьюринга. 3. Задача (тема – логика предикатов). |
Курсовая работа
Трудоемкость – 32 часа.
Цель курсовой работы состоит в применении булевой алгебры для синтеза цифровых электронных схем из функциональных логических элементов. В соответствии с заданным вариантом на основании таблицы истинности требуется выполнить следующие задания:
1). Записать логические выражения для двух переключательных функций в совершенной дизъюнктивной нормальной форме (СДНФ)
2). Выполнить минимизацию полученных логических выражений с помощью диаграмм Вейча (карт Карно), используя стандартные логические элементы «И», «ИЛИ», «НЕ».
3). Построить модели соответствующих цифровых электронных схем в пакете Multisim (или аналогичном), получить временные диаграммы их работы и сравнить результаты с таблицами истинности.
4). Выполнить минимизацию логических выражений, используя два указанных в варианте задания функционально полных набора логических элементов (то есть всего в итоге должно получиться 4 формулы).
5). Аналогично пункту 3 построить модели полученных четырех схем, получить их временные диаграммы, сравнить результаты с таблицами истинности. В пояснительной записке требуется обосновать, что полученные схемы действительно содержат минимально возможное количество вентилей.
Пример схемы (не минимизированной) для функции «дизъюнкция» на элементах «И-НЕ» и её временная диаграмма показаны на следующих рисунках.
Примерная тематика/формулировки заданий (по вариантам):
| Вари-ант | Названия функций | Задание курсовой работы | |||||
| Таблицы истинности | Логические элементы (для пунктов 4 и 5) | ||||||
| X1 = | |||||||
| X2 = | |||||||
| Запрет по X2 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Штрих Шеффера | Y2= | ||||||
| Переменная X1 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Запрет по X1 | Y2= | ||||||
| Сумма по модулю 2 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Инверсия X2 | Y2= | ||||||
| Стрелка Пирса | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Инверсия X1 | Y2= | ||||||
| Равнозначность | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Импликация от X2 к X1 | Y2= | ||||||
| Конъюнкция | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Импликация от X1 к X2 | Y2= | ||||||
| Запрет по X2 | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Штрих Шеффера | Y2= | ||||||
| Переменная X1 | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Запрет по X1 | Y2= | ||||||
| Сумма по модулю 2 | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Инверсия X2 | Y2= | ||||||
| Стрелка Пирса | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Инверсия X1 | Y2= | ||||||
| Равнозначность | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Импликация от X2 к X1 | Y2= | ||||||
| Конъюнкция | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Импликация от X1 к X2 | Y2= | ||||||
| Запрет по X2 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Импликация от X1 к X2 | Y2= | ||||||
| Запрет по X1 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Штрих Шеффера | Y2= | ||||||
| Переменная X1 | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Сумма по модулю 2 | Y2= | ||||||
| Стрелка Пирса | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Инверсия X2 | Y2= | ||||||
| Равнозначность | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Инверсия X1 | Y2= | ||||||
| Конъюнкция | Y1= | И-НЕ ИЛИ и НЕ | |||||
| Импликация от X2 к X1 | Y2= | ||||||
| Запрет по X2 | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Импликация от X1 к X2 | Y2= | ||||||
| Запрет по X1 | Y1= | ИЛИ-НЕ И и НЕ | |||||
| Штрих Шеффера | Y2= |
Примерный объем пояснительной записки – 15-20 страниц, примерный объем графической части – 3 листа формата A4.