Материал: 5540

Решение. Допустим противное: на некотором множестве М имеется конкретный предикат А(х), такой, что данная формула превращается в

( у) А( у) . Из истинности первого следует, что высказывание А(а) ложно, а из истинности второго – что предикат А(у) тождественно истинный и, значит, для любого предмета из М, в том числе и для a M , высказывание А(а) истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.

Пример 4.7. Показать, что формула ( х) (Р(х) Р(х)) – тавтология. Решение. Допустим противное: на некотором множестве М имеется

конкретный предикат А(х), такой, что данная формула превращается в

Ложность дизъюнкции даёт ложность высказываний А(а) и А(a) . Из ложности первого следует истинность второго, а из ложности второго – истинность первого. Получаем противоречие, исключающее предположение о необщезначимости исходной формулы. Следовательно, она тавтология.

Пример 4.8. Докажите, что формула ( х) (Р(х) Q(x) P(x)) является тавтологией.

Решение. Предположим противное: на некотором множестве М имеются конкретные предикаты А(х) и В(х), такие, что данная формула

образом, требуется, чтобы существовала константа а в области М такая, что

91

А(а) ≡ 0 и А(а) ≡ 1, что невозможно. Следовательно, принятое

противоречием.

Задача 4.13. Докажите методом от противного, что следующие формулы являются тавтологиями:

Нахождение тавтологий является одной из важнейших задач логики предикатов, как и алгебры высказываний. При установлении общезначимости формулы таблицы истинности должны уступить место процессам рассуждения, так как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря, можно сделать бесконечным числом способов.

Рассмотрим наиболее важные тавтологии логики предикатов (ниже Р

– любая формула, не содержащая х).

Законы коммутативности для кванторов

92

Законы перенесения кванторов через конъюнкцию и дизъюнкцию

4.4 Эквивалентные соотношения. Префиксная нормальная форма

Две формулы, F и Н логики предикатов называются эквивалентными (равносильными) на множестве М, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определённых на М, формулы превращаются в эквивалентные предикаты. Если две формулы эквивалентны на любых множествах, то их будем называть просто эквивалентными (равносильными). Эквивалентность будем обозначать так: F ≡ H.

В логике предикатов эквивалентные соотношения позволяют выполнять корректные преобразования предикатных формул. Переход от одной эквивалентной формулы к другой называется эквивалентным (равносильным) преобразованием исходной формулы. В логике предикатов справедливы все эквивалентные соотношения логики высказываний, а также собственные эквивалентные соотношения, включающие связки и .

Формулы F и Н эквивалентны (F ≡ H) тогда и только тогда, когда формула F ↔ H является тавтологией (╞ F ↔ H).

Это замечание вместе с (4.1) – (4.15) позволяет указать наиболее важные примеры эквивалентных формул (ниже под Р будем понимать переменное высказывание или формулу, не содержащую х):

93

относительно дизъюнкции. Если в этих выражениях поменять местами

Поэтому в таких случаях эквивалентных преобразований применяют переименование переменной х в одном из предикатов на новую переменную:

Для анализа сложных суждений рекомендуется формулы приводить к тому или иному более удобному виду. Один из таких видов носит название приведённой формы.

Приведённой формой для формулы логики предикатов называется такая эквивалентная ей формула, в которой из операций алгебры высказываний имеются только операции отрицания, конъюнкции и дизъюнкции, причём знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Ещё одним удобным видом формулы, к которому её можно привести эквивалентными преобразованиями, является префиксная нормальная форма.

94

Префиксной нормальной формой (ПНФ) для формулы логики предикатов называется такая её приведённая форма, в которой все кванторы стоят в её начале, а область действия каждого из них распространяется до конца формулы, т.е. это формула вида

(k1x1) … (kmxm) (F(x1, …, xn)),

где ki есть один из кванторов или (i = 1, …, m), m ≤ n, причём формула F не содержит кванторов и является приведённой формулой (заметим, что кванторы в формуле могут отсутствовать вовсе).

Алгоритм приведения формулы к виду ПНФ

1. Исключите всюду логические связки ↔ и → по правилам:

F1 ↔ F2 ≡ (F1 → F2) (F2 → F1) ≡ ( F1 F2) ( F2 F1); F1 ↔ F2 ≡ F1 F2.

2. Представьте предикатную формулу таким образом, чтобы символы отрицания были расположены непосредственно над символами предикатов, воспользовавшись правилами (4.16) – (4.17), а также правилом:

3. Для формул, содержащих подформулы вида

( x)F1(x) ( x)F2 (x), ( x)F1(x) ( x)F2 (x),

ввести новые переменные, позволяющие использовать соотношения (4.22) – (4.25). 4. С помощью формул (4.18) – (4.25) получить формулы в виде ПНФ. Пример 4.9. Привести к ПНФ следующую предикатную формулу:

95