Алгебраическая логика

В математической логике , алгебраическая логика рассуждение получается манипулируя уравнения с свободными переменными .

То, что сейчас обычно называют классической алгебраической логикой, фокусируется на идентификации и алгебраическом описании моделей, подходящих для изучения различных логик (в форме классов алгебр, составляющих алгебраическую семантику этих дедуктивных систем ) и связанных проблем, таких как представление и двойственность. Хорошо известные результаты, такие как теорема о представлении булевых алгебр и двойственность Стоуна, подпадают под действие классической алгебраической логики ( Czelakowski 2003 ).

Работы в более поздней абстрактной алгебраической логике (AAL) сосредоточены на самом процессе алгебраизации, например, на классификации различных форм алгебраизируемости с использованием оператора Лейбница ( Czelakowski 2003 ).

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

Гомогенное бинарное отношение находится в наборе мощности из X × X для некоторого множества X , в то время как гетерогенное соотношение находится в наборе мощности X × Y , где X ≠ Y . Справедливо ли данное отношение для двух людей - это один бит информации, поэтому отношения изучаются с помощью булевой арифметики. Элементы набора мощности частично упорядочены включением , и решетка этих наборов становится алгеброй посредством относительного умножения или композиции отношений .

«Основные операции - это теоретико-множественное объединение, пересечение и дополнение, относительное умножение и преобразование». ^[1]

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

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

Пример исчисления отношений возникает в эротетике , теории вопросов. Во вселенных высказываниях есть заявления S и вопросы Q . Есть два отношения π и α от Q к S : q α a выполняется, когда a является прямым ответом на вопрос q . Другое соотношение q π p выполняется, когда p является предпосылкой вопроса q . Обратное соотношение π ^T работает от S до Qтак что композиция π ^T ; α является однородным отношение на S . Искусство постановки правильного вопроса, чтобы получить достаточный ответ, признано в диалоге с сократовским методом .

Функции [ править ]

Описание ключевых бинарных отношений было сформулировано с помощью исчисления отношений. Унивалентности свойство функций описывает соотношение R , который удовлетворяет формуле где есть отношение тождественно на интервале R . Инъективная соответствует свойство для однолистности R ^T , или формулы , где на этот раз я тождественный на области R .${\ displaystyle R ^ {T} R \ substeq I,}$${\ displaystyle RR ^ {T} \ substeq I,}$

Но однолистное отношение - это только частичная функция , тогда как однолистное полное отношение - это функция . Формула тотальности состоит в том, что Чарльз Лёвнер и Гюнтер Шмидт используют термин отображение для обозначения тотального, однолистного отношения. ^{[2] [3]}${\ displaystyle I \ substeq RR ^ {T}.}$

Объект из взаимодополняющих отношений вдохновил Август Де Морган и Эрнст Шрёдер ввести эквивалентности , используя для дополнения отношения R . Эти эквивалентности предоставляют альтернативные формулы для однолистных отношений ( ) и полных отношений ( ). Следовательно, отображения удовлетворяют формуле, которую Шмидт использует как «сползание под отрицание слева». ^[4] Для отображения${\displaystyle {\bar {R}}}$${\displaystyle R{\bar {I}}\subseteq {\bar {R}}}$${\displaystyle {\bar {R}}\subseteq R{\bar {I}}}$${\displaystyle {\bar {R}}=R{\bar {I}}.}$${\displaystyle f,\quad f{\bar {A}}={\overline {fA}}.}$

Абстракция [ править ]

Структура алгебры отношений , основанная на теории множеств, была преодолена Тарским с помощью описывающих ее аксиом. Затем он спросил, может ли каждая алгебра, удовлетворяющая аксиомам, быть представлена ​​отношением множества. Отрицательный ответ ^[5] открыл границы абстрактной алгебраической логики . ^{[6] [7] [8]}

Алгебры как модели логик [ править ]

Алгебраическая логика рассматривает алгебраические структуры , часто ограниченные решетки , как модели (интерпретации) определенных логик , что делает логику ветвью теории порядка .

В алгебраической логике:

