Трехзначная логика

В логике — трёхзначная логика (также троичная логика , трёхвалентная , троичная или трёхзначная , ^[1] иногда сокращенно 3VL ) — любая из нескольких многозначных логических систем, в которых есть три значения истинности, обозначающие истину , ложь и какое-то третье значение. Это контрастирует с более широко известными бивалентными логиками (такими как классическая сентенциальная или булева логика ), которые предусматривают только истину и ложь .

Эмилю Леону Посту приписывают первое введение дополнительных степеней логической истинности в его теории элементарных предложений 1921 года. ^[2] Концептуальная форма и основные идеи трехзначной логики были первоначально опубликованы Яном Лукасевичем и Кларенсом Ирвингом Льюисом . Затем они были переформулированы Григоре Константином Моисилом в аксиоматической алгебраической форме, а также распространены на n -значные логики в 1945 году.

Предварительное открытие

Примерно в 1910 году Чарльз Сандерс Пирс определил систему многозначной логики . Он никогда не публиковал это. Фактически, он даже не пронумеровал три страницы заметок, где определял свои трехзначные операторы. ^[3] Пирс решительно отверг идею, что все предложения должны быть либо истинными, либо ложными; граничные предложения, пишет он, находятся «на границе между Р и не Р». ^[4] Однако, как бы он ни был уверен в том, что «Триадическая логика универсальна», ^[5] он также записал: «Все это очень близко к чепухе». ^[6] Только в 1966 году, когда Макс Фиш и Этвелл Теркетт начали публиковать то, что они заново открыли в его неопубликованных рукописях, триадические идеи Пирса стали широко известны. ^[7]

Представление ценностей

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

в сбалансированной троичной системе каждая цифра имеет одно из трех значений: −1, 0 или +1; эти значения также можно упростить до −, 0, + соответственно; ^[8]
в избыточном двоичном представлении каждая цифра может иметь значение -1, 0, 0/1 (значение 0/1 имеет два разных представления);
в троичной системе счисления каждая цифра представляет собой трит (тройную цифру), имеющую значение: 0, 1 или 2;
в косой двоичной системе счисления только младшая ненулевая цифра может иметь значение 2, а остальные цифры имеют значение 0 или 1;
1 для истинного , 2 для ложного и 0 для неизвестного , непознаваемого / неразрешимого , нерелевантного или того и другого ; ^[9]
0 для false , 1 для true и третий нецелочисленный символ «может быть», например ?, #, ½, ^[10] или ху.

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

Эта статья в основном иллюстрирует систему троичной логики высказываний, использующую значения истинности {ложь, неизвестное, истинное}, и расширяет обычные логические связки до трехвалентного контекста.

Логика

Булева логика позволяет 2 ² = 4 унарных оператора ; добавление третьего значения в троичной логике приводит в общей сложности к 3 ³ = 27 различных операторов для одного входного значения. (Это можно прояснить, рассмотрев все возможные таблицы истинности для произвольного унарного оператора. Учитывая два возможных значения TF одного логического входа, существует четыре различных шаблона вывода TT, TF, FT, FF, возникающих в результате действия следующих унарных операторов: для каждого значения: всегда T, Identity, NOT, всегда F. Учитывая три возможных значения троичной переменной, каждый раз три возможных результата унарной операции, существует 27 различных выходных шаблонов: TTT, TTU, TTF, TUT, TUU, TUF, TFT, TFU, TFF, UTT, UTU, UTF, UUT, UUU, UUF, UFT, UFU, UFF, FTT, FTU, FTF, FUT, FUU, FUF, FFT, FFU и FFF.) Аналогично, где логическое значение логика имеет 2 ^2×2 = возможно 16 различных бинарных операторов (операторов с 2 входами), троичная логика имеет 3 ^3×3 = 19 683 таких оператора. Там, где можно назвать нетривиальные логические операторы ( AND , NAND , OR , NOR , XOR , XNOR ( эквивалентность ) и 4 варианта импликации или неравенства), с шестью тривиальными операторами, учитывающими только 0 или 1 входные данные, неразумно пытаться назовите все, кроме небольшой части возможных тернарных операторов. ^[11] Как и в бивалентной логике, где не всем операторам даны имена и используются подмножества функционально полных операторов, могут существовать функционально полные множества троичных операторов.

