Просмотр кода страницы Математическая логика

{{Значения|Логистика (значения)}}
'''Математи́ческая ло́гика''' (''теоретическая логика''{{sfn|Гильберт, Аккерман|1947|с=5}}, ''символическая логика''{{sfn|Бродский|1972|с=3}}, <small>устар.</small> ''логи́стика''<ref>{{БСЭ3|Логистика}}</ref>) — раздел [[математика|математики]], изучающий [[математические обозначения]], [[Формальная система|формальные системы]], [[Верификация|доказуемость]] математических [[Суждение|суждений]], природу математического [[Доказательство (математика)|доказательства]] в целом, [[Теория вычислимости|вычислимость]] и прочие аспекты [[Метаматематика|оснований математики]]<ref>{{Cite web |url=http://www.oxforddictionaries.com/definition/american_english/mathematical-logic |title=mathematical logic: definition of mathematical logic in Oxford dictionary (American English)<!-- Заголовок добавлен ботом --> |access-date=2014-02-07 |archive-date=2014-02-23 |archive-url=https://web.archive.org/web/20140223180949/http://www.oxforddictionaries.com/definition/american_english/mathematical-logic |deadlink=no }}</ref>.

В более широком смысле рассматривается как математизированная ветвь [[формальная логика|формальной логики]]<!-- «''математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков)''»--><ref>Н. И. Кондаков, ''Логический словарь-справочник'', М.: «Наука», 1975, с. 259. </ref> — «''логика по предмету, математика по методу''»<ref>Согласно определению первого автора работ по математической логике на русском языке [[Порецкий, Платон Сергеевич|Платона Порецкого]]</ref>, «''логика, развиваемая с помощью математических методов''»<ref>С. К. Клини, ''Математическая логика'', М., 1973, с.12.</ref>.

== История ==
Первые попытки математизации логических операций были предприняты на рубеже XIII—XIV вв., [[Раймунд Луллий|Раймундом Луллием]], сконструировавшим специальную «логическую машину» для механизации процесса логического вывода, которую он описал в своём трактате «Ars Magna» («Великое искусство»). Его машина состояла из семи концентрических кругов, на которых были обозначены термины и буквы. Для получения комбинаций Луллий использовал два концентрических круга, разделенных радиальными линиями на секторы. Вращая внутренний круг он получал таблицу различных комбинаций. Конечно эта попытка была несовершенной, но сыграла свою роль в дальнейшем развитии идеи математизации логических выводов.

Первое дошедшее до нас сочинение по [[Формальная логика|формальной логике]] — «{{iw|Первая Аналитика||en|Prior Analytics}}» [[Аристотель|Аристотеля]] (384—322 гг. до нашей эры). В нём рассматриваются основы [[Силлогистика|силлогистики]] — правила вывода одних высказываний из других. Так из высказываний «Все люди смертны» и «Сократ — человек» можно сделать вывод, что «Сократ смертен». Однако на практике такие рассуждения встречаются крайне редко.{{Нет АИ|29|05|2020}}

Вопрос о создании символической логики как универсального научного языка рассматривал [[Лейбниц]] в [[1666 год в науке|1666 году]] в работе «Искусство комбинаторики» ({{lang-la2|De arte combinatoria}}). Он думал о записи высказываний на специальном языке, чтобы затем по логическим законам вычислять истинность других. В середине XIX века появились первые работы по алгебраизации аристотелевой логики, сформировавшие первооснову [[исчисление высказываний|исчисления высказываний]] ([[Джордж Буль|Буль]], [[Морган, Огастес де|де Морган]], [[Эрнст Шрёдер|Шрёдер]]). В 1847 г. Дж. Буль опубликовал работу «The Mathematical Analysis of Logic» («Математический анализ логики»), а в 1854 г.— «An Investigation of the Laws of Thought» «Исследование законов мышления»). В них Буль изложил основы своей алгебры логики, где применил алгебраическую символику для записи логических операций и логических выводов. [[Булева алгебра]] логики в виде исчисления классов явилась первой системой математической логики. Основным результатом Булевой алгебры отмечается то, что теперь не ограничиваются применением символики к логике, а строят специальные логические исчисления; логические законы выступают в алгебре логики как необходимый момент формализованных систем; всякое [[суждение]] рассматривается как утверждение о равенстве классов; процесс [[Умозаключение|умозаключения]] сводится к решению логических равенств. Однако, как отмечал [[Джевонс, Уильям Стенли|Джевонс]], операция вычитания в этой алгебре логики была не совсем удобной и иногда приводила к недоразумениям.
Алгебру логики Буля усовершенствовали У. С. Джевонс и Э. Шрёдер. Сам Джевонс в книге «Чистая логика» критиковал излишнюю математизацию, алгебры логики Буля и предложил свою теорию, основанную на принципе замещения, то есть замене равного равным.

