Дискретно-непрерывная математика (стр. 49 )

то среди чисел есть число п — 1.

Поэтому То есть

а значит, Аналогично функция

равна функции Ji(х). Действительно, при x = i выполняется ра­венство

А присреди чисел

естьчисло п — 1. Поэтому

То есть

Для доказательства утверждения осталось получить только функциюДля этого воспользуемся следующим равен-

ством:

которое аналогично равенствудля функ-

ций алгебры логики. Таким образом, достаточно получить функцию N(x) .

Покажем, как получать произвольные функции одной пере­менной из Рп. Для произвольных из Vn рассмотрим функции

При функция ψ принимает значение k—1, а при

выполняется равенство Поэтому Пусть теперь g(x) - произвольная функ­ция (одной переменной) из Рп. Тогда

Следовательно, мы можем получить и функцию N (х) .

Итак, мы выразили все функции системы

в виде формул над исходной системой. Поскольку система F явля­ется полной, то получаем, что— полная система5.

• Система, состоящая из функции Вебба является

полной в Рn.

Доказательство. Действительно, Поэтому

можно получить любую функциюКроме то-

го, выполняется равенство По-

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

Как видим, обычно доказательство полноты конкретных сис­тем в Рп производится с помощью метода сведения к заведомо пол­ным системам.

7.3.2. Признаки функциональной полноты и неполноты

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

Пусть обозначает множество всех функций n-значной ло­гики, зависящих от одной переменной. Функция от одной перемен­ной называется разнозначной, если она принимает все п значений. Тогда множество всех разнозначных функций из Рn обозначим по­средством

Критерий Слупецкого: Системаполна в Рn (при

т. т.т., когда f(х) — существенная функция [Shipecki 1939].

Критерий Яблонского: Система полна в Рn (при

т. т.т., когда f(x) — существенная функция [Яблонский 1958; 1986].

Критерий Саломаа: Системаполна в Рn (при

т. т.т., когда f(x) — существенная функция [Salomaa 1962].

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

следует, что обе функции принадлежат к классу функций, со­храняющих множество истинностных значенийт. е. для любого набора σ, состоящего из 0 и п-1, значение функции яв-

ляется 0 или n-1. Очевидно, что является примером

еще одного замкнутого класса. В силу сохранения множества {0, n-1} замкнутый класс не содержит, например, константу 1. Значит, при F не будет полной системой. На этом примере

видно, что хотя система и является обобщением системы

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

су функций, сохраняющих В силу этого n-значная логика

Лукасевича не является функционально полной при

(Дж. Мак-Кинси [McKinsey 1936] показывает, что функция Вебба не может быть определена в терминах за исключени­ем случая, когда п=2. Таким образом, здесь впервые опубликовано доказа­тельство того, что множество функций не является функционально полным ни для какого)

7.3.3. Критерий функциональной полноты. Предполнота

Сложной технической проблемой для n-значных логик является проблема распознавания полноты для произвольных систем. Выде­ляются два подхода к решению задачи о полноте, Первый подход основывается на теореме о существовании алгоритма, позволяюще­го для каждой конечной системы F выяснить, будет ли она полна или нет. Суть алгоритма сводится к построению строго возрастаю­щей цепочки множеств Rr, содержащих функции от двух перемен­ных. Начиная с некоторого множества Rr* процесс стабилизирует­ся, т. е. последующие множества не содержат новых функций (а всего функций от двух переменных Поскольку множество содержит все функции от двух переменных из класса [F], то систе­ма F полна тогда и только тогда, когда функция Вебба при­надлежит множеству (см. [Яблонский 1958; 1986]).

Большой интерес вызвал второй подход, который основывается на совокупности всех предполных классов функций в Рn. Система F функций называется предполной (максимальной) в Рп, если F представляет не полную систему, но добавление к F любой функ­ции f такой, чтопреобразует F в полную систему. Или, в терминах замыкания: F преддолна в Рn, если и где Важная роль предполных классов функций видна из следующей теоремы , которая формулирует критерий функциональной полноты: Для любого п