Алгебраїчна логіка — напрям математичної логіки, у якому міркування досліджують за допомогою маніпулювання рівняннями з вільними змінними.
Те, що нині зазвичай називають класичною алгебричною логікою, зосереджується на виявленні та алгебричному описі моделей, придатних для вивчення різних логік (у вигляді класів алгебр, що становлять цих дедуктивних систем), а також пов'язаних із ними проблем, таких як та дуальність. Відомі результати, такі як теорема представлення для булевих алгебр та належать до класичної алгебричної логіки .
Праці з новішого напряму — () — зосереджені на самому процесі алгебризації, зокрема на класифікації різних форм алгебризовності за допомогою .
Числення відношень Однорідне бінарне відношення є елементом булеана для деякої множини X, тоді як неоднорідне відношення є елементом булеана , де . Факт виконання або невиконання заданого відношення для пари об'єктів містить один біт інформації, тому відношення досліджують за допомогою булевої арифметики. Елементи булеана частково впорядковані за включенням, а ґратка цих множин стає алгеброю завдяки відносному множенню або композиції відношень.
«Основними операціями є теоретико-множинні об'єднання, перетин і доповнення, відносне множення та обернення».
Обернення означає обернене відношення, яке завжди існує, на відміну від теорії функцій. Задане відношення може бути представлене за допомогою логічної матриці; тоді обернене відношення представляється транспонованою матрицею. Відношення, отримане як композиція двох інших відношень, у такому разі представляється логічною матрицею, отриманою за допомогою множення матриць із використанням булевої арифметики.
Приклад Приклад числення відношень виникає в — теорії запитань. В універсумі висловлювань виділяють висловлювання S та запитання Q. Існують два відношення, та α, від Q до S: відношення q α a виконується тоді, коли a є безпосередньою відповіддю на запитання q. Інше відношення, q p виконується тоді, коли p є пресупозицією запитання q. Обернене відношення T спрямоване від S до Q, тому композиція Tα є однорідним відношенням на SEugene Freeman (1934) The Categories of Charles Peirce, page 10, , цитата: «Зберігаючи реалістичні припущення пересічної людини щодо справжності зовнішньої реальності, Пірс спроможний посилити хиткі засади конвенціоналістської теорії природи потужним арсеналом реалізму здорового глузду». Мистецтво ставити правильне запитання, щоб отримати достатню відповідь, визнається в діалозі за методом Сократа.
Функції Опис основних властивостей бінарних відношень було сформульовано за допомогою числення відношень. Властивість однозначності функцій описує відношення , що задовольняє формулу де — тотожне відношення на області значень . Ін'єктивна властивість відповідає однозначності , або формулі де цього разу — тотожне відношення на області визначення .
Однак однозначне відношення є лише частковою функцією, тоді як однозначне є функцією. Формула тотальності має вигляд та використовують термін відображення для тотального однозначного відношенняG. Schmidt & T. Ströhlein (1993) Relations and Graphs Discrete Mathematics for Computer Scientists, page 54, EATCS Monographs on Theoretical Computer Science, Springer Verlag, G. Schmidt (2011) Relational Mathematics, Encyclopedia of Mathematics and its Applications, vol. 132, pages 49 and 57, Cambridge University Press .
Можливість використання доповнень відношень надихнула Августуса де Моргана та Ернста Шредера ввести еквівалентності використовуючи для доповнення відношення . Ці еквівалентності дають альтернативні формули для однозначних відношень (), і тотальних відношень (). Отже, відображення задовольняють формулу Шмідт використовує цей принцип під назвою «перенесення заперечення зліва вниз»G. Schmidt & M. Winter(2018) Relational Topology, page 8, vol. 2208, Springer Verlag, . Для відображення маємо
Абстракція Структура алгебри відношень, побудована на основі теорії множин, була узагальнена Тарським за допомогою аксіом, що її описують. Потім він поставив питання, чи можна кожну алгебру, що задовольняє цим аксіомам, представити за допомогою відношення на множині. Негативна відповідь відкрила напрям The Origins of the Calculus of Relations, from Stanford University (1991) «The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations», 50: 421-55Alfred Tarski (1941), «On the Calculus of Relations», 6: 73–89 .
Алгебри як моделі логіки Алгебраїчна логіка використовує алгебраїчні структури, зокрема обмежені ґратки, як моделі (інтерпретації) певних логік, досліджуючи логіки за допомогою алгебраїчних структур.
В алгебраїчній логіці: Змінні неявно є загальнозначущими щодо деякого універсуму міркування. Немає екзистенційно квантифікованих змінних або відкритих формул; терми будуються зі змінних за допомогою примітивних і визначених операцій. Логічні зв'язки відсутні; формули, побудовані з термів звичайним способом, можна прирівнювати, якщо вони є логічно еквівалентними. Щоб виразити тавтологію, формулу прирівнюють до істиннісного значення; Правилами доведення є підстановка рівного замість рівного та однорідна заміна. Modus ponens залишається чинним, але застосовується рідко.
У таблиці нижче в лівому стовпці наведено одну або кілька логічних або математичних систем, а праворуч у тому самому рядку — алгебраїчну структуру, яка є їхньою моделлю. Деякі з цих структур є булевими алгебрами або їхніми . Модальні та інші некласичні логіки зазвичай моделюються структурами, які називають «булевими алгебрами з операторами».
До алгебраїчних формалізмів, які принаймні в деяких аспектах виходять за межі логіки першого порядку, належать:
Комбінаторна логіка, що має виражальну силу теорії множин; , яку можна вважати парадигмальною алгебраїчною логікою, здатна виражати арифметику Пеано та більшість аксіоматичних теорій множин, зокрема канонічну ZFC.
Логічна системаКласична логіка висловлюваньБулева алгебраІнтуїціоністська логіка висловлюваньАлгебра ГейтингаЛогіка ЛукашевичаМодальна логіка S4Льюїса , монадична логіка предикатівЛогіка першого порядку, , Логіка першого порядку з рівністюТеорія множинКомбінаторна логіка,
Історія
Алгебраїчна логіка, можливо, є найдавнішим підходом до формальної логіки; її початок, імовірно, пов'язаний із низкою записок, написаних Лейбніцем у 1680-х роках, деякі з яких було опубліковано в XIX столітті та перекладено англійською мовою у 1918 році (1918) A Survey of Symbolic Logic, University of California Press, second edition 1932, Dover edition 1960. Однак майже всі відомі праці Лейбніца з алгебраїчної логіки були опубліковані лише 1903 року, після того як виявив їх у . і переклали англійською мовою добірки текстів із тому Кутюра.
Сучасна математична логіка розпочалася 1847 року з двох брошур, авторами яких були відповідно Джордж БульGeorge Boole, The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning (London, England: Macmillan, Barclay, & Macmillan, 1847). і Аугустус де МорганAugustus De Morgan (1847), Formal Logic, London: Taylor & Walton, link from HathiTrust. У 1870 році Чарлз Сандерс Пірс опублікував першу з кількох праць, присвячених логіці відношень. опублікував свою працю Principles of the Algebra of Logic («Принципи алгебри логіки») (1879), Principles of the Algebra of Logic, via Internet Archive у 1879 році, а 1883 року , учениця Пірса в Університеті Джонса Гопкінса, опублікувала працю «Про алгебру логіки» (On the Algebra of Logic) (1883), On the Algebra of Logic via Google Books. Логіка набула більш алгебраїчного характеру, коли бінарні відношення поєднали з композицією відношень. Для множин A і B, відношення між A і B подають як елемент булеана A×B, а його властивості описують засобами булевої алгебри. «Числення відношень» імовірно, стало кульмінацією підходу Лейбніца до логіки. В числення відношень розвивав Ернст ШредерErnst Schröder (mathematician)|Ernst Schröder, (1895), Algebra der Logik (Exakte Logik) Dritter Band, Algebra und Logik der Relative, Leibzig: via Internet Archive. Зокрема, він сформулював правила Шредера, хоча де Морган передбачив їх у своїй теоремі K.
У 1903 році Бертран Расселл розвинув алгебру відношень і логіцизм як власну версію чистої математики, заснованої на операціях алгебри відношень як первинних поняттяхB. Russell (1903) . «Алгебра логіки Буля—Шредера» була викладена у підручнику , опублікованому 1918 року в Каліфорнійському університеті в Берклі (1918) A Survey of Symbolic Logic, University of California Press, second edition 1932, Dover edition 1960. Він розглядав логіку відношень як похідну від пропозиційних функцій двох або більше змінних.
, Готлоб Фреге, Джузеппе Пеано та Альфред Норт Вайтгед поділяли мрію Лейбніца про поєднання символічної логіки, математики та філософії.
Деякі праці та Торальфа Скулема з алгебраїчної логіки з'явилися після публікації Principia Mathematica у 1910—1913 роках, а Тарський відновив інтерес до відношень своєю статтею «Про числення відношень» (On the Calculus of Relations), опублікованою 1941 року.
За словами Гелени Расіової: «У 1920—1940 роках, зокрема в польській школі логіки, проводилися дослідження некласичних числень висловлень за допомогою так званого методу логічних матриць. Оскільки логічні матриці є певними абстрактними алгебрами, це привело до застосування алгебраїчного методу в логіці»Helena Rasiowa (1974), «Post Algebras as Semantic Foundations of m-valued Logics», pages 92–142 in Studies in Algebraic Logic, edited by Aubert Daigneault, Mathematical Association of America .
розглядає тісні історичні зв'язки між алгебраїчною логікою та теорією моделей. Засновники теорії моделей Ернст Шредер і Леопольд Левенгайм були логіками алгебраїчної традиції. Альфред Тарський, засновник теоретико-множинної теорії моделей як важливої галузі сучасної математичної логіки, також: започаткував абстрактну алгебраїчну логіку за допомогою ; винайшов був одним із першовідкривачів .
У практичному застосуванні числення відношень використовував алгебраїчну логіку для розвитку корисних понять: він поширив поняття відношення еквівалентності (на множині) на неоднорідний випадок, увівши поняття дифункціонального відношення. Ріге також поширив поняття впорядкування на неоднорідний контекст, зазначивши, що східчаста логічна матриця має доповнення, яке також є східчастим, і що теорема випливає з інтерпретації транспонування східчастої матриці. Ріге отримав прямокутні відношення беручи зовнішній добуток логічних векторів; вони пов'язані з нерозширюваними прямокутниками у .
Лейбніц не мав впливу на становлення алгебраїчної логіки, оскільки його логічні праці мало вивчали до перекладів Паркінсона та Лоемкера. Сучасне розуміння Лейбніца як логіка ґрунтується переважно на працях Вольфганга Ленцена, узагальнених у . Про те, як сучасні дослідження в галузі логіки та метафізики можуть черпати натхнення з ідей Лейбніца й водночас проливати на них світло, див. .
Див. також Алгебра логіки
Символьні обчислення Універсальна алгебра
Примітки
Джерела
Література Willard Van Orman Quine (1976). «Algebraic Logic and Predicate Functors». In: The Ways of Paradox and Other Essays. 2nd ed. Cambridge, Massachusetts: Harvard University Press. pp. 283—307. Paul R. Halmos (2016). Algebraic Logic. Mineola, New York: Dover Publications. 272 p. ISBN 978-0-486-80145-2. Перевидання видання 1962 року, опублікованого Chelsea Publishing Company. Вступне видання, що добре підходить для читачів, які вже знайомі з некласичними логіками, але не мають значної підготовки з теорії порядку та/або універсальної алгебри; у книзі ці необхідні передумови докладно розглянуто. Водночас цю книгу критикували за неякісний, а подекуди й некоректний виклад результатів абстрактної алгебраїчної логіки. Рецензія Януша Челяковського Draft. В основному про абстрактну алгебраїчну логіку. Stanley Burris (2015), "The Algebra of Logic Tradition". Stanford Encyclopedia of Philosophy.