3. Барашев В.П., Унучек С.А. Дискретная математика

φ2(x) = fi2 (φ1(x), φ1(x), . . . , φ1(x)) = fi2 (fi1 , fi1 , . . . , fi1 ) ≡ 0.

Обе константы уже получены, функцию x можем выразить по лемме М из немонотонной функции fi4 .

б) fi1 (1, 1, . . . , 1) = 0

Рассмотрим наборы α = (0, 0, . . . , 0) и β = (1, 1, . . . , 1).

e

По лемме М можно получить функцию x.

e e

Наборы α и β противоположны, все значения их координат различны. Все координаты этих наборов заменяем на х. Получим набор γ = (x, x, . . . , x).

φ1(0) = fi1 (0, 0, . . . , 0) = 1 φ1(1) = fi1 (1, 1, . . . , 1) = 0

В этом случае у нас есть функция x, выраженная через функцию fi1 (xe) , и по лемме S мы можем получить по крайней мере одну из констант из несамодвойственной функции fi3 .

Оставшуюся константу можно выразить через функции fi1 и fi3 , либо опять применяя лемму S (если есть соответствующая пара противоположных наборов), либо используя формулы

0 = 1

1 = 0 .

Заметим, что применять эти тождества можно только после того, как получили одну из констант и функцию "отрицание".

2. Получение функций x y и x&y

151

Константы 0, 1 и функция x уже выражены через функции си- стемы fi1 , fi2 , fi3 и fi4 .

По лемме L можно получить одну из функций дизъюнкцию или конъюнкцию из нелинейной функции fi5 . Вторую нелинейную

функцию можно получить из уже полученной формулы, приме-

{

x y = x&y x&y = x y

Таким образом, используя функции fi1 , fi2 , fi3 , fi4 , fi5 мы получили полную систему 1 = {x, x y, x&y}. Значит, по теореме 8.1, и исходная система функций полна.

Замечание 8.1. Необходимо строго придерживаться порядка получения функций 0, 1, x, x y, x&y. Например, нельзя применять лемму L, подставляя вместо одной переменной константу, если эта функция еще не выражена через функции системы.

Замечание 8.2. Исследовать систему функций = {f1, f2, . . . , fk} на полноту удобно, используя так называемую таблицу Поста

(ещё одно название - критериальная таблица).

Вывод : Согласно теореме Поста система функций полна тогда и только тогда, когда в каждом столбце таблицы есть хотя бы один минус.

В связи с этим, нет необходимости заполнять таблицу полностью: если в столбце стоит хотя бы один минус, переходим к следующему столбцу.

152

Для получения "- \в столбце, соответствующего классу М, удобно пользоваться выводами о немонотонности (см. замечание 7.13 на стр. 128); в столбце, соответствующем классу L - следствием 7.9.1 к необходимому признаку линейности функции (см. теорему 7.9).

Пример 8.1. Доказать с помощью теоремы Поста полноту системы функций = {f1, f2}, где f1(x) = (1010 1010), f2(x) = (0011 0101).

2.fe1 S; (см. пример 7.6 п.б )

Для определения самодвойственности функции fe2 воспользуемся алгоритмом 2 проверки самодвойственности функции.

fe2 = (0011 0101)

(0011 | 0101)

←−−−−

(1010) (1 0 1 0) (0101)

Так как (0011) ≠ (0101), то функция fe2 не является самодвойственной.

3.Так как f1(000) = 1, а f1(001) = 0, то, согласно выводу 1 из замечания 7.13 на странице 128, функция fe1 немонотонна:

(000) 4 (001), а f1(000) = 1 > f1(001) = 0 )

Исследуем функцию fe2 на монотонность, используя алгоритм 2 определения монотонности функции:

f2(xe) = (0011 0101)

αe0 = (0011) 4̸ αe1 = (0101) fe1 / M.

Заметим, что можно было не исследовать функцию fe2 на принадлежность классам T0, T1 и M, так как в соответствующих столбцах таблицы уже есть "- \.

153

4. Выше было установлено:

f1(xe) = 1 x3 L.

