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

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

История [ править ]

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

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

Примеры [ править ]

Клини (сильный) K ₃ и Priest logic P ₃ [ править ]

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

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

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

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

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

Логика Belnap ( B ₄ ) [ править ]

Логика Белнапа B ₄ объединяет K ₃ и P ₃ . Значение сверхдетерминированной истины здесь обозначаются как B и недоопределённое значение истинности как N .

Гёделевские логики G _k и G _∞ [ править ]

В 1932 г. Гёдель определил ^[5] семейство многозначных логик с конечным числом значений истинности , например, имеет значения истинности и имеет . Подобным образом он определил логику с бесконечным множеством значений истинности , в которой значения истинности - это все действительные числа в интервале . Обозначенное значение истинности в этих логиках равно 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 \ клин}$${\ displaystyle \ vee}$

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

Отрицание и импликация определяются следующим образом:${\ 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}}\\u{\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{\xrightarrow[{L}]{}}v&:=\min\{1,1-u+v\}\end{aligned}}}$

Впервые Лукасевич использовал это определение в 1920 году для своей трехзначной логики со значениями истинности . В 1922 году он разработал логику с бесконечным числом значений , в которой значения истинности охватывали действительные числа в интервале . В обоих случаях обозначенное значение истинности было 1. ^[6]${\displaystyle L_{3}}$${\displaystyle 0,{\tfrac {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}}}$

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

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

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

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

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

Пост логики 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}}\\u{\underset {P}{\wedge }}v&:=\min\{u,v\}\\u{\underset {P}{\vee }}v&:=\max\{u,v\}\end{aligned}}}$

Роза логика [ править ]

В 1951 году Алан Роуз определил другое семейство логик для систем, истинностные значения которых образуют решетки. (« Логические системы, истинностные значения которых образуют решетки », Math. Annalen, том 123, декабрь 1951 г., стр. 152–165; источник ).

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

Семантика матриц (логические матрицы) [ править ]

См. Логическую матрицу

Отношение к классической логике [ править ]

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

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

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

Диссертация Сушко [ править ]

Функциональная полнота многозначной логики [ править ]

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

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

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

Приложения [ править ]

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

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

Место проведения исследований [ править ]

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

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

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

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

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

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

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

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

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

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

Общий

• Аугусто, Луис М. (2017). Многозначная логика: математическое и вычислительное введение. Лондон: Публикации колледжа. 340 страниц. ISBN 978-1-84890-250-3 . Страница в Интернете 
• Béziau J.-Y. (1997), Что такое многозначная логика? Материалы 27-го Международного симпозиума по многозначной логике , Компьютерное общество IEEE, Лос-Аламитос, стр. 117–121.
• Малиновский, Грегор, (2001), Многозначная логика, в Гобле, Лу, изд., Блэквелл: Руководство по философской логике . Блэквелл.
• Бергманн, Мерри (2008), Введение в многозначную и нечеткую логику: семантика, алгебры и системы вывода , Cambridge University Press, ISBN 978-0-521-88128-9
• Cignoli, RLO, D'Ottaviano, I, ML , Mundici, D., (2000). Алгебраические основы многозначного мышления . Kluwer.
• Малиновский, Гжегож (1993). Многозначная логика . Кларендон Пресс. ISBN 978-0-19-853787-8.
• С. Готвальда , Трактат о многозначных логик. Исследования в области логики и вычислений, т. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.
• Готвальд, Зигфрид (2005). «Многозначная логика» (PDF) . Архивировано 03 марта 2016 года. Cite journal requires |journal= (help)CS1 maint: bot: original URL status unknown (link)
• Миллер, Д. Майкл; Торнтон, Митчелл А. (2008). Многозначная логика: концепции и представления . Синтез лекций по цифровым схемам и системам. 12 . Издатели Morgan & Claypool. ISBN 978-1-59829-190-2.
• Хайек П. , (1998), Метаматематика нечеткой логики . Kluwer. (Нечеткая логика понимается как многозначная логика sui generis .)

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

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

Внешние ссылки [ править ]

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