Математическая логика

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

История

Вопрос о создании символической логики как универсального научного языка рассматривал Лейбниц в 1666 году в работе «Искусство комбинаторики» (De arte combinatoria). В середине XIX века появились первые работы по алгебраизации аристотелевой логики, сформировавшие первооснову исчисления высказываний (Буль, де Морган, Шрёдер). В работах Фреге и Пирса (конец 1870-х — начало 1880-х) в логику введены предметные переменные, кванторы и, тем самым, основано исчисление предикатов. В конце 1880-х годов Дедекинд и Пеано применили эти инструменты в попытках аксиоматизации арифметики, при этом Пеано создал удобную систему обозначений, закрепившуюся и в современной математической логике.

Уайтхед и Рассел создают в 1910—1913 годах трактат Principia Mathematica, который оказал исключительное влияние на все последующее развитие математической логики. Ещё одной важной вехой в развитии логики стало обнаружение свойственных уровню развития логических исчислений и теории множеств конца XIX века парадоксов, в преодоление которых появилась концепция интуиционизма и интуиционистская логика (Брауэр, 1908) и, в качестве альтернативы, Гильбертом создана программа обоснования математики посредством аксиоматической формализации с использованием строго ограниченных средств, не приводящих к противоречиям.

Основные положения

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

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

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

Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат Курта Гёделя о том, что классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка (теорема Гёделя о полноте). С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является теорема Гёделя о неполноте, утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики.

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

Разделы

В Математической предметной классификации математическая логика объединена в одну секцию верхнего уровня с основаниями математики, в которой выделены следующие разделы:

• общая логика (англ. general logic), включает классическую логику первого порядка, логики высших порядков (логику второго порядка), комбинаторную логику, λ-исчисление, временную логику, модальную логику, многозначные логики, нечёткую логику, логику в информатике;
• теория моделей;
• теория вычислимости и теория рекурсии;
• теория множеств;
• теория доказательств и конструктивная математика;
• алгебраическая логика (включает вопросы изучения булевых алгебр, алгебр Гейтинга, квантовых логик, цилиндрических и полиадических алгебр, алгебр Поста);
• нестандартные модели.

Литература

• Бродский И. Н. Элементарное введение в символическую логику. — Издательство Ленинградского университета, 1972. — 63 с.
• Марков А. А.. Элементы математической логики. М.: Изд-во МГУ, 1984.
• Новиков П. С. Элементы математической логики. 2-ое изд. М.: Наука, 1973. — 400 с.
• Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.
• Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 508 с.
• Шенфилд Дж. Математическая логика. М.: Наука, 1975.
• Клини С. К. Математическая логика. — М.: изд-во Мир, [1967]1973.

Отрывок, характеризующий Математическая логика

