С.В. Яблонский - Введение в дискретную математику, страница 7

Теорема 7 (о функциональной полноте). !()!ля того чтобы система функций $ была полной, необходимо и достаточно, чтобы она целиком не содерзсалась ни в одном иг пяти замкнутых классов Т„То Я, М и Ь. Доказательство. Необходимость. Пусть $ полна, т. е. Я Р,. Допустим, что $ содержится в одном из указанных классов — обозначим его через в(, т.

е. Фыр. Тогда в силу свойств замыкания и замкнутости Я имеем Рг Я вЂ” (111 11. Значит в( ° Р„что не так. Необходимость доказана. Достаточность. Пусть $ целиком не содержится ни в одном из пяти указанных классов. Тогда из $ можно выделить подсистему $', содержащую нв более пяти функций, которая также обладает этим свойством. Для этого возьмем в чг функции ?„?„~ь ~, ?ь которые не принадлежат соответственно классам Т„Т„Я, М и Ь, и положим Ф'-(А Ь 1 у! 1-). Можно считать, что все эти функции аавцсят от одних и твх же переменных х„..., х„(см.

замечание нз з 1). Доказательство достаточности будем проводить в три зтапа. 1. Построение при помощи функций ~ч ~, и ~, констант О и 1. Рассмотрим функцию ?, Ф Т,. Возможны два случая: 1. Д(1, ..., 1) 1. Тогда ф(х)=1,(х, . „х) есть константа 1, ибо ф(О)-Л(О, ". О)-1, ф(1)-И1, ",1)-1. Вторая константа получается нз ?,: ?,(1, ..., 1)= О. 2. 1<(1, ..., 1)-0.

Тогда ф(х)=?Д(х, ..., х) есть х, ибо ф(О)- 1!(О, ..., О) = 1, ф(1) = 1!(1, ..., 1) = О. Возьмем ~, (?, Ф Я). Так как мы имеем х, то в силу леммы 1 из ?„ мы можем получить константу. Поскольку ГЛ. Ь АЛГЕБРА ЛОГИКИ мы располатаем х, то находим и вторую константу.

Итак, в обоих случаях мы получаем константы О и 1. 11. Построение при помощи констант О, 1 и функции 1„функции У. Это осуществляется на основе леммы 2. 1П. Построение при помощи констант О, 1 и функций х и 1, функции х,й х,. Это осуществляется на основе леммы 3. Таким образом, мы при помощи формул над 9' (а значит и над з1) реализовали функции х и х, йхь Этим достаточность доказана. Следствие 1. Всякий замкнутый класс йй функций из Р, такой, что ИчьР„содержится по крайней мере е одном из построенных классов. Определение. Класс И функций из Р, называется предполным (нли максимальным), если У1 неполный, а для любой функции 1(1ырм )Фй) класс %0(1)— полный. Из определения следует, что предполный класс является замкнутым. Следствие 2.

В алэебре лоеики существует только пять предполных классов, а именно: Т„Т„Я, М и Ь. Рассмотрим пример, иллюстрирующий возможности теоремы о функциональной полноте. Пример 15. Покажем, что система функций )~ хх ( О (1 1 и ~~ х~+хв+хэ является полной. Мы имеем: (, Ф Т„(,Ф Т„), ФЯ, /,ФМ, (,Ф Б. С другой стороны, удаление любой из функций приводит к неполной системе: ((и 1„1,) Ь, (1„)„),) Т„ ((о(м/.) =Т„9„(.,Я-М. Из доказательства теоремы 7 непосредственно вытекает следующая теорема.

Теорема 8. Яэ всякой полной е Р, системы $ функций можно выделить полную подсистему, содержащую не более четырех функций. Доказательство. Мы видели, что из 9 можно выделить полную подсистему $', содержащую не более пяти функций. Оказывается, что функция ), Ф Т„кроме ч. ь фтнкцпонлльнык спствмы с опкглцпямн того, либо не самодеойственна (случай 1), так как )~(0, ..., 0)= );(1, ..., 1), либо не сохраняет 1 и не монотонна (случай 2): ),(О, ..., 0)) 7,(1, ..., 1). Поэтому полной будет либо система (гь )е ), ),), либо система ()ь )ь М Пример 15 показывает, что константа 4 не может быть понпжена.

Теорема о функциональной полноте на самом деле дает не только критерий полноты. Она позволяет (в сочетании с разложением в д. н. ф. или к. н. Ф.) найти для произвольной булевой функции г' формулу через Функции полной системы 3. $7. Представление о ревультатах Поста Весьма глубокое изучение замкнутых классов в Р, было осуществлено американским математиком Э. Постом.

Им была описана структура всех замкнутых классов в Р,. Сформулируем некоторые ие важнейших результатов, связанных с этим исследованием. Определение. Система функций (7„)о ..., 1„.. ) из замкнутого класса йй называется волной в й, если ее замыкание совпадает с И. Иначе говоря, система полна в йй, если каждая функция ие йй может быть выражена в виде формулы через функции данной системы. Определение. Система Функций (1о 1м. °,7., ) из замкнутого класса й называется его базисом, если она полна в йч, но всякая ее собственная подсистема не является полной в й. Так, система Л-хх, Л-О, 1в-1, Л-х,+х,+х, является базисом в Р,.

Можно показать, что система функций (О, 1, х, дс х„ х,'ч'х,) является базисом для класса М. Теорема 9 (Пост [471). Каждый замкнутый класс из Р, имеет конечный базис. Т е о р е м а 10 (Пост 147]). Мощность множества замкнутых классов в Р, — счетная. Хотя вторая иа этих теорем логически следует из первой, тем не менее в доказательстве Поста сначала устанавливается второй факт, а затем — первый. ГЛ. 2.

А.ЗНАЧНАЯ ЛОГИКА Глава 2 й-ЗНАЧНАЯ ЛОГИКА Конечнозначные логики вводятся как обобщение двузначной логики, В силу этого наше изложение местами будет кратким, а некоторые аналогичные определения и доказательства будут опущены. Особое внимание обратны на два обстоятельства: 1) в й-значпых логиках сохраняются многие свойства и результаты, которые имели место в двузначной логике; 2) в й-значных логиках наблюдаются явления, обнаруживающие принципиальное их отличие от алгебры логики. В связи с этим некоторые задачи не имеют такого исчерпывающего решения как в алгебре логики, а другие вовсе не решены.

$1. Функции й-вначной логики. Формулы и реализация функций формулами Пусть У=(и„и„..., и, ...) — исходный алфавит переменных (аргументов). Будем рассматривать функции ~ (ий, ..., и~„) (им Ф и;„при т чь р), аргументы которых определены на множестве Е, (О, 1, ..., й — 1), и такие, что ~(ао ..., 22.)жЕн когда а~жЕ, ($ 1,2,...,л). Для упрощения записи мы будем использовать для переменных из У метаобозначения х, р, з, ..., а также л„р„зе ... и употреблять для функций более простую запись Дх„..., х.). Очевидно, что функция Дхо ..., х„) полностью определена, если задана ее таблица (см.

табл. 1). В этой таблице наборы суть разложения в й-ичной системе счисления чисел О, 1, ..., й" — 1. Символ ~ здесь будет интерпретироваться как символ, обозначающий отображение, характеризуемое таблицей, а символы ло л2, ... ..., х„— как названия столбцов. Для функций одной переменной мы наряду с таблицами будем использовать запись в виде (обобщенной) подстановки 0 1...Й вЂ” 1 где 8(и) = 1,. 44 ч, ь егнкциональнык систвыы с опкгациями Обозначим через Р„множество всех функций й-значной логики над алфавитом У, а также констант О, 1, ... ..., й — 1. Так как число наборов (а„ ..., а„) значений переменных х„..., х„равно Й", то имеем следующий результат. таблица к«~ " ° «»-««») «4" «» — 1 «» 0 ...

0 0 0 ... 0 г'(О, ..., О, 0) ((О, ...,О, 1) 0 ... 0 а — 1 0 ... 1 0 ((а 1, ...,а — 1, «-1) Теорем а 1. Число всех амуниций ив Рм зависли)их от и переменных х„..., х„, ровно й"" Из сказанного вытекает, что в Р, при й > 3 в значительной степени возрастают трудности по сравнению с Р, как в возможности эффективного использования табличного аадания функций, так и в воэможности просмотра всех функций от и переменпых. Уже в Р, число функций от двух переменных равно 3' 19683, т.

е. это множество практически необозримо. В Р„часто употребляют вместо табличного аадания функций аадание при помощи алгоритма вычислимости функций. Например, щах(хи ..., х ) можно рассматривать, как алгоритм, который для любого набора (а„..., а„) аначений переменных выдает их максимум. Этот алгоритм определяет в Р„единственную функцию, которую мы будем обозначать тем же символом. Далее вводится (как в Р,) понятие существенной в несущественной переменных, а также понятие равенства функций. Это позволяет рассматривать функции в Р, с точностью до фиктивных переменных. После этого рассматриваются примеры некоторых конкретных функций из Р„, которые можно считать «элементарными» функциями.

ГЛ. 2. А-ЗНАЧНАЯ ЛОГИКА 1) И х+ 1(шобх). Здесь И представляет обобще- ние отрицания в смысле «циклического» сдвига значений. 2) 1«х й — 1 — х. Здесь Жх или, как часто обозна- чают, -х ивляется другим обобщением отрицания в смысле «зеркальнего» отображения значений. В литера- туре оно носит название отрицания Лукаш«вича.

1й — 1 при х= 2, 3) 1, (х) . («=О,...,й — 1). О при хФ1 Функции А(х) при «'чей — 1 являются обобщениями не- которых свойств отрицания. (1прих 1, 4) $0 при хчь(. Функция 1<(х) — характеристическая функция значения $ и при 1'Р*й — 1 представляет собой обобщение отри- цания. 5) ш1п(х„х,) — обобщение конъюнкции. б) х,х,(шо«1 й) — второе обобщение конъюнкции.

