- •Часть 1
- •Часть 1. Логика высказываний. Логика предикатов. Учебное пособие – Калининград: кгту, 2001, с.140
- •1.Логика высказываний
- •1.1 Алгебра высказываний
- •1.1.1 Логические операции
- •1.1.2 Правила записи сложных формул
- •1.1.3 Законы алгебры логики
- •1.1.4 Эквивалентные преобразования формул
- •1.1.5 Нормальные формы формул
- •Шаг 2. Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:
- •1.1.5.2 Алгоритм преобразования днф к виду сднф.
- •1.1.5.3 Алгоритм преобразования кнф к виду скнф.
- •1.2 Исчисление высказываний
- •1.2.1 Интерпретация формул
- •1.2.2 Аксиомы исчисления высказываний
- •1.2.3 Правила вывода
- •1.2.3.1 Правила подстановки
- •1.2.3.2. Правила введения и удаления логических связок
- •1.2.3.3 Правила заключения
- •1.3. Метод дедуктивного вывода
- •Принцип резолюции
- •1.4.1 Алгоритм вывода по принципу
- •Проблемы в исчислении высказываний
- •1.6 Описание высказываний на языке prolog
- •Расчетно-графическая работа
- •2. Логика предикатов
- •2.1 Алгебра предикатов
- •2.1.1 Логические операции
- •2.1.2 Правила записи сложных формул
- •2.1.3 Законы алгебры предикатов
- •2.1.4 Предваренная нормальная форма
- •2.1.4.1 Алгоритм приведения формулы к виду пнф
- •2.1.5 Сколемовская стандартная форма
- •2.1.5.1 Алгоритм Сколема
- •2.2. Исчисление предикатов
- •2.2.1 Интерпретация формул
- •2.2.2 Правила вывода
- •2.2.2.1 Правила подстановки
- •2.2.2.2 Правила введения и удаления кванторов
- •2.2.2.3 Правила заключения
- •2.2.3 Метод дедуктивного вывода
- •2.2.4 Принцип резолюции
- •2.3 Проблемы в исчислении предикатов
- •2.4 Логическое программирование
- •Расчетно-графическая работа
- •Алгоритм вывода по принципу резолюции, 69
- •Высказывание, 5, 78 Высказывательная функция, 85
Калининградский государственный технический
университет
В.Ф. Пономарев
математическая логика
Часть 1
Логика высказываний. Логика предикатов
Утверждено Ученым советом университета в качестве учебного пособия для студентов направления 552800 – Информатика и вычислительная техника и специальности 654600 – Информатика и вычислительная техника
Калининград
2001г.
ББК. 22
Л 55
В.Ф. Пономарев Математическая логика.
Часть 1. Логика высказываний. Логика предикатов. Учебное пособие – Калининград: кгту, 2001, с.140
Учебное пособие предназначено для студентов университета, изучающих “Математическую логику”. В нем изложены основные принципы формирования языка, основные правила дедуктивного вывода, основные механизмы доказательства истинности заключения в логике высказываний и логике предикатов. Все доказательства подкреплены множеством примеров. Каждый студент выполняет расчетно-графическую работу. В расчетно-графической работе по логике высказываний доказывается истинность заключения методами дедуктивного вывода и по принципу резолюции. В расчетно-графической работе по логике предикатов выполняется преобразование формулы к виду ПНФ и ССФ с последующей унификацией контрарных атомов дизъюнктов.
ВВЕДЕНИЕ
Родоначальником науки о логике является греческий философ Аристотель (384-322 г. до н.э.). Он, используя законы человеческого мышления, формализовал известные до него правила рассуждений. Лишь в конце XVII века немецкий математик Г. Лейбниц предложил математизировать формальные рассуждения Аристотеля, вводя символьное обозначение для основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал, что “мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления”.
Применение математики в логике определило новую науку – математическую логику. Математическое описание рассуждений позволило получить точные утверждения и эффективные процедуры в решении конкретных задач логики. Рассуждения в математической логике изучаются с точки зрения формы описания процесса, явления или события и формального преобразования этого описания. Такой процесс называют выводом заключения Иногда математическое описание рассуждений называют логико-математическим моделированием.
Основными объектами при изучения математической логики являются формальный язык логики и правила вывода. Формальный язык необходим для символьного описания процессов, явлений или событий и логических связей между ними. Правила вывода необходимы для формирования процедуры рассуждения. Для обеспечения вывода вводится система аксиом, формализующая весь механизм вывода заключения.
Математическое описание логики следует воспринимать, как некую формальную систему, оперирующую с символами по определенным правилам, облегчающим интерпретацию в реальном мире.
Выделяют несколько типов математических моделей формальной логики. Среди них можно выделить Логику высказываний, Логику предикатов, Логику нечетких множеств и отношений, Реляционную логику и др.
Логика высказываний (prepositional calculus) есть модель формальной системы, предметом которой являются высказывания или повествовательные предложения, взятые целиком без учета их внутренней структуры.
Логика предикатов (predicate calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутренних состава и структуры.
Логика нечетких множеств и отношений (fuzzi calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутреннеих состава и структуры и при нечетком (размытом) задании характерных признаков отдельных элементов или отношений между ними.
Логика реляционная (relation calculus) есть модель формальной системы, предметом которой являются отношения в виде множества однородных повествовательных предложений, существенно расширяющие логику предикатов.
Учебное пособие состоит из четырех частей, знакомящих студента с методами рассуждения и вывода заключения в четырех вышеуказанных логоках. По каждому разделу студент выполняет индивидуальное задание в виде расчетно-графической работы.