Алгебра Де Моргана - Википедия - De Morgan algebra

В математика, а Алгебра де Моргана (названный в честь Огастес Де Морган, британский математик и логик) представляет собой структуру А = (A, ∨, ∧, 0, 1, ¬) такое, что:

В алгебре Де Моргана законы

не всегда держат. При наличии законов Де Моргана один из законов подразумевает другой, и алгебра, которая им удовлетворяет, становится Булева алгебра.

Замечание: Отсюда следует, что ¬ (x ∨ y) = ¬x ∧ ¬y, ¬1 = 0 и ¬0 = 1 (например, ¬1 = ¬1 ∨ 0 = ¬1 ∨ ¬¬0 = ¬ (1 ∧ ¬0 ) = ¬¬0 = 0). Таким образом, ¬ является двойственным автоморфизм.

Если вместо этого решетка определяется в терминах порядка, то есть (A, ≤) является ограниченным частичным порядком с наименьшей верхней границей и наибольшей нижней границей для каждой пары элементов, а операции соединения и соединения, определенные таким образом, удовлетворяют закону распределения , то дополнение также можно определить как инволютивный антиавтоморфизм, то есть структуру А = (A, ≤, ¬) такое, что:

Алгебры Де Моргана были введены Григоре Моисил[1][2] около 1935 г.[2] хотя без ограничения наличия 0 и 1.[3] Тогда их по-разному называли квазибулевы алгебры в польской школе, например к Расиова а также распределительный я-решетки к Дж. А. Кальман.[2] (я-решетка, являющаяся аббревиатурой от решетки с инволюцией.) Они были дополнительно изучены в аргентинской школе алгебраической логики. Антонио Монтейро.[1][2]

Алгебры Де Моргана важны для изучения математических аспектов нечеткая логика. Стандартная нечеткая алгебра F = ([0, 1], макс (Икс, у), мин (Икс, у), 0, 1, 1 − Икс) является примером алгебры Де Моргана, в которой не выполняются законы исключенного среднего и непротиворечивости.

Другой пример Данн 4-значная логика, в которой ложный < ни-правда-ни-ложь < истинный и ложный < и-правда-и-ложь < истинный, пока ни-правда-ни-ложь и и-правда-и-ложь несопоставимы.[2]

Клини алгебра

Если алгебра Де Моргана дополнительно удовлетворяет Икс ∧ ¬Икс ≤ у ∨ ¬у, это называется Клини алгебра.[1][3] (Это понятие не следует путать с другим Клини алгебра обобщающие регулярные выражения.) Это понятие также называют нормальный я-решетка пользователя Kalman.

Примеры алгебр Клини в определенном выше смысле включают: решеточно-упорядоченные группы, Посталгебры и Алгебры Лукасевича.[3] Булевы алгебры также соответствуют этому определению алгебры Клини. Простейшая алгебра Клини, не являющаяся булевой, - это алгебра Клини. трехзначная логика K3.[4] K3 впервые появился в Клини с Об обозначениях для порядковые номера (1938).[5] Алгебра была названа в честь Клини Бриньоле и Монтейро.[6]

Связанные понятия

Алгебры Де Моргана - не единственный возможный способ обобщения булевых алгебр. Другой способ - сохранить ¬Икс ∧ Икс = 0 (т.е. закон непротиворечия), но отбросить закон исключенной середины и закон двойного отрицания. Этот подход (названный полудополнение) корректно определено даже для (встречи) полурешетка; если набор полудополнений имеет величайший элемент это обычно называется псевдодополнение. Если псевдодополнение удовлетворяет закону исключенного третьего, результирующая алгебра также булева. Однако если бы только более слабый закон ¬Икс ∨ ¬¬Икс = 1 требуется, это приводит к Каменные алгебры.[1] В более общем смысле алгебры Де Моргана и Стоуна являются собственными подклассами Алгебры Оккама.

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

