Задание 9. 9.1. Имеется формула исчисления предикатов

9.1. Имеется формула исчисления предикатов. Требуется: а) переименовать связанные переменные (если это необходимо), затем в полученной формуле указать свободные и связанные переменные, определить длину формулы, привести данную формулу (равносильным образом) к приведенной, нормальной форме, указать длину полученной формулы, б) определить, выполнимы или нет эти формулы, если считать что А(х, у) - предикат 2х = у, а В(х) - предикат: х - чётное число (причем оба предиката имеют в качестве интерпретации множество всех целых неотрицательных чисел).

($ х) А(х, у) Þ ù (" х) В(х) (1)

Решение:

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

1) при переносе квантора через отрицание - квантор меняет свой смысл;

2) в конъюнкции (дизъюнкции) двух выражений квантор, стоящий перед одним из них можно выносить за скобки, если в другое выражение не входит переменная, связанная этим квантором.

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

($ х) А(х, у) Þ ù (" z) В(z) (2)

Здесь x и z - связанные переменные, а у - свободная.

Длина формулы (2), определяющаяся общим числом символов предикатов, кванторов и логических символов, равна 5.

Теперь получим приведенную нормальную формулу, равносильную формуле (2). Для этого“убираем” символ Þ, исходя из тождества (А Þ В)º (ù А Ú В).

В результате, формула (2) равносильна формуле

ù ($ х) А (х, у) Ú ù (" z) B (z). (3)

Теперь, чтобы формула (3) стала приведённой, нужно, чтобы отрицания встали непосредственно перед предикатами. Так как перенос квантора через отрицание означает его замену на противоположный по смыслу, получаем:

(" х)(ù А (х, у)) Ú ($ z)(ù B (z)). (4)

Теперь формула (4) является приведённой. Для того, чтобы она стала нормальной, нужно, чтобы кванторы стояли в её начале. Так как от связанной переменной х переменная z не зависит, то получаем:

(" х)($ z)(ù А (х, у)) Ú ù B (z)). (5)

Формула (5) является приведённой нормальной; её длина равна 6.

б) Формула (5), также как и (1), является выполнимой (в данной интерпретации: А (х, у) - “ у = 2 х ”, В (х) - “ х чётно”). Более того, формула (5), а значит, и формула (1), тождественно истинны в этой интерпретации, так как $ z такое, что В (z) ложно (независимо от А (х, у)). Например, можно взять z = 3.