Функциональная полнота систем переключательных функций

Элементарные переключательные функции позволяют получить сложные функции от большего числа аргументов путем подстановки в данную функцию вместо ее переменных других функций. Такой метод получения функций называется суперпозицией. Например, имея элементарные функции двух переменных z 1= х1х2и z 2= х3∨ х4, можно получить функции z 3= x 1( x 3∨ х4), z 4= x 3∨ х1x 2, зависящие от трех переменных.

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

Эта проблема называется проблемой функциональной полноты переключательных функций. Для ее решения были выделены следующие классы логических функций.

1. Класс функций, сохраняющих константу 0. В этот класс входят функции, которые на нулевом наборе переменных принимают нулевое значение: f (00...0) = 0. Такова, например, конъюнкция f 8(00) =0 · 0 = 0.

2. Класс функций, сохраняющих константу 1. В этот класс входят функции, которые на единичном наборе переменных принимают единичное значение: f (11 ... 1) = 1. Этим свойством также обладает конъюнкция f 8(11) = 1 · 1 = 1. Классы 1, 2 легко устанавливаются по таблице истинности.

3. Класс самодвойственных функций. Переключательные функции f ( x 1x 2... х n) и g ( x 1x 2... х n) называются двойственными , если имеет место равенство т. е. когда одна функция получается из другой, если провести замену всех переменных на их инверсии и провести инверсию функции. Например, f 8( x 1x 2) = х1х2и f 14(х1x 2) = х1∨ х2двойственны: Это можно доказать, построив таблицу истинности (табл. 27).

Таблица 27

Таблица истинности

Переключательная функция называется самодвойственной , если она двойственна по отношению к самой себе: Такова, например, функция

Самодвойственность устанавливается по таблице истинности следующим образом: значения функции, симметричные относительно середины таблицы, инверсны. Например, для f 10( x 1x 2) значения функции представляют собой вектор каждый разряд которого является инверсным по отношению к симметричному разряду относительно середины, отмеченной пунктиром.

Эти разряды соответствуют инверсным наборам х1х2: 00-11, 01-10. Самодвойственны функции

4. Класс линейных функций. Переключательная функция называется линейной , если возможно представление в виде линейного полинома, использующего функцию сложения по модулю 2:

f ( x 1х2) = с0⊕ с1х1⊕ с2х2, где с0, с1, с2— константы 0, 1,

Например, для функции f 6(х1х2) = х1⊕ х2при с0= 0, с1= с2= 1 : f 6(х1х2) = 0 ⊕ 1 · х1⊕ 1х2.

Получим все линейные функции двух переменных, задав все возможные значения с0с1c 2(табл. 28).

Таблица 28