История математической логики кратко

Обновлено: 05.07.2024

В середине XIX века сын небогатого ремесленника Джордж Буль совершил одно из важных открытий для современной науки, представив весь мир в виде нулей и единиц. Именно благодаря ему уже через сто лет появилась минимально возможная единица значения — бит, которой мы оперируем до сих пор.

Еще Ницше предупреждал, что сражающемуся с чудовищами следует остерегаться, как бы самому не стать чудовищем. Таким чудовищем, без сомнения, следует признать современную логику, потому что она сыграла злую шутку со всеми, кто всерьез ей занимался. Готтлоб Фреге ушел в депрессию и исступленный антисемитизм, Георг Кантор умер в психиатрической лечебнице, Курту Гёделю постоянно чудилось, что холодильник сильно гудит, вокруг снуют призраки, а окружающие хотят его отравить (ну а когда его жена оказалась в больнице с травмой позвоночника, то никто и не заметил, как он умер от голода). Неужели быть психически здоровым — это исключительный случай для любого логика?

Ясно одно: основатель символической логики Джордж Буль сохранил здравый рассудок — возможно потому, что он сам и создал тот самый лабиринт, из которого не смогли найти выход его последователи. Буль создал бинарную систему из нулей и единиц, которая является основой любого современного языка программирования.

Только вот утверждать, что Джордж Буль был просто математиком, было бы ошибкой. Он родился в 1815 году в английском городе Линкольн в семье сапожника и с самых ранних лет прослыл вундеркиндом: самостоятельно выучив латынь и греческий, он в двенадцатилетнем возрасте так хорошо перевел оду Горация, что преисполненный гордости отец опубликовал ее, а учитель местной школы даже усомнился, что ребенок вообще способен на такую глубину чувств.

Все это никак не смутило Буля. Он продолжил изучать языки и освоил немецкий, итальянский и французский, а в 16 лет, когда дела отца пошли плохо, стал основным кормильцем большой семьи: работая вначале помощником учителя, а потом и учителем в Институте механики своего родного города Линкольн. Мальчика привлекала карьера священника, однако педагогическая стезя в итоге одержала верх, и через четыре года 20-летний Буль открыл собственную школу

Его обращение к математике после глубокого интереса к классическим и современным языкам связано с откровением, которое он испытал в 17 лет. В этом откровении не было ничего сверхъестественного — не сравнить с опытами Чарльза Бэббиджа, который пытался выманить дьявола из своего царства, очертив себя кругом из крови (тот опыт провалился, а сам Бэббидж стал веселым агностиком). В случае Буля не было ни искушения, ни драмы, просто в очередной раз проходя по тропинке через луг, он вдруг задался вопросом: почему люди обозначают такие разные вещи, например яблоки и груши, одними и теми же знаками — в этом случае цифрой 3? Получается, в человеческом мозге есть какая-то природная сила, которая сопровождает любое осознание и любую мысль, позволяя одинаковым образом считать и яблоки, и груши?

В самой постановке вопроса нет ничего революционно нового: многие поколения математиков до Буля были убеждены в том, что числа — это что-то априорное, изначально присущее нашему рассудку ровно в той же мере, что и чувство прекрасного, доброго и хорошего. Однако в этой точке зрения есть одна загвоздка: мысль о том, что каждый человек — математик от рождения, может, пожалуй, возмутить какого-нибудь математика, притом что вся остальная общественность вряд ли сильно впечатлится этим. И потом — такое утверждение порождает серьезные логические проблемы. Скажем, человек от рождения знает о числе 3. А о числах 4001 и 41627? А об отрицательных числах? А об иррациональном и трансцендентном числе π?

Таким образом, мы только что описали искомый бумажник, который для простоты будем называть X, и можем преобразовать это описание в уравнение:

1 — не-X (то есть вселенная без того, что не является моим бумажником) = 0 + X (то есть ничто плюс бумажник).

