Гуманитарные технологии Аналитический портал • ISSN 2310-1792

Логики многозначные

Наиме­нова­ние: Логики многозначные
Опреде­ление: Многозначная логика — это совокупность логических систем, опирающихся на принцип многозначности, в соответствии с которым всякое высказывание имеет одно (и только одно) из трёх или более истинностных значений.
Текст статьи: Авторы: А. С. Карпенко. Подготовка элект­ронной публи­кации и общая редакция: Центр гумани­тарных техно­логий. Инфор­мация на этой стра­нице периоди­чески обнов­ляется. Послед­няя редакция: 08.10.2017.

Многозначная логика — это совокупность логических систем, опирающихся на принцип многозначности (см. Принцип многозначности), в соответствии с которым всякое высказывание имеет одно (и только одно) из трёх или более истинностных значений. Принцип многозначности, который лежит в основе многозначной логики, противопоставляется принципу двузначности, лежащему в основе классической [двузначной] логики (см. Логика), согласно которой всякое высказывание является либо истинным, либо ложным, то есть принимает одно из двух возможных истинностных значений — «истинно» и «ложно». Принцип многозначности утверждает, что высказывание имеет одно из n-значений истинности (например: «неопределённо», «возможно», «бессмысленно» и так далее), где и больше двух и может быть как конечным, так и бесконечным. В зависимости от множества истинностных значений различают конечнозначные и бесконечнозначные логики. Несмотря на это то, что принцип двузначности отбрасывается, построение многозначной логики осуществляется по аналогии с классической двузначной логикой (C2 — см. Логика высказываний). Следует отметить, что ни двузначность, ни многозначность не являются прирождёнными свойствами человеческого мышления. Решение одних проблем может быть получено в рамках двузначной логики, рассуждение о других может оказаться более успешным, если опирается на тот или иной вариант многозначной логики.

Первыми логическими системами, опирающимися на принцип многозначности, были трёхзначная логика Ł3 Я. Лукасевича (1920) и n-значная логика Э. Поста (1921), в которой высказываниям приписывались значения из конечного множества натуральных чисел 1, 2, … n, где n больше единицы и конечно.

Лукасевичем была построена трёхзначная логика с целью опровержения логического фатализма (см. Логический фатализм). В этой логике явным образом указывается число истинностных значений, в данном случае 1 (истина),½ (случайность) и 0 (ложь). Выделенным истинностным значением, как и в C2, является 1.

Исходными логическими связками у Лукасевича являются → (импликация) и ~ (отрицание). Как и в случае с C2, даётся их табличное определение:

1 ½ 0 ~ ~ р
*1 1 ½ 0 1 0
½ 1 1 ½ ½ ½
0 1 1 0 0 1

Посредством исходных связок определяются ν (дизъюнкция), ∧ (конъюнкция) и ≡ (эквиваленция):

  • p ∨ q = (p → q) → q
  • p ∧ q = ~ (~ p → ~ q)
  • p ≡ q = (p → q) ∧ (q → p)

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

Логика Ł3 оказалась весьма необычной, например в ней не имеют места следующие законы C2:

  • p ∨ ~ p — закон исключённого третьего
  • ~ (p ∧ ~ p) — закон непротиворечия
  • (p → (p → q)) → (p → q) — закон сокращения

С другой стороны, выразительные средства Ł3 богаче C2, поскольку в ней уже можно выразить своеобразные модальные операторы ◊p (возможно, что p) и ⎕p (необходимо, что p):

    p = ~ p → p и ⎕p = ~ ◊ ~ p

что и было сделано А. Тарским в 1921 году.

Понятно, что множество связок {~, ∧, ∨} недостаточно для определения →. С другой стороны, добавление к {~, ∧, ∨} одного из модальных операторов позволяет определить →.

В 1931 году Ł3 была аксиоматизирована учеником Лукасевича М. Вайсбергом:

  1. (p → q) → (q → r) → (p → r)
  2. p → (q → p)
  3. (~ p → ~ q) → (q → p)
  4. (p → ~ p) → p) → p

