Определение булевых функций. Замкнутые классы, теорема Поста. Моделирование релейно-контактных схем и сумматоров. Основные положения математической логики. Неформальное определение алгоритма. Конечные автоматы и некоторые классические алгоритмы.
С ее помощью можно строить защиту в суде, но невозможно сконструировать электрическую, релейную или логическую схему. Точного определения дать невозможно (как нельзя дать точного определения точки в геометрии). Простые высказывания как элементы математической логики называются пропозициональными переменными, обозначаются буквами и принимают истинностные значения «И» или «Л». Составные высказывания строятся из простых с помощью логических связок. Импликация обладает неожиданным свойством: из лжи следует истина, но из истины ложь следовать не может.Булевой функцией переменных будем называть однозначное отображение пространства , которое является прямым произведением пространств , состоящих из двух элементов, в пространство . Среди булевых функций выделяются так называемая тавтология - функция, равная единице при любом наборе аргументов, и противоречие - функция, принимающая значение O при любом наборе аргументов. Отрицание функции - это такая функция , которая для любого набора аргументов принимает значение, противоположное соответствующему значению . Если для двух функций их значения при каждом наборе аргументов совпадают, то они считаются одной и той же функцией. В то же время имеется еще одна возможность задания булевых функций с помощью применения специальных обозначений для некоторого класса функций, причем функции, не входящие в этот класс, возникают как суперпозиции функций, входящих в исходный класс.Рассмотрим некоторую булеву функцию, заданную формулой. Для составления ее таблицы истинности достаточно в цикле перебрать все значения аргументов и вычислить значения, принимаемые в этих наборах. Шапкой таблицы являются наборы аргументов в виде векторов-столбцов; в строках выписаны значения функции в этих наборах. С таблично заданной функцией можно взаимно однозначно сопоставить логическое выражение (формулу), построенное по следующему правилу: - для каждой строки, отвечающей истинности функции, выписывается конъюнкция, содержащая все независимые переменные, причем с нулем сопоставляется отрицание, и такие конъюнкции называются конституэнтами; Если ограничиться строками, отвечающими истинности функции, то СНДФ-заданную функцию можно представить в виде матрицы, содержащей строки в количестве размерности пространства аргументов, а в качестве столбцов - наборы аргументов, соответствующих истинности заданной функции: .
План
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. БУЛЕВЫ ФУНКЦИИ
1.1 Определение булевых функций
1.2 Построение СНДФ, СНКФ и СНПФ. Минимизация
1.3 Реализация метода Квайна - Мак-Класки
1.4 Замкнутые классы. Полнота. Теорема Поста
1.5 Моделирование релейно-контактных схем
1.6 Моделирование сумматоров
2. ОСНОВНЫЕ ПОЛОЖЕНИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
2.1 Формальные теории
2.2 Исчисление высказываний
2.3 Исчисление предикатов
2.4 Приложение исчисления предикатов к аналитической геометрии
3. ВЫЧИСЛИМОСТЬ
3.1 Неформальное определение алгоритма. Примеры
3.2 МНР-вычислимые функции
3.3 Рекурсия
3.4 Вычислимость по Тьюрингу
4. КОНЕЧНЫЕ АВТОМАТЫ
4.1 Основные определения и способы задания
4.2 Эквивалентность автоматов. Минимизация
4.3 Автоматы Мили и Мура. Размеченные графы
4.4 Автоматные языки
4.5 Возможности автоматов
5. НЕКОТОРЫЕ КЛАССИЧЕСКИЕ АЛГОРИТМЫ
5.1 Алгоритмы сортировки и их классификация
5.2 Поиск
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