Логика Клини и Приста

Ниже приведен набор таблиц истинности , показывающий логические операции Стивена Коула Клини «сильной логики неопределенности» Грэма Приста и «логики парадокса» .

(F — ложь; U — неизвестно; T — правда)

НЕ(А)
А	¬A
Ф	Т
В	В
Т	Ф

И(А, Б)
А ∧ Б		Б
А ∧ Б		Ф	В	Т
А	Ф	Ф	Ф	Ф
	В	Ф	В	В
	Т	Ф	В	Т

ИЛИ(А, Б)
А ∨ Б		Б
А ∨ Б		Ф	В	Т
А	Ф	Ф	В	Т
	В	В	В	Т
	Т	Т	Т	Т

Исключающее ИЛИ(А, Б)
А ⊕ Б		Б
А ⊕ Б		Ф	В	Т
А	Ф	Ф	В	Т
	В	В	В	В
	Т	Т	В	Ф

(-1, ложь; 0, неизвестно; +1, правда)

НЕГ(А)
А	¬A
−1	+1
0	0
+1	−1

МИН(А, Б)
А ∧ Б		Б
А ∧ Б		−1	0	+1
А	−1	−1	−1	−1
	0	−1	0	0
	+1	−1	0	+1

МАКС(А, Б)
А ∨ Б		Б
А ∨ Б		−1	0	+1
А	−1	−1	0	+1
	0	0	0	+1
	+1	+1	+1	+1

МИН(МАКС(A, B), ОТР(МИН(A, B)))
А ⊕ Б		Б
А ⊕ Б		−1	+1
А	−1	−1	+1
	0	0	0
	+1	+1	−1

В этих таблицах истинности неизвестное состояние можно рассматривать как ни истинное, ни ложное в логике Клини или как истинное и ложное в логике Приста. Разница заключается в определении тавтологии. Там, где единственным назначенным значением истинности логики Клини является T, назначенными значениями истинности логики Приста являются как T, так и U. В логике Клини знание о том, представляет ли какое-либо конкретное неизвестное состояние тайно истинное или ложное в любой момент времени, недоступно. Однако некоторые логические операции могут давать однозначный результат, даже если они используют неизвестный операнд. Например, поскольку OR true равно true , а true OR false также равно true , то true ORknown true равно true также . В этом примере, поскольку любое двухвалентное состояние может лежать в основе неизвестного состояния, и любое состояние также дает один и тот же результат, истинные результаты во всех трех случаях.

Если числовые значения, например, сбалансированные троичные значения, присвоены false , неизвестному и истинному , так что false меньше неизвестного , а неизвестное меньше истинного , то A AND B AND C... = MIN(A, B, C .. .) и A OR B OR C ... = MAX(A, B, C...).

Материальное значение логики Клини можно определить как:

$A\rightarrow B\ {\overset {\underset {\mathrm {def} }{}}{=}}\ {\mbox{OR}}(\ {\mbox{NOT}}(A),\ B)$ , и его таблица истинности равна

ИМП _K (A, B), OR(¬A, B)
А → Б		Б
А → Б		Ф	В	Т
А	Ф	Т	Т	Т
	В	В	В	Т
	Т	Ф	В	Т

ИМП _К (А, В), МАКС(-А, В)
А → Б		Б
А → Б		−1	0	+1
А	−1	+1	+1	+1
	0	0	0	+1
	+1	−1	0	+1

что отличается от логики Лукасевича (описанной ниже).