Правила вывода: modus ponens и подстановка.

В общей теории многозначных логик основным способом задания является матричный. Система 〈M = MD, ∨, ∧, ⊃, ¬〉 называется логической матрицей, где M — множество истинностных значений; D ⊃ M есть множество выделенных значений; ∨, ∧, ⊃ — это двуместные, а ¬ — это одноместные операции на M. Поскольку алгебра 〈A = M; ∨, ∧, ⊃, ¬〉 является однотипной алгеброй формул пропозиционального языка L, то обычным образом определяется функция оценки ∨ (гомоморфизм) формул языка L в матрице M. Формула A называется общезначимой в M, если при всех значениях переменных в множестве M значение A принадлежит D. Логическая матрица называется характеристической для исчисления высказываний L, если общезначимы те и только те формулы, которые выводимы в L. Множество всех общезначимых формул называется матричной многозначной логикой. Здесь возникают две проблемы:

  1. Нахождение минимальной характеристической матрицы для L.
  2. Нахождение конечной аксиоматизации (если это возможно) по каждой конечной матрице M.

Примерами минимальных характеристических матриц могут служить матрицы для классической двузначной логики C2 и трёхзначной логики Лукасевича Ł3. Ниже представлены примеры других n-значных логик (n ≥ 3).

При изучении многозначных логик понятие функции является основным и наряду с булевыми функциями (функциями двузначной логики) используется для описания дискретных устройств, компоненты которых могут находиться в некотором числе различных состояний. Произвольная функция f (x1, … xm) от любого конечного числа переменных, областью определения которых и областью значения самой функции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2, … n − 1), называется n-значной функцией, или функцией n-значной логики. Имеются различные способы задания функций. Например, функция f (x1, … xm) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m (из элементов 0, 1, 2, … n − 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число n-ичных наборов длины m равно nm и на каждом из них значение функции можно задать n способами. Поэтому число всех функций n-значной логики Pn, зависящих от аргументов x1, … xm, составляетnnm. Случай n > 2 оказывается существенно более сложным, чем классический случай P2. Уже в P3 число функций от двух переменных равно 19 683, в то время как в P2 таких функций всего 16.

Как и в двузначном случае, в Ρn выделяются функции, которые наиболее часто употребляются в логике и кибернетике и играют там важную роль. Такие функции называются элементарными. Вот некоторые из них: константы 0, 1, 2, … n − 1 — это нульместные функции; отрицание Лукасевича: ~ x = (n − 1) − x — это обобщение отрицания в смысле «зеркального отрицания»; отрицание Поста: ¬ x = x + 1 (mod n) — это обобщение отрицания в смысле «циклического сдвига значений»; характеристическая функция числа 1, 1 = 0, 1, … n − 1:

Ji(x) = { n − 1, если x = i
0, если x ≠ i.

Ji(x) — это обобщение некоторых свойств отрицания; минимум x и yx ∧ y = min (xy) — это обобщение конъюнкции; максимум x и yx ν y = max (xy) — это обобщение дизъюнкции; сумма по модулю nx ⊕ y = x + y (mod n) — это обобщение суммы по mod 2 (значение этой функции равно остатку от деления суммы x + y на n); импликация Лукасевича:

x → y = { n − 1, если x ≤ y
n − 1 − x + y, если xy.

x → y — это обобщение одного из свойств классической импликации; функция Вебба: Wn (xy) = max (xy) + 1 (mod n) — это обобщение штриха Шеффера на функционально полную логику Поста Ρn.

Операция дизъюнкции x ∨ y и отрицание Поста ¬ x, определённые на множестве M, являются исходными операциями первой n-значной логикой (n ≥ 3), названной Pn, которая была построена Постом в 1921 году, притом с произвольным числом выделенных значений. В свою очередь, n-значная логика Лукасевича Łn была построена в 1922–1923 годах как обобщение Ł3. Изучение Łn и Pn составило наиболее важный этап в развитии теории многозначных логик.

Кроме двух рассмотренных способов задания функций (табличного и алгоритмического (в последнем случае x ∨ y, к примеру, задаётся как max (xy) не менее известным способом является формула, описывающая функцию как суперпозицию исходных элементарных функций. Функция, полученная из функций f1, … fk подстановкой и/или переименованием аргументов, называется суперпозицией f1, … fk. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой, и тогда говорят, что формула реализует или представляет данную функцию. В этом случае имеем дело с формульной моделью многозначной логики, а сама модель зачастую отождествляется с этой логикой. Основной проблемой здесь является проблема интерпретации истинностных значений. Для широкого класса многозначных логик эта проблема решена А. С. Карпенко (1983) в терминах классических истинностных значений.

В кибернетике такие модели рассматриваются как управляющие системы. Элементарные функции при этом являются элементами, производящими определённые операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными для формульной модели являются: задача об указании всех формул, реализующих заданную константу; задача об эквивалентных преобразованиях; задача о сложности реализации; задача о минимизации и так далее. Однако в зависимости от того, какие цели преследуются при изучении многозначных логик, по-разному понимается, что собой представляет её модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы, обозначаемой (Pn, C), где Pn есть множество всех функций n-значной логики (или множество всех функций счётнозначной логики Ρω) с заданной на нём операцией суперпозиции C, а сама функциональная система (Pn, C) зачастую отождествляется с многозначной логикой, то есть (Pn, C) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмотренных выше алгебр истинностных значений, является алгеброй функций.

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

Наиболее трудной проблемой при изучении функциональных систем является следующая: какие функции могут быть сконструированы из данного множества функций. Проблема эта возникает и в самом пропозициональном исчислении, представленном формульной моделью, и в синтезе автоматов, и в универсальной алгебре; но именно здесь ей уделяется специальное внимание. Наиболее важное свойство функциональной системы есть свойство функциональной полноты (например, для того, чтобы можно было реализовать любую переключательную схему). Система функций ℜ = {f1, … fk, …} из Pn называется функционально полной, если любая функция из Pn представима посредством суперпозиций функций из системы ℜ. Таким образом, указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество ℜ функционально полным? Например, логика Поста Pn, как и классическая двузначная логика, является функционально полной. Отсюда их исключительно широкое применение и развитие.

С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть ℜ ⊆ Pn. Множество всех функций, которые могут быть получены из функций системы ℜ с помощью операции суперпозиции, называется замыканием ℜ и обозначается [ℜ]. Класс функций ℜ называется (функционально) замкнутым, если [ℜ] = ℜ, то есть замкнутость класса функций ℜ обозначает собой сохранение при суперпозиции «наследственных» свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: ℜ — полная система, если [ℜ] = Pn.

Сложной технической проблемой для n-значных логик остаётся распознавание полноты для произвольных систем. Выделяются два подхода к решению задачи о полноте. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту системы функций; во втором рассматривается совокупность всех предполных классов функций в Pn. Система ℜ функций называется предполной в Pn, если ℜ представляет не полную систему, но добавление к ℜ любой функции f такой, что f ∊ Pn и f ∉ ℜ преобразует ℜ в полную систему. Или, в терминах замыкания: ℜ предполна в Pn, если [ℜ] ≠ Pn и [ℜ ∪ {f}] = Pn, где f ∊ Pn и f ∉ ℜ. Важная роль предполных классов функций видна из следующей теоремы, которая формулирует критерий функциональной полноты: система функций ℜ n-значной логики полна тогда и только тогда, когда она не содержится целиком ни в одном предполном классе. Г. Розенбергом в 1970 году было дано описание всех предполных классов в n-значной логике, и хотя число предполных классов π (n) конечно для любого n, однако очень быстрый их рост указывает на малую практическую эффективность предполных классов для решения проблемы полноты.

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

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

Однако наиболее сложной глобальной задачей для многозначной логики остаётся описание решётки замкнутых классов данной модели многозначной логики. Для двузначной логики эта задача полностью решена Э. Постом в начале 1920-х годов, где установлено, что мощность множества замкнутых классов в P2 счётна. Позже им дано полное описание решётки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Однако с многозначной логикой дело обстоит совсем по-другому. Оказалось, что имеются существенные различия между классической двузначной логикой и многозначной, говорящие о принципиальной несводимости второй к первой. В отличие от P2 для всякого n ≥ 3 существует в Pn замкнутый класс, не имеющий базиса, а также для всякого n ≥ 3 существует в Pn замкнутый класс со счётным базисом. Непосредственно к этому примыкает следующий результат: для всякого n ≥ 3 Pn содержит континуум различных замкнутых классов, то есть уже P3 содержит континуум различных замкнутых классов. Следует отметить, что точная природа такого различия между двузначной и трёхзначной логиками пока неясна.

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

    M = 〈[0, 1]; →, ~, {1}〉, где x → y = min (1, 1 − x + y), ~ x = 1 − x.

Почти через тридцать лет Łω была аксиоматизирована следующим образом: аксиома Вайсберга (4) заменяется аксиомой (p → q) → q) → (q → p) → p). Последние десятилетия алгебраические исследования Łω приобрели исключительный масштаб, который позволяет говорить о новом направлении в алгебраической логике. Другим интересным и весьма важным примером бесконечнозначной логики является интуиционистская логика. Ещё К. Гёдель в 1932 году показал, что никакая конечнозначная матрица не может быть для неё характеристической.

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

Библио­графия:
  1. Бочвар Д. Α., Финн В. К. О многозначных логиках, допускающих формализацию анализа антиномий, 1. — В книге: Исследования по математической лингвистике, математической логике и информационным языкам. — М., 1972.
  2. Бочвар Д. Α., Финн В. К. Некоторые дополнения к статьям о многозначных логиках. — В книге: Исследования по теории множеств и неклассическим логикам. — М., 1976.
  3. Зиновьев А. А. Философские проблемы многозначной логики. — М., 1960.
  4. Карпенко А. С. Многозначные логики (монография), в серии «Логика и компьютер», вып. 4. — М., 1997.
  5. Карпенко А. С. Логики Лукасевича и простые числа. — М., 2000.
  6. Кудрявцев В. Б. О функциональных системах. — М., 1981.
  7. Кудрявцев В. Б. Многозначная логика. — В книге: Математическая энциклопедия, т. 3. — М., 1982.
  8. Яблонский С. В. Функциональные построения в k-значной логике. — В книге: Труды математического института имени В. А. Стеклова, т. 51, 1958.
  9. Bolc L., Borowik P. Many-valued logics: Theoretical foundations, v. 1. — В., 1992.
  10. Butler S. W., Butler J. T. Profiles of topics and authors of the International Symposium on Multiple-Valued Logic for 1971–1991. — ISMVL, 22th, Sendai., 1992.
  11. Computer science and multiple-valued logic: Theory and applications. — Amsterdam, 1977 (2nd revised ed. 1984).
  12. Epstein G. Multiple-valued logic design: an introduction. — Bristol, 1993.
  13. Karpenko A. S. Factor-semantics for n-valued logics. — «Studia Logica», 1983, v. 42, № 2–3.
  14. Malinowski G. Many-valued logics. — Oxford, 1993.
  15. Rescher N. Many-valued logic. — NY, 1969.
  16. Rosser J. В., Turquette A. R. Many-valued logics. — Amsterdam, 1952 (2nd ed. 1958).
  17. Wolf R. G. A survey of many-valued logics (1966–1974), in: Modern uses of multiple-valued logic. — Dordrecht., 1977.
Источник: Логики многозначные. Гуманитарная энциклопедия [Электронный ресурс] // Центр гуманитарных технологий, 2010–2017 (последняя редакция: 08.10.2017). URL: http://gtmarket.ru/concepts/6940
Авторы статьи: © А. С. Карпенко. Подготовка электронной публикации и общая редакция: Центр гуманитарных технологий.
Логика: понятия и концепции

Тематический раздел

Новые концепты
Базисные концепты