Алгебра Моргана
В математике алгебра Де Моргана (названная в честь Огастеса Де Моргана , британского математика и логика) — это структура A = (A, ∨, ∧, 0, 1, ¬), такая что:
- ( A , ∨, ∧, 0, 1) — ограниченная дистрибутивная решетка и
- ¬ является инволюцией Де Моргана: ¬( x ∧ y ) = ¬ x ∨ ¬ y и ¬¬ x = x . (т.е. инволюция , которая дополнительно удовлетворяет законам Де Моргана )
В алгебре Де Моргана действуют законы
- ¬ x ∨ x = 1 ( закон исключенного третьего ), и
- ¬ x ∧ x = 0 ( закон непротиворечия )
не всегда держится. При наличии законов Де Моргана один закон влечет за собой другой, и алгебра, удовлетворяющая им, становится булевой алгеброй .
Замечание: Отсюда следует, что ¬(x ∨ y) = ¬x ∧ ¬y, ¬1 = 0 и ¬0 = 1 (например, ¬1 = ¬1 ∨ 0 = ¬1 ∨ ¬¬0 = ¬(1 ∧ ¬0 ) = ¬¬0 = 0). Таким образом, ¬ является двойственным автоморфизмом ( A , ∨, ∧, 0, 1).
Если вместо этого решетка определена в терминах порядка, т. е. (A, ≤) является ограниченным частичным порядком с наименьшей верхней границей и наибольшей нижней границей для каждой пары элементов, а определенные таким образом операции встречи и соединения удовлетворяют дистрибутивному закону , то дополнение также можно определить как инволютивный антиавтоморфизм, то есть структуру A = (A, ≤, ¬) такую, что:
- (A, ≤) — ограниченная дистрибутивная решетка и
- ¬¬ x = x и
- Икс ≤ y → ¬ y ≤ ¬ x .
Алгебры де Моргана были введены Григоре Мойсилом. [1] [2] около 1935 года, [2] хотя и без ограничения наличия 0 и 1. [3] они тогда по-разному назывались квазибулевыми алгебрами В польской школе , например, Расёвой , а также дистрибутивными i -решетками Калманом Я. А. . [2] ( i -решетка является аббревиатурой решетки с инволюцией.) В дальнейшем они изучались в аргентинской школе алгебраической логики Антонио Монтейро . [1] [2]
Алгебры де Моргана важны для изучения математических аспектов нечеткой логики . Стандартная нечеткая алгебра F = ([0, 1], max( x , y ), min( x , y ), 0, 1, 1 − x ) является примером алгебры Де Моргана, в которой действуют законы исключенного среднего и непротиворечивость не имеет места.
Другим примером является T четырехзначная семантика Данна для алгебры Де Моргана, которая имеет значения ( rue), F (alse), B (oth) и N (либо), где
- Ф < Б < Т ,
- F < N < T и
- Б и Н несопоставимы. [2]
Алгебра Клини
[ редактировать ]Если алгебра Де Моргана дополнительно удовлетворяет условию x ∧ ¬ x ⩽ y ∨ ¬ y , она называется алгеброй Клини . [1] [3] (Это понятие не следует путать с другой алгеброй Клини, обобщающей регулярные выражения также назвал это понятие нормальной i -решеткой .) Калман .
Примеры алгебр Клини в определенном выше смысле включают: решеточно-упорядоченные группы , алгебры Поста и алгебры Лукасевича . [3] Булевы алгебры также соответствуют этому определению алгебры Клини. Простейшей алгеброй Клини, не являющейся булевой, является трехзначная логика Клини K 3 . [4] K 3 впервые появился в Об книге Клини « обозначениях порядковых чисел» (1938). [5] Бриньоль и Монтейро назвали алгебру в честь Клини. [6]
Связанные понятия
[ редактировать ]Алгебры де Моргана — не единственный возможный способ обобщения булевых алгебр. Другой способ — сохранить ¬ x ∧ x = 0 (т. е. закон непротиворечия), но отказаться от закона исключенного третьего и закона двойного отрицания. Этот подход (называемый полудополнением ) четко определен даже для (встречающейся) полурешетки ; если набор полудополнений имеет наибольший элемент , его обычно называют псевдодополнением . Если псевдодополнение удовлетворяет закону исключенного третьего, результирующая алгебра также является булевой. только более слабый закон ¬x ∨ ¬¬x Однако если требуется = 1, это приводит к алгебрам Стоуна . [1] В более общем смысле и алгебры Де Моргана, и Стоуна являются собственными подклассами алгебр Оккама .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д Блит, Т.С.; Варлет, JC (1994). Алгебры Оккама . Издательство Оксфордского университета. стр. 4–5 . ISBN 978-0-19-859938-8 .
- ↑ Перейти обратно: Перейти обратно: а б с д и Безио, Жан-Ив (2012). «История истинных ценностей». В Габбае, Дов М.; Пеллетье, Фрэнсис Джеффри; Вудс, Джон (ред.). Логика: история ее центральных понятий . Северная Голландия (отпечаток Elsevier). стр. 280–281. ISBN 978-0-08-093170-8 .
- ↑ Перейти обратно: Перейти обратно: а б с Чиньоли, Роберто (1975). «Инъективные алгебры де Моргана и Клини» (PDF) . Труды Американского математического общества . 47 (2): 269–278. дои : 10.1090/S0002-9939-1975-0357259-4 . JSTOR 2039730 .
- ^ Каарли, Калле; Пиксли, Олден Ф. (21 июля 2000 г.). Полиномиальная полнота в алгебраических системах . ЦРК Пресс. стр. 297–. ISBN 978-1-58488-203-9 .
- ^ Клини, Южная Каролина (1938). «Об обозначениях порядковых числительных». Журнал символической логики . 3 (4): 150–155. дои : 10.2307/2267778 . JSTOR 2267778 .
- ^ Бриньоль, Д.; Монтейро, А. (1964). «Характеризация алгебр Нельсона равенствами». Заметки по математической логике . 20 . Институт математики Университета Саут-Бэй-Бланка. (Возможно, сокращенная) версия этой статьи появилась позже в Proceedings of the Japan Academy : Бриньоль, Диана; Монтейро, Антонио (1967). «Характеризация алгебр Нельсона равенствами I» . Труды Японской академии, серия A, Математические науки . 43 (4). дои : 10.3792/pja/1195521624 , Бриньоль, Диана; Монтейро, Антонио (1967). «Характеризация алгебр Нельсона равенствами, II» . Труды Японской академии, серия A, Математические науки . 43 (4). дои : 10.3792/pja/1195521625 .
Дальнейшее чтение
[ редактировать ]- Балбес, Раймонд; Двингер, Филип (1975). «Глава IX. Алгебры де Моргана и алгебры Лукасевича». Распределительные решетки . Университет Миссури Пресс. ISBN 978-0-8262-0163-8 .
- Биркгоф, Г. (1936). «Рецензии: Моисиль Гр. С. Исследования по алгебре логики. Научные летописи Ясского университета, т. 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). «Решетки с внутренними и замыкающими операторами и абстрактные пространства аппроксимации». Транзакции с грубыми множествами X . Конспекты лекций по информатике 67–116. Том. 5656. стр. 67–116. дои : 10.1007/978-3-642-03281-3_3 . ISBN 978-3-642-03280-6 .
- Герке, М .; Уокер, К.; Уокер, Э. (2003). «Нечеткая логика, возникающая из строгих систем Де Моргана». В Родабо, ЮВ; Клемент, Е.П. (ред.). Топологические и алгебраические структуры в нечетких множествах: Справочник по последним разработкам в математике нечетких множеств . Спрингер. ISBN 978-1-4020-1515-1 .
- Далла Кьяра, Мария Луиза ; Джунтини, Роберто; Гричи, Ричард (2004). Рассуждения в квантовой теории: четкая и нерезкая квантовая логика . Спрингер. ISBN 978-1-4020-1978-4 .