В логике Клини нет тавтологии (действительных формул), поскольку всякий раз, когда всем атомарным компонентам правильно составленной формулы присваивается значение «Неизвестно», сама формула также должна иметь значение «Неизвестно». (И единственным обозначенным значением истинности для логики Клини является «Истина».) Однако отсутствие действительных формул не означает, что в ней отсутствуют действительные аргументы и/или правила вывода. Аргумент является семантически действительным в логике Клини, если всякий раз (для любой интерпретации/модели) все его посылки истинны, вывод также должен быть истинным. ( Логика парадокса (ЛП) имеет те же таблицы истинности, что и логика Клини, но имеет два назначенных значения истинности вместо одного; это: Истинно и Оба (аналог Неизвестного), так что ЛП действительно имеет тавтологии, но имеет меньше действительных правил вывода). ^[12]

Логика Лукасевича

Лукасевич Ł3 имеет те же таблицы для И, ИЛИ и НЕ, что и логика Клини, приведенная выше, но отличается определением импликации тем, что «неизвестное подразумевает неизвестное» истинно . Этот раздел следует за презентацией главы Малиновского «Справочника по истории логики» , том 8. ^[13]

Материальным смыслом таблицы истинности логики Лукасевича является

ИМП _Ł (А, Б)
А → Б		Б
А → Б		Ф	В	Т
А	Ф	Т	Т	Т
	В	В	Т	Т
	Т	Ф	В	Т

ИМП _Ł (A, B), МИН(1, 1−A+B)
А → Б		Б
А → Б		−1	0	+1
А	−1	+1	+1	+1
	0	0	+1	+1
	+1	−1	0	+1

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

$А \lor B знак равно (А \to B) \to B$
$А \land B = \neg(\neg А \lor \neg B)$
$А \Leftrightarrow B знак равно (А \to B) \land (B \to А)$

Также возможно вывести несколько других полезных унарных операторов (впервые выведенных Тарским в 1921 году): ^{[ нужна ссылка ]}

$М А = \neg А \to А$
$Л А = \neg М \neg А$
$Я А = М А \land \neg L А$

Они имеют следующие таблицы истинности:

$А$	$М А$
Ф	Ф
В	Т
Т	Т

$А$	$ A$
Ф	Ф
В	Ф
Т	Т

$А$	$Я $
Ф	Ф
В	Т
Т	Ф

M читается как «это не ложно, что...» или в (неудачной) попытке Тарского-Лукасевича аксиоматизировать модальную логику с использованием трехзначной логики, «возможно, что...» L читается «это правда, что..." или "необходимо, что..." Наконец читается "неизвестно, что..." или "возможно, что..."

В Ł3 Лукасевича обозначенное значение — «Истина», а это означает, что только предложение, имеющее это значение повсюду, считается тавтологией . Например, $A \to A$ и $A \leftrightarrow A$ являются тавтологиями в Ł3, а также в классической логике. Не все тавтологии классической логики доводятся до Ł3 «как есть». Например, закон исключенного третьего A $A \lor \neg A$ и закон непротиворечия ¬ $(A \land \neg) не$ являются тавтологиями в Ł3. выше оператор $Однако, используя определенный$ , можно сформулировать тавтологии, являющиеся их аналогами:

$A \lor I A \lor \neg A$ ( закон исключенной четвертой )
$\neg(A \land \neg I A \land \neg A)$ ( расширенный принцип противоречия ).

Логика RM3

Таблица истинности материального значения R-mingle 3 (RM3) такова:

ИМП _РМ3 (А, Б)
А → Б		Б
А → Б		Ф	В	Т
А	Ф	Т	Т	Т
	В	Ф	В	Т
	Т	Ф	Ф	Т

Определяющей характеристикой RM3 является отсутствие аксиомы ослабления:

$(А \to (Б \to А))$

что по сопряженности эквивалентно проекции произведения:

$(А \otimes Б) \to А$

RM3 — недекартова симметричная моноидальная замкнутая категория; произведение, которое слева сопряжено с импликацией, не имеет действительных проекций и имеет $U$ в качестве тождества моноида.Эта логика эквивалентна «идеальной» паранепротиворечивой логике, которая также подчиняется контрапозитиву.

HT-логика

