Понятия математической логики

ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Топоркова О.М.

КОНСПЕКТ ЛЕКЦИЙ И ПРАКТИЧЕСКИЕ ЗАДАНИЯ

(по материалам учебного пособия проф. Пономарева В.Ф.

«Математическая логика»)

Калининград 2012
Оглавление

1. Понятия математической логики. 4

2. Логика высказываний. 6

2.1. Алгебра высказываний. 7

2.1.1. Основные понятия. 7

2.1.1.1. Практика по формальному представлению сложных высказываний. 8

2.1.2. Таблицы истинности. 11

2.1.3. Законы алгебры высказываний. 14

2.1.4. Эквивалентные преобразования формул. 15

2.1.4.1. Практика по эквивалентному преобразованию формул. 15

2.1.5. Нормальные формы формул. 17

2.1.5.1. Практика по преобразованию формул к нормальным формам.. 19

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

2.2.1. Аксиомы исчисления высказываний. 22

2.2.2. Метод дедуктивного вывода. 24

2.2.2.1. Практика по дедуктивному выводу. 25

2.2.3. Метод резолюции. 33

2.2.3.1. Практика по методу резолюции. 34

3. Логика предикатов. 37

3.1. Основные понятия. 37

3.1.1. Практика по представлению предикатов. 39

3.2. Алгебра предикатов. 41

3.2.1. Логические операции. 42

3.2.1.1. Практика по записи сложных предикатных формул. 43

3.2.2. Законы алгебры предикатов. 46

3.2.3. Предварённая нормальная форма. 47

3.2.3.1. Практика по преобразованию предикатных формул к ПНФ.. 48

3.2.4. Сколемовская стандартная форма. 49

3.2.4.1. Практика по преобразованию предикатных формул к ССФ.. 50

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

3.3.1. Аксиомы исчисления предикатов. 54

3.3.2. Правила унификации предикатов. 55

3.3.3. Метод дедуктивного вывода. 56

3.3.3.1. Практика по предикатному дедуктивному выводу. 56

3.3.4. Метод резолюции. 60

3.3.4.1. Практика по предикатному методу резолюции. 61

4. Логика реляционная. 63

4.1. Основные понятия. 63

4.2. Реляционная алгебра. 66

4.2.1. Унарные операции. 67

4.2.2. Бинарные операции. 71

4.2.3. Правила реляционной алгебры.. 74

4.2.4. Практика по реляционной алгебре. 75

4.3. Реляционное исчисление. 78

4.3.1. Операции реляционного исчисления. 79

5. Нечёткая логика. 84

5.1. Нечёткие множества. 84

5.2. Нечёткая алгебра. 85

5.2.1. Операции нечеткой алгебры.. 86

5.2.2. Нечеткие множества отображений. 88

5.2.2.1. Практика по нечетким отображениям.. 89

5.2.3. Законы нечёткой алгебры.. 92

5.2.4. Свойства нечетких отношений. 93

5.2.4.1. Практика по свойствам нечетких отношений. 94

5.3. Нечёткое исчисление. 95

5.3.1. Нечёткие высказывания. 95

5.3.2. Нечеткие предикаты, переменные и постоянные. 96

5.3.3. Нечеткие формулы.. 97

5.3.4. Нечёткие правила вывода. 97

6. Модальная логика. 99

6.1. Структура современной модальной логики. 99

6.2. Модальная логика, использующая модальные понятия необходимости и возможности. 102

7. Темпоральная (или временнáя) логика. 103

8. Алгоритмическая логика. 105

8.1. Пропозициональная динамическая логика. 106

8.2. Логика Хоара. 108

Логика как наука впервые упоминается в трудах греческого философа Аристотеля (384-322г. до н.э.). С тех времен эта наука учит, как надо правильно рассуждать, правильно делать умозаключения и получать верные суждения. Поэтому было признано, что логика должна содержать счетное и конечное множество правил рассуждения для вывода новых, но верных высказываний. Основное правило, установленное еще в трудах Аристотеля, утверждает, что из двух известных и правильных суждений можно получить новое и верное суждение. Это правило получило название силлогизм.

