Лейбниц Г.В

Введение

Лекция 1

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

Предпосылки появления математической логики. Идея построения универсального языка для описания всей математики возникла еще в 17 веке (Лейбниц).

Готфрид Вильгельм Лейбниц (1646-1716)

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

В середине 19 в. Буль, Морган, Пирс разработали язык алгебры логики, были введены такие понятия, как высказывания, предикаты, предметные переменные, кванторы. Во многом разрабатываемый математический аппарат опирался на некую самоочевидность, которая была нарушена в конце 19 в. появлением парадоксов.

Буль Джордж (Boole George) 2.11.1815 – 8.12.1864 – английский математик и логик. Заложил основы математической логики.

Морган Огастес (De Morgan Augustus) 27.6.1806 – 8.3.1871 – шотландский математик и логик.

Пирс Чарльз Сандере (Peirce Charles Sanders) 10.9.1839 – 19.4.1914 – американский математик, филисоф и логик. Ввел понятие квантора.

Вот примеры парадоксов [1,7].

Пример 1: Парадокс лжеца.

Некто говорит: «Я лгу». Он лжет и не лжет одновременно.

Пример 2: Парадокс Рассела:

· Множество может являться элементом самого себя – множество всех множеств.

· Множество может не являться элементом самого себя – множество всех котов.

· Рассмотрим множество А всех таких множеств Х, что Х не есть элемент Х.

· Если А принадлежит А, то согласно определению А, А не принадлежит А.

· Если А не принадлежит А, то согласно определению А, А принадлежит А.

· Противоречие!

Рассел Бертран Артур Уильям (Russel Bertrand Arthur William) 18.5.1872 – 2.2.1970 – английский математик, логик, философ. Сформулировал в 1902 г. один из парадоксов теории множеств.

Два пути преодоления возникших трудностей:

1. Брауэр – интуиционистский подход к математике (отказ от закона исключенного третьего). Для доказательства существования элемента не достаточно привести к противоречию предположение об его несуществовании, этот элемент необходимо «указать».

2. Гильберт – аксиоматический подход. Были введены такие понятия, как формальный язык, теория (исчисление). Понятия: теория, предложения теории, аксиомы, правила вывода, теоремы, полнота, непротиворечивость.

Брауэр Лёйтзен Эгберт Ян (Brouwer Luitzen Egbert Jan) 27.2.1881 – 2.12.1966 – голландский математик, основоположник математическому интуиционизму.

Гильберт Давид (Hilbert David) 28.1.1862 – 14.2.1943 – немецкий математик, одним из многочисленных направлений научной деятельности были логические основы математики.

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

В 1930 Гёдель доказал полноту и непротиворечивость исчисления предикатов первого порядка. Однако, тот же Гедель в 1931 году доказал теорему о неполноте формальной арифметики – теории, основанной на исчислении предикатов первого порядка.

Гёдель Курт (Godel Kurt) 28.4.1906 – 14.1.1978 – австрийский логик и математик, автор теорем Гёделя о полноте и неполноте.

Тезис Черча об уточнении интуитивного понятия алгоритма – рекурсивные функции. Машина Тьюринга – тоже уточнение понятия алгоритма.

Чёрч Алонзо (Church Alonzo) 1903 -???? – американский логик и математик, внес большой вклад в развитие математической логики и теории автоматов.

Тьюринг Алан Матисон (Turing Alan Mathison) 23.6.1912 – 7.6.1954 – английский математик, ввел в 1936 г. понятие уточненного абстрактного эквивалента алгоритма, автор абстрактной вычислительной машины – машины Тьюринга.

Понятия разрешимости (объекта по отношению к некоторому свойству), перечислимости (множеств) вычислимости (функций) и сложности алгоритма.

Теория формальных языков - математические основы построения трансляторов.

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

Исчисление – аксиомы, правила вывода.

Порождение и распознавание.

Дата добавления: 2013-12-13