Так как следствие 7.9.1 к необходимому признаку линейности булевой функции (теорема 7.9 ) применить нельзя, проверим линейность функции fe2 с помощью 3 алгоритма представления функции в виде многочлена Жегалкина (метода треугольника):

L, и, по теореме Поста, полна.

II.Выразим элементарные булевы функции 0, 1, x, x&y, x y через функции fe1 и fe2.

1.Сначала выразим функции одной переменной. Эти функции удобно получать на крайних наборах таблицы истинности, то есть на наборах (000) и (111).

154

Замечание 8.3. Рассмотрим получение функций одной переменной на примере булевой функции g.

В зависимости от принадлежности функции g классам T0 и T1, возможны следующие варианты:

Константы и функцию x на этой паре наборов получить нельзя. В этом случае переходим к той функции, у

155

которой есть минус в первых двух столбцах таблицы Поста (случаи а, б или в ). Такая функция по теореме Поста обязательно есть среди функций . Выражаем через неё все возможные функции одной переменной. Функцию g4, возможно, будем использовать позже для получения тех элементарных функций, которые не смогли выразить через остальные функции системы.

Так как f1 / M, f1(000) = 1 > f1(111) = 0, то функцию x удобно получить из функции f1 на крайних наборах таблицы истинности (случай а ):

2.Функция f2 принадлежит классам T0 и T1, поэтому на наборах (000) и (111) функции одной переменной получить не можем (случай г ).

Константы 0 и 1 выразим из несамодвойственной функции f2 (так как f1 S, то лемма S к функции f1 не применима).

fe2 = (0011 0101).

@

@

На парах противоположных наборов (001) и (110); (010) и (101) нарушается самодвойственность функции f2. Выразим константы, используя те наборы, которые содержат больше единиц, заменив "1"на x, "0 на x:

αe1 = (110) 7→γe1 = (x, x, x)

φ2(x) = f2(x, x, x) ≡ 0,

так как

φ2(0) = f2(000) = f2(001) = 0

φ2(1) = f2(111) = f2(110) = 0

156

f2(x, x, f1(x, x, x)) ≡ 0.

αe2 = (101) 7→γe2 = (x, x, x)

φ3(x) = f2(x, x, x) ≡ 1,

так как

φ3(0) = f2(000) = f2(010) = 1

φ3(1) = f2(111) = f2(101) = 1

f2(x, f1(x, x, x), x) ≡ 1.

Замечание 8.4. Мы выбираем наборы, содержащие наименьшее количество нулей, чтобы при выражении 0 и 1 набор γe содержал как можно меньше функций x.

3.Нелинейные функции x&y и x y выразим из нелинейной функции f2 ( к функции f1 L лемма L не применима).

f2(x1, x2, x3) = x2 x1x3 x1x2.

Многочлен Жегалкина функции f2 содержит 2 конъюнкции ранга 2. Возьмем, например, K = x1x3. Переменные x1 и x3, входящие в К, оставим без изменения, переменную x2 заменим на 0.

Вычислим значение функции f2 на наборе γe = (x1, 0, x3):

f2(x1, 0, x3) = 0 x1x3 x1 · 0 = x1x3

Заменим x1 ↔ x; x3 ↔ y; φ4(x, y) = f2(x, 0, y) = xy

Подставим формулу для функции 0:

f2(x, f2(x, x, f1(x, x, x)), y) = xy

4.Для получения дизъюнкции применим законы де Моргана xy = x y, навесив отрицание на обе части полученного тождества f2(x1, 0, x3) = x1x3 :

f2(x1, 0, x3) = x1 x3 f2(x1, 0, x3) = x1 x3

Заменим x1 ↔ x; x3 ↔ y; φ5(x, y) = f2(x, 0, y) = x y

157

Подставим функции одной переменной, выраженные через функции системы

f2(f1(x, x, x), f2(x, x, f1(x, x, x)), f1(y, y, y)) = x y

Окончательно получим

