- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
16. Синтаксис и семантика языка логики предикатов
16.1. Понятие предиката
Предикат (от лат. «сказуемое») Р(x1,x2,...,xn) – функция, переменные которой принимают значения из некоторого произвольного множества М или множеств, возможно и бесконечных, а сама функция принимает 2 значения: «истина» или «ложь».
Р(x1,x2,...,xn):MnB, B:{0,1}.
То есть, предикат – это отображение n-ой степени произвольного множества в бинарное множество В, элементы которого принимают два значения: «истина» или «ложь».
Переменные называются предметными или пропозициональными.
Таким образом, понятие предиката является расширением понятия логическая функция.
Предикат от n переменных называется n-местным предикатом.
Вместо предметных переменных в предикат могут быть подставлены определенные значения из предметной области М, т.е. константы. Также в предикат могут быть подставлены некоторые n-местные функции:
f(x1,x2,...,xn):MnM.
Очевидно, что высказывание – нульместный предикат, свойство – одноместный предикат, n-местное отношение – n-местный предикат.
Предикат на конечных множествах может быть задан соответствующей таблицей (табл. 84) [24].
Пример.
P(x,y) «x<y»
Мх={1,2,3}
Му={2,4}
МхМуВ
Таблица 84
Предикат на конечных множествах
-
(x,y)
x<y
P(x,y)
1,2
1<2
1
1,4
1<4
1
3,2
3<2
0
2,4
2<4
1
3,4
3<4
1
2,2
2<2
0
Множество истинности данного предиката – множество, в котором предикат принимает значение «1».
16.2. Кванторы и связанные переменные
Все формулы логики высказывания являются частными случаями логики предикатов. Все операции логики высказывания переносятся в логику предикатов для связывания предметных букв. Дополнительно используются обозначения кванторов:
x F(х), т.е. «Все х обладают свойством F»;
x F(х), т.е. «Некоторые х обладают свойством F (но возможно и все)»,
где – квантор общности, – квантор существования.
Квантор общности и квантор существования называются двойственными.
Иногда используют обозначения квантора «Равно один»: !.
Если переменная связана квантором, то она называется связанной, иначе – свободной.
Например: x F(x,y), x F(x,y), здесь x – связанная переменная, y – свободная переменная.
16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
В качестве алфавита в логике предикатов используется латинский язык, как и в логике высказываний [25].
Вводятся следующие обозначения:
константы: a,b,c,d,e,... – строчные буквы из начала латинского алфавита;
логические константы (0 – ложь, 1 – истина);
предметные переменные: x, y, z, v, w,... – строчные буквы из конца латинского алфавита;
функции: f,g,h,... –строчные буквы из середины латинского алфавита;
предикатные символы: F, G, H, P, Q, ... – прописные буквы латинского алфавита;
символы логических операций и кванторов (, |, , ,,,…);
служебные символы, например, символы скобок ( [, ], {, }, (, )).
Символы функций и предикатов называют сигнатурой.
Функции и предикаты иногда снабжаются верхним индексом местности операции.
При определении формулы используется понятие «терм». Терм – объединяет понятия переменных и функций, к которым применяются предикатные буквы.
Всякая предметная переменная или константа – терм.
Если f – n-местная функция, а t1,t2,...,tn – терм, то fn(t1,t2,...,tn) – тоже терм.
Никакие другие выражения не являются термами.
Пример. f3(a,x,g2(x,y)) – это терм с трехместной функцией f, двухместной функцией g, a – константа.
Если F – n-местный предикат, t1,t2,...,tn – термы, то Fn(t1,t2,...,tn) – элементарная формула. Никакие другие выражения не являются элементарными формулами.
Элементарную формулу иногда называют атомарной или атомом.
Введем понятие формула:
всякая элементарная формула – это формула;
если F и Q – формулы, а х – предметная переменная, которая входит в F, то x F(x), x F(x), ,F Q, F Q, F Q, F Q – являются формулами.
Примеры.
P2(a,f1(x)) – формула;
Q1(x,g2(x,b)) – не формула, так как предикат Q должен быть одноместным;
P2(y,Q1(z)) – не формула, так как Q1(z) – не терм;
f1(g2(x,y)) – не формула, а терм;
F2(a,y)Q1(b) – формула.