Введение

Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 18-го века.

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

Данное учебно-практическое пособие соответствует учебной программе курса «Математическая логика и теория алгоритмов» для специальностей «Информационные системы и технологии», «Вычислительные машины, комплексы и сети».

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

1. Содержание

   • Введение
   • Программа курса математическая логика и терия алгоритмов
   • Логическое следствие в алгебре высказываний
   • 2.1.3. Эквивалентные формулы алгебры высказываний
   • 2.1.4. Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний
   • 2.1.5. Совершенные дизъюнктивные и конъюнктивные нормальные формы
   • Исчисление высказываний
   • Определение формального исчисления
   • Система аксиом и правил вывода
   • Теорема о дедукции в исчислении высказываний
   • Теорема о замене в исчисления высказываний
   • Свойства выводимых и эквивалентных формул исчисления высказываний
   • Основные эквивалентности исчисления высказываний
   • Полнота и непротиворечивость исчисления высказываний
   • Логика предикатов
   • Алгебраические системы
   • Пример 3. Построить подсистему алгебраической системы , порожденную множествомХ:
   • Формулы логики предикатов
   • Истинность формулы логики предикатов в алгебраической системе
   • 2.3.4. Логическое следствие в логике предикатов
   • 2.3.5. Эквивалентные формулы логики предикатов
   • 2.3.6. Пренексная нормальная форма в логике предикатов
   • X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
   • X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
   • Xφ≡X(φ)xφ≡X(φ)
   • 2.4. Исчисление предикатов
   • 2.4.1. Система аксиом и правил вывода
   • 2.4.2. Эквивалентные формулы исчисления предикатов
   • 2.4.3. Теорема Геделя о полноте. Непротиворечивость исчисления предикатов
   • Элементы теории алгоритмов
   • 2.5.1. Машины Тьюринга
   • 2.5.2. Примитивно рекурсивные функции
   • 2.5.3. Частично рекурсивные функции
   • Задания для домашних и контрольных работ
   • 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
   • 3.2. Логическое следствие в алгебре высказываний
   • Логическое следствие в логике предикатов
   • Частично рекурсивные функции
   • Список литературы
   • Основная литература
   • 4.2. Дополнительная литература
   • Содержание