- •Математическая логика и теория алгоритмов
- •Воронеж 2011
- •1. Логика высказываний
- •1.1. Алгебра высказываний
- •Операции над высказываниями
- •1.1.2. Правила записи сложных формул
- •1.1.3. Таблицы истинности
- •1.1.4. Равносильность формул
- •1.1.5. Дизъюнктивные и конъюнктивные нормальные формы
- •1.1.6. Логическое следствие
- •1.2. Исчисление высказываний
- •1.2.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2.2. Метод резолюций в исчислении высказываний
- •1.2.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.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
2.2.3. Законы алгебры предикатов
Формулы называют равносильными, если при любых подстановках предметных постоянных они принимают одинаковое значение. Если две формулы F1 и F2 равносильны, т. е. F1F2, то они эквивалентны.
Если формула алгебры предикатов F имеет вхождением подформулу Fi, т. е. F( t1, t2,, Fi, ), для которой существует эквивалентная ей подформула Fj т.е. Fi = Fj, то возможна подстановка всюду в формулу F вместо формулы Fi подформулу Fj без нарушения истинности формулы, т.е.
F( t1, t2,, Fi, )F( t1, t2,, Fj, ).
Если в законах алгебры высказываний вместо имеющихся пропозициональных переменных всюду подставить предикаты так, чтобы вместо одной и той же пропозициональной переменной стоял один и тот же предикат, то получится закон алгбры предикатов.
Основные законы эквивалентных преобразований алгебры предикатов представлены в табл. 1.
Таблица 1
Наименование закона и правила |
Равносильные формулы FiFj |
коммутативности
|
xy(F2(x, y)) yx(F2(x, y))*); xy(F2(x, y)) yx(F2(x, y))*). *) только для одноименным кванторов. |
дистрибутивности |
x(F1(x))x(F2(x)) x(F1(x)F2(x))*); x(F1(x))x(F2(x)) x(F1(x)F2(x))**); *)для логической связки формул только с кванторами по одной переменной x. **)для логической связки формул только с кванторами по одной переменной x. |
идемпотентности {;} |
x(F(x)) x(F(x)) x(F(x)); x(F(x))x(F(x)) x(F(x)) |
исключенного третьего |
x(F(x)) 1, где {;} |
противоречия |
x(F(x)) 0, где {;} |
де Моргана |
x( ) ; x( ) |
двойного отрицания |
x(F(x)), где {;} |
свойства констант |
x(F(x))0x(F(x)); x(F(x))11; x(F(x))00; x(F(x))1x(F(x)), где {;}. |
Пример. Упростить формулу
Выполнить операцию отрицания формулы:
выполнить операцию отрицания формулы:
3) удалить логическую связку :
4) выполнить операцию отрицания формулы:
5) выполнить операцию отрицания формулы:
6) выполнить операцию отрицания формулы:
перенести квантор x3 влево:
Пример. Упростить формулу
Удалить логическую связку :
выполнить операцию отрицания формулы:
выполнить операцию отрицания формулы:
4) применить закон дистрибутивности по квантору x:
5) применить закон дистрибутивности к формуле:
6) применить закон исключенного третьего и свойство констант для логической связки :
7) применить закон де Моргана:
8) применить закон дистрибутивности по квантору x:
9) применить закон исключенного третьего:
применить свойство констант для логической связки : F=1, т. е. формула
является тождественно истиной.