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

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

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

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

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

Представление значений [ править ]

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

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

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

Логика [ править ]

Булева логика позволяет 2 2 = 4 унарных оператора ; добавление третьего значения в троичной логике приводит в общей сложности к 3 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 0 +1
А −1 −1 0 +1
0 0 0 0
+1 +1 0 −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...).

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

, и его таблица истинности равна

ИМП 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

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

  • А ∨ B знак равно ( А → B ) → B
  • А ∧ B = ¬(¬ А ∨ ¬ B )
  • А ⇔ B знак равно ( А → B ) ∧ ( B → А )

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

  • М А = ¬ А → А
  • Л А = ¬ М ¬ А
  • Я А = М А ∧ ¬ L А

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

А М А
Ф Ф
В Т
Т Т
А ​ A
Ф Ф
В Ф
Т Т
А Я ​
Ф Ф
В Т
Т Ф

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

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

Логика RM3 [ править ]

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

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

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

  • ( А → ( Б → А ))

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

  • ( А ⊗ Б ) → А

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

HT-логика [ править ]

Дополнительная информация: Промежуточная логика.
Дополнительная информация: Многозначная логика § Логики Гёделя Gk и G∞.

Логика здесь и там ( 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 [ править ]

Дополнительная информация: Null (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] это означает, что его логические операторы могут выражать (в комбинации) любую мыслимую трехзначную логическую функцию.

См. также [ править ]

Ссылки [ править ]

  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.
  17. ^ Рон ван дер Мейден, « Логические подходы к неполной информации: обзор » в Хомицки, январь; Сааке, Гюнтер (ред.) Логика для баз данных и информационных систем , Kluwer Academic Publishers ISBN   978-0-7923-8129-7 , с. 344; Препринт PS (примечание: нумерация страниц в препринте отличается от опубликованной версии)
  18. ^ CJ Date, Сочинения о реляционных базах данных, 1991–1994 , Аддисон-Уэсли, 1995, стр. 371

Дальнейшее чтение [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Three-valued_logic&oldid=1224362561"