• Переменные неявно универсально количественно оцениваются в некоторой вселенной дискурса . Нет никаких экзистенциально количественных переменных или открытых формул ;
• Термины создаются из переменных с использованием простых и определенных операций . Нет связок ;
• Формулы , построенные из терминов обычным способом, можно приравнять, если они логически эквивалентны . Чтобы выразить тавтологию , приравняйте формулу к значению истинности ;
• Правила доказательства - это замена равных на равные и единообразная замена. Modus ponens остается в силе, но применяется редко.

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

Алгебраические формализмы, выходящие за рамки логики первого порядка по крайней мере в некоторых отношениях, включают:

• Комбинаторная логика , обладающая выразительной силой теории множеств ;
• Алгебра отношений , возможно, парадигматическая алгебраическая логика, может выражать арифметику Пеано и большинство аксиоматических теорий множеств , включая канонический ZFC .

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

Алгебраическая логика, возможно, является самым старым подходом к формальной логике, возможно, начиная с ряда меморандумов, написанных Лейбницем в 1680-х годах, некоторые из которых были опубликованы в 19 веке и переведены на английский язык Кларенсом Льюисом в 1918 году. ^{[9] : 291 –305} Но почти вся известная работа Лейбница по алгебраической логике была опубликована только в 1903 году, после того как Луи Кутюра обнаружил ее в « Начале» Лейбница . Паркинсон (1966) и Лемкер (1969) перевели отрывки из тома Кутюра на английский язык.

Современная математическая логика началась в 1847 году с двух брошюр, авторами которых были Джордж Буль ^[10] и Август Де Морган . ^[11] В 1870 году Чарльз Сандерс Пирс опубликовал первую из нескольких работ по логике родственников . Александр Макфарлейн опубликовал свои « Принципы алгебры логики» ^[12] в 1879 году, а в 1883 году Кристин Лэдд , студентка Пирса из Университета Джона Хопкинса , опубликовала «Об алгебре логики». ^[13] Логика стала более алгебраической, когда бинарные отношения были объединены ссостав отношений . Для множеств A и B отношения сначала понимались как элементы множества степеней A × B со свойствами, описываемыми булевой алгеброй . «Исчисление отношений» ^[8] , возможно, является кульминацией подхода Лейбница к логике. В Высшей школе Карлсруэ исчисление отношений было описано Эрнстом Шредером . ^[14] В частности, он сформулировал правила Шредера , хотя Де Морган предвосхитил их в своей теореме K.

«Буль-Шредера алгебра логики» была разработана в Университете Калифорнии, Беркли в учебнике по Кларенс Льюисом в 1918 году ^[9] Он рассматривал логику отношений, вытекающих из пропозициональных функций двух или более переменных.

Хью МакКолл , Готтлоб Фреге , Джузеппе Пеано , Бертран Рассел и А. Н. Уайтхед разделяли мечту Лейбница о соединении символической логики , математики и философии .

Некоторые работы Леопольда Левенхайма и Торальфа Сколема по алгебраической логике появились после публикации « Начала математики» в 1910–13 годах , и Тарский возродил интерес к отношениям с его эссе 1941 года «Об исчислении отношений». ^[8]

По словам Хелены Расайовой , «Года 1920-40 видели, в частности , в польской школе логики, исследования по неклассическим пропозициональным исчислениям проводятся , что называется логическая матрица метод. Поскольку логические матрицы определенные абстрактные алгебр, это привело к использование алгебраического метода в логике ». ^[15]

Брэди (2000) обсуждает богатые исторические связи между алгебраической логикой и теорией моделей . Основатели теории моделей Эрнст Шредер и Леопольд Лёвенгейм были логиками в алгебраической традиции. Альфред Тарский , основатель теории теоретико-множественных моделей как основного раздела современной математической логики, также:

• Инициировал абстрактную алгебраическую логику с алгебрами отношений ^[8]
• Изобрел цилиндрическую алгебру
• Со-открытая алгебра Линденбаума – Тарского .

