Многозначная логика

Многозначная логика — это логика, в которой логические выражения могут принимать значения из множества, содержащего более, чем два элемента. При этом некоторые из этих значений считаются истинными. Такими свойствами многозначная логика отличается от классической логики Аристотеля, в которой логические выражения могут принимать только одно из двух возможных значения — «истина» или «ложь». Однако классическая двухзначная логика может быть дополнена до n-значной с n > 2. Наиболее популярными в литературе являются трёхзначная логика (например, логика Яна Лукасевича и Стивена Клини, которая принимает значения «истина», «ложь» и «неизвестно»), конечнозначная (может иметь более трёх значений) и бесконечнозначная логики (сюда относят вероятностную логику с непрерывной шкалой значений истинности от 0 до 1, а также нечёткую логику).

История

Первым известным ученым, который не полностью принимал и полагался на закон исключенного третьего, был Аристотель (который, по иронии судьбы, был признан «отцом классической логики»). Аристотель признавал тот факт, что его законы не всегда могут быть применены к будущим событиям, однако он не стал обобщать двухзначную логику на n-мерный случай, чтобы устранить неточности.

До конца XIX столетия математики следовали законам Аристотелевской логики, в основе которой был закон исключенного третьего. Однако в XX веке интерес к многозначной логике начал расти. Так, например, польский математик и философ Ян Лукасевич начал разрабатывать первую систему многозначной логики, использующей третье значение — «нейтрально», чтобы преодолеть сформулированный Аристотелем парадокс морского сражения. Тем временем американский математик Эмиль Пост представил работу, в которой была описана возможность введения дополнительных истинностных значений при [math]\displaystyle{ n\gt 2 }[/math]. Чуть позже и Лукасевич в соавторстве с Альфредом Тарским смогли повторить успех Поста, сформулировав основные принципы n-значной логики при [math]\displaystyle{ n\gt 2 }[/math]. В 1932 году Ханс Райхенбах обобщил эти принципы при [math]\displaystyle{ n \rightarrow\infin }[/math].

В 1932 году Курт Гедель показал, что интуиционистское исчисление не является конечномерным и ввел свою систему (Геделевское исчисление, англ. Gödel logic) как промежуточное звено между классической логикой и интуиционистской. Геделевское исчисление позже стало называться «промежуточной» логикой (англ. intermediate logic).

Основные сведения

Основные статьи: трёхзначная логика, четырёхзначная логика, девятизначная логика

Для описания многозначных пропозициональных логик используются, так называемые ло­гические матрицы, то есть алгебраические системы вида [math]\displaystyle{ \mathfrak{M} = (V, f_1 ,f_2, . . . , f_l, \mathcal{D}) }[/math], где [math]\displaystyle{ V }[/math] — универсум, [math]\displaystyle{ f_1 ,f_2, . . . , f_l }[/math] — функциональные символы, [math]\displaystyle{ \mathcal{D} }[/math] — одноместный предикатный символ. Элементам универсума соответствуют логические значения, а функциональным символам — логические связ­ки (операции), поэтому термы сигнатуры [math]\displaystyle{ \sigma(\mathfrak{M}) }[/math] представляют собой ло­гические формулы. Если логическая формула [math]\displaystyle{ A(x_1, x_2, ...,x_k) }[/math] такова, что [math]\displaystyle{ \mathfrak{M}\models\forall{x_1}\forall{x_2}{..} \forall{x_k}\mathcal{D}(A(x_1, x_2,...,x_k)) }[/math], то она называется общезначимой или тавтологией данной логической матрицы, при этом предикат [math]\displaystyle{ \mathcal{D} }[/math] определя­ет подмножество логических значений, которые трактуются как истинные. Таким образом, строятся матричные представления пропозициональных логик — множеств тавтологий в языке, состоящем из имен переменных и связок.

Любая функция [math]\displaystyle{ f:E^k _{n+1}\rightarrow E_{n+1} }[/math], в том числе выраженная формулой многозначной логики, где [math]\displaystyle{ E_{n+1} = \{0,1,2,...,n\} }[/math], может быть представлена в виде совершенной дизъюнктивной нормальной формы (СДНФ) много­значной логики, следующим образом:

[math]\displaystyle{ f(x_1, x_2, .., x_k) = \bigvee_{(a_1, a_2, .., a_k) \in E^k _{n+1}} f (a_1, a_2, .., a_k) \wedge\left(\bigwedge_{m = 1, ..,k}J_{a_m}(x_m) \right) }[/math],

