586

МНОГОЗНАЧНЫЕ ЛОГИКИ ции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2,..., п-1), называется n-значной функцией, или функцией n-значной логики. Имеются различные способы задания функций. Напр., функция f(x,..., xm) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m (из элементов 0, 1, 2,..., п — 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число п-ичных наборов длины m равно nm и на каждом из них значение функции можно задать п способами. Поэтому число всех функций n-значной логики Ри, зависящих от аргументов х,..., хт, составляет п"™ . Случай п > 2 оказывается существенно более сложным, чем классический случай Рт Уже в Р3 число функций от двух переменных равно 19 683, в то время как в Р2 таких функций всего 16. Как и в двузначном случае, в Рп выделяются функции, которые наиболее часто употребляются в логике и кибернетике и играют там важную роль. Такие функции называются элементарными. Вот некоторые из них: константы 0,1, 2,..., п—1 — (нульместные функции); отрицание Лукасевича: ~х=(п— 1)—х — обобщение отрицания в смысле «зеркального отрицания»; отрицание Поста: —ix = х + l(mod n) — обобщение отрицания в смысле «циклического сдвига значений»; характеристическая функция числа i, i = 0,1,..., n — 1: т ( ч _ f n — 1, если х = i, JiW~ 10,еслих*1. J.(x) — обобщение некоторых свойств отрицания; минимум х и у: х л у = min (x, у) — обобщение конъюнкции; максимум х и у: х V у = max (x, у) — обобщение дизъюнкции; сумма по модулю п:х ® у = х + у (mod n) — обобщение суммы по mod 2 (значение этой функции равно остатку от деления суммы х + у на п); импликация Лукасевича: х =/п- 1,еслих <у, \ (п — 1) — х + у, если х > у. х —> у — обобщение одного из свойств классической импликации; функция Вебба: Wn(x, у) = тах(х, у) + l(mod n) — обобщение штриха Шеффера на функционально полную логику Поста Рп. Операция дизъюнкции х V у и отрицание Поста -iX, определенные на множестве М, являются исходными операциями первой n-значной логикой (п>3), названной Рп, которая была построена Постом в 1921, притом с произвольным числом выделенных значений. В свою очередь, n-значная логика Лукасевича Ln была построена в 1922—23 как обобщение L3. Изучение Ln и Рп составило важнейший этап в развитии теории многозначных логик. Кроме двух рассмотренных способов задания функций (табличного и алгоритмического (в последнем случае x v у, к примеру, задается как тах(х, у)) не менее известным способом является формула, описывающая функцию как суперпозицию исходных элементарных функций. Функция, полученная из функций f,,..., fk подстановкой и/или переименованием аргументов, называется суперпозицией f,,..., fk. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой, и тогда говорят, что формула реализует или представляет данную функцию. В этом случае имеем дело с формульной моделью многозначной логики, а сама модель зачастую отождествляется с этой логикой. Основной проблемой здесьявляется проблема интерпретации истинностных значений. Для широкого класса многозначных логик эта проблема решена А. С. Карпенко (1983) в терминах классических истинностных значений. В кибернетике такие модели рассматриваются как управляющие системы. Элементарные функции при этом являются элементами, производящими определенные операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными для формульной модели являются: задача об указании всех формул, реализующих заданную константу; задача об эквивалентных преобразованиях; задача о сложности реализации; задача о минимизации и т. д. Однако в зависимости от того, какие цели преследуются при изучении многозначных логик, по-разному понимается, что собой представляет ее модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы, обозначаемой (Рп, С), где Рп есть множество всех функций n-значной логики (или множество всех функций счетнозначной логики PJ с заданной на нем операцией суперпозиции С, а сама функциональная система (Рп, С) зачастую отождествляется с многозначной логикой, т. е. (Рл, С) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмотренных выше алгебр истинностных значений, является алгеброй функций. Известна содержательная трактовка понятия функциональной системы ((РпУ С) выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Р, Q), в которых Р есть множество отображений, реализуемых управляющими системами из некоторого класса, a Q состоит из операции, используемой при построении новых управляющих систем из заданных. В нашем случае Q представляет собой операцию суперпозиции С. Труднейшей проблемой при изучении функциональных систем является следующая: какие функции могут быть сконструированы из данного множества функций. Проблема эта возникает и в самом пропозициональном исчислении, представленном формульной моделью, и в синтезе автоматов, и в универсальной алгебре; но именно здесь ей уделяется специальное внимание. Важнейшее свойство функциональной системы есть свойство функциональной полноты (напр., для того, чтобы можно было реализовать любую переключательную схему). Система функций 9t = {f,,—, fk,...} из Р называется функционально полной, если любая функция из Рп пред- ставима посредством суперпозиций функций из системы 9t. Т. о., указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество 9t функционально полным? Напр., логика Поста Рп, как и классическая двузначная логика, является функционально полной. Отсюда их исключительно широкое применение и развитие. С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть 9t c P • Множество всех функций, которые могут быть получены из функций системы 9t с помощью операции суперпозиции, называется замыканием 91 и обозначается [9t ]. Класс функций 9t называется (функционально) замкнутым, если [9t ] = 9t, т. е. замкнутость класса функций 9I обозначает собою сохранение при суперпозиции «наследственных» свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: 9t — полная система, если [ 9t ] = Р .

587

МНОЖЕСТВ ТЕОРИЯ Сложной технической проблемой для n-значных логик остается распознавание полноты для произвольных систем. Выделяются два подхода к решению задачи о полноте. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту системы функций; во втором рассматривают совокупность всех предполных классов функций в Ря. Система Э{ функций называется предполной в Р, если 9? представляет не полную систему но добавление к SR любой функции f такой, что f Е Ря и f e 9( преобразует Э( в полную систему. Или, в терминах замыкания: SR предполна в Ря, если [ SR]9t/>nH[SRu{f}] = P,raefG Pnfe SR. Важная роль предполных классов функций видна из следующей теоремы, которая формулирует критерий функциональной полноты: система функций SR n-значной логики полна тогда и только тогда, когда она не содержится целиком ни в одном предполном классе. Г. Розенбергом в 1970 было дано описание всех предполных классов в n-значной логике, и хотя число предполных классов я(п) конечно для любого п, однако очень быстрый их рост указывает на малую практическую эффективность предполных классов для решения проблемы полноты. Удивительную связь свойства функциональной предполноты с теорией простых чисел имеет логика Лукасевича Ln. Как было установлено В. К. Финном в 1970, n — 1 является простым числом тогда и только тогда, когда Ln предполно в Ря. Т. о., мы имеем новое определение простого числа. Более того, оказалось возможным построить такие Ln, которые имеют класс общезначимых формул тогда и только тогда, когда n — 1 есть простое число. Последние результаты привели А. С. Карпенко к открытию закона порождения классов простых чисел, притом порождаются все простые числа. К проблеме полноты примыкает задача о базисах, состоящая в указании всех полных в замкнутом классе SR c P подмножеств, никакое собственное подмножество которых уже не полно в 9R, т. е. базисом является минимальная полная независимая система функций, удаление из которой любой функции делает систему неполной. Особую роль играют базисы, состоящие из одной функции, т. е. штрихи Шеффера. Однако наиболее сложной, можно сказать, глобальной задачей для многозначной логики остается описание решетки замкнутых классов данной модели многозначной логики. Для двузначной логики эта задача полностью решена Э. Постом в начале 20-х гг., где установлено, что мощность множества замкнутых классов в Р2 счетна. Позже им дано полное описание решетки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Однакос многозначной логикой дело обстоит совсем по-другому. Оказалось, что имеются существенные различия между классической двузначной логикой и многозначной, говорящие о принципиальной несводимости второй к первой. В отличие от /ущя всякого n > 3 существует в Ря замкнутый класс, не имеющий базиса, а такте для всякого n > 3 существует в Рв замкнутый класс со счетным базисом. Непосредственно к этому примыкает следующий результат: для всякого n > 3 Ря содержит континуум различных замкнутых классов, т. е. уже Р3 содержит континуум различных замкнутых классов. Вообще говоря, точная природа такого различия между двузначной и трехзначной логиками неясна. Особый интерес в силу их различных приложений представляют собой бесконечнозначные логики. Исторически первой такой логикой была бесконечнозначная логика Лукасевича Lw (1929), которая определяется следующей матрицей: М = <[0,1];^,~,{1}>,где х —> у = min(l, 1 — х + у), ~х = 1 — х. Почти через тридцать лет L была аксиоматизирована следующим образом: аксиома Йайсберга (4) заменяется аксиомой ((р —> q) —> q)) —> ((q —> p) —> p). Последние десятилетия алгебраические исследования Ьш приобрели исключительный масштаб и можно говорить о новом направлении в алгебраической логике. Другим интересным и весьма важным примером бесконечнозначной логики является интуиционистская логика Н. Еще К, Педель в 1932 показал, что никакая конеч- нозначная матрица не может быть для нее характеристической. В заключение заметим, что ни одно из направлений некласси- ческихлогиктж бурно не развивается, как многозначная логика. Это объясняется всевозможными приложениями и применениями многозначных логик в различных областях науки и техники и особенно в компьютерных науках. Поэтому вопрос о библиографии по многозначной логике заслуживает специального рассмотрения. Литература здесь совершенно необозрима и, по-видимому, имеет тенденцию к экспоненциальному росту. Тем не менее имеется хронологическая, а также хорошо тематизированная библиография в монографии Н. Решера (1969). Р. Вольф (1977) дополнил и довел ее до 1974 с указанием некоторых работ, которые должны были выйти в ближайшем времени. Обширная библиография, включая работы последних лет, содержится в монографии А. С. Карпенко (1997). Важнейшим и основным источником современной литературы по многозначной логике, и в особенности их применению к компьютерным наукам, служат материалы ежегодного международного симпозиума по многозначным логикам (International Symposium on Multiple-\folued Logic), которые проводятся начиная с 1971. В материалах 22-го симпозиума дается обзор и анализ работы первых 21 симпозиумов и приводятся различные статистические данные. Разработана также база данных статей, авторов и тем. Лет.: БочварДА., Финн В. К. О многозначных логиках, допускающих формализацию анализа антиномий, 1.— В кн.: Исследования по математической лингвистике, математической логике и информационным языкам. М., 1972; Они оке. Некоторые дополнения к статьям о многозначных логиках.— В кн.: Исследования по теории множеств и неклассическим логикам. М., 1976; Зиновьев А. А. Философские проблемы многозначной логики. М., 1960; Карпенко А. С. Многозначные логики (монография), в серии «Логика и компьютер», вып. 4. М., 1997; Он оке. Логики Лукасевича и простые числа. М., 2000; Кудрявцев В. Б. О функциональных системах. М., 1981; Он оке. Многозначная логика.— В кн.: Математическая энциклопедия, т. 3. М., 1982; Яблонский С. В. Функциональные построения в k-значной логике.— В кн.: Труды математического института им. В. А. Стеклова, т. 51, 1958; Bok L, Borowik P. Many-valued logics: Theoretical foundations, v. 1. В., 1992; Butler S. W., Butler J. T. Profiles of topics and authors of the International Symposium on Multiple-Wued Logic for 1971 - 1991.- ISMVL, 22th, Sendai., 1992; Computer science and multiple-valued logic: Theory and applications. Amst., 1977 (2nd revised ed. 1984); Epstein G. Multiple-valued logic design: an introduction. Bristol, 1993; KarpenkoA. S. Factor-semantics for n-valued logics.— «Studia Logica», 1983, v. 42, N 2/3; Mahnowski G. Many-valued logics. Oxf., 1993; RescherN. Many-valued logic. N. Y, 1969; Rosser J. A, Turquette A. R. Many-valued logics. Amst., 1952 (2nd ed. 1958); WofR. G. A survey of many-valued logics (1966—1974), in: Modern uses of multiple-valued ю-