Этим приемом Булю удалось добиться того, что было невозможно в классической математике, потому что теперь вычисления стало можно производить с чем угодно. В определенном смысле такой способ мышления значительно точнее, чем традиционный подход, основанный на числах: ведь когда я ищу потерянный бумажник, я не думаю о красно-коричневом кожаном бумажнике шириной 12,5 см, высотой 9 см, глубиной 2 см, содержащем ровно 67 евро и 58 центов. Нет, я просто ищу и не нахожу знакомый мне предмет. В этот момент идентификация предмета происходит не через числа, а через восприятие — то есть через осознание того факта, что нужная мне вещь отсутствует на привычном месте. Все это скорее роднит булеву логику с обычной операцией поиска, а не с операцией подсчета.

Если вы успели уследить за моими объяснениями, то уже начинаете понимать, что идеи Буля были такими же революционными, каким было открытие электрического флюида. Они позволяли описывать любой объект и любое соотношение объектов в логике нулей и единиц: бумажник (есть или нет), состояние двери в квартиру (открыта или закрыта), количество сорванных с дерева яблок или груш в корзине. Числа передают только один из аспектов окружающего мира (квант), а булева логика позволяет описывать все мыслимые качества: голос, который приглашает покупателей в магазин, данные о местоположении кита или движение руки (которое за человеком тут же повторяет робот). Это даже не математика, это шаг к созданию совершенно новой универсальной письменности. Какова же наименьшая единица этой письменности? В логике наличия и отсутствия это уже не цифра, а минимально возможная единица значения — бит.

Доступное нам пространство для вычислений удваивается с каждым битом, как в задаче о шахматной доске, где за первую клетку изобретатель шахмат запросил у короля одно рисовое зернышко, а за каждую следующую вдвое больше, чем за предыдущую. Если тремя битами можно записать восемь чисел (от 0 до 7), то четырьмя битами — уже 16 чисел, пятью битами — 32 числа, а шестьдесят четыре бита уже позволяют нам оперировать невообразимым количеством из 18 квинтиллионов 446 квадриллионов 744 триллионов с мелочью чисел. При всем этом число является лишь одним из возможных выражений последовательности битов, ведь с таким же успехом ее можно представить в виде акустической волны или букв (а если это ASCI-код, то это будут такие же буквы, какими вы читаете эту книжку).

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

Много лет назад, когда я впервые увидел эту формулу, она поразила меня как гром среди ясного неба. Почему? Да потому что она переворачивает привычные представления о мире с ног на голову. Первым в ней бросается в глаза то, что она описывает не равновесие, а структурную асимметрию мироустройства. При этом такая асимметрия вполне знакома нам, хотя и кажется чуждой: мы же знаем, что все, что было оцифровано, может быть воспроизведено бессчетное количество раз. Если же применить эту формулу к себе самому, то сразу начинаешь ощущать ее беспощадность, ведь она выражает мысль, которую каждый всегда гнал от себя: я — всего лишь один из многих, я образую популяцию, мое существование необязательно. В этот момент нас настигает болезненное осознание и когнитивный диссонанс: смутные подозрения реализовались, потому что мы-то знаем, что человеческое тело — не цифровая сущность, и его нельзя просто так взять и воспроизвести. Однако именно в этом и состоит фокус — булева формула дарит любой заурядной вещи возможность бесконечного существования. Это формула-обманка, подражающая природе, почти идеальная машина, которая, как и все успешные машины до нее, будет преобразовывать мир по своему образу и подобию. Я уже говорил, что булев закон поразил меня как гром среди ясного неба, но за этим последовало изумление: я ждал, что грозовая туча разразится ливнем, но не услышал ничего, кроме звенящей тишины. Дело в том, что мне так до сих пор и не удалось встретить хоть кого-нибудь, кто находит булеву логику естественной или хотя бы понятной. Наверное, именно поэтому люди пишут книги и утверждают в них, что могут точно определить момент начала какой-то истории. Как, например, понять фильм, если включаешь телевизор только в момент основной развязки?

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

Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления (отсюда одно из ее названий - формальная логика), были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.

Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

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

Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