Приехав на Патриаршие пруды, Пьер отыскал дом Баздеева, в котором он давно не бывал. Он подошел к калитке. Герасим, тот самый желтый безбородый старичок, которого Пьер видел пять лет тому назад в Торжке с Иосифом Алексеевичем, вышел на его стук.
– Дома? – спросил Пьер.
– По обстоятельствам нынешним, Софья Даниловна с детьми уехали в торжковскую деревню, ваше сиятельство.
– Я все таки войду, мне надо книги разобрать, – сказал Пьер.
– Пожалуйте, милости просим, братец покойника, – царство небесное! – Макар Алексеевич остались, да, как изволите знать, они в слабости, – сказал старый слуга.
Макар Алексеевич был, как знал Пьер, полусумасшедший, пивший запоем брат Иосифа Алексеевича.
– Да, да, знаю. Пойдем, пойдем… – сказал Пьер и вошел в дом. Высокий плешивый старый человек в халате, с красным носом, в калошах на босу ногу, стоял в передней; увидав Пьера, он сердито пробормотал что то и ушел в коридор.
– Большого ума были, а теперь, как изволите видеть, ослабели, – сказал Герасим. – В кабинет угодно? – Пьер кивнул головой. – Кабинет как был запечатан, так и остался. Софья Даниловна приказывали, ежели от вас придут, то отпустить книги.
Пьер вошел в тот самый мрачный кабинет, в который он еще при жизни благодетеля входил с таким трепетом. Кабинет этот, теперь запыленный и нетронутый со времени кончины Иосифа Алексеевича, был еще мрачнее.
Герасим открыл один ставень и на цыпочках вышел из комнаты. Пьер обошел кабинет, подошел к шкафу, в котором лежали рукописи, и достал одну из важнейших когда то святынь ордена. Это были подлинные шотландские акты с примечаниями и объяснениями благодетеля. Он сел за письменный запыленный стол и положил перед собой рукописи, раскрывал, закрывал их и, наконец, отодвинув их от себя, облокотившись головой на руки, задумался.
Несколько раз Герасим осторожно заглядывал в кабинет и видел, что Пьер сидел в том же положении. Прошло более двух часов. Герасим позволил себе пошуметь в дверях, чтоб обратить на себя внимание Пьера. Пьер не слышал его.
– Извозчика отпустить прикажете?
– Ах, да, – очнувшись, сказал Пьер, поспешно вставая. – Послушай, – сказал он, взяв Герасима за пуговицу сюртука и сверху вниз блестящими, влажными восторженными глазами глядя на старичка. – Послушай, ты знаешь, что завтра будет сражение?..
– Сказывали, – отвечал Герасим.
– Я прошу тебя никому не говорить, кто я. И сделай, что я скажу…
– Слушаюсь, – сказал Герасим. – Кушать прикажете?
– Нет, но мне другое нужно. Мне нужно крестьянское платье и пистолет, – сказал Пьер, неожиданно покраснев.
– Слушаю с, – подумав, сказал Герасим.
Весь остаток этого дня Пьер провел один в кабинете благодетеля, беспокойно шагая из одного угла в другой, как слышал Герасим, и что то сам с собой разговаривая, и ночевал на приготовленной ему тут же постели.
Герасим с привычкой слуги, видавшего много странных вещей на своем веку, принял переселение Пьера без удивления и, казалось, был доволен тем, что ему было кому услуживать. Он в тот же вечер, не спрашивая даже и самого себя, для чего это было нужно, достал Пьеру кафтан и шапку и обещал на другой день приобрести требуемый пистолет. Макар Алексеевич в этот вечер два раза, шлепая своими калошами, подходил к двери и останавливался, заискивающе глядя на Пьера. Но как только Пьер оборачивался к нему, он стыдливо и сердито запахивал свой халат и поспешно удалялся. В то время как Пьер в кучерском кафтане, приобретенном и выпаренном для него Герасимом, ходил с ним покупать пистолет у Сухаревой башни, он встретил Ростовых.