Логика здесь и там ( HT , также называемая логикой Сметанова SmT или логикой Гёделя G3), введенная Хейтингом в 1930 году. ^[14] как модель для изучения интуиционистской логики , представляет собой трехзначную промежуточную логику , где третье истинностное значение NF (не ложное) имеет семантику предложения, ложность которого можно доказать интуиционистски, но не имеет интуиционистского доказательства правильности .

(F — ложь; NF — не ложь; T — правда)

НЕ _ХТ (А)
А	¬A
Ф	Т
НФ	Ф
Т	Ф

ИМП _ХТ (А, Б)
А → Б		Б
А → Б		Ф	НФ	Т
А	Ф	Т	Т	Т
	НФ	Ф	Т	Т
	Т	Ф	НФ	Т

Его можно определить либо путем добавления одной из двух эквивалентных аксиом (¬ q → p ) → ((( p → q ) → p ) → p ) или, что эквивалентно, p ∨(¬ q )∨( p → q ) к аксиомам интуиционистской логики или явных таблиц истинности для ее операций. В частности, конъюнкция и дизъюнкция такие же, как в логике Клини и Лукасевича, а отрицание другое.

HT-логика — это уникальный коатом в решетке промежуточных логик. В этом смысле ее можно рассматривать как «вторую по силе» промежуточную логику после классической логики.

Бочварская логика

Эта логика также известна как слабая форма трехзначной логики Клини.

Тернарная логика Post

not(a) = (a + 1) mod 3, или

not(a) = (a + 1) mod (n), где (n) — значение логики

Модульные алгебры

Некоторые арифметические операции с модулями 3VL были введены совсем недавно, мотивированные скорее схемными проблемами, чем философскими вопросами: ^[15]

Алгебра Кона
Прадханская алгебра
Дуброва ^[16] и алгебра Муцио

Приложения

SQL

Язык структурных запросов базы данных SQL реализует троичную логику как средство обработки сравнений с содержимым поля NULL . Изначально NULL предназначался для использования в качестве контрольного значения в SQL для представления отсутствующих данных в базе данных, т.е. предполагалось, что фактическое значение существует, но в настоящее время это значение не записано в базе данных. SQL использует общий фрагмент логики Kleene K3, ограниченный таблицами AND, OR и NOT.

В SQL промежуточное значение интерпретируется как НЕИЗВЕСТНО. Явное сравнение с NULL, в том числе с другим NULL, дает UNKNOWN. Однако от этого выбора семантики отказываются для некоторых операций над множествами, например UNION или INTERSECT, где значения NULL рассматриваются как равные друг другу. Критики утверждают, что эта несогласованность лишает SQL интуитивной семантики при обработке NULL. ^[17] Стандарт SQL определяет дополнительную функцию под названием F571, которая добавляет некоторые унарные операторы, среди которых IS UNKNOWN соответствующий Лукасевичу I в этой статье. Добавление IS UNKNOWN другим операторам трехзначной логики SQL делает трехзначную логику SQL функционально завершенной , ^[18] это означает, что его логические операторы могут выражать (в комбинации) любую мыслимую трехзначную логическую функцию.

См. также

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

Ссылки

