Выше показано, что любая функция может быть выражена в виде ДНФ, т.е. формулой, использующей функциональные знаки ,
,┐ и
символы переменных. Еще один интересный пример дает система функций
{1, X Y, X
Y}. (1)
Выше показано, что ┐Х = Х 1. Используя это равенство и закон
де Моргана (свойство 11), выразим дизъюнкцию Х
Y через функции системы (1).
X Y = ┐(┐X
┐Y) = (X
2) ∙
(Y
1)
1 = XY
X
Y
1
1 =
= XY
X
Y
Поэтому в любой ДНФ можно выразить дизъюнкцию и отрицание через функции системы (1).
1) ┐X YZ = [заменяем знак отрицания] = (X
l)
YZ= [заменяем знак дизъюнкции] = (X
1)
∙ YZ
(X
1)
YZ = [раскрываем скобки] = XYZ
YZ
X
1
YZ = XYZ
X
1.
2) XY XZ = [заменяем знак дизъюнкции] = XY ∙ XZ
XY
XZ= [используем поглощение Х ∙ Х = Х ] = XYZ
XY
XZ.
3) XY XZ = XY ∙ (X
1)
∙ Z
XY
(X
l) ∙ Z =
XYZ
XYZ
XY
XZ
Z=XY
XZ
Z. To же преобразование можно выполнить проще, заменяя сначала знак дизъюнкции:
XY ┐XZ = XY ∙ ┐XZ
XY
┐XZ . Первое слагаемое равно 0, так как
содержит произведение Х ∙ ┐Х , и его можно из формулы удалить. Оставшуюся часть преобразуем, заменяя знак отрицания:
XY XZ = XY
(X
1) ∙ Z = [раскрываем скобки] =XY
XZ
Z.
Как видно из рассмотренных примеров, если в формуле после произведенных замен раскрыть скобки и выполнить умножения и сложения, а также поглощение по правилам эквивалентных преобразований, то получится формула, представляющая сумму но модулю 2 некоторых конъюнкций переменных (в каждой конъюнкции переменные не повторяются, но, в отличие от элементарных конъюнкций - без отрицаний) и, быть может, константы 1.
Полученная формула, порожденная логическими константами 0 и
1 и функциями X Y и Х
Y называется многочленом Жегалкина. Можно показать, что различные (с точностью до перестановки слагаемых в сумме и сомножителей в конъюнкциях) многочлены представляют различные функции, т.е. имеет место единственность представления булевой функции многочленом Жегалкина
В самом деле, пусть два многочлена Р(Х1, Х2,...,Хn) и Q(Х1, Х2,...,Хn) равны как функции, т.е. на одинаковых наборах принимают одинаковые значения. Тогда для какого-нибудь существенного переменного,(пусть это Х1), вынеся Х1 за скобки из всех содержащих его членов, Р и Q можно представить в виде
Р(Х1, Х2,...,Хn) = X1 R1(Х2,...,Хn)
S1(Х2,...,Хn) (∙)
Q(Х1, Х2,...,Хn) = X1 R2(Х2,...,Хn)
S2(Х2,...,Хn) (∙∙)
где Ri, Si - многочлены, зависящие от переменных (Х2,...,Хn).
Достаточно показать, что
R1 = R2, S1 = S2 как многочлены. Легко проверить, что для n = 1 утверждение о единственности многочлена верно: все функции одной переменной - в таблице 1. Тем самым выполнено базовое условие для применения метода математической индукции по числу переменных n. Выполним индукционный шаг: предположим, что утверждение справедливо для функций (n -1) переменных и докажем его для n. Поскольку Р и Q тождественно равны, то при Х1 = 0 они также равны. Но при этом Р = S1(Х2,...,Хn), а Q = S2( Х2,...,Хn).Значит, S1 и S2 совпадают как многочлены, по предположению
индукции, и, прибавив S1, к обеим частям (∙>) и, соответственно, S2 к (∙∙), получим
P S1 = X1
R1;
Q S2= X1
R2.
Левые части этих равенств равны, следовательно, равны и правые, в том числе, при X = 1, откуда R1 и R2 равны как функции. Тогда, по предположению индукции, они совпадают и как многочлены, что завершает доказательство.
Возникает вопрос: как определить для системы функций, можно ли с ее помощью выразить любую логическую функцию. В связи с этим рассмотрим несколько понятий.
Замыкание системы булевых функций D - класс всех суперпозиций функций системы D .
1) Если система D - множество из двух функций:
конъюнкции и дизъюнкции, то ее замыкание - всевозможные ДНФ такие, что входящие в них элементарные конъюнкции не содержат отрицаний переменных (например, XZT YS
YSTW
XYT). Любую другую суперпозицию конъюнкции и дизъюнкции можно привести к такому виду: во всякой формуле, представляющей собой конъюнкцию дизъюнкций можно раскрыть скобки и преобразовать ее в дизъюнкцию конъюнкций. Так,
X
(XZ
Y)(XT
XYZ) = Z
XXZT
XYT
XXYYZ
XYYZ = [используем поглощение X ∙ X = X] = X
XZT
XYT
XYZ.
2) Если система D состоит из одной функции X Y , то ее замыкание -
всевозможные суммы различных переменных.
Замкнутый класс булевых функций - множество функций K, любая
суперпозиция которых принадлежит K, т.е. замкнутый класс представляет собой множество булевых функций, замкнутое относительно операции суперпозиции.
1) Замыкание любой системы функций - замкнутый класс.
2) 4 функции одной переменной - замкнутый класс.
3) 2 функции ┐X и X образуют замкнутый класс.
4) Множество сумм по модулю 2 нечетного числа переменных является
замкнутым классом, поскольку подстановка в такую функцию вместо переменной функции этого класса увеличивает число вхождений переменных в формулу на четное число; при этом некоторые слагаемые могут взаимно сократиться ввиду эквивалентности X X = 0, и число переменных остается нечетным, поскольку при сокращениях в формуле переменные устраняются парами.
Функционально полная система функций - система, замыкание которой составляет P2 - множество всех логических функций.
Как показано выше, системы функций {X Y, X
Y, ┐X} и {1,
X
Y, X
Y }полны.
Можно обобщить построения, примененные при рассмотрении полноты систем многочленов Жегалкина, и сформулировать следующее утверждение.
Пусть система {ƒ1, ...,ƒk} - полная и пусть каждая из функций ƒi может быть выражена суперпозицией через функции g1, ...,gm.
Тогда система {g1, ...,gm} тоже полная, потому что в формуле, составленной из функциональных знаков системы {ƒ1, ...,ƒk}, можно заменить каждое вхождение символа функции ƒ на ее выражение через символы функций {g1, ...,gm}.
Вот несколько примеров.
(1) Система {┐, } полна, так как X
Y = ┐(┐X
┐Y) (закон де
Моргана).
(2) Аналогично показывается полнота системы {┐, }.
(2) Система {->, ┐} полна, поскольку X Y = ┐X ->Y.
Здесь мы рассмотрим 5 замкнутых классов, играющих особую роль в вопросе о функциональной полноте. Они называются предполными: причина будет выявлена ниже.
1)Класс T0 - класс функций, сохраняющих 0, т.е. функций, для которых ƒ(0,0,...,0) = 0 . Замкнутость класса Т0 очевидна: если в функцию Z = ƒ(X1, X2, ...,Xn) вместо некоторых переменных подставить функции, принадлежащие T0 , то на нулевом наборе аргументов все они имеют значение 0, и для внешней функции ƒ набор ее переменных будет также нулевым, откуда Z = 0 .
2)Класс T1 - класс функций, сохраняющих 1, т.е. функций, для
которых ƒ(1,1,...,1) = 1 . Замкнутость T1, устанавливается аналогично предыдущему.
Примерами функций, принадлежащих классам T0 и T1, служат функции
Х Y и Х
Y ; отрицание ┐X не принадлежит ни T1 ни T0;
функция X
Y принадлежит T0, но не принадлежит T1, импликация
Х -> Y напротив, не принадлежит T1, но принадлежит T0 .
3) Для определения следующего класса введем понятие двойственности. Двойственная функция для функции Z = ƒ(X1, X2, ...,Xn) - функция Z* =┐ƒ(┐X1, ┐X2, ..., ┐Xn). Если на наборе σ˜ = (σ1, σ2, ...,σn) функция ƒ принимает значение α, то двойственная ей функция ƒ* на противоположном наборе ┐σ˜ = (┐σ1, ┐σ2, ...,┐σn) принимает противоположное значение ┐α.
Для булевых функций справедлив принцип двойственности - если в формуле F , представляющей функцию ƒ, все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула F* будет представлять функцию ƒ*, двойственную ƒ.
Класс S самодвойственных функций - то есть функций таких, что ƒ(X1, X2, ...,Xn) = ƒ*(X1, X2, ...,Xn). Из определения следует, что двоичный набор значений самодвойственной функции антисимметричен относительно своей середины. Таким способом удобно проверять по таблице самодвойственность функции. Например, можно убедиться, что одноместные функции X и ┐X - самодвойственные, а среди функций двух переменных самодвойственными являются только функции с одной несущественной переменной. Функция большинства m3(X, Y, Z) является самодвойственной.
Из определения нетрудно вывести, что класс самодвойственных
функций - замкнутый, поскольку в любой суперпозиции на противоположных наборах внутренние подформулы принимают противоположные значения, и, тем самым, наборы значений аргументов внешней функции также противоположны.
Пусть ƒ(X1, X2, ...,Xn), φ1(t1, t2, ...,tm), ...., φn(t1, t2, ...,tm) ≥ S и
F(t1, t2, ...,tm) = ƒ(φ1(t1, t2, ...,tm), ..., φn(t1, t2, ...,tm)) - суперпозиция этих самодвойственных функций.
Тогда ┐F(t1, t2, ...,tm) = ┐ƒ(φ1(t1, t2, ...,tm), ..., φn(t1, t2, ...,tm)) = [поскольку ƒ ≥ S] =
ƒ(┐φ1(t1, t2, ...,tm), ..., ┐φn(t1, t2, ...,tm)) =
= [поскольку φ1(t1, t2, ...,tm), ..., φn(t1, t2, ...,tm) ≥ S] =
= ƒ(φ1(┐t1, ...,┐tm), ..., φn(┐t1, ...,┐tm)) = F(┐t1, ...,┐tm).
4)Мы убедились в возможности представления любой функции многочленом Жегалкина.
Подмножеством множества многочленов является класс L линейных
функций - функции вида Xi1 Xi2
...
Xin
σ. Здесь Xi1 , Xi2 , Xin - переменные, σ - булева константа (0 или 1).
Очевидно, что класс линейных функций - замкнутый: подстановка сумм
вместо переменных представляет собой сумму, при этом некоторые пары слагаемых могут взаимно сократиться ввиду эквивалентности
Х Х=0.
Пусть ƒ(X, Y, Z) = X Y
Z
1, φ1 = X
Y
S
T,
φ2 = S
Z
1.
Тогда суперпозиция F(X, Y, Z, S, T) = ƒ(φ1, φ2, Z) [в функцию ƒ
подставляем функцию φ1 вместо Х и функцию φ2 вместо Y] представляет собой линейную функцию:
F(X, Y, Z, S, T) = (X Y
S
T)
(S
Z
1)
Z
1 = X
Y
T.
5) Введем отношение частичного порядка для булевых векторов: X ≤ Y (где X = (α1, α2В начале , ...,αn), Y = (β1, β2, ...,βn)) - если αi ≤ βi, для I = 1,2,...,n. Заметим, что для булевых переменных строгое неравенство α < β означает, что α = 0, β = 1, поскольку других возможностей нет. Равенство α = β добавляет варианты α = β = 0 и α = β = 1. Поэтому неравенству α ≤ β удовлетворяют 3 пары (α, β); (0, 0); (0, 1); (1, 1) и не удовлетворяет только пара (1, 0). Можно заметить, что (α ≤ β) эквивалентно (α -> β).
Класс M монотонных функций - это класс функций таких, что если X ≤ Y , то ƒ(X) ≤ ƒ(Y), т.е. функция на большем наборе принимает не меньшее значение. Среди заданных в таблице 6 функций двух существенных переменных монотонными являются конъюнкция и дизъюнкция.
Покажем, что класс монотонных функций - замкнутый.
Пусть функции
ƒ(X1, X2, ...,Xn), φ1(t1, t2, ...,tm), ..., φn
(t1, t2, ...,tm) ≥ M и F(t1, t2, ...,tm) =
= ƒ(φ1(t1, t2, ...,tm), ..., φn(t1, t2, ...,tm))
суперпозиция этих монотонных функций.
Пусть также
α ≤ β (α = (α1, α2, ...,αn), β = (β1, β2, ...,βn)).
Тогда φi(α) ≤ φi(β) для i = 1, 2,..., m , так как φi ≥ M.
Поэтому
F(α1, α2, ...,αm) = ƒ(φ1(α1, α2, ...,αm), ..., φn(α1, α2, ...,αm)) ≤
≤ [поскольку ƒ ≥ M] ≤ ƒ(φ1(β1, β2, ...,βm), ..., φn(β1, β2, ...,βm)) = F(β1, β2, ...,βm) что и требовалось доказать.
Отметим, что для каждой упорядоченной пары (A, B) различных классов из пяти рассмотренных предполных T0, T1, S, L, M существует функция, входящая в A и не входящая в B. Таблица 1 содержит такие примеры: каждая функция таблицы входит в класс, соответствующий строке и не входит в класс, соответствующий столбцу. Например, входит в M , но не входит в S функция-константа 0; входит в S , но не входит в L функция m3(X, Y, Z) . Из этого замечания можно сделать важный вывод: никакой из пяти классов T0, T1, S, L, M не входит целиком ни в какой из остальных четырех.
A: B: |
T0 | T1 | S | L | M |
T | * | 0 | 0 | X ![]() |
X ![]() |
T1 | 1 | * | 1 | X ![]() |
X ˜ Y |
S | ┐X | ┐X | * | m3(X, Y, Z) | ┐X |
L | ┐X | ┐X | X ![]() |
* | X ![]() |
M | 1 | 0 | 0 | X ![]() |
* |
![]() |
Практические задания |
![]() |
Tест для самоконтроля |