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

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

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

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

Исчисление отношений

Однородное бинарное отношение находится в степеней наборе $X \times X$ для некоторого набора X , тогда как отношение находится в наборе степеней $X \times Y$ , где $X \neq Y.$ гетерогенное Выполняется ли данное отношение для двух людей, это один бит информации, поэтому отношения изучаются с помощью булевой арифметики. Элементы степенного множества частично упорядочены путем включения , а решетка этих множеств становится алгеброй посредством относительного умножения или композиции отношений .

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

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

Пример

Пример исчисления отношений возникает в эротетике , теории вопросов. вселенной высказываний существуют утверждения S и вопросы Q. Во Существуют два отношения $π$ и α от Q к S : qα a a выполняется, когда является прямым ответом на вопрос q . Другое соотношение q $π$ p имеет место, когда p является предпосылкой вопроса q . Обратное соотношение $π$ ^Т пробегает от S до Q, так что композиция $π$ ^Тα — однородное отношение на S . ^[2] Искусство поставить правильный вопрос, чтобы получить достаточный ответ, признано в сократовском методе диалога.

Функции

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

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

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

Абстракция

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

Алгебры как модели логики

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

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

Переменные молчаливо и универсально количественно оцениваются в некоторой вселенной дискурса . Не существует экзистенциально определяемых переменных или открытых формул ;
Термы создаются из переменных с использованием примитивных и определенных операций . нет Связей ;
Формулы , построенные из термов обычным способом, могут быть приравнены, если они логически эквивалентны . Чтобы выразить тавтологию , приравняйте формулу к истинностному значению ;
Правила доказательства – это замена равных равными. ^{[ нужны разъяснения ]}, и равномерная замена. Modus ponens остается в силе, но используется редко.

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

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

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

Логическая система	Алгебра Линденбаума–Тарского
Классическая сентенциальная логика	Булева алгебра
Интуиционистская пропозициональная логика	Алгебра Гейтинга
Логика Лукасевича	MV-алгебра
Модальная логика К	Модальная алгебра
Льюиса S4	Внутренняя алгебра
Льюиса S5 , монадическая логика предикатов	Монадическая булева алгебра
Логика первого порядка	Полная булева алгебра , полиадическая алгебра , функторная логика предикатов
Логика первого порядка с равенством	Цилиндрическая алгебра
Теория множеств	Комбинаторная логика , алгебра отношений

История

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Бьярни Йонссон (1984). «Максимальные алгебры бинарных отношений». У Кеннета И. Аппеля; Джон Дж. Рэтклифф; Пол Э. Шупп (ред.). Вклад в теорию групп . Современная математика. Том. 33. Провиденс/РАЙ: Американское математическое общество . стр. 299–307. ISBN 978-0-8218-5035-0 .
↑ Юджин Фриман (1934) Категории Чарльза Пирса , страница 10, Open Court Publishing Company , цитата: Сохраняя реалистичные предпосылки простого человека относительно подлинности внешней реальности, Пирс может укрепить шаткую защиту конвенционалистской теории. природы мощным вооружением здравого реализма.
^ Г. Шмидт и Т. Стрёлейн (1993) Отношения и графики Дискретная математика для ученых-компьютерщиков, стр. 54, Монографии EATCS по теоретической информатике, Springer Verlag, ISBN 3-540-56254-0
^ Г. Шмидт (2011) Реляционная математика , Энциклопедия математики и ее приложений, том. 132, страницы 49 и 57, издательство Кембриджского университета. ISBN 978-0-521-76268-7
^ Г. Шмидт и М. Винтер (2018) Реляционная топология , стр. 8, Конспекты лекций по математике, том. 2208, Шпрингер Верлаг, ISBN 978-3-319-74451-3
^ Роджер К. Линдон (май 1950 г.). «Представление реляционных алгебр». Анналы математики . 51 (3): 707–729. дои : 10.2307/1969375 . JSTOR 1969375 . МР 0037278 .
^ Вон Пратт. Истоки исчисления отношений , из Стэнфордского университета.
^ Роджер Мэддукс (1991) «Происхождение алгебр отношений в развитии и аксиоматизации исчисления отношений», Studia Logica 50 : 421-55
^ Jump up to: ^а ^б ^с ^д Альфред Тарский (1941), «Об исчислении отношений», Журнал символической логики 6: 73–89. дои : 10.2307/2268577
^ Jump up to: ^а ^б Кларенс Льюис (1918) Обзор символической логики , University of California Press , второе издание 1932 г., Дуврское издание 1960 г.
^ Джордж Буль , Математический анализ логики, эссе по исчислению дедуктивного рассуждения (Лондон, Англия: Macmillan, Barclay & Macmillan, 1847).
^ Огастес Де Морган (1847), Формальная логика , Лондон: Тейлор и Уолтон, ссылка из Hathi Trust
^ Александр Макфарлейн (1879), Принципы алгебры логики , через Интернет-архив
^ Кристин Лэдд (1883), Об алгебре логики через Google Книги
^ Эрнст Шредер , (1895), Алгебра логики (точная логика), третий том, Алгебра и логика родственников , Лейбциг: Б. Г. Тойбнер через Интернет-архив
^ Б. Рассел (1903) Принципы математики
^ Хелена Расёва (1974), «Посталгебры как семантические основы m-значной логики», страницы 92–142 в «Исследованиях по алгебраической логике» , под редакцией Обера Дейно, Математическая ассоциация Америки ISBN 0-88385-109-1

