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

Пропозициональное исчисление, в котором существует более двух значений истинности

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

История

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

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

Примеры

Клин (крепкий)К 3и логика священникаП 3

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

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

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

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

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

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

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

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

В 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}}}$

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

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

Ян Лукасевич определил импликацию и отрицание посредством следующих функций: ${\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\}}$

Логика постовП м

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

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

Научно-исследовательские центры

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

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

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

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

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

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

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

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

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

Ссылки

1. Херли, Патрик. Краткое введение в логику , 9-е издание. (2006).
2. Жюль Вюйемен, Необходимость или случайность , CSLI Lecture Notes, N°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. Hajek, Petr: Fuzzy Logic . В: Edward N. Zalta: The Stanford Encyclopedia of Philosophy , весна 2009. ([1])
9. Роуз, Алан (декабрь 1951 г.). «Системы логики, истинностные значения которых образуют решетки». Mathematische Annalen . 123 : 152–165. doi :10.1007/BF02054946. S2CID  119735870.
10. Смит, Николас (2012). Логика: Законы Истины . Princeton University Press. стр. 124.
11. Malinowski, Grzegorz (1993). Многозначные логики . Clarendon Press. С. 26–27.
12. Чёрч, Алонзо (1996). Введение в математическую логику. Princeton University Press. ISBN 978-0-691-02906-1.
13. Пост, Эмиль Л. (1921). «Введение в общую теорию элементарных предложений». American Journal of Mathematics . 43 (3): 163–185. doi :10.2307/2370324. hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN  0002-9327. JSTOR  2370324.
14. Дуброва, Елена (2002). Синтез и оптимизация многозначной логики, в Hassoun S. и Sasao T., редакторы, Логический синтез и проверка , Kluwer Academic Publishers, стр. 89-114
15. Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (22 августа 2008 г.). "50 Years of CORDIC: Algorithms, Architectures and Applications" (PDF) . IEEE Transactions on Circuits & Systems I: Regular Papers . 56 (9) (опубликовано 9 сентября 2009 г.): 1893–1907. doi :10.1109/TCSI.2009.2025803. S2CID  5465045. Архивировано (PDF) из оригинала 9 октября 2022 г. . Получено 3 января 2016 г. .
16. Абрамовичи, Мирон; Брейер, Мелвин А.; Фридман, Артур Д. (1994). Тестирование цифровых систем и проверяемое проектирование . Нью-Йорк: Computer Science Press. стр. 183. ISBN 978-0-7803-1062-9.
17. "Международный симпозиум IEEE по многозначной логике (ISMVL)". www.informatik.uni-trier.de/~ley .
18. "MVLSC home". Архивировано из оригинала 15 марта 2014 г. Получено 12 августа 2011 г.

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

Общий

• Аугусто, Луис М. (2017). Многозначная логика: математическое и вычислительное введение. Лондон: College Publications. 340 страниц. ISBN 978-1-84890-250-3 . Веб-страница 
• Béziau J.-Y. (1997), Что такое многозначная логика? Труды 27-го Международного симпозиума по многозначной логике , IEEE Computer Society, Лос-Аламитос, стр. 117–121.
• Малиновский, Грегорц, (2001), Многозначные логики, в книге Гобла, Лу, ред., «Руководство Блэквелла по философской логике» . Блэквелл.
• Бергманн, Мерри (2008), Введение в многозначную и нечеткую логику: семантика, алгебры и системы вывода , Cambridge University Press, ISBN 978-0-521-88128-9
• Чиньоли, РЛО, Д'Оттавиано, И, МЛ , Мундичи, Д. (2000). Алгебраические основы многозначных рассуждений . Клювер.
• Малиновский, Гжегож (1993). Многозначные логики . Clarendon Press. ISBN 978-0-19-853787-8.
• S. Gottwald , Трактат о многозначных логиках. Исследования по логике и вычислениям, т. 9, Research Studies Press: Baldock, Хартфордшир, Англия, 2001.
• Готвальд, Зигфрид (2005). "Многозначные логики" (PDF) . Архивировано из оригинала 3 марта 2016 г. {{cite journal}}: Цитировать журнал требует |journal=( помощь )CS1 maint: bot: original URL status unknown (link)
• Миллер, Д. Майкл; Торнтон, Митчелл А. (2008). Многозначная логика: концепции и представления . Лекции по синтезу цифровых схем и систем. Том 12. Издательство Morgan & Claypool. ISBN 978-1-59829-190-2.
• Hájek P. , (1998), Метаматематика нечеткой логики . Kluwer. (Нечеткая логика понимается как многозначная логика sui generis .)

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

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

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

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