В XX веке огромную роль в развитии математической логики сыграл Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований самой математики. Наконец, в последние десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).

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

Хорошо известно, что в математике нет двусмысленностей. Учитывая математический аргумент, он либо действителен, либо просто нет. Оно не может быть ложным и истинным одновременно.

Особый аспект математики состоит в том, что у нее есть формальный и строгий язык, с помощью которого можно определить обоснованность аргумента. Что делает определенное рассуждение или любое математическое доказательство неопровержимым? Вот в чем суть математической логики.

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

Для этого используются аксиомы и другие математические аспекты, которые будут развиты позже.

Происхождение и история

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

Аристотель

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

Математики Джордж Буль и Георг Кантор также оказали большое влияние в то время, внося важный вклад в теорию множеств и таблицы истинности, в которых они выделяются среди других аспектов, булевой алгеброй (Джорджа Буля) и аксиомы выбора. (Джордж Кантор).

Есть также Август Де Морган с хорошо известными законами Моргана, которые рассматривают отрицания, союзы, дизъюнкции и условные выражения между предложениями, ключи к развитию символической логики, и Джон Венн со знаменитыми диаграммами Венна.

В 20 веке, примерно между 1910 и 1913 годами, Бертран Рассел и Альфред Норт Уайтхед выделяются своей публикацией Principia mathematica, набор книг, которые собирают, развивают и постулируют серию аксиом и результатов логики.

Что изучает математическая логика?

Предложения

Математическая логика начинается с изучения предложений. Утверждение - это утверждение, которое без какой-либо двусмысленности можно сказать, верно оно или нет. Ниже приведены примеры предложений:

2+4=6.
5 2 =35.
В 1930 году в Европе произошло землетрясение.

Первое - истинное утверждение, второе - ложное. Третье, даже если человек, читающий его, может не знать, правда ли это или сразу, - это утверждение, которое можно проверить и определить, действительно ли это произошло.

Ниже приведены примеры выражений, которые не являются предложениями:

Она блондинка.
2х = 6.
Поиграем!
Вам нравится кино

Последние два утверждения не соответствуют утверждению, поскольку их невозможно отрицать или подтверждать.

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

Утверждения, сделанные с помощью предложений, обычно длинные, поэтому всегда утомительно писать их, как мы уже видели. По этой причине используется символический язык. Предложения обычно обозначаются заглавными буквами, например P, Q, R, S, так далее. И следующие символические связки:

В взаимный условного предложения

И встречный (или противоположный) предложения

Таблицы истинности

Еще одно важное понятие в логике - это таблица истинности. Значения истинности предложения - это две возможности для предложения: истинное (которое будет обозначено V и будет сказано, что его значение истинности равно V) или ложное (которое будет обозначено F и будет сказано, что его значение действительно F).

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

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

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

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

Ниже приведены таблицы истинности логических связок:

Существуют пропозициональные формулы, которые получают только значение V в своей таблице истинности, то есть последний столбец их таблицы истинности имеет только значение V. Эти типы формул известны как тавтологии. Например:

Ниже приводится таблица истинности формулы

Говорят, что из формулы α логически следует другая формула β, если α истинно каждый раз, когда β истинно. То есть, в таблице истинности α и β строки, где α имеет V, β также имеют V. Это интересуют только строки, в которых α имеет значение V. Обозначения для логической импликации следующие. :

В следующей таблице приведены свойства логической импликации:

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

В следующих таблицах обобщены свойства логической эквивалентности:

Типы математической логики

Существуют разные типы логики, особенно если принять во внимание прагматическую или неформальную логику, указывающую, среди прочего, на философию.

Что касается математики, типы логики можно резюмировать следующим образом:

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

Области

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

Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления (отсюда одно из ее названий - формальная логика), были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - Аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.

Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

22 1 РЕКУРСИВНЫЕ ФУНКЦИИ

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

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.

Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

ГОСТ