где [math]\displaystyle{ \wedge }[/math] операция конъюнкции:

[math]\displaystyle{ x \wedge y = min (x, y), }[/math]

символ [math]\displaystyle{ \vee }[/math] обозначает операцию дизъюнкции:

[math]\displaystyle{ x \vee y = max (x, y), }[/math]

а [math]\displaystyle{ J_{i}(x) }[/math] операторы Россера — Тюркетта:

[math]\displaystyle{ J_{i}(x)= \begin{cases} n, & x = i, \\ 0, & x \neq i. \end{cases} }[/math]

K₃ логика Клини и P₃ логика Приста

Логика неопределенности Клини [math]\displaystyle{ K_3 }[/math](иногда обозначают [math]\displaystyle{ K_3^S }[/math]) и «логика парадокса» Приста вводят третье «неопределенное» или «промежуточное» значение I. Таблицы истинности для отрицания (¬), конъюнкции (˄), дизъюнкции (˅), импликации (→) и эквиваленции (↔), выглядят следующим образом:

¬ T F I I F T

∧ T I F T T I F I I I F F F F F

∨ T I F T T T T I T I I F T I F

Шаблон:Underset T I F T T I F I T I I F T T T

Шаблон:Underset T I F T T I F I I I I F F I T

Отличие двух логик состоит в различном определении тавтологии алгебры высказываний (Тавтология — тождественно истинное высказывание, инвариантное относительно значений своих компонентов). В [math]\displaystyle{ K_3 }[/math] только T определено как истинное значение, в то время как в [math]\displaystyle{ P_3 }[/math] и T и I определены в качестве истины. В логике Клини I является «неопределенной» величиной, не являющейся «истиной» или «ложью»; в логике Приста I является «переопределенной» величиной, являющейся одновременно и «истиной», и «ложью». [math]\displaystyle{ K_3 }[/math] не содержит тавтологий, а [math]\displaystyle{ P_3 }[/math] содержит те же тавтологии, что и классическая двухзначная логика.

Внутренняя трёхзначная логика Бочвара

Другим примером может служить «внутренняя» трёхзначная логика Бочвара [math]\displaystyle{ B_3^I }[/math], полученная в 1938 году Дмитрием Анатольевичем Бочваром. Её также называют слабой трёхзначной логикой Клини. Таблицы истинности для отрицания и эквивалентности остаются прежними, а для трёх других операций принимают вид:

Шаблон:Underset T I F T T I F I I I I F F I F

Шаблон:Underset T I F T T I T I I I I F T I F

Шаблон:Underset T I F T T I F I I I I F T I T

В внутренней логике Бочвара I может быть описана как «независимая», поскольку её значение не зависит от значений T и F.

Логика Бельнапа B₄

Логика, предложенная Нуэлем Бельнапом, объединяет в себе [math]\displaystyle{ K_3 }[/math] и [math]\displaystyle{ P_3 }[/math]. «Переопределенная» величина обозначается через B, а «недоопределенная» — через N.

f¬ T F B B N N F T

f∧ T B N F T T B N F B B B F F N N F N F F F F F F

f∨ T B N F T T T T T B T B T B N T T N N F T B N F

Логика Геделя G_k и G_∞

В 1932 году Гедель определил семейство [math]\displaystyle{ G_k }[/math] многозначной логики с конечным набором значений:[math]\displaystyle{ 0, \frac{1}{k-1},\frac{2}{k-1}, ...,\frac{k-2}{k-1},1 }[/math]

Например, для [math]\displaystyle{ G_3 }[/math] значениями будут [math]\displaystyle{ 0, \frac{1}{2},1 }[/math]

Для [math]\displaystyle{ G_4 }[/math] значения примут вид: [math]\displaystyle{ 0, \frac{1}{3},\frac{2}{3}, 1 }[/math]

Похожим образом Гедель определил логику с бесконечным количеством значений [math]\displaystyle{ G_{\infty} }[/math]. Все значения в [math]\displaystyle{ G_{\infty} }[/math] являются действительными числами, принадлежащими интервалу [0, 1]. Истиной в такой логике является 1.

Конъюнкция (˄) и дизъюнкция (˅) определяются как минимальное/максимальное значение следующих выражений:

[math]\displaystyle{ \begin{align} u\wedge v &:= \min\{u,v\} \\ u\vee v &:= \max\{u,v\} \end{align} }[/math]

Отрицание (¬) и импликация (→) определяются следующим образом:

