Волжский Университет им. Татищева.
Лекции по математической логике и теории алгоритмов.
Составитель: доцент С.В. Каверин.
Тольятти 2002.
§1.1. Определение булевой функции.......................................................... 2
§1.2. Элементарные булевы функции......................................................... 3
§1.3. Задание булевых функций посредством элементарных.................... 5
§1.4. Существенные и несущественные переменные.................................. 6
§1.5. Таблицы истинности. Эквивалентные функции................................. 6
§1.6. Основные эквивалентности................................................................. 7
§1.7. Функциональная полнота................................................................... 8
§2.1. Нормальные формы.......................................................................... 11
§2.2. Совершенные нормальные формы.................................................. 13
§2.3. Минимизация ДНФ методом Квайна............................................... 17
Глава III. Алгебра Жегалкина................................................................... 23
Глава IV. Высказывания. Предикаты....................................................... 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
Булевой функцией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), таблица истинности которой имеет вид
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Вектором значений булевой функции y=f(x1,x2,…,xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).
Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
1. Булева функция f(x 1 ,x 2 ,…,x n ) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.
2. Булева функция f(x 1 ,x 2 ,…,x n ) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение:0.
3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности
| x | 0 | 1 |
| f(x) | 1 | 0 |
Обозначения:Ÿx, x . Запись Ÿx читается «не икс» или «отрицание икс».
4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 0 | 0 | 1 |
Другие названия: логическое умножение (произведение); логическое «и».
Обозначения: x&y, xÿy, x⁄y, min(x,y).
Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».
5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 1 | 1 | 1 |
Другие названия: логическое сложение (сумма); логическое «или».
Обозначения: x¤y, max(x,y).
Запись x¤y может читаться так: «икс или игрек» или «сумма икс и игрек».
6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 1 | 0 | 1 |
Другое название: логическое следование. Обозначения: xØy, xfly, xy.
Запись xØy может читаться так: «из икс следует игрек».
7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 0 | 0 | 1 |
Обозначения: x~y, x¨y,.xªy.
Запись x~y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».
8. Суммой по модулю_2 называется булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 1 | 1 | 0 |
Другое название: антиэквивалентность. Обозначения: x∆y, x+y.
Запись x∆y может читаться так: «икс плюс игрек».
9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 1 | 1 | 0 |
Другое название: отрицание конъюнкции, логическое «не-и».
Обозначение: x|y.
Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».
10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 0 | 0 | 0 |
Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.
Обозначение: x∞y; для функции Вебба - x±y.