В 1877 году [[Эрнст Шрёдер|Шрёдер]] опубликовал книгу по математической логике «Der Operationskreis des Logikkalkuls», в которой систематически изложил основы математической логики. Большой вклад в развитие математической логики внёс русский астроном, логик и математик, профессор Казанского университета [[Порецкий, Платон Сергеевич|П. С. Порецкий]]. Обобщив достижения Буля, Джевонса и Шрёдера, он на основе многолетних самостоятельных исследований создал содержательный труд «О способах решения логических равенств и об обратном способе математической логики», в котором значительно продвинул вперёд разработку аппарата алгебры логики. Работы П. С. Порецкого превосходят не только труды его коллег — современников, но и в части, касающиеся алгебры логики превосходят соответствующие разделы Уайтхеда и Рассела. П. С. Порецкий первым в России начал читать лекции по математической логике. Математическая логика, говорил он, «по предмету своему есть логика, а по методу математика». Задачу математической логики он видел в «построении теории умозаключений», но при этом, точно определял связь и границу между [[Математика|математикой]] и математической логикой. "Если формы, изучаемые алгеброй, суть количественные, — писал он, — то, наоборот, те формы, с которыми имеет дело логика, суть качественные, то есть существенно отличные от первых. Это различие ближайших предметов изучения алгебры и логики делает невозможным прямое перенесение, то есть непосредственное применение, принципов и приёмов алгебры к предмету логики. Однако приспособление этих приёмов (с полным сохранением их точности) к изучению качественных форм вполне возможно. Большим вкладом П. С. Порецкого в математическую логику явилась предложенная им полная законченная теория качественных форм. Он разработал теорию логических равенств, предложил наиболее общий, исчерпывающий метод нахождения всех эквивалентных форм посылок, всех следствий из них, всех простейших неразложимых посылок, на которые может быть разложена система посылок.

В работах [[Готлоб Фреге|Фреге]] и [[Пирс, Чарльз Сандерс|Пирса]] (конец 1870-х — начало 1880-х) в логику введены предметные [[переменные]], [[квантор]]ы и, тем самым, основано [[исчисление предикатов]]. В 1879 году, в своей книге «Исчисление понятий», Фреге представил свою теорию исчисления высказываний, которая стала первым разделом современной математической логики. В ней Фреге представил первое аксиоматическое построение [[Логика высказываний|логики высказываний]], ввёл в математическую логику понятие квантора, которое затем уже Пирс вводит в обиход логической науки. Фреге также ввёл понятие истинностного значения, предложил различать свойства и отношения как значения, соответственно, одноместных и многоместных [[Предикат|пропозициональных функций]]. Но идеи Фреге не сразу нашли сторонников, а исчисления высказываний развивалось, как отмечает А.Чёрч, на основе более старой точки зрения, как это можно видеть в работах Пирса, Шрёдера и других.