[math]\displaystyle{ \begin{align} \neg_G u & =\begin{cases} 1, & \text{if }u=0\\ 0, & \text{if }u\gt 0 \end{cases} \\ u \xrightarrow[G]{} v &= \begin{cases} 1, & \text{if }u\leq v\\ v, & \text{if }u\gt v \end{cases} \end{align} }[/math]

Логика Геделя полностью аксиоматизируема, поэтому возможно определить логическое исчисление, в котором все тавтологии могут быть доказаны.

Логика Лукасевича L_v и L_∞

Импликация (→) и отрицание (¬) были определены Лукасевичем с помощью следующих функций:

[math]\displaystyle{ \begin{align} \underset{L}{\neg} u &:= 1 - u \\ u\xrightarrow[L]{} v &:= \min\{1, 1 - u + v\} \end{align} }[/math]

Вначале Лукасевич использовал эти определения в 1920 при описании логики [math]\displaystyle{ L_3 }[/math] со значениями [math]\displaystyle{ 0, \frac{1}{2},1 }[/math].

В 1922 он описал бесконечнозначную логику [math]\displaystyle{ L_{\infty} }[/math], все значения которой лежали в интервале [0, 1] и представляли собой действительные числа. В обоих случаях истиной являлась 1.

Описывая значения подобным Геделю способом, а именно: [math]\displaystyle{ 0, \frac{1}{v-1},\frac{2}{v-1}, ...,\frac{v-2}{v-1}, 1 }[/math] можно создать конечнозначное семейство логик [math]\displaystyle{ L_v }[/math], а также логику [math]\displaystyle{ L_{N_0} }[/math], в которых значения также представлены рациональными числами и лежат в интервале [0, 1]. Множество тавтологий в [math]\displaystyle{ L_{\infty} }[/math] и [math]\displaystyle{ L_{N_0} }[/math] идентичны.

Результирующая логика Π

В результирующей логике мы имеем значения, принадлежащие интервалу [0,1], для которых коньюнкция (ʘ) и импликация (→) определяются следующим образом:

[math]\displaystyle{ \begin{align} u\odot v &:= uv \\ u\xrightarrow[\Pi]{}v &:= \begin{cases} 1, & \text{if }u\leq v\\ \frac {v}{u}, & \text{if }u\gt v \end{cases} \end{align} }[/math]

Ложным значением в данной логике является 0. Через него возможно определить операции отрицания (¬) и конъюнкции по сложению (˄):

[math]\displaystyle{ \begin{align} \underset{\Pi}{\neg} u &:= u \xrightarrow[\Pi]{}\overline{0} \\ u \underset{\Pi}{\wedge} v &:= u\odot (u \xrightarrow[\Pi]{} v) \end{align} }[/math]

Логика Поста P_m

В 1921 Пост определил семейство логик [math]\displaystyle{ P_m }[/math] с значениями:

[math]\displaystyle{ 0, \frac{1}{m-1},\frac{2}{m-1}, ...,\frac{m-2}{m-1}, 1 }[/math]. (аналогично логикам [math]\displaystyle{ L_v }[/math] и [math]\displaystyle{ G_k }[/math]). Отрицание (¬), конъюнкция (˄) и дизъюнкция (˅) определены следующим образом:

[math]\displaystyle{ \begin{align} \underset{P}{\neg} u &:= \begin{cases} 1, & \text{if }u=0\\ u-\frac {1}{m-1}, & \text{if }u\not= 0 \end{cases} \\ u \underset{P}{\wedge} v &:= \min\{u,v\} \\ u \underset{P}{\vee} v &:= \max\{u,v\} \end{align} }[/math]

Логика Роуза

В 1951 году Алан Роуз описал семейство логик для систем, чьи значения образуют решетки.

Семантика

Матричная семантика (логические матрицы)

Основная статья: Логическая матрица

Связь с классической логикой

Логика — это система с набором правил, предназначенная для сохранения свойств предложений при различных преобразованиях. В классической логике это свойство — «истина».

Многозначная логика предназначена для сохранения свойства обозначения. Поскольку в ней присутствует более двух «истинных» значений, правила вывода могут быть применены для сохранения дополнительных данных, которые могут не соответствовать истине. Например, трёхзначная логика может иметь два значения, соответствующих «истине» разной градации (например, они могут быть положительными целыми числа), и правила вывода сохраняют эти значения.

Например, сохраненное свойство могло быть подтверждением, играющим важную роль в интуиционистской логике. Мы не рассматриваем его истинность или ложность; вместо этого мы работаем с такими понятиями как подверженность и ошибочность.