^ «Трилин (Стэнфордский API JavaNLP)» . Стэнфордский университет . Стэнфордская группа НЛП. Архивировано из оригинала 3 мая 2023 года.
^ Пост, Эмиль Л. (1921). «Введение в общую теорию элементарных предложений» . Американский журнал математики . 43 (3): 163–185. дои : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN 0002-9327 . JSTOR 2370324 . Архивировано (PDF) из оригинала 9 мая 2024 г. - через JSTOR.
^ «Дедуктивная логика Пирса > Трехзначная логика Пирса (Стэнфордская энциклопедия философии / издание лета 2020 г.)» . plato.stanford.edu . Проверено 15 мая 2024 г.
^ Лейн, Р. (2001). «Триадическая логика» . Комментарий . Архивировано из оригинала 6 декабря 2023 года.
^ Пирс, Чарльз С. (1839–1914). «Логика: автограф-рукопись тетради, 12 ноября 1865 г. — 1 ноября 1909 г.» . hollisarchives.lib.harvard.edu/repositories/24/digital_objects/63983 . Библиотека Хоутона Гарвардского университета . Проверено 15 мая 2023 г. Триадическая логика универсальна. Но диадическая логика не является абсолютно ложной.
^ Пирс, Чарльз С. (1839–1914). «Логика: автограф-рукопись тетради, 12 ноября 1865 г. — 1 ноября 1909 г.» . hollisarchives.lib.harvard.edu/repositories/24/digital_objects/63983 . Библиотека Хоутона Гарвардского университета . Проверено 15 мая 2023 г.
^ Лейн, Роберт. «Триадическая логика» . www.digitalpeirce.fee.unicamp.br . Проверено 30 июля 2020 г.
^ Кнут, Дональд Э. (1981). Искусство компьютерного программирования Том. 2 . Ридинг, Массачусетс: Издательство Addison-Wesley. п. 190.
^ Хейс, Брайан (ноябрь – декабрь 2001 г.). «Третья база» (PDF) . Американский учёный . 89 (6). Сигма Си , Общество научных исследований: 490–494. дои : 10.1511/2001.40.3268 . Архивировано (PDF) из оригинала 30 октября 2019 г. Проверено 12 апреля 2020 г.
^ Нельсон, Дэвид (2008). Математический словарь Penguin. Четвертое издание . Лондон, Англия: Penguin Books. Запись для «трехзначной логики». ISBN 9780141920870 .
↑ Дуглас В. Джонс, Стандартная троичная логика , 11 февраля 2013 г.
^ "За пределами пропозициональной логики"
^ Гжегож Малиновский, « Многозначная логика и ее философия » в Дов М. Габбай, Джон Вудс (ред.) Справочник по истории логики, том 8. Многозначный и немонотонный поворот в логике , Elsevier, 2009
^ Хейтинг (1930). «Формальные правила интуиционистской логики». Сиденье . 42-56.
^ Миллер, Д. Майкл; Торнтон, Митчелл А. (2008). Многозначная логика: понятия и представления . Обобщающие лекции по цифровым схемам и системам. Том. 12. Издательство Морган и Клейпул. стр. 41–42. ISBN 978-1-59829-190-2 .
^ Дуброва, Елена (2002). Синтез и оптимизация многозначной логики , в Хассун С. и Сасао Т., редакторы, Логический синтез и проверка , Kluwer Academic Publishers, стр. 89-114.
^ Рон ван дер Мейден, « Логические подходы к неполной информации: обзор » в Хомицки, январь; Сааке, Гюнтер (ред.) Логика для баз данных и информационных систем , Kluwer Academic Publishers ISBN 978-0-7923-8129-7 , с. 344; Препринт PS (примечание: нумерация страниц в препринте отличается от опубликованной версии)
^ CJ Date, Сочинения о реляционных базах данных, 1991–1994 , Аддисон-Уэсли, 1995, стр. 371

Дальнейшее чтение

Бергманн, Мерри (2008). Введение в многозначную и нечеткую логику: семантика, алгебры и системы вывода . Издательство Кембриджского университета. ISBN 978-0-521-88128-9 . Проверено 24 августа 2013 г. , главы 5-9
Мундичи, Д. C*-алгебры трехзначной логики. Логический коллоквиум '88, Материалы коллоквиума, проходившего в Падуе 61–77 (1989). дои : 10.1016/s0049-237x(08)70262-3
Райхенбах, Ганс (1944). Философские основы квантовой механики . Издательство Калифорнийского университета. Дувр 1998: ISBN 0-486-40459-5

[1] «Трилин (Стэнфордский API JavaNLP)» . Стэнфордский университет . Стэнфордская группа НЛП. Архивировано из оригинала 3 мая 2023 года.

[2] Пост, Эмиль Л. (1921). «Введение в общую теорию элементарных предложений» . Американский журнал математики . 43 (3): 163–185. дои : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN 0002-9327 . JSTOR 2370324 . Архивировано (PDF) из оригинала 9 мая 2024 г. - через JSTOR.

