Файл: Matlog.doc

Методические указания соответствуют программе курса “Математическая логика и теория алгоритмов” для студентов специальности 22.02.03. Приведены краткие сведения по основам логики высказываний, логики предикатов, формальных аксиоматических теорий и теории алгоритмов. Контрольные задания включают упражнения по всем разделам. Приводятся указания к проведению лабораторных работ.

Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.

Рецензент:

Рассмотрено и одобрено на заседании кафедры ИТ-7

"__"____________2002 г. Зав. кафедрой __________О.М. Петров

Ответственный от кафедры за выпуск учебно-методических материалов

доц. Правоторова Н.А.

Содержание

Введение

Тема 1. Логика высказываний

1.1. Определение высказывания

1.2. Операции над высказываниями. Алгебра высказываний

1.3. Формулы логики высказываний. Равносильность формул

1.4. Запись сложного высказывания в виде формулы логики высказываний

1.5. Нормальные формы

1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости

1.7.Формализация рассуждений. Правильные рассуждения

Тема 2. Логика предикатов

2.1. Определение предиката. Кванторы

2.2. Формулы логики предикатов. Равносильность формул

2.3. Приведенные и нормальные формулы

2.4. Выражение суждения в виде формулы логики предикатов

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

Тема 3. Формальные аксиоматические теории (исчисления)

3.1. Принципы построения формальных теорий

3.2. Исчисление высказываний

3.3. Исчисление предикатов

3.4. Автоматическое доказательство теорем. Метод резолюций.

Тема 4. Нечеткая логика

4.1. Нечеткие множества

4.2. Нечеткие высказывания

4.3. Нечеткие предикаты

Тема 5 Алгоритмы

5.1. Определение алгоритма

5.2. Машина Тьюринга

5.3. Вычислимые по Тьюрингу функции

Указания к выполнению лабораторных работ

Контрольные задания по курсу “Математическая логика и теория алгоритмов”

Вопросы к экзамену

Список литературы

Краткие сведения о математиках

ВВЕДЕНИЕ

Логика - одна из самых древних наук. Как самостоятельная наука логика оформилась в трудах греческого ученого Аристотеля ( 384 – 322 г. до н. э.) и стала впоследствии называться формальной или Аристотелевой логикой.

С момента своего возникновения и в течение многих веков логика рассматривалась как часть философии. Математическая логика возникла на стыке двух наук: традиционной или философской логики и математики.

Идея построения логики на математической основе была впервые выдвинута Лейбницем (1646 – 1716). Окончательно как раздел математики математическая логика сформировалась в работах Д. Буля (1815 – 1864), Г. Фреге (1848 – 1925), Б. Рассела (1872 – 1970), Д. Гильберта (1862 – 1943).

Математическая логика используется при решении трех групп задач.

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

Во-вторых, это построение формальных теорий (исчислений) для различных математических объектов на основе аксиоматического метода.

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

Тема 1. Логика высказываний

1.1. Определение высказывания

Определение 1.1. Высказыванием называется повествовательное языковое предложение, относительно которого можно сказать истинно оно или ложно.

Пример 1.1.

Следующие утверждения являются высказываниями:

а) Москву основал Юрий Долгорукий.

б) В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов.

в) 2 2 = 5.

Высказывания а) и б) истинны, а высказывание с) ложно.

Пример 1.2.

Следующие утверждения не являются высказываниями:

а) a + b = 2.

б) Математика – интересный предмет.

В логике высказываний нас интересует не суть высказывания, а его истинность или ложность. Мы говорим, что существуют два истинностных значения: истина и ложь (И и Л). Двухэлементное множество {И, Л} есть множество истинностных значений. Высказывания будем обозначать большими буквами: A, B, C, X, Y,.. Выражение А = И означает, что высказывание А истинно, а X = Л означает, что высказывание X ложно.

1.2. Операции над высказываниями. Алгебра высказываний

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

Отрицанием высказывания А называется высказывание А, которое истинно тогда и только тогда, когда высказывание А ложно. Чтобы составить отрицание А достаточно в разговорном языке сказать “неверно, что А”.

Пример 1.3.

А = “Каспаров – чемпион мира по шахматам”.

А = “Неверно, что Каспаров – чемпион мира по шахматам”.

Отрицание определяется следующей таблицей истинности (таблица 1.1):

Таблица 1.1

А

Конъюнкцией двух высказываний А и B называется высказывание А&B, истинное тогда и только тогда, когда истинны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “и”.

Пример 1.4.

А = “Треугольник прямоугольный”.

B = “Треугольник равнобедренный”.

А&B = “Треугольник прямоугольный и равнобедренный”.

Конъюнкция определяется следующей таблицей истинности (таблица 1.2):

Таблица 1.2

А B

А&B

Л Л

Л И

И Л

И И

Дизъюнкцией двух высказываний А и B называется высказывание АÚB, ложное тогда и только тогда, когда ложны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “или”.

Пример 1.5.

А = “Иванов юрист”.

B = “Иванов экономист”.

АÚB = “Иванов юрист или экономист”.

Дизъюнкция определяется следующей таблицей истинности (таблица 1.3):

Таблица 1.3

А B

AÚB

Л Л

Л И

И Л

И И

Импликацией двух высказываний А и B называется высказывание А B, ложное тогда и только тогда, когда А истинно, а B ложно. Импликации соответствуют следующие выражения разговорной речи: “А влечет за собой B”; или “из А следует B”; или “если А, то B”.