Ключевое различие между подтверждением и истиной заключается в том, что закон исключенного третьего в данном случае не выполняется: утверждение, не являющееся ошибочным, не обязательно будет подтверждено; вместо этого доказано только, что оно не ошибочно. Ключевым отличием является определённость сохраняемого свойства: можно показать, что P подтверждено, что P некорректно, или не является ни тем, ни другим. Корректный аргумент сохраняет обоснованность при преобразованиях, поэтому утверждение, полученное на основе обоснованных утверждений, остается обоснованным. Тем не менее в классической логике есть доказательства, которые напрямую зависят от закона исключенного третьего; поскольку этот закон неприменим в рамках данной схемы, существуют утверждения, которые нельзя доказать подобным образом.

Тезис Сушко

Основная статья: Принцип бивалентности

XX век ознаменовался бурным развитием систем многозначных логик, представленных в настоящее время огромным количеством исследований и статей. Однако по мере увеличения количества различных формальных систем, встал вопрос об интерпретации полученных результатов. Ученые остро осознали необходимость сведения (редукции) многозначных логик к единой основе.

В качестве одного из вариантов подобной основы может служить обычная классическая логика. Наиболее ярким представителем данного подхода является польский логик Роман Сушко, предложивший свой алгоритм сведения любой многозначной логики к классической двузначной и сформулировавший принцип, который впоследствии стали называть «тезисом Сушко». Согласно этому принципу для любой многозначной логики можно получить бивалентную семантику, описывающую данную логику.

Функциональная полнота многозначной логики

Функциональная полнота — это термин, использующийся для описания специальных свойств конечных логик и алгебр.

Логический набор является функционально полным тогда и только тогда, когда множество операций этого набора может быть использовано для описания формулы, соответствующей всевозможным функциям истинности.

Функционально полная алгебра — алгебра, в которой каждое конечное отображение может быть выражено через композицию введенных на ней операций.

Классическая логика: [math]\displaystyle{ CL = (\{ 0,1\} \ \neg \ \rightarrow \land \ \lor \longleftrightarrow) }[/math] является функционально полной, в то время как логика Лукасевича или бесконечнозначная логика таким свойством не обладает.

Мы можем определить конечнозначную логику следующим образом: [math]\displaystyle{ L_n(\{1,2,...,n\}, \ f_1,...,f_m) }[/math], где [math]\displaystyle{ n\geq2 }[/math] и n принадлежит множеству натуральных чисел. Эмиль Пост в 1921 доказал, что если логика способна произвести функцию m-ого порядка, то существует комбинация операторов в [math]\displaystyle{ L_n }[/math], которая произведет функцию m+1 порядка.

Бесконечнозначные логики

Бесконечнозначную логику можно ввести следующим образом:

• истинностное значение находится в отрезке действительных чисел от 0 до 1;
• отрицание определяется как: ¬A = 1−A;
• конъюнкция определяется как: A∧B = min(A, B);
• дизъюнкция определяется как: A∨B = max(A, B).

К формальным системам бесконечнозначной логики могут быть отнесены системы R-функций В. Л. Рвачёва.

Теория вероятностей и многозначные логики

Может показаться, что теория вероятностей очень похожа на бесконечнозначную логику: вероятность соответствует истинностному значению (1=истина, 0=ложь), вероятность ненаступления какого-либо события соответствует отрицанию, вероятность одновременного наступления двух событий соответствует конъюнкции, а вероятность наступления хотя бы одного из двух событий соответствует дизъюнкции.

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

Это проявляется, в частности, в том, что в теории вероятностей выполняется эквивалент «закона исключённого третьего»: вероятность того, что некоторое событие наступит или не наступит, всегда равна единице, в то время как в многозначных логиках закон исключённого третьего не выполняется.

В теории вероятностей выполняется также эквивалент «закона противоречия»: вероятность того, что некоторое событие одновременно наступит и не наступит, всегда равна 0, в то время как в многозначных логиках закон противоречия не выполняется.

В то же время существует некоторая связь между истинностными значениями вышеописанной бесконечнозначной логики и вероятностями теории вероятностей, а именно:

• если a — вероятность некоторого события, то вероятность ненаступления этого события составляет 1−a;
• если a и b — вероятности некоторых двух событий, то вероятность совместного наступления этих двух событий не превышает min(a, b);
• если a и b — вероятности некоторых двух событий, то вероятность наступления хотя бы одного из этих двух событий больше или равна max(a, b).

Приложения

Приложения многозначной логики можно условно разделить на две группы.

