Многозначная логика - Many-valued logic

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

История

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

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

Примеры

Клини (сильная) К 3 и логика Жреца P 3

Клини «ы„(сильная) логика неопределенности“ К 3 (иногда ) и Priest » s „логика парадокса“ добавить третий „неопределенную“ или значение истинности „неопределенной“ I . Функции истинности для отрицания (¬), конъюнкции (∧), дизъюнкции (∨), импликации (K) и двусмысленный (K) даются:

¬  
Т F
я я
F Т
Т я F
Т Т я F
я я я F
F F F F
Т я F
Т Т Т Т
я Т я я
F Т я F
K Т я F
Т Т я F
я Т я я
F Т Т Т
K Т я F
Т Т я F
я я я я
F F я Т

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

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

Другая логика - «внутренняя» трехзначная логика Дмитрия Бочвара , также называемая слабой трехзначной логикой Клини. За исключением отрицания и двусмысленности, все его таблицы истинности отличаются от приведенных выше.

+ Т я F
Т Т я F
я я я я
F F я F
+ Т я F
Т Т я Т
я я я я
F Т я F
+ Т я F
Т Т я F
я я я я
F Т я Т

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

Логика Belnap ( B 4 )

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

f ¬  
Т F
B B
N N
F Т
f Т B N F
Т Т B N F
B B B F F
N N F N F
F F F F F
f Т B N F
Т Т Т Т Т
B Т B Т B
N Т Т N N
F Т B N F

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

В 1932 году Гёдель определил семейство многозначных логик с конечным числом значений истинности , например, имеет значения истинности и имеет . Подобным образом он определил логику с бесконечным множеством значений истинности , в которой значения истинности - это все действительные числа в интервале . Обозначенное значение истинности в этих логиках равно 1.

Конъюнкция и дизъюнкция определяются соответственно как минимум и максимум операндов:

Отрицание и импликация определяются следующим образом:

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

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

Импликация и отрицание были определены Яном Лукасевичем через следующие функции:

Впервые Лукасевич использовал эти определения в 1920 году для своей трехзначной логики со значениями истинности . В 1922 году он разработал логику с бесконечным числом значений , в которой значения истинности охватывали действительные числа в интервале . В обоих случаях обозначенное значение истинности было 1.

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

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

В логике продукта у нас есть значения истинности в интервале , конъюнкции и импликации , определяемые следующим образом

Кроме того, имеется отрицательное обозначенное значение , обозначающее понятие ложного . Через это значение можно определить отрицание и дополнительную конъюнкцию следующим образом:

а потом .

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

В 1921 году Пост определил семейство логик со значениями истинности (как в и ) . Отрицание, союз и дизъюнкция определяются следующим образом:

Роза логика

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

Семантика

Семантика матриц (логические матрицы)

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

Площадки для исследований

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

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

Математическая логика
Философская логика
Цифровая логика

использованная литература

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

Общий

  • Аугусто, Луис М. (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) . Архивировано 3 марта 2016 года. Цитировать журнал требует |journal=( помощь )CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
  • Миллер, Д. Майкл; Торнтон, Митчелл А. (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.

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