Лекция 2. Математическая логика и теория алгоритмов

### Введение

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

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

Стройную научную систему логики впервые разработал великий греческий учёный Аристотель (ученик Платона, воспитатель Александра Македонского). В своём логическом своде «Органон» («Категории», «Об истолковании», «Аналитики» 1-я и 2-я, «Топика») он создал раздел формальной логики силлогистику. Его труды оказали влияние на развитие логической науки во всём мире. В Европе до 17 века вся логика развивалась на основе аристотелевского учения.

В последние сто лет в логике произошла научная революция и на смену традиционной логике пришла современная логика, называемая также математической или символической логикой. В основе математической логики полoжены идеи Г. Лейбница (1646-1716) о возможности представить доказательство как математическое вычисление. Дж. Буль (1815-1864) истолковал умозаключение как результат решения логических равенств, после чего теория умозаключения приобрела вид своеобразной алгебры.

Основными разделами современной математической логики (её классического варианта) являются логика высказываний, идущая от Дж. Буля и не охватывающая силлогистику Аристотеля, и значительно более широкая логика предикатов, содержащая силлогистику как часть. Современный вид математическая логика приобрела в 1880-е годы в трудах немецкого логика, математика и философа Г. Фреге(1848-1925). Он дал первую аксиоматику логики высказываний и предикатов и сделал попытку свести математику к логике.

Значительный вклад в развитие логики внесли:Б.Рассел (Russel), А.Н.Уайтхед (Whitehead), Д.Гилберт (Hilbert), К.Гедель (Godel), А.Тарский, А.Черч (Church).

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

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

Аристотель | Г. Лейбниц | Дж. Буль | Г. Фреге | Б.Рассел
А.Н.Уайтхед | Д.Гилберт | К.Гедель | А.Тарский | А.Черч