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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При изучении многозначных логик понятие функции является основным и наряду с булевыми функциями (функциями двузначной логики) используется для описания дискретных устройств, компоненты которых могут находиться в некотором числе различных состояний. Произвольная функция f (x₁, … x _m ) от любого конечного числа переменных, областью определения которых и областью значения самой функции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2, … n − 1), называется n-значной функцией, или функцией n-значной логики. Имеются различные способы задания функций. Например, функция f (x₁, … x _m ) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m (из элементов 0, 1, 2, … n − 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число n-ичных наборов длины m равно n ^m и на каждом из них значение функции можно задать n способами. Поэтому число всех функций n-значной логики P_n, зависящих от аргументов x₁, … x _m , составляет_nn ^m . Случай n> 2 оказывается существенно более сложным, чем классический случай P₂. Уже в P₃ число функций от двух переменных равно 19 683, в то время как в P₂ таких функций всего 16.

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

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

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

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

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

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

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

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

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

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

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

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

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

Особый интерес в силу их различных приложений представляют собой бесконечнозначные логики. Исторически первой такой логикой была бесконечнозначная логика Лукасевича Ł_ω (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 года.