Алгебраическая логика
В математической логике алгебраическая логика — это рассуждения, полученные путем манипулирования уравнениями со свободными переменными .
То, что сейчас обычно называют классической алгебраической логикой, фокусируется на идентификации и алгебраическом описании моделей , подходящих для изучения различных логик (в виде классов алгебр, составляющих алгебраическую семантику этих дедуктивных систем ) и связанных с ними проблем, таких как представление и двойственность. Хорошо известные результаты, такие как теорема о представлении булевых алгебр и двойственность Стоуна, подпадают под действие классической алгебраической логики ( 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 . Обратное соотношение π Т пробегает от S до Q , так что композиция π Т α — однородное отношение на S . [2] Искусство поставить правильный вопрос, чтобы получить достаточный ответ, признано в сократовском методе диалога.
Функции [ править ]
Описание ключевых свойств бинарных отношений сформулировано с помощью исчисления отношений. Свойство однолистности функций описывает отношение R , удовлетворяющее формуле где I — тождественное отношение в R. диапазоне Инъективное свойство соответствует однолистности , или формула где на этот раз — тождество в области R. I
Но однолистное отношение — это лишь частичная функция , тогда как однолистное тотальное отношение — это функция . Формула тотальности такова: Чарльз Лёвнер и Гюнтер Шмидт используют термин «отображение» для обозначения полного одновалентного отношения. [3] [4]
Возможность дополнительных отношений вдохновила Августа Де Моргана и Эрнста Шредера ввести эквивалентности, используя для дополнения отношения R . Эти эквивалентности дают альтернативные формулы для однолистных отношений ( ) и полные отношения ( ). Следовательно, отображения удовлетворяют формуле Шмидт использует этот принцип как «скольжение ниже отрицания слева». [5] Для отображения f ,
Абстракция [ править ]
Структура алгебры отношений , основанная на теории множеств, была превзойдена Тарским с помощью описывающих ее аксиом. Затем он спросил, может ли каждая алгебра, удовлетворяющая аксиомам, быть представлена отношением множеств. Отрицательный ответ [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
- ^ Перейти обратно: а б с д Альфред Тарский (1941), «Об исчислении отношений», Журнал символической логики 6: 73–89. дои : 10.2307/2268577
- ^ Перейти обратно: а б Кларенс Льюис (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). Лейбниц: Логические статьи . Издательство Оксфордского университета.
- Залта, EN, 2000, « (Лейбницианская) теория понятий », Philosophiegeschichte und logische Analysis / Logical Analysis and History of Philosophy 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 в Algebraic Logic , Colloquia Mathematica Societatis János Bolyai # 54, Математическое общество Яноша Бойяи и Elsevier ISBN 0444885439
Внешние ссылки [ править ]
| Базы данных органов управления : Национальные |
|---|
