Новая философская энциклопедия. Том второй Е—М

МНОЖЕСТВ ТЕОРИЯ Сложной технической проблемой для 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 ю-