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

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

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

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

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

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

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

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

Пример

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

Функции

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

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

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

Абстракция

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Languages

In other projects