Источники

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

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

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

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

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

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

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

[1] Бьярни Йонссон (1984). «Максимальные алгебры бинарных отношений». У Кеннета И. Аппеля; Джон Дж. Рэтклифф; Пол Э. Шупп (ред.). Вклад в теорию групп . Современная математика. Том. 33. Провиденс/РАЙ: Американское математическое общество . стр. 299–307. ISBN 978-0-8218-5035-0 .

[2] Юджин Фриман (1934) Категории Чарльза Пирса , страница 10, Open Court Publishing Company , цитата: Сохраняя реалистичные предпосылки простого человека относительно подлинности внешней реальности, Пирс может укрепить шаткую защиту конвенционалистской теории. природы мощным вооружением здравого реализма.

[3] Г. Шмидт и Т. Стрёлейн (1993) Отношения и графики Дискретная математика для ученых-компьютерщиков, стр. 54, Монографии EATCS по теоретической информатике, Springer Verlag, ISBN 3-540-56254-0

[4] Г. Шмидт (2011) Реляционная математика , Энциклопедия математики и ее приложений, том. 132, страницы 49 и 57, издательство Кембриджского университета. ISBN 978-0-521-76268-7

[5] Г. Шмидт и М. Винтер (2018) Реляционная топология , стр. 8, Конспекты лекций по математике, том. 2208, Шпрингер Верлаг, ISBN 978-3-319-74451-3

[6] Роджер К. Линдон (май 1950 г.). «Представление реляционных алгебр». Анналы математики . 51 (3): 707–729. дои : 10.2307/1969375 . JSTOR 1969375 . МР 0037278 .

[7] Вон Пратт. Истоки исчисления отношений , из Стэнфордского университета.

[8] Роджер Мэддукс (1991) «Происхождение алгебр отношений в развитии и аксиоматизации исчисления отношений», Studia Logica 50 : 421-55

[T41-9] Jump up to: ^а ^б ^с ^д Альфред Тарский (1941), «Об исчислении отношений», Журнал символической логики 6: 73–89. дои : 10.2307/2268577

[Lewis-10] Jump up to: ^а ^б Кларенс Льюис (1918) Обзор символической логики , University of California Press , второе издание 1932 г., Дуврское издание 1960 г.

[11] Джордж Буль , Математический анализ логики, эссе по исчислению дедуктивного рассуждения (Лондон, Англия: Macmillan, Barclay & Macmillan, 1847).

[12] Огастес Де Морган (1847), Формальная логика , Лондон: Тейлор и Уолтон, ссылка из Hathi Trust

[13] Александр Макфарлейн (1879), Принципы алгебры логики , через Интернет-архив

[14] Кристин Лэдд (1883), Об алгебре логики через Google Книги

[15] Эрнст Шредер , (1895), Алгебра логики (точная логика), третий том, Алгебра и логика родственников , Лейбциг: Б. Г. Тойбнер через Интернет-архив

[16] Б. Рассел (1903) Принципы математики

[17] Хелена Расёва (1974), «Посталгебры как семантические основы m-значной логики», страницы 92–142 в «Исследованиях по алгебраической логике» , под редакцией Обера Дейно, Математическая ассоциация Америки ISBN 0-88385-109-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]