МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Автор курса: Гринченков Дмитрий

доцент, к.т.н., заведующий кафедрой ПОВТ

законы и формы корректных человеческих рассуждений.

Этот раздел математики имеет особое

значение в изучении математических наук.

знаний, связанная с расширением, развитием и формализацией положений и законов

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

так как они определяют понятия и правила строгого выполнения логических

доказательств.

Строгое доказательство правильности тех или иных утверждений – это центральное звено любой математической теории.

понятия "математическое доказательство".
Поскольку математика является наукой, в которой все утверждения

доказываются с помощью умозаключений, математическая логика может представляться как инструмент (как совокупность средств) для описания правил построения множества других математических теорий.

некоторой предметной области удобно разделить на две части:
Содержательная часть теории

(семантика).
Формальная часть теории (синтаксис).

и позволяет описывать его поведение и свойства в терминах соответствующей

области знания; все утверждения такого описания имеют содержательный смысл.

осуществлять преобразования и формировать новые истинные утверждения на основе ранее

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

следует А.
Вывод: из С следует В.

Эта цепочка рассуждений может иметь

практически любое содержание.

студенты сдали сессию.
Петров  студент.
Следовательно, Петров сдал сессию.

символов, из которых строятся формулы, и правил, по которым доказывается

истинность новых формул.

основных задач этой теории является установление значения истинности (или ложности)

сложных (составных) высказываний и формирования в ее рамках средств, для описания реальных логических устройств.

этой теории – логика предикатов, она представляет расширение логики высказываний

в части описания множества отношений и двоичных функций (в том числе функций непрерывных переменных).

система, которая дает инструмент для доказательства истинных в данной теории

утверждений (теорем).

вв. до н.э. Оформление же ее как самостоятельной науки произошло

в трудах греческого философа Аристотеля (384  322 гг. до н.э.), который в своих "Аналитиках" систематизи-ровал известные до него сведения, и эта система стала впоследствии называться формальной логикой.

двадцать столетий.
Сравнительно рано возникла идея и о том, что,

записав исходные посылки формулами, похожими на математические, удастся заменить все рассуждения формальными "вычислениями".
Уже в средние века делались попытки даже создания таких "логических" машин.

ее развития. Идеи о построении логики на математической основе были

высказаны немецким математиком
Г. Лейбницем (1646  1716) в конце XVII века.

которые соединяются по особым правилам. Это позволит всякое рассуждение заменить

вычислением.
Лейбниц говорил: «Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, что­бы облегчить сам процесс нашего мышления».

(точнее, алгебре логики), принадлежит английскому ученому Дж. Булю (1815 

1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний.

введению символов в логику была получена основа для создания новой

науки  математической логики.
Применение математики к логике позволило представить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, ранее практически недоступных человеческому мышлению, что существенно расширило область логических исследований.
Ставшие в конце XIX века актуальными вопросы обоснования основных математических понятий также имели логическую природу, что привело к дальнейшему активному развитию математической логики.

взаимосвязей, которые отражаются в логической систематизации математики, в доказательстве математических

теорем.
Именно поэтому современную математическую логику определяют как раздел математики, посвященный изучению математических доказательств и вопросов оснований математики.

1925), посвященных теории формальных языков, и Д.Пеано (1858  1932),

который применил математическую логику для обоснования арифметики и теории множеств.

(1862  1943), выступившего в 20-х годах прошлого века с

программой обоснования математики на базе математической логики, именно с этого момента и начинается активное развитие современной математической логики.

теорий как синтаксических теорий, в которых все утверждения записываются формулами

в некотором алфавите и точно указываются правила вывода одних формул из других.
В теорию как составная часть входит математическая логика. Таким образом, математическая теория, непротиворечивость которой требовалось доказать, стала предметом другой математической теории, которую Гильберт назвал метаматематикой, или теорией доказательств.

формализованной аксиоматической теории самой математической логики.
Выбирая по-разному системы аксиом

и правила вывода одних формул из других, получают различные синтаксические логические теории. Каждую из них называют логическим исчислением.

Распространение аксиоматического метода в построении различных математических теорий, в первую

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

геометрии.

пытается дать определение исходных понятий (точки, прямой, плоскости).
В доказательстве

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

системе аксиом данной теории. Она означает, что из данной системы

аксиом нельзя логическим путем вывести два противоречащих друг другу утверждения.
Интерес инженеров связан с тем, что в рамках математической логики уже создан аппарат для расчета действия самых различных вычислительных и управляющих дискретных устройств и систем.

состоящих из технических объектов, вступающих в дискретные отношения, высказал в

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

практи­ке алгебру логики Дж. Буля для анализа и расчета релейных

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