- •1. Исчисление высказываний
- •1.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2. Метод резолюций в исчислении высказываний
- •1.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.2.3. Условные обозначения и схемные соединения машин Тьюринга
- •3.2.4. Рекурсивные функции и вычисления на машинах Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
2.2. Алгебра предикатов
Если объект высказывания, т. е. о чем говорится в предложении, не определен, то это предложение называют высказывательной функцией. Аргументами высказывательной функции являются предметные переменные, которые обозначают строчными буквами латинского алфавита х, у, z Эта функция приобретет значение «и» (1) или «л» (0) только при подстановке в высказывательную функцию вместо предметных переменных их конкретных значений. Конкретные значения аргументов высказывательной функции называют предметными постоянными, которые обозначают строчными буквами латвийского алфавита а, в, с, .
Высказывательную функцию иначе называют предикатом (лат. praedicatum – логическое сказуемое).
Пример.
а) если на множестве натуральных чисел задать высказывательные функции или предикаты
Р1(x)= «x – простое число»,
P2(6, y)=«y меньше 6»,
P3(6, y, z)=«z есть частное от деления числа 6 на y»,
где z и y есть предметные переменные (целые числа), а 6 – предметная постоянная (целое число), то высказываниями будут
P1(3) = 1, P1(4) = 0,
P2(6,2) = 1, P2(6,7) = 0,
P3(6,2,3) =1, P3(6,2,5) = 0,
б) если на множестве имен индивидов, университетов и специальностей задать высказывательные функции или предикаты
P4(x)=«х – студент»,
P5(x, ВГТУ)=«тудент х университета ВГТУ»,
P6(x, y, системы автоматизированного проектирования)= «студент x университета y, обучающийся по специальности «системы автоматизированного проектирования», где x и y есть предметные переменные, а ВГТУ и «системы автоматизированного проектирования» – предметные постоянные, то высказываниями будут
P4(Петров) = 1, P4(Сидоров) =0,
P5(Петров, ВГТУ) = 1, P5(Сидоров, ВГТУ) = 0,
P6(Петров, ВГТУ, «системы автоматизированного проектирования») = 1,
P6(Сидоров, ВГТУ, «системы автоматизированного проектирования») = 0.
Множество предметных переменных Т1= {x, y, z,..} и постоянных Т2= {a, b, c,..}, функциональных символов Т3={f i1 ; fj2 ; f k3 ;..} и предикатных Т4=(P i1 ; P j2 ; P k3 ;..} с заданными над T={T1; T2; T3; T4} логическими операциями F={ , ,, ,, , } формируют алгебру предикатов, т.е.
Aп=<T, F>.
Любую предметную переменную и предметную постоянную называют терм и обозначают символом ti.
Если f ni есть n-местный функциональный символ и t1, t2, tn – термы, то f ni ( t1, t2, tn ) также есть терм, где n –число аргументов функции, i – числовой индекс функции.
Никаких иных термов нет.
Если P ni – n-местный предикатный символ и t1, t2, tn – термы, то F= Pni (t1, t2, tn ) – элементарная формула или атом. Предметные переменные, входящие в термы атома, являются свободными.
Если F1 и F2 формулы, то , (F1F2), (F1F2), (F1F2), также формулы.
В этих формулах предметные переменные также являются свободными.
Если F формула, a x – предметная переменная, входящая в атомы формулы F, то x(F) и x(F) также формулы. В этих формулах предметная переменная x среди множества термов формулы F является связанной.
Никаких иных формул нет.
Для формирования сложных формул используют вспомогательные символы ( и ) (скобки).