Учебное пособие: Дискретная математика
Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени.
Теорема. Любая функция булевой алгебры может быть представлена, и притом единственным образом, с помощью полинома Жегалкина вида
J =.
Представим, например, в виде полинома выражение вида X1X2. Для этого проведем следующие рассуждения.
Пусть
X1X2 = aX1X2+bX1+cX2+k,
где а, b, с, k – неопределенные коэффициенты.
При X1 = X2 = 0 имеем k = 0. При Х1 = 1, X2= 0 имеем b= 1. При Х1= 0, Х2= 1 имеем с= 1. При X1=Х2= 1 имеем а + b + с = 1, т. е. а = -1. Таким образом, получаем:
X1X2 = – X1X2+ X1+ X2.
СПНФ образуется путем замены в СДНФ: на + и на
1 х.
,
,
В последнем случае выражение для легко можно упростить, если раскрыть скобки и взаимно сократить все одинаковые слагаемые, входящие в формулу четное число раз:
.
Подобное упрощение, которое называется минимизацией логической функции, можно осуществить и по отношению к СДНФ и СКНФ.
Таблица 6
y | |||
0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 |
0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
Применение законов алгебры логики позволяет найти более компактные аналитические выражения для заданной функции у, т. е. минимальную дизъюнктивную нормальную форму . Приведем соответствующие формы представления функции у, заданной табл. 6:
,
и для СКНФ, т. е. минимальную КНФ:
.
После того, как найдены минимальные нормальные формы (МНФ), их рекомендуется проверить на всех наборах аргументов . Переменные или часто называют термами. Именно полный набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.
Как мы только что убедились на примере, импликанты появляются в результате склейки смежных конституент, различающихся одним термом.
Контрольные вопросы и упражнения
1. Дайте определение логической функции многих переменных.
2. Что такое вектор значений булевой функции? Приведите пример построения таблицы истинности логической функции многих переменных.
3. Сколько существует булевых функций от n переменных?
4. Что такое ДНФ и КНФ?
5. Каков алгоритм построения СДНФ? Приведите пример построения СДНФ.
6. Каков алгоритм построения СКНФ? Приведите пример построения СКНФ.
7. Составьте СКНФ и СДНФ для функции .
8. Приведите пример построения СПНФ.
3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса
Система булевых функций {f1, f2,…, fm} называется полной, если любая булева функция может быть выражена через функции f1, f2,…, fm с помощью суперпозиций.
Пусть К0={f1(x1,…,xk1), f2(x1,…,xk2),…, fm(x1,…,xkm)} – конечная система булевых функций. Функция f называется элементарной суперпозицией (суперпозицией ранга 1) функций f1, f2,…, fm, если f может быть получена одним из следующих способов:
а) переименованием некоторой переменной xj какой-нибудь функции fi;
б) подстановкой некоторой функции вместо какой-либо переменной xj любой из функций .
Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающийся из функций класса Ks-1 суперпозицией ранга s‑1 с помощью элементарных суперпозиций, называется классом функций Ks суперпозиций ранга s. Суперпозициями функций из К0 называются функции, входящие в какой-то из классов Ks.
Согласно введенным определениям, можно говорить, что система булевых функций полна. Тогда любую булеву функцию можно представить в виде многочлена от своих переменных.
В современном компьютере цифрами являются ноль и единица. Следовательно, команды, которые выполняет процессор, суть булевы функции. Мы уже видели, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие . Далее рассмотрим вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающие тем свойством, что с их помощью можно выразить все другие функции. Рассмотрим некоторые замкнутые классы (классы Поста), их пять.
1. Класс функций, сохраняющих константу нуль (обозначается T0 или P0):
T0:= f (0,0,…, 0)=0.
К этому классу относятся, например, функции ; ; ; .
2. Класс функций, сохраняющих константу единица (обозначается T1 или P1):
T1:=f .
К нему относятся все нечетные функции.
3. Класс самодвойственных функций (обозначается T* или S):
T*:= f*;
Пример и .
Функция называется двойственной по отношению к функции , если . Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, т. е. в таблице истинности нужно заменить 0 на 1, 1 на 0.
Пример. Двойственной к функции является функция, соответствующая формуле , т. е. или : . Аналогично , .
Принцип двойственности:
Если ,
то .
Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций.
Этот принцип удобен при нахождении двойственных функций, представленных формулами, содержащими лишь конъюнкции, дизъюнкции и отрицание. В этом случае в исходной формуле конъюнкции заменяются на дизъюнкции, а дизъюнкции – на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ.
Пример. ,
если , то и .
Функция называется самодвойственной, если .
Пример. Покажем, что формула задает самодвойственную функцию.
Убедимся, что на всех противоположных наборах значений переменных и формула принимает противоположные значения. Действительно, составим таблицу истинности:
x | y | z | |
0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
1 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 |
Получаем , , , .
4. Класс монотонных функций (обозначается TM или M):
, где , , , .
5. Класс линейных функций (обозначается TL или L):
.
Эквивалентность является линейной функцией . Стрелка Пирса – нет, .
, , ,…, ,
т. е.
, ,…, . (7)
Таким образом, проверка линейности сводится к нахождению коэффициентов по формулам (7) и сопоставлению таблиц истинности данной формулы и полученной формулы .
Пример. Проверим, является ли линейной функция . Имеем , , . Таким образом, . Сопоставляя таблицы истинности формул и , убеждаемся, что они не совпадают. Вывод: функция нелинейна.