f1(f2(f1(x, x, x), f2(x, x, f1(x, x, x)), f1(y, y, y)),

f2(f1(x, x, x), f2(x, x, f1(x, x, x)), f1(y, y, y)),

f2(f1(x, x, x), f2(x, x, f1(x, x, x), f1(y, y, y))) = x y

Пример 8.2. Проверить полноту системы 2 = {f, g}, где f~ = (1001 1001) , g~ = (0110 1010). В случае полноты системы представить формулами над 2 функции 0, 1, ¬, &, .

Решение.

I. Заполним таблицу Поста для системы функций 2.

Замечание 8.5. Несмотря на то, что проверять функцию g на принадлежность классу T0 не обязательно (в соответствующем столбце таблицы уже получен "минус"), первые два столбца таблицы всегда будем заполнять полностью, чтобы использовать замечание 8.3 при выражении функций одной переменной на крайних наборах функции системы.

2. Исследуем самодвойственность функций системы: fe= (1001 1001)

(1001 | 1001)

←−−−−

(1001) (1 0 0 1)

(1001) ≠ (0110) fe / S.

3.Так как f(000) = 1, а в векторе значений функции f есть нули, то, согласно выводу 1 из замечания 7.13 на странице 128, функция f не монотонна.

158

Не будем исследовать принадлежность функции g классам S и M, так как система 2 не содержится целиком в этих классах.

4.Так как вектор значений обеих заданных функций содержит равное количество нулей и единиц, без многочлена Жегалкина определить нелинейную функцию нельзя.

f(xe) = x2 x3 1 L

g(xe) = x3 x2 x1 x1x2 / L

Представить функции системы в виде многочлена Жегалкина предлагаем читателю самостоятельно.

5.Система целиком не содержится ни в одном из основных замкнутых классов T0, T1, S, M и L, и, по теореме Поста, полна.

II. Выразим основные элементарные функции 0, 1, x, x&y, x y через функции f и ge.

1. Начинаем с крайних наборов в таблице истинности, то есть наборов (000) и (111).

Так как f(000) = f(111) = 1, то на этих наборах нарушается самодвойственность (случай б) из замечания 8.3). Заменив в

2.Так как g(000) = g(111) = 0, функция g также несамодвойственна (случай в) из замечания 8.3). Аналогично предыдущему случаю, получаем функцию 0:

3.Функцию x получим из немонотонной функции f.

Для этого найдем любую пару наборов, на которой нарушается монотонность, например, (000) (так как f(000) = 1) и любой из наборов αe, на котором f(αe) = 0. Таких наборов 4;

159

возьмем первый по порядку следования в таблице истинности,

e

то есть β = (001).

(000) 4 (001), f(000) = 1 > f(001) = 0

{ αe = (000)

e

β = (001) γe = (0, 0, x)

φ3(0) = f(000) = 1 φ3(x) = f(0, 0, x) = x, так как φ3(1) = f(001) = 0

f(g(x, x, x), g(x, x, x), x) = x

4.Нелинейные функции x&y и x y выразим через нелинейную функцию g ( к функции f лемма L не применима).

g(x1, x2, x3) = x3 x2 x1 x1x2.

Многочлен Жегалкина функции g содержит единственную конъюнкцию K = x1x2. Оставляем переменные x1 и x2 без изменения, вместо x3 подставим 0.

Вычислим значение функции g на наборе γe = (x1, x2, 0) :

g(x1, x2, 0) = 0 x2 x1 x1x2 = x1 x2 x1x2 =

=x1 1 1 (1 x1)x2 = x1 1 x1x2 = x1(1 x2) 1 =

=x1 x2 1 = x1 x2 = x1 x2

Заменим x1 ↔ x; x2 ↔ y; φ4(x, y) = g(x, y, 0) = x y

g(x, y, g(x, x, x)) = x y

5.Функцию "конъюнкция"можно получить, применяя законы де Моргана и навешивая отрицание на обе части полученного тождества g(x1, x2, 0) = x1 x2 :

g(x1, x2, 0) = x1 x2 = x1 x2

Заменяем x1 ↔ x; x2 ↔ y; φ5(x, y) = g(x, y, 0) = x y

160