Akademik

    МНОГОЗНАЧНЫЕ ЛОГИКИ — обобщение классической двузначной логики (см. Логика высказываний) к примеру, посредством которого к обычным истинностным значениям “истина” и “ложь” добавляются и другие (промежуточные) значения. Этот факт указывает на то, что принцип двузначности (“каждое высказывание или истинно, или ложно”) отбрасывается, хотя построение многозначной логики осуществляется по аналогии с классической двузначной логикой (С,). Именно на этом пути была впервые построена в 1920 Я. Лукасевичем трехзначная логика (Ьд) с целью опровержения логического фатализма.

    В этой логике явным образом указывается число истинностных значений, в данном случае 1(истина), У; (случайность) и 0 (ложь). Выделенным истинностным значением, как и в С,, является 1. Исходными логическими связками у Лукасевича являются -> (импликация) и МНОГОЗНАЧНЫЕ ЛОГИКИ (отрицание). Как и в случае с С-, дается их табличное определение:

    Посредством исходных связок определяются v (дизъюнкция), л (конъюнкция) и = (эквивалеиция): pvq=(p-^q)-”q, pAq=МНОГОЗНАЧНЫЕ ЛОГИКИ(-pvМНОГОЗНАЧНЫЕ ЛОГИКИq), p=q=(p-”q)A(q-”p).

    Значения p у q и p л q, как и в Су есть max и min соответственно от значений p и q. Формула А является общезначимой (законом логическим), если при любом приписывании значений из множества {1, '/^, 0} переменным, входящим в А, формула А принимает значение 1.

    Логика î-3 оказалась весьма необычной, напр. в ней не имеют места следующие законы Су

    p vМНОГОЗНАЧНЫЕ ЛОГИКИ p — исключенного третьего закон, МНОГОЗНАЧНЫЕ ЛОГИКИ(р л- p) — непротиворечия закон, (р -> (р —> q)) —> (р —> q) — закон сокращения.

    С другой стороны, выразительные средства L^ богаче Сд, поскольку в ней уже можно выразить своеообразные модальные операторы Ор (возможно, что р) и Dp (необходимо, что р): Ор = -р -> р и пр = -О-р, что и было сделано А. Тарским в 1921 г. Понятно, что множество связок {-, л, v} недостаточно для определения —>. С другой стороны, добавление к {-, л, v} одного из модальных операторов позволяет определить ->. В 1931 1.3 была аксиоматизирована учеником Лукасевича М. Вайсбергом: 1. (р -> q) -> ((q -> г) -> (р -” г))

    2.p-^(q->p)

    3.(-p->-q)->(q->p)

    4.((р-”-р)-”р)->р.

    Правила вывода: modus ponens и подстановка. В общей теории многозначных логик основным способом задания является матричный. Система Af= называется логической матрицей, где М — множество истинностных значений; D э М есть множество выделенных значений; v, л, э — двуместные, a -i — одноместная операции на М. Поскольку алгебра Л = М; ν, л, э, -ι> является однотипной с алгеброй формул пропозиционального языка L, то обычным образом определяется функция оценки ν (гомоморфизм) формул языка L в матрице М. Формула А называется общезначимой в М, если при всех значениях переменных в множестве М значение А принадлежит D. Логическая матрица называется характеристической для исчисления высказываний L, если общезначимы те и только те формулы, которые выводимы в L. Множество всех общезначимых формул называется матричной многозначной логикой. Здесь возникают две проблемы: 1) нахождение минимальной характеристической матрицы для L; 2) нахождение конечной аксиоматизации (если это возможно) по каждой конечной матрице М. Примерами минимальных характеристических матриц могут служить матрицы для классической двузначной логики С^ и трехзначной логики Лукасевича ?-з. Приведем примеры других п-значных логик (п Эг 3).

    При изучении многозначных логик понятие функции является основным и наряду с булевыми функциями (функциями двузначной логики) используется для описания дискретных устройств, компоненты которых могут находиться в некотором числе различных состояний. Произвольная функция f(xi, ..., Хщ) от любого конечного числа переменных, областью определения которых и областью значения самой функции является множество M (без ограничения общности можно считать, чтоего элементами являются 0,1,2,..., п-1), называется п-значной функцией, или функцией п-значной логики. Имеются различные способы задания функций. Напр., функция f(X),..., Xm) может быть задана таблицей, где в некотором порядке перечислены все п-ичные наборы длины m (из элементов 0, 1, 2,..., η — 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число п-ичных наборов длины m равно η"' и на каждом из них значение функции можно задать η способами. Поэтому число всех функций п-значной логики Р„, зависящих от аргументов X],..., Хт, составляет п"". Случай η > 2 оказывается существенно более сложным, чем классический случай Р^. Уже в Ρ} число функций от двух переменных равно 19 683, в то время как в Р^ таких функций всего 16.

    Как и в двузначном случае, в Ρ выделяются функции, которые наиболее часто употребляются в логике и кибернетике и играют там важную роль. Такие функции называются элементарными. Вот некоторые из них: константы 0,1,2,..., η — 1 — (нульместные функции); отрицание Лукасевича: МНОГОЗНАЧНЫЕ ЛОГИКИх=(п—1)—х— обобщение отрицания в смысле “зеркального отрицания”; отрицание Поста: -тх = χ + l(mod n) — обобщение отрицания в смысле “циклического сдвига значений”; характеристическая функция числа i, i = 0,1,..., n — 1: n— l, если χ = i, О, если х 1- i.

    J(x); J (χ) — обобщение некоторых свойств отрицания; минимум х и у: х л у = ηυη(χ, у) — обобщение конъюнкции; максимум х и у: χ ν у = тах(х, у) — обобщение дизъюнкции; сумма по модулю n:x©y=x+y (mod η) — обобщение суммы по mod 2 (значение этой функции равно остатку от деления суммы х + у на п); импликация Лукасевича: п—1,еслиху, (п — 1) — х + у, если х > у.

    x->y=

    х -> у — обобщение одного из свойств классической импликации; функция Вебба: W (х, у) = тах(х, у) + l(mod n) — обобщение штриха Шеффера на функционально полную логику Поста Р^.

    Операция дизъюнкции χ ν у и отрицание Поста -к, определенные на множестве М, являются исходными операциями первой п-значной логикой (п > 3), названной Рп, которая была построена Постом в 1921, притом с произвольным числом выделенных значений. В свою очередь, п-значная логика Лукасевича L,, была построена в 1922—23 как обобщение Ьз. Изучение Lu и Рп составило важнейший этап в развитии теории многозначных логик.

    Кроме двух рассмотренных способов задания функций (табличного и алгоритмического (в последнем случае χ ν у, к примеру, задается как тах(х, у)) не менее известным способом является формула, описывающая функцию как суперпозицию исходных элементарных функций. Функция, полученная из функций fp—if., подстановкой и/или переименованием аргументов, называется суперпозицией f.,..., f.. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой, и тогда говорят, что формула реализует или представляет данную функцию. В этом случае имеем дело с формульной моделью многозначной логики, а сама модель зачастую отождествляется с этой логикой. Основной проблемой здесь является проблема интерпретации истинностных значений. Для широкого класса многозначных логик эта проблема решена А. С. Карпенко (1983) в терминах классических истинностных значений.

    В кибернетике такие модели рассматриваются как управляющие системы. Элементарные функции при этом являются элементами, производящими определенные операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными для формульной модели являются: задача об указании всех формул, реализующих заданную константу; задача об эквивалентных преобразованиях; задача о сложности реализации; задача о минимизации и т. д. Однако в зависимости от того, какие цели преследуются при изучении многозначных логик, по-разному понимается, что собой представляет ее модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы, обозначаемой (Рп, С), где Рп есть множество всех функций п-значной логики (или множество всех функций счетнозначной логики Pyj с заданной на нем операцией суперпозиции С, а сама функциональная система {Р„, С) зачастую отождествляется с многозначной логикой, т. е. (Рп, С) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмотренных выше алгебр истинностных значений, является алгеброй функций.

    Известна содержательная трактовка понятия функциональной системы ((Рп, С) выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Ρ, Ω), в которых P есть множество отображений, реализуемых управляющими системами из некоторого класса, a Ω состоит из операции, используемой при построении новых управляющих систем из заданных. В нашем случае Ω представляет собой операцию суперпозиции С.

    Труднейшей проблемой при изучении функциональных систем является следующая: какие функции могут быть сконструированы изданного множества функций. Проблема эта возникает и в самом пропозициональном исчислении, представленном формульной моделью, и в синтезе автоматов, и в универсальной алгебре; но именно здесь ей уделяется специальное внимание. Важнейшее свойство функциональной системы есть свойство функциональной полноты (напр., для того, чтобы можно было реализовать любую переключательную схему). Система функций 9i= {fi,...,fk,...} из Р„ называется функционально полной, если любая функция из Р„ представима посредством суперпозиций функций из системы Я. Т. о., указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество 9Î функционально полным? Напр., логика Поста Рд, как и классическая двузначная логика, является функционально полной. Отсюда их исключительно широкое применение и развитие.

    С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть 9О е Р„. Множество всех функций, которые могут быть получены из функций системы 9I с помощью операции суперпозиции, называется замыканием 9I и обозначается [9I]. Класс функций 9I называется (функционально) замкнутым, если [9I] = 9О, т. е. замкнутость класса функций 9I обозначает собою сохранение при суперпозиции “наследственных” свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: 9I — полная система, если [9I] = Рд.

    Сложной технической проблемой для п-значных логик остается распознавание полноты для произвольных систем. Выделяются два подхода к решению задачи о полноте. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту системы функций; во втором рассматривают совокупность всех предполных классов функций в РП. Система 9Î функций называется предполной в Р„, если 9Î представляет не полную систему, но добавление к % любой функции f такой, что feP„Hfe9î преобразует 3Î в полную систему. Или, в терминах замыкания: 9Î предполна в Р„, если 9Î] * Р„ и [9î u{f}] = Р„, где fe Рп и Кг ЭД. Важная роль предполных классов функций видна из следующей теоремы, которая формулирует критерий функциональной полноты: система функций ЭД п-значной логики полна тогда и только тогда, когда она не содержится целиком ни в одном предполном классе. Г. Розенбергом в 1970 было дано описание всех предполных классов в п-значной логике, и хотя число предполных классов π(η) конечно для любого п, однако очень быстрый их рост указывает на малую практическую эффективность предполных классов для решения проблемы полноты.

    Удивительную связь свойств функциональной предполноты с теорией простых чисел имет логика Лукасевича Ln. Как было установлено В. К. Финном в 1970, η—1 является простым числом тогда и только тогда, когда Ln предполно в ?„• Т. о., мы имеем новое определение простого числа. Более того, оказалось возможным построить такие Ln, которые имеют класс общезначимых формул тогда и только тогда, когда η — 1 есть простое число. Последние результаты привели А. С. Карпенко к открытию закона порождения классов простых чисел, притом порождаются все простые числа.

    К проблеме полноты примыкает задача о базисах, состоящая в указании всех полных в замкнутом классе 9Î с Р„ подмножеств, никакое собственное подмножество которых уже не полно в %, т. е. базисом является минимальная полная независимая система функций, удаление из которой любой функции делает систему неполной. Особую роль играют базисы, состоящие из одной функции, т. е. штрихи Шеффера.

    Однако наиболее сложной, можно сказать, глобальной задачей для многозначной логики остается описание решетки замкнутых классов данной модели многозначной логики. Для двузначной логики эта задача полностью решена Э. Постом в начале 20-х гг., где установлено, что мощность множества замкнутых классов в Р^ счетна. Позже им дано полное описание решетки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста.

    Однако с многозначной логикой дело обстоит совсем по-другому. Оказалось, что имеются существенные различия между классической двузначной логикой и многозначной, говорящие о принципиальной несводимости второй к первой. В отличие от РгДля всякого η > 3 существует в Р„ замкнутый класс, не имеющий базиса, а также для всякого η > 3 существует в Р„ замкнутый класс со счетным базисом. Непосредственно к этому примыкает следующий результат: для всякого η > 3 Рд содержит континуум различных замкнутых классов, т. е. уже РЗ содержит континуум различных замкнутых классов. Вообще говоря, точная природа такого различия между двузначной и трехзначной логиками неясна.

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

    M =[0,1];->, -,{!}>, где χ —> у = min(l, 1 — χ + у), МНОГОЗНАЧНЫЕ ЛОГИКИх = 1 — χ.

    Почти через тридцать лет L„ была аксиоматизирована следующим образом: аксиома Вайсберга (4) заменяется аксиомой ((р —> q) —> q)) -” ((q —> ρ) —> ρ). Последние десятилетия алгебраические исследования L„ приобрели исключительный масштаб и можно говорить о новом направлении в алгебраической логике. Другим интересным и весьма важным примером бесконечнозначной логики является интуиционистская логика Н. Еще К. Гёдель в 1932 показал, что никакая конечнозначная матрица не может быть для нее характеристической.

    В заключение заметим, что ни одно из направлений неклассических логик так бурно не развивается, как многозначная логика. Это объясняется всевозможными приложениями и применениями многозначных логик в различных областях науки и техники и особенно в компьютерных науках. Поэтому вопрос о библиографии по многозначной логике заслуживает специального рассмотрения. Литература здесь совершенно необозрима и, по-видимому, имеет тенденцию к экспоненциальному росту. Тем не менее имеется хронологическая, а также хорошо тематизированная библиография в монографии Н. Решера (1969). Е Вольф (1977) дополнил и довел ее до 1974 с указанием некоторых работ, которые должны были выйти в ближайшем времени. Обширная библиография, включая работы последних лет, содержится в монографии А. С. Карпенко (1997).

    Важнейшим и основным источником современной литературы по многозначной логике, и в особенности их применению к компьютерным наукам, служат материалы ежегодного международного симпозиума по многозначным логикам (International Symposium on Multiple-Valued Logic), которые проводятся начиная с 1971. В материалах 22-го симпозиума дается обзор и анализ работы первых 21 симпозиумов и приводятся различные статистические данные. Разработана также база данных статей, авторов и тем.

    Лит.: БочварД. А., Финн В. К. О многозначных логиках, допускающих формализацию анализа антиномий, 1.— В кн.: Исследования по математической лингвистике, математической логике и информационным языкам. М., 1972; Они же. Некоторые дополнения к статьям о многозначных логиках.— В кн.: Исследования по теории множеств и неклассическим логикам. М., 1976; Зиновьев А. А. Философские проблемы многозначной логики. М., 1960; Карпенко А. С. Многозначные логики (монография), в серии “Логика и компьютер”, вып. 4. М., 1997; Он же. Логики Лукасевича и простые числа. М., 2000; Кудрявцев В. Б. О функциональных системах. М., 1981; Он же. Многозначная логика.— В кн.: Математическая энциклопедия, т. 3. М., 1982; Яблонский С. В. Функциональные построения в к-значной логике.— В кн.: Труды математического института им. В. А. Стеклова, т. 51, 1958; Bole L., Borowik P. Many-valued logics: Theoretical foundations, v. 1. В., 1992; Butler S. W., Butler J. T. Profiles of topics and authors f the International Symposium on Multiple-Valued Logic for 1971—1991.- ISMVL, 22th, Sendai., 1992; Computer science and multiple-valued logic: Theory and applications. Amst., 1977 (2nd revised ed. 1984); EpsteinG. Multiple-valued logic design: an introduction. Bristol, 1993; Karpenko A. S. Factor-semantics for n-valued logics.— “Studia Logica”, 1983, v. 42, N2/3; Malinomki G. Many-valued logics. Oxf., 1993; Rescher N. Many-valued logic. N.Y, 1969; Rosser J. В., TurquetteA. R. Many-valued logics. Amst., 1952 (2nd ed. 1958); Wolf R. G. A survey of many-valued logics (1966—1974), in: Modem uses of multiple-valued logic. Dordrecht., 1977.

    А. С. Карпенко