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

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

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

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

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

Для описания многозначных пропозициональных логик используются, так называемые ло­гические матрицы^[1][2], то есть алгебраические системы вида ${\displaystyle {\mathfrak {M}}=(V,f_{1},f_{2},...,f_{l},{\mathcal {D}})}$ , где ${\displaystyle V}$  — универсум, ${\displaystyle f_{1},f_{2},...,f_{l}}$  — функциональные символы, ${\displaystyle {\mathcal {D}}}$  — одноместный предикатный символ. Элементам универсума соответствуют логические значения, а функциональным символам — логические связ­ки (операции), поэтому термы сигнатуры ${\displaystyle \sigma ({\mathfrak {M}})}$ представляют собой ло­гические формулы. Если логическая формула ${\displaystyle A(x_{1},x_{2},...,x_{k})}$ такова, что ${\displaystyle {\mathfrak {M}}\models \forall {x_{1}}\forall {x_{2}}{..}\forall {x_{k}}{\mathcal {D}}(A(x_{1},x_{2},...,x_{k}))}$ , то она называется общезначимой или тавтологией данной логической матрицы, при этом предикат ${\displaystyle {\mathcal {D}}}$ определя­ет подмножество логических значений, которые трактуются как истинные. Таким образом, строятся матричные представления пропозициональных логик — множеств тавтологий в языке, состоящем из имен переменных и связок.

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

${\displaystyle f(x_{1},x_{2},..,x_{k})=\bigvee _{(a_{1},a_{2},..,a_{k})\in E_{n+1}^{k}}f(a_{1},a_{2},..,a_{k})\wedge \left(\bigwedge _{m=1,..,k}J_{a_{m}}(x_{m})\right)}$ ,

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

${\displaystyle x\wedge y=min(x,y),}$

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

${\displaystyle x\vee y=max(x,y),}$

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

${\displaystyle J_{i}(x)={\begin{cases}n,&x=i,\\0,&x\neq i.\end{cases}}}$

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

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

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

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

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

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

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

Логика, предложенная Нуэлем Бельнапом, объединяет в себе ${\displaystyle K_{3}}$ и ${\displaystyle P_{3}}$ . «Переопределенная» величина обозначается через B, а «недоопределенная» — через N.

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

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

Например, для ${\displaystyle G_{3}}$ значениями будут ${\displaystyle 0,{\frac {1}{2}},1}$

Для ${\displaystyle G_{4}}$ значения примут вид: ${\displaystyle 0,{\frac {1}{3}},{\frac {2}{3}},1}$

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

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

${\displaystyle {\begin{aligned}u\wedge v&:=\min\{u,v\}\\u\vee v&:=\max\{u,v\}\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\neg _{G}u&={\begin{cases}1,&{\text{if }}u=0\\0,&{\text{if }}u>0\end{cases}}\\u{\xrightarrow[{G}]{}}v&={\begin{cases}1,&{\text{if }}u\leq v\\v,&{\text{if }}u>v\end{cases}}\end{aligned}}}$

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

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

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}u\odot v&:=uv\\u{\xrightarrow[{\Pi }]{}}v&:={\begin{cases}1,&{\text{if }}u\leq v\\{\frac {v}{u}},&{\text{if }}u>v\end{cases}}\end{aligned}}}$

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

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

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

В 1921 Пост определил семейство логик ${\displaystyle P_{m}}$ с значениями:

${\displaystyle 0,{\frac {1}{m-1}},{\frac {2}{m-1}},...,{\frac {m-2}{m-1}},1}$ . (аналогично логикам ${\displaystyle L_{v}}$ и ${\displaystyle G_{k}}$ ). Отрицание (¬), конъюнкция (˄) и дизъюнкция (˅) определены следующим образом:

${\displaystyle {\begin{aligned}{\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{aligned}}}$

Логика Роуза

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

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

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

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

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

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

Тезис Сушко

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

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

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

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

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

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

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

Мы можем определить конечнозначную логику следующим образом: ${\displaystyle L_{n}(\{1,2,...,n\},\ f_{1},...,f_{m})}$ , где ${\displaystyle n\geq 2}$ и n принадлежит множеству натуральных чисел. Эмиль Пост в 1921 доказал, что если логика способна произвести функцию m-ого порядка, то существует комбинация операторов в ${\displaystyle L_{n}}$ , которая произведет функцию m+1 порядка.

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

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

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

Может показаться, что теория вероятностей очень похожа на бесконечнозначную логику: вероятность соответствует истинностному значению (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 года. Основные направления работы симпозиума — обслуживание различных цифровых приложений и проблемы верификации.

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

• Яблонский С. В. Введение в дискретную математику. 2-е изд. М.: Наука, 1986. 384с. (недоступная ссылка)  (недоступная ссылка с 13-05-2013 [4012 дней]) Глава 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.

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