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

Propositional calculus in which there are more than two truth values

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

История

Неверно , что первым известным классическим логиком, который не полностью принял закон исключенного третьего, был Аристотель (который, по иронии судьбы, также обычно считается первым классическим логиком и «отцом [двузначной] логики» ^{[1] ]} ). В действительности Аристотель оспаривал не универсальность закона исключенного третьего, а универсальность принципа двувалентности: он признавал, что не все эти принципы применимы к будущим событиям ( De Interpretatione , гл. IX ), ^[2] но он не создал системы многозначной логики для объяснения этого единичного замечания. До наступления 20 века более поздние логики следовали аристотелевской логике , которая включает или предполагает закон исключенного третьего .

XX век вернул идею многозначной логики. Польский логик и философ Ян Лукасевич начал создавать системы многозначной логики в 1920 году, используя третье значение, «возможное», для решения парадокса Аристотеля о морском сражении . Между тем, американский математик Эмиль Л. Пост (1921) также ввел формулировку дополнительных степеней истинности с n  ≥ 2, где n — значения истинности. Позже Ян Лукасевич и Альфред Тарский вместе сформулировали логику n истинностных значений, где n  ≥ 2. В 1932 году Ганс Райхенбах сформулировал логику многих истинностных значений, где n → ∞. Курт Гёдель в 1932 году показал, что интуиционистская логика не является логикой конечного числа значений, и определил систему логик Гёделя , промежуточную между классической и интуиционистской логикой; такие логики известны как промежуточные логики .

Примеры

Клини (сильная) K 3 и логика Священника P 3

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

Разница между двумя логиками заключается в том, как определяются тавтологии . В K3 только T является обозначенным значением истинности , тогда как в P3 и T _, и I являются таковыми (логическая формула считается тавтологией, если ее значение соответствует назначенному значению истинности) _. В логике Клини меня можно интерпретировать как «недоопределенного», не являющегося ни истинным, ни ложным, тогда как в логике Приста меня можно интерпретировать как «переопределенного», будучи одновременно истинным и ложным. К ₃ не имеет тавтологий, а Р ₃ имеет те же тавтологии, что и классическая двузначная логика. ^[4]

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

Другая логика — «внутренняя» трёхзначная логика Дмитрия Бочвара , также называемая слабой трёхзначной логикой Клини. За исключением отрицания и двуусловия, все его таблицы истинности отличаются от приведенных выше. ^[5] ${\displaystyle B_{3}^{I}}$

Промежуточное значение истинности во «внутренней» логике Бочвара можно охарактеризовать как «заразное», поскольку оно распространяется в формуле независимо от значения любой другой переменной. ^[5]

Логика Белнапа ( B 4 )

Логика Белнапа B ₄ объединяет K ₃ и P ₃ . Переопределенное значение истинности здесь обозначено как B , а недоопределенное значение истинности как N.

Гёделева логика G k и G ∞

В 1932 году Гёдель определил ^[6] семейство многозначных логик с конечным числом истинностных значений , например имеет истинностные значения и имеет . Подобным же образом он определил логику с бесконечным множеством значений истинности, в которой значениями истинности являются все действительные числа в интервале . Обозначенное значение истинности в этой логике равно 1. ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{k-1}},{\tfrac {2}{k-1}},\ldots ,{\tfrac {k-2}{k-1}},1}$ ${\displaystyle G_{3}}$ ${\displaystyle 0,{\tfrac {1}{2}},1}$ ${\displaystyle G_{4}}$ ${\displaystyle 0,{\tfrac {1}{3}},{\tfrac {2}{3}},1}$ ${\displaystyle G_{\infty }}$ ${\displaystyle [0,1]}$

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

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

Отрицание и импликация определяются следующим образом: ${\displaystyle \neg _{G}}$ ${\displaystyle {\xrightarrow[{G}]{}}}$

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

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

логики Лукасевича L v и L ∞

Импликация и отрицание были определены Яном Лукасевичем через следующие функции: ${\displaystyle {\xrightarrow[{L}]{}}}$ ${\displaystyle {\underset {L}{\neg }}}$

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

