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

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

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

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

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

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

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

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

Пример

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

Функции

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

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

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

Абстракция

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники

• Брэди, Джеральдин (2000). От Пирса до Сколема: забытая глава в истории логики. Амстердам, Нидерланды: Северная Голландия / Elsevier Science BV. Архивировано из оригинал на 2009-04-02. Получено 2009-05-15.
• Челаковский, Януш (2003). "Обзор: Алгебраические методы в философской логике Дж. Майклом Данном и Гэри М. Хардегри". Вестник символической логики. Ассоциация символической логики, Cambridge University Press. 9. ISSN  1079-8986. JSTOR  3094793.CS1 maint: ref = harv (ссылка на сайт)
• Ленцен, Вольфганг, 2004 г. "Логика Лейбница "в Gabbay, D., and Woods, J., eds., Справочник по истории логики, Vol. 3: Возвышение современной логики от Лейбница до Фреге. Северная Голландия: 1-84.
• Loemker, Leroy (1969) [первое издание 1956], Лейбниц: Философские статьи и письма (2-е изд.), Reidel.CS1 maint: ref = harv (ссылка на сайт)
• Паркинсон, G.H.R (1966). Лейбниц: Логические статьи. Издательство Оксфордского университета.CS1 maint: ref = harv (ссылка на сайт)
• Залта, Э. Н., 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 в Пути парадокса, Издательство Гарвардского университета.

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

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

внешняя ссылка

• СМИ, связанные с Алгебраическая логика в Wikimedia Commons