В конце 1880-х годов [[Дедекинд, Рихард|Дедекинд]] и [[Пеано]] применили эти инструменты в попытках аксиоматизации арифметики, при этом Пеано создал удобную систему обозначений, закрепившуюся и в современной математической логике. Он ввёл в математическую логику символы: ∈ — знак принадлежности множеству, ⊂ — знак включения, ⋃ — знак объединения, ∩ — знак пересечения множеств; разработал систему [[Аксиома|аксиом]] для [[Арифметика|арифметики]] [[Натуральное число|натуральных чисел]]. Но главное, Пеано с помощью изобретённого им символического исчисления попытался исследовать основные математические понятия, что стало первым шагом практического применения математической логики к изучению основ математики. В своём пятитомном труде «Formulaire de Mathematiques» (1895—1905) Пеано показал, как с помощью символического исчисления можно аксиоматически построить математические дисциплины.

[[Альфред Норт Уайтхед|Уайтхед]] и [[Бертран Рассел|Рассел]] создают в 1910—1913 годах трактат [[Principia Mathematica]]. Этот труд значительно способствовал развитию математической логики по пути дальнейшей аксиоматизации и формализации исчисления высказываний, классов и предикатов. Б. Рассел и А. Уайтхед выход из кризиса, в котором оказалась математика в связи с обнаружением [[Парадоксы теории множеств|парадоксов]] в [[Теория множеств|теории множеств]], видели в том, чтобы свести всю чистую математику к [[Логика|логике]]. Это была концепция [[логицизм]]а. С этой целью они построили формализованную логико-математическую систему, в которой, по их утверждению, могут быть доказаны все содержательно истинные предложения. Но вскоре стало понятно, что попытка Б. Рассела и А. Уайтхеда свести всю чистую математику к логике не увенчалась успехом. В [[1930]]—[[1931 год]]ах [[Гёдель, Курт|К. Гёдель]] установил, что не только разработанная Б. Расселом и А. Уайтхедом система, но и любая система формализованной математики является неполной, то есть не все содержательно истинные предложения могут быть в ней доказаны.

