Введение
Предложная логика, в которой используется более двух истинностных значений.
Многозначная логика (также поливалентная или множественнозначная логика) — это предложная логика, в которой используется более двух истинностных значений. Традиционно, в логическом исчислении Аристотеля, для любого высказывания существовало только два возможных значения (то есть "истина" и "ложь"). Классическая двухзначная логика может быть расширена до n-значной логики при n больше 2. Наиболее распространенными в литературе являются трехзначные (например, логики Лукасевича и Клини, принимающие значения "истина", "ложь" и "неопределенность"), четырехзначные, девятизначные, конечнозначные (с конечным числом значений) с более чем тремя значениями, и бесконечнозначные (с бесконечным числом значений), такие как нечеткая логика и вероятностная логика.
История
Неправильно считать, что первым известным классическим логиком, не принявшим в полной мере закон исключённого третьего, был Аристотель (который, иронично, обычно считается первым классическим логиком и "отцом [двухзначной] логики"). Фактически, Аристотель не оспаривал универсальность закона исключённого третьего, а универсальность принципа бивалентности: он признал, что этот принцип не всегда применим к будущим событиям (De Interpretatione, гл. IX), но не создал систему многозначной логики для объяснения этого отдельного замечания. Вплоть до начала XX века последующие логики придерживались аристотелевской логики, которая включает или предполагает закон исключённого третьего. В XX веке идея многозначной логики была возрождена. Польский логик и философ Ян Лукасевич начал разрабатывать системы многозначной логики в 1920 году, используя третье значение – "возможное" – для решения парадокса Аристотеля о морском сражении. В то же время американский математик Эмиль Л. Пост (1921) также предложил формулировку дополнительных степеней истинности с n ≥ 2, где n – количество значений истинности. Позднее Ян Лукасевич и Альфред Тарский совместно сформулировали логику на n значениях истинности, где n ≥ 2. В 1932 году Ганс Райхенбах сформулировал логику многих значений истинности, где n → ∞. Курт Гёдель в 1932 году показал, что интуиционистская логика не является многозначной с конечным числом значений, и определил систему логик Гёделя, промежуточную между классической и интуиционистской логикой; такие логики известны как промежуточные логики.
Пост логики Pm
В 1921 году Пост определил семейство логик с (как в и ) значениями истинности. Отрицание и конъюнкция, и дизъюнкция определяются следующим образом:
Розовая логика
В 1951 году Алан Роуз определил другое семейство логик для систем, значения истинности которых образуют решетки.
Связь с классической логикой
Логики обычно представляют собой системы, предназначенные для кодификации правил сохранения некоторого семантического свойства высказываний при преобразованиях. В классической логике это свойство – "истинность". В корректном аргументе истинность выведенного высказывания гарантируется, если все посылки истинны, поскольку применение корректных шагов сохраняет это свойство. Однако это свойство не обязательно должно быть именно "истинностью"; оно может быть иным понятием. Многозначные логики предназначены для сохранения свойства обозначенности (или быть обозначенным). Поскольку существует более двух истинностных значений, правила вывода могут быть направлены на сохранение не только тех, которые соответствуют (в соответствующем смысле) истинности. Например, в трехзначной логике иногда обозначаются два наибольших истинностных значения (если они представлены, например, положительными целыми числами), и правила вывода сохраняют эти значения. В точности, корректный аргумент будет таким, что значение посылок, рассматриваемых совместно, всегда будет меньше или равно значению заключения. Например, сохраняемым свойством может быть обоснованность – основополагающее понятие интуиционистской логики. Таким образом, высказывание не истинно или ложно; вместо этого оно обосновано или несостоятельно. Ключевое различие между обоснованностью и истинностью в данном случае заключается в том, что закон исключённого третьего не выполняется: высказывание, которое не является несостоятельным, не обязательно обосновано; скорее, просто не доказано, что оно несостоятельно. Ключевое различие заключается в определённости сохраняемого свойства: можно доказать, что P обосновано, что P несостоятельно, или оказаться неспособным доказать ни то, ни другое. Корректный аргумент сохраняет обоснованность при преобразованиях, поэтому высказывание, выведенное из обоснованных высказываний, остаётся обоснованным. Однако в классической логике существуют доказательства, зависящие от закона исключённого третьего; поскольку этот закон неприменим в рамках данной схемы, существуют высказывания, которые невозможно доказать таким образом.
Функциональная полнота многозначных логик
Функциональная полнота — термин, используемый для описания специального свойства конечных логик и алгебр. Совокупность связок логики считается функционально полной или адекватной, если и только если с помощью этой совокупности связок можно построить формулу, соответствующую каждой возможной булевой функции. Адекватная алгебра — это такая, в которой любое конечное отображение переменных может быть выражено некоторой композицией её операций. Классическая логика: CL = ({0,1}, ¬, →, ∨, ∧, ↔) функционально полна, в то время как никакая логика Лукасевича или бесконечнозначная логика не обладает этим свойством. Конечную многозначную логику можно определить как Ln ({1, 2, ..., n}, ƒ1, ..., ƒm), где n ≥ 2 — заданное натуральное число. Пост (1921) доказывает, что если логика способна породить функцию любой модели порядка m, то существует соответствующая комбинация связок в адекватной логике Ln, которая может породить модель порядка m+1.
Приложения
Известные применения многозначной логики можно приблизительно классифицировать на две группы. Первая группа использует многозначную логику для более эффективного решения бинарных задач. Например, хорошо известный подход к представлению булевой функции с множественным выходом заключается в рассмотрении её выходной части как одной многозначной переменной и преобразовании её в единственную выходную характеристическую функцию (в частности, индикаторную функцию). Другие применения многозначной логики включают проектирование программируемых логических матриц (ПЛМ) с входными декодерами, оптимизацию конечных автоматов, тестирование и верификацию. Вторая группа направлена на разработку электронных схем, использующих более двух дискретных уровней сигналов, таких как многозначные памяти, арифметические схемы и полевые программируемые вентильные матрицы (ПЛИС). Многозначные схемы обладают рядом теоретических преимуществ по сравнению со стандартными двоичными схемами. Например, можно уменьшить количество межсоединений внутри и вне кристалла, если сигналы в схеме принимают четыре или более уровней, а не только два. В конструкции памяти хранение двух, а не одного бита информации на ячейку памяти удваивает плотность памяти при том же размере кристалла. Приложения, использующие арифметические схемы, часто выигрывают от использования альтернатив двоичным системам счисления. Например, остаточные и избыточные системы счисления могут уменьшить или устранить распространение переноса, возникающее при обычном двоичном сложении или вычитании, что приводит к высокоскоростным арифметическим операциям. Эти системы счисления имеют естественную реализацию с использованием многозначных схем. Однако практическая ценность этих потенциальных преимуществ во многом зависит от наличия схемотехнических решений, которые должны быть совместимы или конкурентоспособны с современными стандартными технологиями. Помимо помощи в проектировании электронных схем, многозначная логика широко используется для тестирования схем на наличие неисправностей и дефектов. Практически все известные алгоритмы автоматической генерации тестовых наборов (ATG), используемые для тестирования цифровых схем, требуют симулятора, способного обрабатывать 5-значную логику (0, 1, x, D, D'). Дополнительные значения – x, D и D' – представляют собой (1) неизвестное/неинициализированное состояние, (2) 0 вместо 1 и (3) 1 вместо 0.
Места проведения исследований
Международный симпозиум IEEE по многозначной логике (ISMVL) проводится ежегодно с 1970 года. Он в основном ориентирован на области применения в цифровом проектировании и верификации. Также существует журнал, посвященный многозначной логике и мягким вычислениям.