Впервые Лукасевич использовал эти определения в 1920 году для своей трехзначной логики со значениями истинности . В 1922 году он разработал логику с бесконечным числом значений , в которой значения истинности охватывали действительные числа в интервале . В обоих случаях назначенное значение истинности было 1. ^[7] ${\displaystyle L_{3}}$ ${\displaystyle 0,{\frac {1}{2}},1}$ ${\displaystyle L_{\infty }}$ ${\displaystyle [0,1]}$

Приняв значения истинности, определенные так же, как для логик Гёделя , можно создать конечнозначное семейство логик , упомянутых выше и логики , в которых значения истинности задаются рациональными числами в интервале . Набор тавтологий в и одинаков. ${\displaystyle 0,{\tfrac {1}{v-1}},{\tfrac {2}{v-1}},\ldots ,{\tfrac {v-2}{v-1}},1}$ ${\displaystyle L_{v}}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{\aleph _{0}}}$ ${\displaystyle [0,1]}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{\aleph _{0}}}$

Логика продукта Π

В логике продукта у нас есть значения истинности в интервале , конъюнкция и импликация , определяемые следующим образом ^[8] ${\displaystyle [0,1]}$ ${\displaystyle \odot }$ ${\displaystyle {\xrightarrow[{\Pi }]{}}}$

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

Кроме того, существует отрицательное обозначенное значение , обозначающее концепцию false . С помощью этого значения можно определить отрицание и дополнительный союз следующим образом: ${\displaystyle {\overline {0}}}$ ${\displaystyle {\underset {\Pi }{\neg }}}$ ${\displaystyle {\underset {\Pi }{\wedge }}}$

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

а потом . ${\displaystyle u\mathbin {\underset {\Pi }{\wedge }} v=\min\{u,v\}}$

Пост-логика P m

В 1921 году Пост определил семейство логик с (как в и ) истинностными значениями . Отрицание , конъюнкция и дизъюнкция определяются следующим образом: ${\displaystyle P_{m}}$ ${\displaystyle L_{v}}$ ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{m-1}},{\tfrac {2}{m-1}},\ldots ,{\tfrac {m-2}{m-1}},1}$ ${\displaystyle {\underset {P}{\neg }}}$ ${\displaystyle {\underset {P}{\wedge }}}$ ${\displaystyle {\underset {P}{\vee }}}$

${\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}}\\[6pt]u\mathbin {\underset {P}{\wedge }} v&:=\min\{u,v\}\\[6pt]u\mathbin {\underset {P}{\vee }} v&:=\max\{u,v\}\end{aligned}}}$

Розовая логика

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

Отношение к классической логике

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

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

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

диссертация Сушко

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

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

Классическая логика: CL = ({0,1}, ¬ , →, ∨, ∧, ↔) является функционально полной, тогда как ни одна логика Лукасевича или бесконечно многозначные логики не обладают этим свойством. ^{[11] [12]}

Мы можем определить конечно-многозначную логику как L _n ({1, 2, ..., n } ƒ ₁ , ..., ƒ _m ), где n ≥ 2 — заданное натуральное число. Пост (1921) доказывает, что если предположить, что логика способна создать функцию любой модели m ^{-го порядка, то в адекватной логике L} _n существует некоторая соответствующая комбинация связок, которая может создать модель порядка m+1 . ^[13]

Приложения

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

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

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

Международный симпозиум IEEE по многозначной логике (ISMVL) проводится ежегодно с 1970 года. Он в основном посвящен приложениям в области цифрового проектирования и проверки. ^[17] Существует также Журнал многозначной логики и мягких вычислений . ^[18]

Смотрите также

• Философский портал
• Психологический портал

Математическая логика

• Степени истины
• Нечеткая логика
• Гёдель логика
• Семизначная логика джайнов
• Клини логика
• Алгебра Клини (с инволюцией)
• Логика Лукасевича
• MV-алгебра
• Пост-логика
• Принцип бивалентности
• АН Приор
• Логика релевантности

Философская логика

• Ложная дилемма
• Му

Цифровая логика

• MVCML , многозначная логика текущего режима
• IEEE 1164 — девятизначный стандарт для VHDL.
• IEEE 1364 — четырехзначный стандарт Verilog.
• Логика трех состояний
• Логика, основанная на шуме

