1-8. ПОЛНЫЕ СИСТЕМЫ ФУНКЦИЙ

Определение 1-9. Система функций алгебры логики называется полной в классе если любая функция принадлежащая может быть представлена суперпозицией функций

Определение 1-10. Система функций являющаяся полной в классе называется базисом.

Определение 1-11. Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций образующих этот базис, превращает систему функций в неполную.

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

В силу теоремы 1-1 общее число различных функций, зависящих от аргументов, равно Поэтому существует тривиальная полная система в классе состоящая из всех 2 функции этого класса. Рассмотрим другие полные системы функций в классе

В предыдущем параграфе мы показали, что любая функция может быть представлена в виде ДСНФ или КСНФ [соотношения (1 -33) и (1-34)]. Следовательно, оказывается верным утверждение о полноте системы, состоящей из трех функций; конъюнкции, отрицания и дизъюнкции. Если воспользоваться формулами де Моргана

то в ДСНФ или КСНФ можно заменить конъюнкцию через отрицание и дизъюнкцию или дизъюнкцию заменить через отрицание и коньюнкцию. Легко проверить, что базисы являются минимальными.

Из того факта, что всякая функция представима в совершенной полиномиальной форме, следует полнота системы, состоящей из функций конъюнкции, сложения по модулю 2 и отрицания. Из этой системы можно исключить отрицание, воспользовавшись соотношением Если в ПСНФ произвести такую замену, то мы получим представление функции через сложение по модулю 2, конъюнкцию и константу 1. Такое представление носит название полинома Жегалкина (полинома по модулю 2).

Пример 1-10. Записать виде полинома по модулю 2 функцию

Применяя соотношения (1-4), (1-5), (1-14), (1-17) и распределительный закон сложения по модулю относительно конъюнкции, получаем:

Из соотношения (1-29) и способа построения характеристических функций вытекает, что полную систему функций образуют отрицание, дизъюнкция и эквивалентность, а из теоремы 1-6 вытекает представимость любой функции в системе, состоящей из конъюнкции, отрицания и импликации. Для последного представления можно заменить конъюнкцию через отрицание и импликацию а отрицание — через импликацию и константу нуль Импликация и нуль образуют минимальный базис.

Теорема 1-8. Функция Шеффера образует в полную систему.

Доказательство теоремы вытекает из таблицы

Таким образом,

т. е.

Теорема доказана, так как отрицание и конъюнкция образуют в полную систему.

Теорема 1-9. Функция Вебба образует в полную систему.

Доказательство теоремы проводится так же, как и теоремы 1-8.

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

Пример 1-11. Записать, используя только функцию Вебба, функцию алгебры логики

Используя последовательно соотношения

получаем:

Задача о полноте состоит в следующем. Дана система функций алгебры логики Ответ на вопрос, является ли эта система полной в классе дает следующая теорема Поста — Яблонского, которую мы приводим без доказательства.

Теорема 1-10. Для того чтобы система функций была полной, необходимо и достаточно, чтобы она содержала функции: 1) не сохраняющую константу нуль, 2) не сохраняющую константу единица,

3) не являющуюся самодвойственной, 4) не являющуюся линейной, 5) не являющуюся монотонной.

Применим теорему 1-10 к доказательству полноты системы функций Функция отрицания не сохраняет константы нуль и единицы и не является монотонной.

Функция дизъюнкции не является самодвойственной и линейной.

На основании критерия полноты можно утверждать, что система является полной.

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

Пример 1-12. Доказать, что система функций неполна в классе

Для показательства проверяем условия теоремы 1-10. Функция отрицания не сохраняет константы и не является монотонной. Однако и функции отрицания и функция эквивалентности являются линейными. Необходимые условия критерия полноты не выполнены и, следовательно, система неполна.

Интересна следующая теорема, связанная с проблемой построения минимального базиса в классе

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

Пусть — полная система. Тогда среди найдется в силу теоремы 1-10 функция не сохраняющая константу нуль. Если

то эта же функция является несамодвойственной. Если же

то является функцией, не сохраняющей константу единица и немонотонной.

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

Обобщим понятие функций Вебба и Шеффера.

Многоместной функцией Шеффера будем называть любую функцию которая является одновременно функцией, не сохраняющей константы 0 и 1, и является несамодвойственной, немонотонной и нелинейной. Такая функция на основании теоремы 1-10 образует полную систему.

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

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

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

Следуя Г. А. Шестопал, назовем базис простым, если образующие его функции обладают следующим свойством: при любом отождествлении аргументов получающаяся система функций не является базисом. Простые базисы изучались Г. А. Шестопал, которая показала, что для двоичной логики существует всего 44 различных простых базиса; 2, содержащих одну функцию; 16, содержащих две функции; 23, содержащих три функции, и 3, содержащих четыре функции.

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

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

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

Теорема 1-12. Для того чтобы в система функций была полна, необходимо и достаточно, чтобы эта система не содержалась целиком ни в одном из вышеперечисленных классов.

Для неполностью определенных функций можно доказать теорему, являющуюся аналогом теоремы 1-11 для .-полностью определенных функций.

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

Доказательство этой теоремы проводится по аналогии с доказательством теоремы 1-11.

Роль функции Шеффера в играет функция

Эти функция образует в полную систему (минимальный базис). Р. В. Фрейвалдом показано, что в это единственная функция, образующая в единичном количестве полную систему.