Математическая логика
.
2.5.2 Функция Вебба (Пирса)
![]()
Аксиомы:
.
Коммутативность:
.
Формулы
преобразования
функций
Ї через
↓:
.
2.5.3 Функция импликации
![]()
Аксиомы:
.
Импликация обладает свойством коммутативности в виде:
;
ассоциативность не выполняется.
Формулы
преобразования
функций
Ї через
→:
.
2.5.4 Функция Шеффера
![]()
Аксиомы:
.
Свойство коммутативности верно только для двух переменных:
![]()
ассоциативность не выполняется.
Формулы преобразования:
![]()
3. Системы функций алгебры логики
3.1 Функциональная полнота
Алгебра над
множеством
логических
функций с двумя
бинарными
операциями
и
называется
алгеброй
Жегалкина.
В алгебре Жегалкина
выполняются
следующие
соотношения:

а также соотношения булевой алгебры, относящиеся только к конъюнкции и константам (с конъюнкцией).
Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:
![]()
![]()
Формулы,
содержащие
знаки
называют полиномами.
Полином вида:
,
где
есть либо 1, либо
переменная,
либо конъюнкция
различных
переменных,
при
,
называется
полиномом
Жегалкина.
Теорема.
Любая булева функция может быть представлена полиномом Жегалки- на
![]()
где ki
– коэффициенты,
принимающие
значения 0 или
1:
.
3.2 Класс линейных функций (К Л)
Булева функция называется линейной, если она представима полиномом первой степени
.
Количество
линейных функций
равно
,
где п
– число перемен-ных.
Для п = 2 их 8:

3.3 Класс функций, сохраняющих ноль (К 0)
Если булева
функция на
нулевом наборе
переменных
равна нулю, то
говорят, что
функция
сохраняет ноль:
![]()
3.4 Класс функций, сохраняющих единицу (К 1)
Если булева
функция на
единичном
наборе переменных
равна единице,
то говорят, что
функция
сохраняет
единицу:
![]()
3.5 Класс монотонных функций (К м)
Булева функция
называется
монотонной,
если для любых
двоичных наборов
из того, что
,
выполняется
неравенство:
.
3.6 Класс самодвойственных функций (К с)
Булева функция
называется
двойственной
для функции
,
если таблицу
истинности
для функции
можно получить
из таблицы для
функции f,
заменив в значениях
аргумента
функции 0 на 1
и 1 на 0, т.е. имеет
место равенство
![]()
Например, конъюнкция и дизъюнкция двойственны друг другу, отрицание двойственно самому себе.
Функция, совпадающая со своей двойственной, называется самодвойственной.
Самодвойственная
функция на
противоположных
наборах
и
принимает
противоположные
значения.
Противоположными
являются наборы,
сумма десятичных
эквивалентов
которых равна
2n
– 1, где п
– количество
переменных,
от которых
зависит функция.
Распределение булевых функций двух переменных по классам
| Функция | К л | К 0 | К 1 | К м | К с |
| f 0 | * | * | * | ||
| f 1 | * | * | * | ||
| f 2 | * | ||||
| f 3 | * | * | * | * | * |
| f 4 | * | ||||
| f 5 | * | * | * | * | * |
| f 6 | * | * | |||
| f 7 | * | * | * | ||
| f 8 | - | - | - | - | - |
| f 9 | * | * | |||
| f 10 | * | * | |||
| f 11 | * | ||||
| f 12 | * | * | |||
| f 13 | * | ||||
| f 14 | - | - | - | - | - |
| f 15 | * | * | * |
3.7 Принцип двойственности
Если в формуле
алгебры логики
F
заменить знаки
всех логических
функций на
знаки двойственных
функций, то
получится
двойственная
формула F
*, реализующая
функцию, двойственную
той, которая
реализуется
формулой F.
При этом, если
формулы равны
F
1 = F
2, то
верно равенство
двойственных
формул
,
которое называется
двойственным
предыдущему.
Например, равенства,
являющиеся
двойственными
друг другу:
и
;
и
;
и
;
и
;
и
.
3.8 Полнота функций алгебры логики
Суперпозицией
функций
называется
функция f,
полученная
с помощью подстановок
этих функций
друг в друга
и переименования
переменных,
а формулой
называется
выражение,
описывающее
эту суперпозицию.
Например, суперпозицию функций f1, f2, f3 можно задать формулой
.
Если f1 обозначает дизъюнкцию, f2 – конъюнкцию, а f3 – сложение по mod 2, то последняя формула примет вид:
.
Если рассматривается произвольная система функций, то возникает вопрос: всякая ли логическая функция из этой системы представима формулой, содержащей символы только этой системы функций.
Система функций алгебры логики (ФАЛ) называется функционально полной, если любая функция алгебры логики может быть реализована формулой, содержащей лишь символы функций из этой системы ФАЛ, т.е. является суперпозицией функций из этой системы.
Следовательно, система функций должна быть функционально полной.
3.9 Теорема Поста – Яблонского (критерий функциональной полноты)
Для того,
чтобы система
ФАЛ
была полной
необходимо
и достаточно,
чтобы она содержала
функцию:
1) не сохраняющую ноль;
2) не сохраняющую единицу;
3) нелинейную;
4) немонотонную;
5) несамодвойственную.
Примерами функционально полных систем являются, например, системы:
.
Все названные выше классы функций обладают свойством: любая ФАЛ, полученная с помощью операции суперпозиции и подстановки из функций одного класса, обязательно будет принадлежать этому же классу.
Полная система ФАЛ называется базисом,если теряется полнота Ф при удалении хотя бы одной функции системы.
К базису относятся системы функций:
базис 1:
;
базис 2:
;
базис 3:
;
базис 4: функция Шеффера: x1 | x2;
базис 5: функция Пирса (Вебба): x1 ↓ x2.
Базис 1 – избыточный, базисы 4 и 5 – минимальные (удаление хотя бы одной функции превращает систему ФАЛ в неполную).
При исследовании
полноты систем
функций удобно
пользоваться
таблицей, которую
называют
критериальной.
Эта таблица
имеет пять
столбцов, каждый
из которых
соответствует
одному из пяти
классов, а строки
таблицы соответствуют
функциям исследуемой
системы. На
пересечении
строки таблицы,
соответствующей
функции f,
и столбца,
соответствующего
классу К,
ставится знак
плюс, если функция
,
и минус, если
.
Система функций
полна тогда
и только тогда,
когда в каждом
столбце содержится
хотя бы один
знак минус.
Пример.
Является
ли система
булевых функций
полной?
Если является,
то выписать
все возможные
базисы.
Рассмотрим
функцию
.
1. Исследуем ее принадлежность к классу К0:
.
Следовательно,
.
2. Исследуем принадлежность функции к классу К1:
.
Следовательно,
.
3. Установим, является ли функция f1 линейной. Используем метод неопределенных коэффициентов. Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:
.
Найдем коэффициенты
,
исходя из
предположения
линейности
этой функции.
Зафиксируем
набор 000:
,
,
.
Следовательно,
.
Зафиксируем набор 100:
,
,
.
Следовательно,
.
Фиксируем набор 010:
,
Фиксируем набор 001:
![]()
.
Следовательно, функция (по нашему предположению) может быть представлена полиномом первой степени вида:
.
Если функция
линейная, то
полученный
полином, путем
тождественных
преобразований,
должен привестись
к виду заданной
функции. Ясно,
что полученный
полином не
приводится
к исходной
функции. Следовательно,
.
4. Исследуем заданную функцию на самодвойственность.
Функция
самодвойственная,
если на любой
паре противоположных
наборов (наборов,
сумма десятичных
эквивалентов
которых равна
,
где п
– количество
переменных
функции) функция
принимает
противоположные
значения.
Построим
таблицу:
;
вычислим значения
функции на
оставшихся
наборах:
:
|
(000) 0 |
(001) 1 |
(010) 2 |
(011) 3 |
(100) 4 |
(101) 5 |
(110) 6 |
(111) 7 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
На наборах
0 и 7, 1 и 6 функция
принимает
одинаковые
значения.
Следовательно
.
5. Проверим
принадлежность
заданной функции
f1
классу монотонных
функций. Из
таблицы видно:
001< 010, но
.
Следовательно,
функция
.
Рассмотрим
функцию
.
1. Принадлежность функции классу К0:
.
Следовательно,
.
2. Принадлежность функции классу К1:
.
Следовательно,
.
3. Принадлежность функции классу К л.
Предполагаем, что
.
Фиксируем набор 0000:
,
,
.
Фиксируем набор 1000:
,
.
Фиксируем набор 0100:
,
.
Фиксируем набор 0010:
,
.
Фиксируем набор 0001:
.
.
Окончательно получаем
.
Это равенство на других 11 наборах не выполняется. Действительно, для набора 1111 имеем
,
,
т.е.
.
Следовательно,
.
4. Принадлежность функции классу самодвойственных функций.
Строим таблицу:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
Из таблицы
видно, что на
наборах 1 и 14, 2 и
13, 7 и 8 функция
принимает
одинаковые
значения.
Следовательно,
.
5. Принадлежность функции классу монотонных функций.
Из таблицы
видно, что 1000>0000,
а
.
Следовательно,
.
Строим критериальную таблицу:
| К 0 | К 1 | К л | К с | К м | |
| f 1 | + | - | - | - | - |
| f 2 | - | - | - | - | - |
В таблице в каждом столбце стоит хотя бы один минус. Следовательно, система булевых функций является полной.
![]()
![]()
Найдем все возможные базисы. По критериальной таблице составим к.н.ф. К, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве слагаемых символы тех функций, которые не входят в класс, соответствующий столбцу. В данном случае имеем
.
Используя
законы и свойства
дизъюнкции
и конъюнкции,
приведем к.н.ф.
К к д.н.ф.
D,
в которой упрощение
невозможно.
В нашем случае
получим
.
По полученной д.н.ф. D выпишем подмножества функций, соответствующие слагаемым д.н.ф. D. Это и будут искомые базисы. В нашем случае имеется два базиса:
.
Минимальная форма представления ФАЛ содержит минимальное количество термов и переменных в термах (т.е. не допускает никаких упрощений).
Пример.
,
- минимальная
форма.
4 Способы представления функций алгебры логики
Для булевых функций существуют различные способы представления: таблица истинности, числовой, аналитический.
Пример.
Пусть функция
задана таблицей
истинности:
| № набора | х1 | х2 | х3 |
|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 0 |
В таблице в первом столбце под номером набора понимается десятичный эквивалент соответствующего двоичного набора.
Тогда запись
или
является числовым
представлением
этой функции,
где в скобках
показаны номера
наборов, на
которых функция
принимает
значение 1.
Запись
![]()
представляет собой аналитическое представление булевой функции.
Можно в выражении функции вместо конъюнкций термов записать соответствующие двоичные наборы. Тогда получим:
.
Булеву функцию можно задать с помощью единичного п – мерного куба (рис. 7).