1 го сентября в ночь отдан приказ Кутузова об отступлении русских войск через Москву на Рязанскую дорогу.
Первые войска двинулись в ночь. Войска, шедшие ночью, не торопились и двигались медленно и степенно; но на рассвете двигавшиеся войска, подходя к Дорогомиловскому мосту, увидали впереди себя, на другой стороне, теснящиеся, спешащие по мосту и на той стороне поднимающиеся и запружающие улицы и переулки, и позади себя – напирающие, бесконечные массы войск. И беспричинная поспешность и тревога овладели войсками. Все бросилось вперед к мосту, на мост, в броды и в лодки. Кутузов велел обвезти себя задними улицами на ту сторону Москвы.
К десяти часам утра 2 го сентября в Дорогомиловском предместье оставались на просторе одни войска ариергарда. Армия была уже на той стороне Москвы и за Москвою.
В это же время, в десять часов утра 2 го сентября, Наполеон стоял между своими войсками на Поклонной горе и смотрел на открывавшееся перед ним зрелище. Начиная с 26 го августа и по 2 е сентября, от Бородинского сражения и до вступления неприятеля в Москву, во все дни этой тревожной, этой памятной недели стояла та необычайная, всегда удивляющая людей осенняя погода, когда низкое солнце греет жарче, чем весной, когда все блестит в редком, чистом воздухе так, что глаза режет, когда грудь крепнет и свежеет, вдыхая осенний пахучий воздух, когда ночи даже бывают теплые и когда в темных теплых ночах этих с неба беспрестанно, пугая и радуя, сыплются золотые звезды.
2 го сентября в десять часов утра была такая погода. Блеск утра был волшебный. Москва с Поклонной горы расстилалась просторно с своей рекой, своими садами и церквами и, казалось, жила своей жизнью, трепеща, как звезды, своими куполами в лучах солнца.
При виде странного города с невиданными формами необыкновенной архитектуры Наполеон испытывал то несколько завистливое и беспокойное любопытство, которое испытывают люди при виде форм не знающей о них, чуждой жизни. Очевидно, город этот жил всеми силами своей жизни. По тем неопределимым признакам, по которым на дальнем расстоянии безошибочно узнается живое тело от мертвого. Наполеон с Поклонной горы видел трепетание жизни в городе и чувствовал как бы дыханио этого большого и красивого тела.
– Cette ville asiatique aux innombrables eglises, Moscou la sainte. La voila donc enfin, cette fameuse ville! Il etait temps, [Этот азиатский город с бесчисленными церквами, Москва, святая их Москва! Вот он, наконец, этот знаменитый город! Пора!] – сказал Наполеон и, слезши с лошади, велел разложить перед собою план этой Moscou и подозвал переводчика Lelorgne d'Ideville. «Une ville occupee par l'ennemi ressemble a une fille qui a perdu son honneur, [Город, занятый неприятелем, подобен девушке, потерявшей невинность.] – думал он (как он и говорил это Тучкову в Смоленске). И с этой точки зрения он смотрел на лежавшую перед ним, невиданную еще им восточную красавицу. Ему странно было самому, что, наконец, свершилось его давнишнее, казавшееся ему невозможным, желание. В ясном утреннем свете он смотрел то на город, то на план, проверяя подробности этого города, и уверенность обладания волновала и ужасала его.
«Но разве могло быть иначе? – подумал он. – Вот она, эта столица, у моих ног, ожидая судьбы своей. Где теперь Александр и что думает он? Странный, красивый, величественный город! И странная и величественная эта минута! В каком свете представляюсь я им! – думал он о своих войсках. – Вот она, награда для всех этих маловерных, – думал он, оглядываясь на приближенных и на подходившие и строившиеся войска. – Одно мое слово, одно движение моей руки, и погибла эта древняя столица des Czars. Mais ma clemence est toujours prompte a descendre sur les vaincus. [царей. Но мое милосердие всегда готово низойти к побежденным.] Я должен быть великодушен и истинно велик. Но нет, это не правда, что я в Москве, – вдруг приходило ему в голову. – Однако вот она лежит у моих ног, играя и дрожа золотыми куполами и крестами в лучах солнца. Но я пощажу ее. На древних памятниках варварства и деспотизма я напишу великие слова справедливости и милосердия… Александр больнее всего поймет именно это, я знаю его. (Наполеону казалось, что главное значение того, что совершалось, заключалось в личной борьбе его с Александром.) С высот Кремля, – да, это Кремль, да, – я дам им законы справедливости, я покажу им значение истинной цивилизации, я заставлю поколения бояр с любовью поминать имя своего завоевателя. Я скажу депутации, что я не хотел и не хочу войны; что я вел войну только с ложной политикой их двора, что я люблю и уважаю Александра и что приму условия мира в Москве, достойные меня и моих народов. Я не хочу воспользоваться счастьем войны для унижения уважаемого государя. Бояре – скажу я им: я не хочу войны, а хочу мира и благоденствия всех моих подданных. Впрочем, я знаю, что присутствие их воодушевит меня, и я скажу им, как я всегда говорю: ясно, торжественно и велико. Но неужели это правда, что я в Москве? Да, вот она!»