[3] «Дедуктивная логика Пирса > Трехзначная логика Пирса (Стэнфордская энциклопедия философии / издание лета 2020 г.)» . plato.stanford.edu . Проверено 15 мая 2024 г.

[4] Лейн, Р. (2001). «Триадическая логика» . Комментарий . Архивировано из оригинала 6 декабря 2023 года.

[5] Пирс, Чарльз С. (1839–1914). «Логика: автограф-рукопись тетради, 12 ноября 1865 г. — 1 ноября 1909 г.» . hollisarchives.lib.harvard.edu/repositories/24/digital_objects/63983 . Библиотека Хоутона Гарвардского университета . Проверено 15 мая 2023 г. Триадическая логика универсальна. Но диадическая логика не является абсолютно ложной.

[6] Пирс, Чарльз С. (1839–1914). «Логика: автограф-рукопись тетради, 12 ноября 1865 г. — 1 ноября 1909 г.» . hollisarchives.lib.harvard.edu/repositories/24/digital_objects/63983 . Библиотека Хоутона Гарвардского университета . Проверено 15 мая 2023 г.

[7] Лейн, Роберт. «Триадическая логика» . www.digitalpeirce.fee.unicamp.br . Проверено 30 июля 2020 г.

[8] Кнут, Дональд Э. (1981). Искусство компьютерного программирования Том. 2 . Ридинг, Массачусетс: Издательство Addison-Wesley. п. 190.

[9] Хейс, Брайан (ноябрь – декабрь 2001 г.). «Третья база» (PDF) . Американский учёный . 89 (6). Сигма Си , Общество научных исследований: 490–494. дои : 10.1511/2001.40.3268 . Архивировано (PDF) из оригинала 30 октября 2019 г. Проверено 12 апреля 2020 г.

[10] Нельсон, Дэвид (2008). Математический словарь Penguin. Четвертое издание . Лондон, Англия: Penguin Books. Запись для «трехзначной логики». ISBN 9780141920870 .

[11] Дуглас В. Джонс, Стандартная троичная логика , 11 февраля 2013 г.

[12] "За пределами пропозициональной логики"

[13] Гжегож Малиновский, « Многозначная логика и ее философия » в Дов М. Габбай, Джон Вудс (ред.) Справочник по истории логики, том 8. Многозначный и немонотонный поворот в логике , Elsevier, 2009

[14] Хейтинг (1930). «Формальные правила интуиционистской логики». Сиденье . 42-56.

[15] Миллер, Д. Майкл; Торнтон, Митчелл А. (2008). Многозначная логика: понятия и представления . Обобщающие лекции по цифровым схемам и системам. Том. 12. Издательство Морган и Клейпул. стр. 41–42. ISBN 978-1-59829-190-2 .

[16] Дуброва, Елена (2002). Синтез и оптимизация многозначной логики , в Хассун С. и Сасао Т., редакторы, Логический синтез и проверка , Kluwer Academic Publishers, стр. 89-114.

[Meyden-17] Рон ван дер Мейден, « Логические подходы к неполной информации: обзор » в Хомицки, январь; Сааке, Гюнтер (ред.) Логика для баз данных и информационных систем , Kluwer Academic Publishers ISBN 978-0-7923-8129-7 , с. 344; Препринт PS (примечание: нумерация страниц в препринте отличается от опубликованной версии)

[18] CJ Date, Сочинения о реляционных базах данных, 1991–1994 , Аддисон-Уэсли, 1995, стр. 371

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v т и Неклассическая логика
Intuitionistic	Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory
Fuzzy	Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations
Substructural	Structural rule Relevance logic Linear logic
Paraconsistent	Dialetheism
Description	Ontology (computer science) Ontology language
Many-valued	Three-valued Four-valued Łukasiewicz
Digital logic	Three-state logic Tri-state buffer Four-valued Verilog IEEE 1164 VHDL
Others	Dynamic semantics Inquisitive logic Intermediate logic Non-monotonic logic