Рекомендации

1. Херли, Патрик. Краткое введение в логику , 9-е издание. (2006).
2. Жюль Вюймен, Необходимость или непредвиденные обстоятельства , Конспект лекций CSLI, № 56, Стэнфорд, 1996, стр. 133-167.
3. (Готвальд 2005, стр. 19)
4. Хамберстон, Ллойд (2011). Соединения . Кембридж, Массачусетс: MIT Press. стр. 201. ISBN. 978-0-262-01654-4.
5. (Бергманн 2008, стр. 80)
6. Гёдель, Курт (1932). «Zum intuitionistischen Aussagenkalkül». Anzeiger der Akademie der Wissenschaften в Вене (69): 65f.
7. Крейзер, Лотар; Готвальд, Зигфрид; Стельцнер, Вернер (1990). Нихтклассическая логика. Эйне Эйнфюрунг . Берлин: Академия-Верлаг. стр. 41–45 и далее. ISBN 978-3-05-000274-3.
8. Хаек, Петр: Нечеткая логика . В: Эдвард Н. Залта: Стэнфордская энциклопедия философии , весна 2009 г. ([1]).
9. Роуз, Алан (декабрь 1951 г.). «Логические системы, истинностные значения которых образуют решетки». Математические Аннален . 123 : 152–165. дои : 10.1007/BF02054946. S2CID  119735870.
10. Смит, Николас (2012). Логика: Законы истины . Издательство Принстонского университета. п. 124.
11. Малиновский, Гжегож (1993). Многозначная логика . Кларендон Пресс. стр. 26–27.
12. Черч, Алонзо (1996). Введение в математическую логику. Издательство Принстонского университета. ISBN 978-0-691-02906-1.
13. Пост, Эмиль Л. (1921). «Введение в общую теорию элементарных предложений». Американский журнал математики . 43 (3): 163–185. дои : 10.2307/2370324. hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN  0002-9327. JSTOR  2370324.
14. Дуброва, Елена (2002). Синтез и оптимизация многозначной логики, Хассун С. и Сасао Т., редакторы, Логический синтез и проверка , Kluwer Academic Publishers, стр. 89-114.
15. Мехер, Прамод Кумар; Вальс, Хавьер; Хуанг, Цо-Бинг; Шридхаран, К.; Махаратна, Кошик (22 августа 2008 г.). «50 лет CORDIC: алгоритмы, архитектуры и приложения» (PDF) . Транзакции IEEE в схемах и системах I: Регулярные статьи . 56 (9) (опубликовано 9 сентября 2009 г.): 1893–1907. дои : 10.1109/TCSI.2009.2025803. S2CID  5465045. Архивировано (PDF) из оригинала 9 октября 2022 года . Проверено 3 января 2016 г.
16. Абрамович, Мирон; Брейер, Мелвин А.; Фридман, Артур Д. (1994). Тестирование цифровых систем и тестируемое проектирование . Нью-Йорк: Computer Science Press. п. 183. ИСБН 978-0-7803-1062-9.
17. «Международный симпозиум IEEE по многозначной логике (ISMVL)» . www.informatik.uni-trier.de/~ley .
18. "Дом MVLSC" . Архивировано из оригинала 15 марта 2014 года . Проверено 12 августа 2011 г.

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

Общий