Рекомендации

  1. ^ а б c d Blyth, T. S .; Варле, Дж. К. (1994). Алгебры Оккама. Издательство Оксфордского университета. стр.4 –5. ISBN  978-0-19-859938-8.CS1 maint: ref = harv (связь)
  2. ^ а б c d е Безио, Жан-Ив (2012). «История истинных ценностей». В Габбае, Дов М .; Пеллетье, Фрэнсис Джеффри; Вудс, Джон (ред.). Логика: история ее центральных понятий. Северная Голландия (отпечаток Эльзевьера). С. 280–281. ISBN  978-0-08-093170-8.CS1 maint: ref = harv (связь)
  3. ^ а б c Чиньоли, Роберто (1975). "Инъективные алгебры де Моргана и Клини" (PDF). Труды Американского математического общества. 47 (2): 269–278. Дои:10.1090 / S0002-9939-1975-0357259-4. JSTOR  2039730.CS1 maint: ref = harv (связь)
  4. ^ Каарли, Калле; Пиксли, Олден Ф. (21 июля 2000 г.). Полиномиальная полнота в алгебраических системах. CRC Press. С. 297–. ISBN  978-1-58488-203-9.
  5. ^ Клини, С. (1938). «Об обозначении порядковых чисел». Журнал символической логики. 3 (4): 150–155. Дои:10.2307/2267778. JSTOR  2267778.
  6. ^ Brignole, D .; Монтейро, А. (1964). "Характеризация жизни Нельсона по принципу равенства". Notas de Logica Matematica. Instituto de Matematica Universidad del sur Bahia Blanca. 20. Версия этой статьи (возможно, сокращенная) появилась позже в Труды Японской академии: "Характеризация algèbres de Nelson par des egalités, I". Дои:10.3792 / pja / 1195521624, Цитировать журнал требует | журнал = (помощь) "Характеризация algèbres de Nelson par des egalités, II". Дои:10.3792 / pja / 1195521625. Цитировать журнал требует | журнал = (помощь)

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

  • Бальбес, Раймонд; Двинджер, Филипп (1975). «Глава IX. Алгебры Де Моргана и алгебры Лукасевича». Распределительные решетки. Университет Миссури Пресс. ISBN  978-0-8262-0163-8.
  • Биркгоф, Г. (1936). "Отзывы: Moisil Gr. C .. Recherches sur l'algèbre de la logique. Научные Анналы университета Яссы, т. 22 (1936), стр. 1–118". Журнал символической логики. 1 (2): 63. Дои:10.2307/2268551. JSTOR  2268551.
  • Батыршин, И. (1990). «О фаззинестических мерах энтропии на алгебрах Клини». Нечеткие множества и системы. 34 (1): 47–60. Дои:10.1016 / 0165-0114 (90) 90126-Q.
  • Кальман, Дж. А. (1958). «Решетки с инволюцией» (PDF). Труды Американского математического общества. 87 (2): 485–491. Дои:10.1090 / S0002-9947-1958-0095135-X. JSTOR  1993112.
  • Пальяни, Пьеро; Чакраборти, Михир (2008). Геометрия приближения: грубая теория множеств: логика, алгебра и топология концептуальных паттернов. Springer Science & Business Media. Часть II. Глава 6. Основные логико-алгебраические структуры, стр. 193–210. ISBN  978-1-4020-8622-9.
  • Каттанео, Дж .; Чуччи, Д. (2009). Решетки с внутренними операторами и операторами замыкания и абстрактные аппроксимационные пространства. Конспект лекций по информатике 67–116. Дои:10.1007/978-3-642-03281-3_3.
  • Герке, М.; Уокер, С .; Уокер, Э. (2003). «Нечеткая логика, возникающая из строгих систем Де Моргана». In Rodabaugh, S.E .; Клемент, Э. П. (ред.). Топологические и алгебраические структуры в нечетких множествах: Справочник последних достижений в математике нечетких множеств. Springer. ISBN  978-1-4020-1515-1.
  • Далла Кьяра, Мария Луиза; Джунтини, Роберто; Гречи, Ричард (2004). Рассуждения в квантовой теории: резкая и нечеткая квантовая логика. Springer. ISBN  978-1-4020-1978-4.