- •История логики
- •Предыстория логики
- •Логика в древнегреческой философии До Платона
- •Логика Платона
- •Логика Аристотеля
- •Логика стоиков
- •Логика в странах Востока Логика в Индии
- •Логика в Китае
- •Современная логика
- •Логика высказываний
- •]Основные понятия
- •Правила построения формул логики высказываний
- •Соглашения о скобках
- •Истинностное значение
- •Тождественно истинные формулы (тавтологии)
- •Исчисление высказываний
- •Логическая операция
- •Формальная логика
- •Математическая логика
- •Отрицание
- •Схемотехника
- •Конъюнкция
- •Булева алгебра
- •Многозначная логика
- •Классическая логика
- •Схемотехника
- •Дизъюнкция
- •Булева алгебра
- •Многозначная логика
- •Классическая логика
- •Схемотехника
- •Импликация
- •Булева логика
- •Классическая логика
- •Штрих Шеффера
- •Стрелка Пирса
- •Полином Жегалкина
- •Предпосылки
- •Cуществование и единственность представления (теорема Жегалкина)
- •Представление функции в виде полинома Жегалкина с помощью эквивалентных преобразований днф
- •С помощью эквивалентных преобразований сднф
- •Логика высказываний
- •Основные понятия
- •Правила построения формул логики высказываний
- •Соглашения о скобках
- •Истинностное значение
- •Тождественно истинные формулы (тавтологии)
- •Исчисление высказываний
- •Алгебра логики
- •Определение
- •Аксиомы
- •Логические операции
- •Свойства логических операций
- •История
- •Метод равносильных преобразований
- •Метод диаграмм Вейча.
- •Алгоритм построения таблицы истинности
- •Элементарная дизъюнкция
- •Элементарная конъюнкция
- •§ 1. Понятие формулы исчисления высказываний.
- •Исчисление высказываний
- •1.2.3.1 Правила подстановки
- •1.2.3.2. Правила введения и удаления логических связок
- •2.1 Алгебра предикатов
- •3 Законы алгебры предикатов
- •Квантор
- •Примеры
- •Введение в понятие
- •Кванторы в математической логике
- •Вложенные кванторы Свободные и связанные переменные
- •Операции над кванторами
- •Ограниченные кванторы История появления
- •Теория алгоритмов
- •Возникновение теории алгоритмов
- •Модели вычислений
- •Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы
- •Современное состояние теории алгоритмов
- •Анализ трудоёмкости алгоритмов
- •Классы сложности
- •Машина Тьюринга
- •Устройство машины Тьюринга
- •Описание машины Тьюринга
- •Пример машины Тьюринга
- •Полнота по Тьюрингу
- •Варианты машины Тьюринга
- •Машина Тьюринга, работающая на полубесконечной ленте
Теория алгоритмов
Тео́рия алгори́тмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.
Возникновение теории алгоритмов
Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.
Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.
Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.
Модели вычислений
Машина Тьюринга
Лямбда-исчисление — рассматривается пара — λ-выражение и его аргумент, — а вычислением считается применение, или апплицирование первого члена пары ко второму. Это позволяет отделить функцию и то, к чему она применяется. В более общем случае вычислением считаются цепочки, начинающиеся с исходного λ-выражения, за которым следут конечная последовательность λ-выражений, каждое из которых получается из предыдущего применением β-редукции, то есть правила подстановки.
Комбинаторная логика — трактовка вычисления сходна с λ-исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки Y имеет нормальную форму в комбинаторной логике, а в λ-исчислении — не имеет). Комбинаторная логика была первоначально разработана для изучения природы парадоксов и для построения концептуально ясных оснований математики, причем представление о переменной исключалось вовсе, что помогало прояснить роль и место переменных в математике.
Регистровые машины (англ.)
RAM-машина (англ.) — абстрактная вычислительная машина, моделирующая компьютер с произвольным доступом к памяти. Именно эта модель вычислений наиболее часто используется при анализе алгоритмов.