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

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

История

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

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

Примеры

Основные статьи: Трехзначная логика , Четырехзначная логика и Девятизначная логика.

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

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

¬   Т Ф я я Ф Т

∧ Т я Ф Т Т я Ф я я я Ф Ф Ф Ф Ф

∨ Т я Ф Т Т Т Т я Т я я Ф Т я Ф

→ K Т я Ф Т Т я Ф я Т я я Ф Т Т Т

↔ К Т я Ф Т Т я Ф я я я я Ф Ф я Т

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

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

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

∧ + Т я Ф Т Т я Ф я я я я Ф Ф я Ф

∨ + Т я Ф Т Т я Т я я я я Ф Т я Ф

→ + Т я Ф Т Т я Ф я я я я Ф Т я Т

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

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

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

f ¬   Т Ф Б Б Н Н Ф Т

f ∧ Т Б Н Ф Т Т Б Н Ф Б Б Б Ф Ф Н Н Ф Н Ф Ф Ф Ф Ф Ф

f ∨ Т Б Н Ф Т Т Т Т Т Б Т Б Т Б Н Т Т Н Н Ф Т Б Н Ф

Гёделевские логики G _k и G _∞

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

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

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

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

${\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 _∞

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

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

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

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

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

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

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

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

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

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

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

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

${\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 году Алан Роуз определил другое семейство логик для систем, истинностные значения которых образуют решетки .

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

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

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

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

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

Смотрите также: Принцип бивалентности § диссертация Сушко

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

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

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

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

Приложения

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

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

Исследовательские центры

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

См. также

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

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

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

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

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

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

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

Общий

• Аугусто, Луис М. (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: исходный статус URL неизвестен ( ссылка )
• Миллер, Д. Майкл; Торнтон, Митчелл А. (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). Представление функций многозначной логики . Издательство Морган и Клейпул. дои : 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). «Диссертация Сушко» . Стэнфордская энциклопедия философии .
• Карлос Калейру, Вальтер Карниелли, Марсело Э. Конильо и Жоао Маркос, Компания Два: «Обман многих логических ценностей» в Жан-Ив Безио, изд. (2007). Logica Universalis: К общей теории логики (2-е изд.). Springer Science & Business Media. стр. 100-1 174–194. ISBN  978-3-7643-8354-1 .