Первая группа использует многозначную логику для эффективного решения вопроса о бинарном представлении некоторой сущности. Например, представление булевой функции с несколькими выходами состоит в том, чтобы рассматривать её выходную часть как одну переменную, которая зависит от множества аргументов. Дальнейшие преобразования ведутся с ней: её преобразовывают в характеристическую функцию с одним выходом (в частности, индикаторную функцию).

Другие приложения многозначной логики включают в себя проектирование матриц программируемой логики (PLA), оптимизацию конечных автоматов, тестирование и проверку.

Вторая группа нацелена на создание и проектирование электронных схем, использующих более двух дискретных уровней. Сюда можно отнести: многозначную память, арифметико-логические устройства и программируемые пользователем вентильные матрицы (FPGA). Многозначные схемы имеют ряд серьёзных теоретических преимуществ перед стандартными двоичными схемами. Так, например, межсоединение на кристалле и за его пределами может быть меньших размеров, если сигналы в схеме могут имеют дело с четырьмя уровнями, а не только с двумя. В конструкции памяти хранение двух бит информации вместо одного на ячейку памяти удваивает плотность памяти при неизменном размере кристалла.

Программные приложения, использующие арифметико-логические устройства, часто выигрывают от использования альтернатив двоичным системам счисления. Так, например, остаточные и избыточные (англ. redundant binary representation) системы счисления могут уменьшить или исключить сквозные переносы (англ. ripple-carry), которые имеют место в обычном двоичном сложении или вычитании, что приводит к высокоскоростным арифметическим операциям. Такие системы счисления имеют естественную реализацию с использованием многозначных схем.

Однако практичность этих потенциальных теоретических преимуществ сильно зависит от наличия специальных реализаций, которые должны быть совместимы и конкурентоспособны с современными стандартными технологиями. В дополнение к использованию в проектировании электронных схем, многозначная логика широко используется для проверки схем на наличие неисправностей и дефектов. Практически все известные алгоритмы автоматической генерации тестовых последовательностей (ATG), используемые для тестирования цифровых схем, требуют имитатора, который может иметь дело с 5-значной логикой (0, 1, x, D, D'). Дополнительные значения — x, D и D'- представляют собой неизвестный / неинициализированный (значение x), 0 вместо 1 (значение D) и 1 вместо 0 (значение D').

Компьютер на основе троичной логики

Основная статья: Сетунь (компьютер)

Троичная ЭВМ «Сетунь» была создана и введена в эксплуатацию на механико-математическом факультете МГУ в 1958 году.

В отличие от классического подхода, использующегося в современных компьютерах, «Сетунь» использовала троичный код с цифрами −1, 0, 1. Данный подход имеет ряд преимуществ при осуществлении арифметических операций и представлении числа в памяти машины: нет необходимости в несовершенных дополнительном, прямом или обратном кодах чисел, округление осуществляется простым отсечением младших разрядов, операции сдвига единственны, код чисел единообразен.

Исследовательские площадки

Международный симпозиум, посвященный проблемам и вопросам, возникающих при исследовании приложений многозначной логики (ISMVL) проводится ежегодно с 1970 года. Основные направления работы симпозиума — обслуживание различных цифровых приложений и проблемы верификации.

Помимо этого существует журнал, посвященный многозначной логике и её приложениям в цифровой сфере.

Ссылки

• http://plato.stanford.edu/entries/logic-manyvalued
• https://web.archive.org/web/20060308150855/http://www.cs.chalmers.se/~reiner/papers/ipgl.pdf

Литература

• Яблонский С. В. Введение в дискретную математику. 2-е изд. М.: Наука, 1986. 384с. (недоступная ссылка)  (недоступная ссылка с 13-05-2013 [4207 дней]) Глава 2.
• Многозначные логики и их применения: Логические исчисления, алгебры и функциональные свойства. Под ред. Финна В. К. Том 1. М.: УРСС, 2008. 416 с.
• Многозначные логики и их применения: Логики в системах искусственного интеллекта. Под ред. Финна В. К. Том 2. М.: УРСС, 2008. 240 с.
• Карпенко А. С. Многозначные логики. Логика и компьютер. Вып. 4. М.: Наука, 1997. 223с.
• Карпенко А. С. Логики Лукасевича и простые числа. М.: Наука, 2000. 319с.
• Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
• Статьи по многозначным логикам в arxiv.org
• Левин В. И.Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982. 176 с.
• Rescher, N. «Many-Valued Logic», Mc.Graw-Hill, New York, 1969.
• Rosser, J. B., Turquette, A. R. «Many-Valued Logics», North Holland, Amsterdam, 1952.