Самодвойственные функции

В математике существует понятие двойственности. Самодвойственными называются функции, двойственные самим себе. Применительно к булевым функциям.

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

. (5.26)

Монотонные функции

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

Например, (1,0,0,1)(1,0,1,1), (1,0,1,0)(1,0,1,1). В то же время, неверно, что (1,0,0,1) (1,0,1,0).

Очевидно, что данное отношение образует частичный порядок на множестве наборов аргументов.

Монотонной называется булева функция, если при возрастании наборов аргументов ее значения не убывают.

Здесь, естественно, считается, что 1>0.

Линейные функции

Определение 25. Функция f(x₁,…,x_n) называется линейной, если существуют a₀, a₁,…,a_n{0,1} такие, что

f (x₁,…,x_n)=a₀a₁x₁…a_n x_n, (5.27)

т.е. если функция представима линейным полиномом Жегалкина. Здесь в качестве операции по умолчанию подразумевается логическое умножение, т.е. конъюнкция (например, a₁x₁ тождественно a₁  x₁).

Например, инверсия является линейной функцией (), функция конъюнкции не линейна.

Функции, сохраняющие константу

Определение 26. Функция f (x₁,…,x_n) называется функцией, сохраняющей ноль, если f (0,…,0)=0.

Определение 27. Функция f (x₁,…,x_n) называется функцией, сохраняющей единицу, если f (1,…,1)=1.

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

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

Пример 5.15. Рассмотрим классический базис {, , }. Здесь “” не монотонна, не сохраняет ноль и единицу, ““ и ““– не линейные и не самодвойственные.

Пример 5.16. Можно показать, что функции Шеффера и Пирса (каждая сама по себе) являются базисом, т.е. через любую из них могут быть выражены все возможные булевы функции.

Данный факт нашел широкое применение в технике, например, элемент И-НЕ, реализующий функцию Шеффера, является базовым для ряда серий интегральных микросхем, т.е. является тем основным “кирпичиком”, из которых воздвигаются здания и города аппаратных средств вычислительных систем и комплексов.

Вопросы для самоконтроля

1. К каким классам относится функция эквивалентности?

2. Докажите полноту базиса Жегалкина .