8.4.2.1. Монотонные и линейные функции

Определение:

Функцию f() = f(x1,...,xn) называют монотонной, если для любых двух сравнимых наборов и , таких, что ≤ , справедливо f() ≤ f().

Все монотонные функции образуют класс М. Для отнесения произвольной функции из табл. 4.1 к этому классу необходимо сравнить ее значения на всех пяти парах сравнимых наборов: (0,0) ≤ (0,1), (0,0) ≤ (1,0), (0,0) ≤ (1,1), (0,1) ≤ (1,1), (1,0) ≤ (1,1). Среди функций двух переменных монотонными являются шесть функций: f₀, f₁, f₃, f₅, f₇, f₁₅.

Свойство линейности переключательных функций определяется как свойство полинома Жегалкина, представляющего собой формулу над функциональным базисом, {∧, ⊕, 0, 1}. Рассмотрим вначале свойства операции ⊕:

1. операция ⊕ коммутативна: х₁ ⊕ х₂ = х₂ ⊕ х₁;
2. операция ⊕ ассоциативна: (х₁ ⊕ х₂) ⊕ х₃ = х₁ ⊕ (х₂ ⊕ х₃);
3. операция ∧ дистрибутивна по отношению к операции ⊕: x₁(x₂ ⊕ х₃) = x₁x₂ ⊕ x₁x₃;
4. операция ⊕ не идемпотентна: х ⊕ х = 0, х ⊕ х ⊕ х = x.

Следует отметить, что отсутствие идемпотентности распространяется на сумму любого четного (нечетного) числа слагаемых.

5. справедливо равенство x_σ = x ⊕ ; частные случаи: x = x¹ = x ⊕ 0; = x⁰ = x ⊕ 1(связь с инверсией);
6. если в многомерной сумме по модулю 2 x₁ ⊕ x₂ ⊕ ... ⊕ x_n на любом из наборов только одно из слагаемых принимает значение 1, то такая сумма взаимно однозначно совпадает с многомерной дизъюнкцией этих же слагаемых; это следует из того, что x₁ ⊕ x₂ совпадает с x₁ ∨ x₂ на наборах 00, 01, 10 (содержащих не более одной 1). На основании этого свойства замена в СДНФ символов ∨ на ⊕ на будет эквивалентным преобразованием формулы.

В общем случае для построения полинома Жегалкина произвольной ПФ нужно выполнить следующие действия:

• на основании табличного задания либо путем эквивалентных преобразований произвольной формулы построить СДНФ;
• в СДНФ символы операции ∨ заменить на символы ⊕;
• вместо всех инверсных переменных x_i подставить эквивалентные подформулы (x_i ⊕ 1);
• раскрыть скобки и привести подобные члены по правилу: х ⊕ х ⊕...⊕ х ⊕ х = 0 (четное число слагаемых); х ⊕ х ⊕...⊕ х = x (нечетное число слагаемых).

Всякая линейная функция может быть представлена в виде линейного полинома Жегалкина:
(x₁,...,x_n) = a₀ ⊕ a₁x₁ ⊕...⊕ a_ix_i ⊕...⊕ a_nx_n, где a_i ∈ {0,1}, i = 0,1,...,n.

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

Если в построенном полиноме Жегалкина хотя бы один из коэффициентов a_j, j = n+1,...,(2ⁿ-1), соответствующих нелинейным конъюнктивным членам полинома, отличен от нуля, функция не принадлежит классу L, т. е. нелинейна.

Проверим на линейность некоторые функции из табл. 4.1. Очевидно, что в такой проверке не нуждаются функции f₀(x,y) = 0, f₃(x,y) = x, f₅(x,y) = y, f₆(x,y) = x ⊕ y, f₁₅(x,y) = 1.

Функции f₁₂(x,y) = и f₁₀(x,y) = могут быть приведены к полиномам вида f₁₂(x,y) = 1 ⊕ x и f₁₀(x,y) = 1 ⊕ y, являющимся линейными, что указывает на линейность этих функций.

Функция равнозначности f₉(x,y) = x ∼ y может быть представлена СДНФ вида xy ∨ . После замены символа дизъюнкции ∨ символом ⊕ функции mod 2, замены переменных с отрицаниями, раскрытия скобок и приведения подобных членов получим полином Жегалкина

Для функции f₁(x,y) = xy (конъюнкция) полином Жегалкина строится тривиально: f₁(x,y) = xy = 0 ⊕ xy. Как видно, полином и соответственно функция конъюнкции нелинейны.

Теперь построим полином Жегалкина для функции f₇(x,y) = x ∨ y - дизъюнкция:

Для функции f₁₄(x,y) = x / y - функции Шеффера полином строится достаточно просто, так как она (см. табл. 4.1) является инверсией конъюнкции:

.

.

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

Пред.Страница  След.Страница    Раздел    Содержание