В практике исчисления отношений Жак Риге использовал алгебраическую логику для продвижения полезных концепций: он распространил понятие отношения эквивалентности (на множестве) на гетерогенные отношения с дифункциональным понятием. Риге также расширил упорядочение до гетерогенного контекста, заметив, что у логической матрицы лестницы есть дополнение, которое также является лестницей, и что теорема Н. М. Феррерса следует из интерпретации транспонирования лестницы. Риге создал прямоугольные отношения , взяв внешнее произведение логических векторов; они вносят вклад в не-enlargeable прямоугольников из формального анализа понятия.

Лейбниц не оказал никакого влияния на возникновение алгебраической логики, потому что его логические труды были мало изучены до переводов Паркинсона и Лемкера. Наше нынешнее понимание Лейбница как логика происходит главным образом из работ Вольфганга Лензена, обобщенных в Lenzen (2004) . Чтобы увидеть, как современные работы в области логики и метафизики могут черпать вдохновение и проливать свет на мысль Лейбница, см. Zalta (2000) .

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

• Булева алгебра
• Теорема Кодда
• Компьютерная алгебра
• Универсальная алгебра

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

Источники [ править ]

• Брэди, Джеральдин (2000). От Пирса до Сколема: забытая глава в истории логики . Амстердам, Нидерланды: Северная Голландия / Elsevier Science BV. Архивировано из оригинала на 2009-04-02 . Проверено 15 мая 2009 .
• Челаковский, Януш (2003). "Обзор: Алгебраические методы в философской логике Дж. Майклом Данном и Гэри М. Хардегри". Вестник символической логики . Ассоциация символической логики, Cambridge University Press. 9 . ISSN  1079-8986 . JSTOR  3094793 .
• Ленцен, Вольфганг, 2004, « Логика Лейбница » в Габбее, Д., и Вудсе, Дж., Ред., Справочник по истории логики, Vol. 3: Возвышение современной логики от Лейбница до Фреге . Северная Голландия: 1-84.
• Loemker, Leroy (1969) [Первое издание 1956], Leibniz: Philosophical Papers and Letters (2-е изд.), Reidel.
• Паркинсон, GHR (1966). Лейбниц: Логические документы . Издательство Оксфордского университета.
• Залта, Э.Н., 2000, « А (лейбницевская) теория концепций », Philosophiegeschichte und logische Analyze / Логический анализ и история философии 3: 137-183.

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

• Дж. Майкл Данн; Гэри М. Хардегри (2001). Алгебраические методы в философской логике . Издательство Оксфордского университета. ISBN 978-0-19-853192-0.Хорошее введение для читателей, знакомых с неклассической логикой, но не имеющих большого опыта в теории порядка и / или универсальной алгебре; в книге подробно рассматриваются эти предпосылки. Однако эту книгу критиковали за плохое, а иногда и неправильное представление результатов AAL. Отзыв Януша Челаковского
• Хайнал Андрека , Иштван Немети и Ильдико Саин (2001). «Алгебраическая логика». В Дов М. Габбай, Франц Гентнер (ред.). Справочник по философской логике, том 2 (2-е изд.). Springer. ISBN 978-0-7923-7126-7. Проект .
• Рамон Янсана (2011), " Отношения пропозициональной последовательности и алгебраическая логика ". Стэнфордская энциклопедия философии. В основном об абстрактной алгебраической логике.
• Стэнли Беррис (2015), « Алгебра логической традиции ». Стэнфордская энциклопедия философии.
• Уиллард Куайн , 1976, «Алгебраическая логика и функторы предикатов», страницы 283–307 в The Ways of Paradox , Harvard University Press .

Историческая перспектива

• Айвор Граттан-Гиннесс , 2000. В поисках математических корней . Издательство Принстонского университета.
• И. Х. Анеллис и Н. Хаузер (1991) "Корни алгебраической логики и универсальной алгебры девятнадцатого века", страницы 1–36 в алгебраической логике , Colloquia Mathematica Societatis János Bolyai # 54, Математическое общество Яноша Бойяи и Elsevier ISBN 0444885439 

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

• СМИ, связанные с алгебраической логикой, на Викискладе?