Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Формула алгебры предикатов называется тождественно ложной на множестве М[эм], если при всякой подстановке вместо предикатных переменных любых предикатов, заданных на М[эм], она превращается в тождественно ложный предикат.
Приведем примеры.
Представленная на слайде формула (5.26) является тождественно истинной на любом одноэлементном множестве M
1
[эм один]. Однако она не будет тождественно истинной на двухэлементном множестве M
2
[эм два].
Формула (5.27) является тождественно ложной на одноэлементном множестве M
1
[эм один]. Но она не будет тождественно ложной на двухэлементном множестве M
2
[эм два].
Слайд 172
Формулу алгебры предикатов называют общезначимой, или
тавтологией, если при всякой подстановке вместо предикатных переменных любых предикатов, заданных на произвольных множествах, она превращается в тождественно истинный предикат.
Формула общезначима в том и только в том случае, когда ее отрицание невыполнимо ни на одном множестве.
Формулу алгебры предикатов называют тождественно ложной, или
противоречием, если при всякой подстановке вместо предикатных переменных любых предикатов, заданных на произвольных множествах, она превращается в тождественно ложный предикат.
Рассмотрим пример общезначимой формулы.
Докажем, что формула алгебры предикатов (5.28) является тавтологией. Предположим, что формула превращается в ложное высказывание при подстановке в нее некоторых конкретных предикатов
P(x)[пэ от икс] и Q(x)[кю от икс], заданных на некотором множестве. Тогда левая часть формулы (5.28) будет истинной, а правая часть – ложной. На слайде это отмечено в утверждениях (5.29) и (5.30).

Из (5.30) следует, что найдется некоторый элемент a[а]из области определения предикатов, для которого P(a)[пэ от а] – истинное высказывание, а Q(a)[кю от а] – ложное высказывание. Обозначим этот факт как (5.31). Мы видим, что (5.31) противоречит (5.29). Следовательно, формула (5.28) является тавтологией.
Слайд 173
Рассмотрим основные равносильности алгебры предикатов.
При записи эквивалентные выражения будем соединять друг с другом знаком равенства. По определению операции навешивания кванторов являются самыми сильными из всех операций. Это позволяет уменьшить число скобок при записи выражений на языке алгебры предикатов. При отсутствии скобок первыми выполняются операции с кванторами.
Прежде всего отметим, что две эквивалентные формулы алгебры высказываний при замене входящих в нее пропозиционных переменных произвольными предикатными переменными превращаются в эквивалентные формулы логики предикатов.
На слайде представлены наиболее важные эквивалентности логики предикатов, не сводящиеся к равносильности алгебры высказываний. Все такие эквивалентности содержат кванторы.
Знак отрицания можно внести под знак квантора, сменив квантор на двойственный – формулы (5.32). Эти формулы носят названия законов де
Моргана для кванторов.
Одинаковые кванторы можно переставлять – формулы (5.33). При перестановке разных кванторов формулы не равносильны. В этом случае формула (5.37) является тавтологией.
Квантор существования разбивается на два по дизъюнкции – формула
(5.34). Квантор общности разбивается на два по конъюнкции – формула
(5.35). Заметим, что нельзя разбивать квантор общности на два по дизъюнкции. Нельзя разбивать квантор существования на два по конъюнкции.

Под номером (5.36) записаны формулы, отражающие законы пронесения кванторов через импликацию. Участвующая в них предикатная переменная Q[кю]не зависит от предметной переменной х[икс].
Слайд 174
Если формула алгебры предикатов не содержит символов импликации и эквиваленции, а присутствующие в ней знаки отрицания относятся только к предикатным переменным и высказываниям, то она называется приведенной формулой.
Приведенная формула, равносильная исходной формуле, называется приведенной формой.
Каждая формула алгебры предикатов имеет приведенную форму. Для получения приведенной формы заданной формулы необходимо:
1) избавиться от импликации и эквиваленции с помощью основных равносильностей алгебры высказываний;
2) перенести знак отрицания на элементарные формулы с помощью внесения отрицания под знак квантора и законов де Моргана;
3) избавиться от двойных отрицаний с помощью закона двойного отрицания.
Пример приведенной формулы алгебры предикатов – формула (5.38).
Пример нахождения приведенной формы формулы алгебры предикатов представлен преобразованиями (5.39).
Предварённой нормальной формой формулы алгебры предикатов называется такая ее приведенная форма, в которой кванторные операции либо вовсе отсутствуют, либо используются после всех операций алгебры высказываний.
Каждая формула алгебры предикатов имеет предварённую нормальную форму. Примеры предваренных нормальных форм – формулы (5.40) и (5.41).

Слайд 175
Рассмотрим еще один пример нахождения приведенной формы для заданной формулы алгебры предикатов. Исходная формула представляет собой эквиваленцию двух выражений, содержащих знаки кванторов.
На слайде показано, как с помощью равносильных преобразований эквиваленция сводится к конъюнкции, представляющей собой приведенную формулу. Сначала мы заменяем эквиваленцию на конъюнкцию двух импликаций на основании соответствующей равносильности алгебры высказываний. Затем переходим от импликаций к дизъюнкциям. На заключительном этапе мы используем правила внесения отрицания под знак квантора.
При приведении формул алгебры предикатов к предваренной нормальной форме часто оказываются полезными равносильности (5.42) и
(5.43). Участвующая в них предикатная переменная Q[кю]не зависит от предметной переменной х[икс].
Слайд 176
В заключение рассмотрим пример получения предваренной нормальной формы для заданной формулы алгебры предикатов.
Обратимся к формуле, приведенной на слайде. Она представляет собой конъюнкцию двух дизъюнкций, причем элементами каждой дизъюнкции являются выражения, содержащие кванторы.
Прокомментируем выполняемые преобразования.
Сначала мы переобозначим связанные предметные переменные, затем используем свойство пронесения квантора существования через дизъюнкцию, далее применяем свойство дистрибутивности конъюнкции относительно дизъюнкции. Затем вновь переобозначим переменную, выносим за скобки кванторы общности по переменным y[игрек] и z[зет], еще раз повторяем процедуру вынесения за скобки кванторов общности по указанным переменным. Последнее преобразование – повторное применение свойства дистрибутивности конъюнкции относительно дизъюнкции.