Без серьезных изменений эта наука просуществовала более двадцати столетий. Традиционную логику стали подвергать критике лишь в конце XVII века, когда немецкий математик Г. Лейбниц (1646-1716) впервые ввел в логику математические символы и некоторые математические правила. Это позволило заменить некоторые выводы вычислениями. Дальнейшее развитие в логику внесли английский математик Д. Буль (1815-1864), американский математик Пост, немецкие математики Г. Фреге (1848-1925) и Д. Гильберт (1862-1943), итальянский математик Д. Пеано (1858-1932) и многие другие. Так возникла математическая логика как формальная система, носителем которой явились символы и последовательности символов, а правила математики позволили дать точное и удобное определение математического суждения.

Применение символов в логике позволило представить суждения философов в компактной и удобной форме, а применение правил математики - дать простые алгоритмы вывода суждений. Центральным понятием, введенным математикой, явилось доказательство: из положенного с необходимостью вытекает нечто, отличное от положенного.

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

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

В данном определении использованы три ключевые концепта:

1) Понятие – выражение естественного языка, в котором находят отражение какие-либо признаки предмета, процедуры, события или связей между ними, например, понятиями являются: «аудитория», «кафедра», «студент» и т.д.

2) Суждение – выражение естественного языка, в котором утверждается (или отрицается) факт существования предмета, процедуры, события или связей между ними. Над этими выражениями может быть задана логическая функция, принимающая значения «истина» или «ложь». Например, выражение «компьютер используется для обработки данных» является истинным суждением, а выражение «принтер – это устройство для хранения данных» является ложным суждением.

3) Умозаключение – выражение естественного языка, которое позволяет делать выводы о новых суждениях на основе известных. Например, выражение «если компьютер используется для обработки данных, то он может решать вычислительные задачи» выводит новый факт (суждение): «компьютер решает вычислительные задачи»

Математическая логика вместо выражений на естественном языке использует математические символы и математические правила, что позволило заменить правила рассуждения вычислениями. Можно сказать, что этот математический аппарат позволяет «научить» компьютер «рассуждать», имитируя рассуждения человека при решении логических задач. Такие возможности компьютера используются на практике для автоматизации трудно формализуемых задач управления, при решении которых недостаточно или принципиально невозможно использовать традиционные подходы к алгоритмизации, требующие знания входных и выходных параметров решения задачи, а также множества правил (алгоритм) преобразования входных данных в выходные. Именно этот формализм делает возможным создание систем искусственного интеллекта.

Структура математической логики:

1. Классическая логика. Является истиннозначной, т.е. любое суждение или умозаключение должно иметь одно из значений – истина или ложь. Включает разделы:

o Логика высказываний. Предмет исследования – естественно-языковые предложения (фразы), целиком подвергающиеся анализу. Включает подразделы: алгебра высказываний и исчисление высказываний;

o Логика предикатов. Предмет исследования – естественно-языковые предложения (фразы), элементы (отдельные слова или словосочетания) которых подвергаются анализу. Включает подразделы: алгебра предикатов и исчисление предикатов;

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

2. Неклассическая логика. Допускает континуальное множество истинностных значений высказываний. Включает разделы:

o Нечёткая логика (fuzzy logic) оперирует с высказываниями, истинность которых может принимать любые рациональные значения на интервале [0, 1]. Даже неточные знания позволяют с помощью логической системы делать достаточно близкие к истине заключения. Например, мнения экспертов при формировании базы знаний экспертных систем могут быть противоречивыми, но использование логической системы позволяет снять эти ограничения и обеспечить пользователя нужными знаниями. Поэтому нечёткая логика определила развитие экспертных систем и систем искусственного интеллекта. Включает подразделы: нечеткая алгебра и нечеткое исчисление;

o Модальная логика (modal logic) оперирует с так называемыми кванторами модальности высказываний (например, необходимо и возможно). Это определило развитие темпоральной (или временнóй) и алгоритмической логик:

§ Темпоральная логика (temporal logic) исследует модальные связи фактов во времени, описываемые в высказываниях: того, что «должно быть», и того, что «может быть» в прошлом и/или будущем. Эти знания позволяют с помощью логической системы организовать упорядоченное взаимодействие двух или нескольких процессов во времени. Например, параллельные вычисления на компьютере.

§ Алгоритмическая логика (algorithmic logic) показывает, что и как надо делать для достижения очередного результата. Это позволяет организовывать доказательство правильности программ, используя логическую систему и раскрывая семантику языка программирования.

Дата добавления: 2014-01-04