7) шах(хо х«) — обобщение дизъюнкции. 8) х, +х«(шобй). Из рассмотрения этого списка элементарных функций видно, что функции алгебры логики имеют в й-значной логике (й > 3) по нескольку аналогов, каждый из кото- рых обобщает соответствующее свойство функции. Затем, так же как и в алгебре логики, вводится по- нятие формулы над множеством функций 6. Формулы мы обозначаем символами И, 6,... без индексов и с ин- дексами. Если мы хотим указать зависимость формулы от переменных или выделить функции, из которых по- строена формула, то употребляем обозначения И(х„..., х„), И(/о ..., Я Каждой формуле И(х„..., х„) сопоставляется функция 7(х„..., х„) из Р«, при этом говорят также, что форму- ла И реализует функцию 1. Аналогичный смысл здесь имеют суперпозиция функций из $ и операция суперпо- зиции.

Далее вводится понятие эквивалентности формул И и 6: И 6, если соответствующие им функции 1н и 1н равны. Опираясь на понятие эквивалентности, можно описать основные свойства элементарных функций. Укажем не- которые из них. Пусть (х, ° х,) обозначает любую пз функций ш«п(хо х,), х,х«(шобй), шак(х„х,), х,+ + х, (шой Й). 45 ч. ь Функциональные сиСтемы с спиваниями 4. Функция (х, ° х,) обладает свойством ассоциативности: ((Х,'Хз)'тз)=(Хз (Хз'Хз)) 2.

Функция (х, ° х,) обладает свойством коммутатив ности: (х, ° хз) (хз ° х,). Далее мы иногда будем обозначать функции ш!в(х„хз) и шах(хз, хз) соответственно через (хззкхз) и (х, Чх,). В силу свойства ассоциативности и соглашения о том, что операция Й выполняется раньше операции Ч (см. замечания 1-3 $3 гл. $), можно употреблять для записи формул выражения, получающиеся иа формул путем опу- скания некоторых скобок.