Свой выход из кризиса математики и дальнейшее развитии логики внесла концепция [[интуиционизм]]а и [[интуиционизм#Интуиционистская логика|интуиционистская логика]] ([[Брауэр, Лёйтзен Эгберт Ян|Брауэр]], [[1908 год в науке|1908]]). Математика, говорили они, это — математические конструкции. Математический объект существует, если известно, как его строить. Математик имеет дело с миром мысленных объектов, некоторые из них можно создать только в пределе за неограниченную последовательность шагов, никогда не завершающуюся и находящуюся в процессе постоянного становления. С точки зрения интуиционизма понятие актуальной, существующей бесконечности, которого придерживались представители теоретико-множественной концепции математики, является ошибочным. Поэтому интуиционистская логика исследует только конструктивные объекты, существование таких объектов считается доказанным в том и только в том случае, когда указывается конечный способ их построения. В этой логике отрицается применимость [[Закон исключённого третьего|закона исключённого третьего]] в операциях с бесконечными множествами. Возникшая позднее [[конструктивная логика]] критически восприняла объективное содержание интуиционистской логики, и не приняла её философско-методических основ.

Большую роль в развитии математической логики сыграла работа [[Гильберт, Давид|Гильберта]] и [[Аккерман, Вильгельм|В. Аккермана]] «Основные черты теоретической логики» (1928 г.), изданная в России на русском языке под названием «Основы теоретической логики» в 1947 году, в которой была создана [[программа Гильберта|программа]] обоснования математики посредством аксиоматической формализации с использованием строго ограниченных средств, не приводящих к противоречиям. В своей работе они высказались о новом в математической логике: «Логические связи, которые существуют между [[Суждение|суждениями]], [[Понятие|понятиями]] и т. д. — писали они, — находят своё выражение в формулах, толкование которых свободно от неясностей, какие легко могли бы возникнуть при словесном выражении. Переход к логическим следствиям, совершающийся посредством [[Умозаключение|умозаключения]], разлагается на свои последние элементы и представляется как формальное преобразование исходных формул по известным правилам, которые аналогичны правилам счёта в алгебре; логическое мышление отображается в логическом исчислении. Это исчисление делает возможным успешный охват проблем, перед которыми принципиально бессильно чисто содержательное логическое мышление». Гильберт выступал против интуиционизма. Он возражал против того, что интуиционисты отрицали закон исключённого третьего в операциях с множествами. «Запрещение [[Теорема существования|теорем существования]] и [[Закон исключённого третьего|закона исключённого третьего]] — писал он, — равносильно полному отказу от математической науки». В своём методе формализации Гильберт предложил превратить всю математику в совокупность формул, в которых элементы связаны с помощью логических знаков. В фундаменте построения математики заложены некоторые определённые формулы, которые называются аксиомами. В качестве таких аксиом Гильберт взял аксиомы исчисления высказываний математической логики, математические аксиомы равенства и [[Аксиома|аксиомы]] числа, из которых он с помощью правил вывода получил новые, выводимые аксиомы. Вывод получался только на основании формы символов и знаков, за которыми не стояло никакого содержания. Формализованная теория по своей структуре представляла уже не систему осмысленных предложений, а систему символов, рассматриваемых как последовательность терминов. Основное требование, которое Гильберт предъявлял при определении понятия «существование» математического объекта сводилось к доказательству его непротиворечивости. Если в той или иной системе окажется, что в ней выводимо А и не-А, то такая система должна быть отвергнута. Гильберт и его школа пытались обосновать математику только аксиоматически, не выходя за пределы логики и математики.

В тридцатых и сороковых годах XX века начинается разработка [[Металогика|металогики]], предметом которой является исследование системы положений и понятий самой математической логики, которая определяет границы этой логики, изучает теорию доказательства. Основными разделами металогики являются логический [[синтез]] и [[логическая семантика]], изучение значений выражения языка, интерпретаций логических исчислений. В металогических исследованиях уделяется анализу различных свойств формализованных языков, которые в дальнейшем легли в основу электронных машин для автоматизации научных умозаключений. В области логической семантики самыми значительными признаны работы [[Тарский, Альфред|А. Тарского]] «О понятии истины и формализованных языках» 1933 года, а также работы [[Карнап, Рудольф|Р. Карнапа]] «Исследования по семантике» 1942—1947 года. Также важное значение в развитии математической логики имели работы в области многозначных логик, в которых высказываниям приписывается любое конечное или бесконечное множество значений истинности. Первую такую систему трёхзначной логики высказываний разработал и предложил [[Лукасевич, Ян|Я. Лукасевич]]. В 1954 году Я. Лукасевич предложил четырёхзначную систему логики, и далее бесконечнозначную логику. Проблемами многозначной логики занимались также такие известные математики и логики как [[Пост, Эмиль Леон|Э. Пост]], [[Яськовский, Станислав|С. Яськовский]], Д. Вебб, [[Гейтинг, Аренд|А. Гейтинг]], [[Колмогоров, Андрей Николаевич|А. Н. Колмогоров]], Д. А. Бочвар, [[Шестаков, Виктор Иванович|В. И. Шестаков]], [[Райхенбах, Ханс|Х. Рейхенбах]], [[Клини, Стивен Коул|С. К. Клини]] и другие. Одним из крупнейших направлений в математической логике стала [[Теория доказательств|теория математических доказательств]], которая возникла из применения логических исчислений к вопросам оснований математики. Она вышла из алгебры логики девятнадцатого века, предметом изучения которой были конечные объекты. Теория математических доказательств же занимается в основном проблемой бесконечности. Одной из главных задач математической логики, применяемых в математике исчислений, считается задача установления непротиворечивости, то есть считается, что исчисление непротиворечиво, если в нём нельзя вывести формулу А вместе с формулой Ā (не-А). С помощью метода формализации доказательств математическая логика помогла математике решить проблемы доказуемости и непротиворечивости в аксиоматических теориях. Преимущество математической логики состоит в том, что применяемый ею символический аппарат позволяет строго выразить самые сложные рассуждения, понятия для алгоритмической обработки вычислительными системами.

{{Нет АИ|29|05|2020}}
{{Дополнить раздел|дата=2014-10-18}}

== Основные положения ==
[[Файл:Applications of Parity Games.png|мини]]
Математическая логика, так же как и традиционная логика, формальная в том смысле, что она абстрагируется от значения и судит о взаимосвязи, отношениях и переходах от одного предложения (высказывания) к другому и получающемся в итоге выводе из этих предложений не на основании содержания их, а только на основании формы последовательности предложений.

Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие — нет.{{Нет АИ|29|05|2020}}

Важную роль в математической логике играют понятия [[Дедуктивная теория|дедуктивной теории]] и [[Логическое исчисление|исчисления]]. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы <math>A</math>, синтаксически связанные некоторым заранее определённым способом с конечными наборами <math>A_1, \ldots A_n</math> выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы <math>A</math> и <math>(A\to B)</math>, то выводима и формула <math>B</math>.

Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление <math>\text{И}</math> называется семантически пригодным для языка <math>\text{Я}</math>, если любая выводимая в <math>\text{И}</math> формула языка <math>\text{Я}</math> является верной. Аналогично, исчисление <math>\text{И}</math> называется семантически полным в языке <math>\text{Я}</math>, если любая верная формула языка <math>\text{Я}</math> выводима в <math>\text{И}</math>.

Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат [[Гёдель, Курт|Курта Гёделя]] о том, что классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка ([[теорема Гёделя о полноте]]). С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является [[теорема Гёделя о неполноте]], утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики. С другой стороны  в 1936 году [[Генцен, Герхард|Герхард Генцен]] доказал полноту и непротиворечивость арифметики, используя примитивно рекурсивную арифметику с дополнительной аксиомой для [[Трансфинитная индукция|трансфинитной индукции]] до [[Порядковое число|ординала]] ε<sub>0</sub>.

На практике множество элементарных логических операций является обязательной частью набора инструкций всех современных [[микропроцессор]]ов и, соответственно, входит в [[язык программирования|языки программирования]]. Это является одним из важнейших практических приложений методов математической логики, изучаемых в современных учебниках информатики.{{Нет АИ|29|05|2020}}

== Разделы ==
В [[математическая предметная классификация|Математической предметной классификации]] математическая логика объединена в одну секцию верхнего уровня с [[основания математики|основаниями математики]], в которой выделены следующие разделы:<ref>{{Cite web |url=https://mathscinet.ams.org/mathscinet/msc/pdfs/classifications2020.pdf |title=MSC2020-Mathematics Subject Classification System |access-date=2021-05-22 |archive-date=2020-07-14 |archive-url=https://web.archive.org/web/20200714161256/https://mathscinet.ams.org/mathscinet/msc/pdfs/classifications2020.pdf |deadlink=no }}</ref>
* общая логика ({{lang-en|general logic}}), включает классическую [[Логика первого порядка|логику первого порядка]], [[Логика высшего порядка|логики высших порядков]] ([[Логика второго порядка|логику второго порядка]]), [[Комбинаторная логика|комбинаторную логику]], [[λ-исчисление]], [[Временная логика|временную логику]], [[Модальная логика|модальную логику]], [[Многозначная логика|многозначные логики]], [[Нечёткая логика|нечёткую логику]], [[Логика в информатике|логику в информатике]];
* [[теория моделей]];
* [[теория вычислимости]] и [[теория рекурсии]];
* [[теория множеств]];
* [[теория доказательств]] и [[конструктивная математика]];
* [[алгебраическая логика]] (включает вопросы изучения [[Булева алгебра|булевых алгебр]], [[алгебра Гейтинга|алгебр Гейтинга]], [[Квантовая логика|квантовых логик]], [[цилиндрическая алгебра|цилиндрических]] и [[полиадическая алгебра|полиадических]] алгебр, [[алгебра Поста|алгебр Поста]]);
* нестандартные модели.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор= [[Гильберт, Давид|Гильберт Д.]], [[Аккерман, Вильгельм|Аккерман В.]] |заглавие= Основы теоретической логики|оригинал= |ссылка= |викитека= |ответственный= |издание= |место= |издательство= [[Государственное издательство иностранной литературы]]|год= 1947|том= |страницы= |столбцы= |страниц= 306|серия= |isbn= |тираж= |ref= Гильберт, Аккерман}}
* {{книга |автор= {{нп4|Слупецкий, Ежи|Слупецкий Е.||Jerzy Słupecki}}, {{нп4|Борковский, Людвик|Борковский Л.|pl|Ludwik Borkowski}} |заглавие= Элементы математической логики и теории множеств |оригинал=Elementy logiki matematycznej i teorii mnogości |ссылка= |викитека= |ответственный= |издание= |место= М.|издательство= [[Прогресс (издательство)|Прогресс]]|год= 1965|том= |страницы= |страниц= 368|серия= |isbn= |тираж= |ref= Слупецкий, Борковский}}
* {{книга |автор= [[Стяжкин, Николай Иванович|Стяжкин Н. И.]]|заглавие= Формирование математической логики |ссылка= |викитека= |ответственный= |издание= |место= М.|издательство= [[Наука (издательство)|Наука]]|год= 1967|том= |страницы= |столбцы= |страниц= 508|серия= |isbn= |тираж= |ref= Стяжкин}}
* {{книга |автор= [[Столл, Роберт|Столл Р. Р.]] |заглавие= Множества. Логика. Аксиоматические теории|оригинал= |ссылка= |викитека= |ответственный= |издание= |место= |издательство= [[Просвещение (издательство)|Просвещение]]|год= 1968|том= |страницы= |столбцы= |страниц= 232|серия= |isbn= |тираж= |ref= Столл}}
* {{книга |автор= [[Бродский, Иосиф Нусимович|Бродский И. Н.]] |заглавие= Элементарное введение в символическую логику |ссылка= |викитека= |ответственный= |издание= |место= |издательство= Издательство Ленинградского университета|год= 1972|том= |страницы= |столбцы= |страниц= 63|серия= |isbn= |тираж= |ref= Бродский}}
* {{книга |автор= [[Клини, Стивен Коул|Клини С.К.]]|заглавие= Математическая логика|оригинал= |ссылка= |викитека= |ответственный= |издание= |место= М.|издательство= [[Мир (издательство)|Мир]]|год= 1973|том= |страницы= |столбцы= |страниц= 480|серия= |isbn= |тираж= |ref= Клини}}
* {{книга |автор= [[Новиков, Пётр Сергеевич|Новиков П. С.]] |заглавие= Элементы математической логики |ссылка= |викитека= |ответственный= |издание= |место= М.|издательство= Наука|год= 1973|том= |страницы= |столбцы= |страниц= 400|серия= |isbn= |тираж= |ref= Новиков}}
* {{книга |автор= {{нп4|Шенфилд, Джозеф|Шенфилд Дж.||Joseph R. Shoenfield}} |заглавие= Математическая логика|оригинал= |ссылка= |викитека= |ответственный= |издание= |место= М.|издательство= Наука|год= 1975|том= |страницы= |столбцы= |страниц= 400|серия= |isbn= |тираж= |ref= Шенфилд}}
* {{книга|автор= [[Марков, Андрей Андреевич (младший)|Марков А. А.]]|заглавие= Элементы математической логики|ответственный= Под ред. А. Г. Драгалина|место= М.|издательство= изд-во МГУ|год= 1984|страниц= 79|тираж=5660}}
* {{НФЭ||Логика символическая|[[Карпенко, Александр Степанович|А. С. Карпенко]]|ссылка=https://iphlib.ru/library/collection/newphilenc/document/HASH0194dc6f33a7460853864994}}

{{вс}}
{{Логика}}
{{Разделы математики}}

[[Категория:Математическая логика|*]]