Рис. 7
Единичным п – мерным кубом называется граф, каждая вершина которого взаимно однозначно соответствует двоичному набору. Две вершины соединены ребром, если соответствующие наборы отличаются только в одном разряде (в одной координате).
На рис. 7 показаны п-мерные кубы для булевых функций: двух переменных (а), трех переменных (б), четырех переменных (в).
Отметив вершины, в которых булева функция принимает единичные значения, получим геометрическое представление булевой функции. Так функция
![]()
примет вид:

Рис. 8
Часто для изображения булевых функций двух и трех переменных используют прямоугольную систему координат:

Рис. 9
Изображение булевых функций числа переменных более трех в этом случае невозможен.
В методе минимизации булевых функций Квайна – Мак-Класки используется кубическое представление булевых функций (аналог п-мерных кубов).
Терм максимального ранга принято называть 0-кубом и обозначать К 0. Если два 0-куба из комплекса К 0 различаются только по одной координате, то они образуют куб (отрезок) K 1.
Пример.
Для
.
5. Минимизация булевых функций
Импликантой функции называют некоторую логическую функцию, которая обращается в ноль на том же наборе переменных, на котором равна нулю сама функция.
Любой конъюнктивный терм (элементарная конъюнкция) или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции
Элементарная конъюнкция (конъюнктивный терм), в которой удален один или несколько первичных термов, называется простой импликантой.
Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.
5.1 Метод Квайна
На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:
.
Процедура продолжается до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом. В результате получают некоторое количество простых