Лекции по математической логике и теории алгоритмов
Волжский Университет им. Татищева.
Лекции по математической логике и теории алгоритмов.
Составитель: доцент С.В. Каверин.
Тольятти 2002.
СодержаниеСодержание.................................................................................................. 1
Глава I. Алгебра логики.............................................................................. 2
§1.1. Определение булевой функции.......................................................... 2
§1.2. Элементарные булевы функции......................................................... 3
§1.3. Задание булевых функций посредством элементарных.................... 5
§1.4. Существенные и несущественные переменные.................................. 6
§1.5. Таблицы истинности. Эквивалентные функции................................. 6
§1.6. Основные эквивалентности................................................................. 7
§1.7. Функциональная полнота................................................................... 8
Глава II. Булева алгебра............................................................................ 11
§2.1. Нормальные формы.......................................................................... 11
§2.2. Совершенные нормальные формы.................................................. 13
§2.3. Минимизация ДНФ методом Квайна............................................... 17
§ 2.4. Карты Карно.................................................................................... 20
Глава III. Алгебра Жегалкина................................................................... 23
Глава IV. Высказывания. Предикаты....................................................... 25
§4.1. Высказывания................................................................................... 25
§4.2. Предикаты. Логические операции над предикатами....................... 26
§4.3. Кванторы, их свойства...................................................................... 27
Глава V. Формальные теории................................................................... 29
§5.1. Определение формальной теории.................................................... 29
§5.2. Исчисление высказываний................................................................ 30
§5.3. Теорема о дедукции. Полнота ИВ................................................... 32
§5.4. Автоматическое доказательство теорем.......................................... 33
§5.5. Метод резолюций в ИВ.................................................................... 33
Глава VI. Элементы теории алгоритмов.................................................. 35
§6.1. Определение алгоритма.................................................................... 35
§6.2. Машина Тьюринга............................................................................ 36
§6.3. Рекурсивные функции....................................................................... 40
§6.4. Алгоритмически неразрешимые задачи.......................................... 43
§6.5. Алгоритмы и их сложности.............................................................. 44
ЛИТЕРАТУРА........................................................................................... 46
Глава I. Алгебра логики.§1.1. Определение булевой функции.
Булевой функцией y=f(x 1 ,x 2 ,…,x n )отп переменных x 1 , x 2 ,...,x n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц
(x 1 ,x 2 ,...,x n ) ставится в соответствие значение 0 или 1.
Булевы функции называются также функциями алгебры логики, двоичными функциями и переключательными функциями.
Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2n -1 (такой порядок расположения наборов назовем лексикографическим порядком ). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо n
1, заключаем, что существует всего 22 различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.
Пример 1.1.1. (голосование). Рассмотрим устройство, фиксирующее принятие некоторой резолюции "комитетом трех". Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют «за», то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z) , таблица истинности которой имеет вид