• Аугусто, Луис М. (2017). Многозначная логика: математическое и вычислительное введение. Лондон: Публикации колледжа. 340 страниц. ISBN 978-1-84890-250-3 . Веб-страница 
• Безио Ж.-Ю. (1997), Что такое многозначная логика? Труды 27-го Международного симпозиума по многозначной логике , Компьютерное общество IEEE, Лос-Аламитос, стр. 117–121.
• Малиновский, Грегорц (2001), « Многозначная логика», в издании Гобла Лу, « Руководство Блэквелла по философской логике» . Блэквелл.
• Бергманн, Мерри (2008), Введение в многозначную и нечеткую логику: семантика, алгебры и системы вывода , Cambridge University Press, ISBN 978-0-521-88128-9
• Чиньоли, РЛО, Д'Оттавиано, И, МЛ , Мундичи, Д. (2000). Алгебраические основы многозначных рассуждений . Клювер.
• Малиновский, Гжегож (1993). Многозначная логика . Кларендон Пресс. ISBN 978-0-19-853787-8.
• Готвальд С. Трактат о многозначной логике. Исследования по логике и вычислениям, том. 9, Research Studies Press: Бэлдок, Хартфордшир, Англия, 2001.
• Готвальд, Зигфрид (2005). «Многозначная логика» (PDF) . Архивировано из оригинала 3 марта 2016 года. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )CS1 maint: bot: original URL status unknown (link)
• Миллер, Д. Майкл; Торнтон, Митчелл А. (2008). Многозначная логика: понятия и представления . Обобщающие лекции по цифровым схемам и системам. Том. 12. Издательство Морган и Клейпул. ISBN 978-1-59829-190-2.
• Гайек П. , (1998), Метаматематика нечеткой логики . Клювер. (Нечеткая логика понимается как многозначная логика sui Generis .)

Специфический

• Александр Зиновьев , Философские проблемы многозначной логики , Издательство Д. Рейделя, 169 стр., 1963.
• Прайор А. 1957, Время и модальность. Издательство Оксфордского университета , на основе его лекций Джона Локка 1956 года.
• Гоген Дж. А. 1968/69, Логика неточных понятий , Synthese, 19, 325–373.
• Чанг CC и Кейслер HJ 1966. Теория непрерывных моделей , Принстон, Издательство Принстонского университета.
• Герла Г. 2001, Нечеткая логика: математические инструменты для приближенного рассуждения , Kluwer Academic Publishers, Дордрехт.
• Новак В., Перфильева И., Мочкорж Ю. (1999), Математические основы нечеткой логики. Клювер, Бостон.
• Павелка Дж. 1979, О нечеткой логике I: Многозначные правила вывода , Zeitschr. ф. математика. Logik und Grundlagen d. Матем., 25, 45–52.
• Меткалф, Джордж; Оливетти, Никола; Дов М. Габбай (2008). Теория доказательств для нечеткой логики . Спрингер. ISBN 978-1-4020-9408-8.Охватывает также теорию доказательств многозначных логик в традиции Гаека.
• Хэнле, Райнер (1993). Автоматизированный вывод в многозначной логике . Кларендон Пресс. ISBN 978-0-19-853989-6.
• Азеведо, Франциско (2003). Решение ограничений в многозначной логике: приложение к цифровым схемам . ИОС Пресс. ISBN 978-1-58603-304-0.
• Болк, Леонард; Боровик, Петр (2003). Многозначная логика 2: Автоматизированные рассуждения и практические приложения . Спрингер. ISBN 978-3-540-64507-8.
• Станкович, Радомир С.; Астола, Яакко Т.; Морага, Клаудио (2012). Представление функций многозначной логики . Издательство Морган и Клейпул. doi : 10.2200/S00420ED1V01Y201205DCS037. ISBN 978-1-60845-942-1.
• Абрамович, Мирон; Брейер, Мелвин А.; Фридман, Артур Д. (1994). Тестирование цифровых систем и тестируемое проектирование . Нью-Йорк: Computer Science Press. ISBN 978-0-7803-1062-9.

Внешние ссылки

• Готвальд, Зигфрид (2022). «Многозначная логика». В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии (выпуск лета 2022 г.) .
• Шрамко, Ярослав и Вансинг, Генрих (2021). «Истинные ценности». В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии (зимнее издание 2021 г.) .
• Технический комитет IEEE Computer Society по многозначной логике
• Ресурсы по многозначной логике, Райнер Хэнле, Университет Чалмерса
• Сервер Многозначной Логики W3 (в архиве)
• Ярослав Шрамко; Генрих Вансинг (2020). «Диссертация Сушко». Стэнфордская энциклопедия философии .
• Карлос Калейро, Вальтер Карниелли, Марсело Э. Конильо и Жоао Маркос, Компания Two: «Обман многих логических ценностей» в Жан-Иве Безио, изд. (2007). Logica Universalis: К общей теории логики (2-е изд.). Springer Science & Business Media. стр. 174–194. ISBN 978-3-7643-8354-1.