Математическая логика — это подраздел математики, который занимается изучением формальных систем.

История возникновения

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

Основоположником логики считается древнегреческий философ Аристотель, который жил в четвёртом веке до нашей эры. Изначально он заметил, что при доказательстве каких-либо положений на основании других утверждений, за основу берут не их конкретное содержание, а только взаимные отношения их форм. Другой учёный времён Древней Греции, Евклид, выполнил систематизацию большого числа утверждений геометрии с точки зрения логики. Он ввёл в обиход понятие метода аксиом и заложил начало пониманию геометрии как науки, основанной на аксиомах, а понимание всей математической науки как набор математических теорий.

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

Появление науки, названной математической логикой, связано с трудами английского учёного Джона Буля. Он создал алгебру логики, которая впоследствии получила название Булева алгебра. Она явилась итогом использования в логике методов алгебры. Заметным шагом в развитии математической логики явилось появление неевклидовой геометрии, прописанной в работах русского учёного Н.И. Лобачевского. В конце девятнадцатого века были выявлены парадоксы в теории множеств, которые выдвинули в число проблем математической логики проблему обоснования самой математики. Немецкий учёный Г. Фреге увидел разрешение этой проблемы в приведении математики к логике. Он использовал инструментарий математической логики, чтобы обосновать арифметику. Уже в двадцатом веке на основе математической логики была создана теория алгоритмов.

Готовые работы на аналогичную тему

Логика высказываний

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

Приедём некоторые примеры:

А = “Значение √2 будет иррациональным”.

Б = “Неправильно, что значение √2 будет иррациональным”.

В = “Величина √2+1 будет иррациональной”.

Г = “Если величина √2 будет иррациональной, то значение √2 +1 тоже будет иррациональным”.

Д = “Значение х считается иррациональным”.

Е = “Сколько времени?”

Ж = “Иванов! Вызываю вас к доске для решения задачи!”

Из приведённых выше примеров, А, Б, В и Г считаются высказываниями, остальные не являются таковыми. Предложения Е и Ж не повествовательные, а истинность или ложность предложения Д, которое является повествовательным, находится в прямой зависимости от полученного переменной х значения. Высказывания А, В и Г являются истинными, а высказывание Б является ложным. Точнее, значение истинности А, В и Г равно величине истина, соответственно о же само для Б это ложь. Истинные высказывания принято обозначать единицей (1), а ложные нулём (0). Высказывания А и В называются простыми, а высказывания Б и Г называются составными, так как они получены из простых высказываний А и В. Из этого примера можно видеть, что в языковых формах есть методы выстраивания высказываний из набора других высказываний. Эти методы называются операциями. В обычных разговорных языках можно выделить большое количество подобных операций.

В математической логике можно выделить следующие основные операции. Предположим Х и Y определённые выказывания, тогда:

В приведённом выше примере высказывание Б будет отрицанием высказывания А.

Основные пять вышеперечисленных операций имеют следующие символьные обозначения:

& обозначает конъюнкцию.
∨ обозначает дизъюнкцию.
¬ обозначает отрицание.
→ обозначает импликацию.
↔ обозначает эквиваленцию.

Эти знак &, ∨, ¬, →, ↔ принято называть связками. Связь определения истинности вновь образованных высказываний от величин истинности их начальных составляющих моет быть определена таблицей истинности связок.

Логические формулы высказываний

Выше высказывания определялись как некие предложения разговорного языка в повествовательной форме, то есть как объекты лингвистики. Для представления таких объектов методами математики применяется термин логические формулы высказываний. Атомарными логическими формулами высказываний являются заданные символы латинского алфавита с индексацией или без неё. Такими символами могут быть следующие знаки: U, V, W, X, Y, Z.

Логическими формулами высказываний являются:

Атомарные выражения.
Символика обозначения истинности 1 и ложности 0.
Формулы типа (F)&(G), (F)∨(G), ¬(F), (F)→(G), (F)↔(G).

Читайте также: