2. Принципы построения программы курса.

Материал курса изложен в форме лекций, с использованием большого количества примеров.

Курс имеет модульную структуру, студенты могут использовать различные схемы изучения материала. Различные разделы могут быть интересны преподавателям вузов и учителям школ.

3. Методические рекомендации к основным темам курса

1. Общие методические рекомендации

При проведении лекций преподаватель

1. формулирует тему и цель занятия;

2. излагает основные теоретические положения;

3. под запись дает определения основных понятий, теорем, алгоритмов;

4. проводит примеры для наглядного и образного представления изучаемого материала;

5. в конце занятия дает вопросы для самостоятельного изучения.

2. Распределение часов курса по темам и видам работ

№	Тема	Всего часов	Аудиторные занятия				Самостоятельная работа
			В том числе
			лекции	семинары	лабораторные занятия
1	Функции алгебры логики	11	4	6		1
2	Принцип двойственности	8	2	4		2
3	Полнота и замкнутость	18	10	6		2
4	Минимизация ДНФ	18	8	8		2
5	Элементы теории автоматов	16	8	6		2
6	Элементы теории кодирования	13	8	4		1
7	Исчисление высказываний	10	4	4		2
8	Исчисление предикатов	8	2	4		2
Итого		144	62	62		20

3. Темы и краткое содержание

Тема 1. Функции алгебры логики (булевы функции). Табличное представление. Число функций от n переменных. Элементарные функции. Индуктивное определение формулы над множеством булевых функций. Формулы над множеством элементарных функций. Соседние наборы. Существенные и фиктивные переменные. Добавление и исключение фиктивных переменных. Равенство функций и эквивалентность формул. Основные тождества алгебры логики. Операции поглощения и склеивания.

Тема 2. Принцип двойственности. Теорема о двойственной функции. Разложение функции по подмножеству переменных. Теорема о разложении по m переменным. Частные случаи разложения по одной и всем переменным. Вывод формул СДНФ и СКНФ.

Тема 3. Полнота и замкнутость. Определение полной системы. Теорема о полной системе. Примеры полных систем. Определение замыкания. Свойства замыканий. Определение полной системы через замыкание. Определение замкнутого класса. Свойства замкнутых классов, сохраняющих константы. Замкнутый класс самодвойственных функций и его свойства. Лемма о не самодвойственной функции. Сравнимые наборы. Замкнутый класс монотонных функций и его свойства. Лемма о немонотонной функции. Полином Жегалкина. Теорема о единственности полинома для функции. Линейный полином. Замкнутый класс линейных функций и его свойства. Лемма о нелинейной функции. Теорема о необходимых и достаточных условиях полноты систем булевых функций. Теорема о числе функций полных систем. Функции к-значной логики (определение, табличное задание).

Тема 4. Минимизация ДНФ. Теорема о числе ДНФ функций n переменных. Определения минимальной и кратчайшей ДНФ. Тривиальный алгоритм их построения. Геометрическая интерпретация булевой функции (n-мерный куб, матрица в коде Грея). Определение интервала. Свойства интервала. Допустимый и максимальный интервалы. Покрытие множества единичных наборов функции интервалами. Кратчайшее и минимальное покрытия. Импликанта, простая импликанта, их свойства. Сокращенная ДНФ. Теорема Квайна о сокращенной ДНФ. Троичные векторы и операции над ними. Алгоритм Квайна–МакКласки построения сокращенной ДНФ. Таблица Квайна и ее кратчайшие и минимальные покрытия. Теорема Блейка. Алгоритм Блейка построения сокращенной ДНФ. Общая схема построения минимальных и кратчайших ДНФ. Теорема о сокращенной ДНФ монотонной функции. Ортогональные конъюнкции. Ортогональные ДНФ. Теорема о поглощении конъюнкции дизъюнктивной нормальной формой. Использование теоремы для построения безызбыточной ДНФ. Объединение и пересечение безызбыточных (тупиковых) ДНФ. Ядро ДНФ. Теорем Квайна о ядре и ее следствие. Упрощение ДНФ. Минимизация частичных булевых функций. Реализация частичной функции. Допустимый и максимальный интервалы частичной функции. Сокращенная ДНФ и ее построение. Построение минимальной и кратчайшей реализации частичной функции по таблице Квайна.

Тема 5. Элементы теории автоматов. Представление о дискретном устройстве, комбинационном и последовательностном. Простейшие логические элементы. Описание поведения комбинационного устройства. Пример. Проблема анализа и синтеза комбинационного устройства. Анализ комбинационного устройства. Синтез комбинационного устройства в базисе ДНФ, НЕ ИЛИ, НЕ И. Определение автомата. Его представление таблицами переходов-выходов. Диаграммы переходов. Полностью определенные и частичные автоматы. Автономные автоматы, автоматы без выходов, комбинационные автоматы, автоматы Мили, Мура. Триггеры. Канонические уравнения и их получение. Формальные языки и настроенные диаграммы. Конечно-автоматные языки и операции над ними. Замкнутость конечно-автоматных языков.

Тема 6. Элементы теории кодирования. Алфавитное кодирование. Префикс и окончание. Свойство префикса. Теорема. Нетривиальное разложение элементарных кодов в схеме кодирования. Алгоритм проверки однозначности кодирования. Неравенство МакМилана (теорема). Свойства взаимно-однозначных кодов. Теорема. Коды с минимальной избыточностью. Дерево однозначного кодирования. Операции на нем. Насыщенное и приведенное деревья. Алгоритм построения кода с минимальной избыточностью.

Тема 7. Исчисление высказываний. Алфавит, синтаксис и семантика исчисления высказываний. Проблема вывода. Дерево частичных интерпретаций и его построение. Анализ КНФ на невыполнимость резольвентным методом. Связь метода Блейка и резольвентного метода.

Тема 8. Исчисление предикатов. Алфавит, синтаксис и семантика исчисления предикатов. Предваренная нормальная форма. Проблема вывода. Хорновские дизъюнкты.