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

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

Содержание

ВВЕДЕНИЕ 2

1.Логические исчисления 3

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

1.2Понятие формальной теории 7

1.3Исчисление высказываний (ИВ) 8

1.4Теорема дедукции 9

1.5Непротиворечивость и полнота исчисления высказываний 11

1.6Методы проверки выводимости формул ИВ 12

1.7Понятие предиката 16

1.8Логические эквивалентности с кванторами 20

1.9Термы и формулы в исчислении предикатов 21

1.10Аксиомы и правила вывода в исчислении предикатов 22

1.11Теоремы об исчислении предикатов первого порядка 23

1.12Метод резолюций для исчисления предикатов 24

2.Элементы теории алгоритмов и рекурсивных функций 28

2.1Понятие алгоритма 28

2.2Машина Тьюринга 29

2.3Вычисление функций на машине Тьюринга 34

2.4Алгоритмически неразрешимые задачи 37

2.5Примитивно рекурсивные функции 40

2.6Частично рекурсивные функции 44

2.7Характеристики сложности алгоритмов 48

2.8Классы сложности и 51

Литература 54

ВВЕДЕНИЕ

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

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

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

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

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

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

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