Файл: Matlog.doc

в) xyA(x, y) = “Существует такое х, что для всякого у имеет место x > y” = Л (утверждается существование максимального числа на множестве натуральных чисел);

yxA(x, y) = “Для всякого y существует такое х, что x > y” = И;

xyA(x, y)  yxA(x, y).

г) A(х, у) = “Книгу х читал человек у”.

xyA(x, y) = “Каждую книгу читал кто-нибудь” = И (например автор книги читал свою книгу);

yxA(x, y) = “Существует человек, который читал все книги” = Л;

xyA(x, y) yxA(x, y).

6. Переименование связанных переменных.

Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора, получим формулу, равносильную A.

Пример 2.11.

A = xF(x)  xG(x).

Заменяя связанную переменную x на y в первом члене импликации и на z во втором, получим равносильную формулу:

B = yF(y)  zG(z).

A B.

7. В п. 4. была доказана дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции (тождества (2.7) и (2.8)). Этот факт означает, что в вышеуказанных случаях соответствующие кванторы могут быть вынесены за скобки и помещены впереди формулы, что и демонстрируют тождества (2.7) и (2.8).

Рассмотрим теперь случай, когда закон дистрибутивности, вообще говоря не применим. Сначала рассмотрим формулу xA(x)  xB(x) и применим правило переименования переменных. Получим

xA(x)  xB(x) xA(x)  yB(y). (2.11)

Так как yB(y) не зависит от x, справедлива равносильность (2.3), причем B = yB(y). Поэтому в соответствии с (2.3) можно вынести за скобки x:

xA(x)  yB(y) x(A(x)  yB(y)). (2.12)

Так как A(x) не зависит от y, справедлива равносильность (2.3), причем на этот раз B = A(x). Поэтому в соответствии с (2.3) можно вынести за скобки y :

A(x)  yB(y) y(A(x)  B(y)) (2.13)

Учитывая (2.11), (2.12), (2.13), получим:

xA(x)  xB(x)xy(A(x)  B(y)). (2.14)

Таким образом за скобки выносятся два квантора x и y, а выражение в скобках не содержит знаков квантора.

Проведем аналогичные выкладки для формулы xA(x) & xB(x):

xA(x) & xB(x)xA(x) & yB(y)x(A(x) & yB(y)) xy(A(x) & B(y)). (2.15)

Аналогично можно доказать следующие равносильности:

xA(x)  xB(x)xy(A(x)  B(y)). (2.16)

xA(x) & xB(x)xy(A(x) & B(y)). (2.17)

2.3. Приведенные и нормальные формулы

Определение 2.5. Формулы, в которых из логических символов имеются только символы &,  и причем символ встречается лишь перед символами предикатов, называются приведенными формулами.

Пример 2.12.

1. A(x)&B(x, y).

2. xA(x)  xB(x, y).

3. (A(x)&B(x, y)).

4. xA(x)  xB(x, y).

5. (xA(x)  xB(x, y)).

Первые две формулы в соответствии с определением являются приведенными, остальные не являются приведенными. В третьей формуле знак отрицания стоит перед формулой, а не перед символами предикатов. В четвертой формуле используется недопустимый для приведенной формулы символ импликации В пятой формуле знак отрицания стоит перед формулой и используется недопустимый для приведенной формулы символ импликации

Теорема 2.1. Для каждой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают.

Действительно, пользуясь равносильностями логики высказываний, можно получить формулу, содержащую только символы &,  и Применяя затем правило переноса квантора через знак отрицания, можно получить равносильную приведенную формулу. Такая приведенная формула называется приведенной формулой данной формулы. Строгое доказательство теоремы 2.1 содержится, например, в [6].

Пример 2.13.

Рассмотрим третью, четвертую и пятую формулы примера 2.12 и получим для них приведенные формулы.

Для третьей формулы по закону де Моргана:

 (A(x)&B(x, y)) A(x)  B(x, y).

Для четвертой формулы:

xA(x)  xB(x, y) xA(x)  xB(x, y) xA(x)  xB(x, y).

Для пятой формулы:

(xA(x)  xB(x, y)) xA(x)  xB(x, y)) xA(x)) & xB(x, y)) xA(x) & xB(x, y).

Определение 2.6. Приведенная формула называется нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди.

Пример 2.14.

1. xy(A(x)  B(x, y)) – нормальная формула.

2. x(A(x)) & yB(x, y) – приведенная формула, не являющаяся нормальной.

Теорема 2.2. Для каждой приведенной формулы существует равносильная ей нормальная формула.

Строгое доказательство теоремы 2.2 приведено в [6].

Алгоритм, позволяющий из приведенной формулы получить равносильную ей нормальную формулу, основан на правиле переименования связанных переменных и использовании равносильностей (2.3) – (2.8), (2.14) и (2.17).

Пусть Q – любой из кванторов , .

Воспользуемся равносильными преобразованиями (см.предыдущий раздел):

QxA(x)  B  Qx(A(x)  B) (2.18)

QxA(x) & B  Qx(A(x) & B). (2.19)

В тождествах (2.18), (2.19) формула B не зависит от x.

Q₁xA(x) & Q₂xB(x)  Q₁xQ₂z(A(x)&B(z (2.20)

Q₁xA(x)  Q₂xB(x)  Q₁xQ₂z(A(x)B( (2.21)

Тождества (2.18) и (2.19) есть обобщенная запись равносильных преобразований (2.3) – (2.6), а тождества (2.20) и (2.21) обобщают равносильности (2.14) – (2.17).

Мы видим, что тождества (2.18) – (2.21) позволяют поместить кванторы впереди формулы, что и требуется для нормальной формулы.

Пример 2.15.

Найти равносильную нормальную формулу для приведенной формулы: xyA(x, y) & xu(x, u).

В формуле yA(x, y) переменная y связана, поэтому yA(x, y) не зависит от y. Обозначим D(x) = yA(x, y).

В формуле uB(x, u) переменная u связана, поэтому uB(x, u) не зависит от u . Обозначим F(x) = uB(x, u).

Тогда

xyA(x, y) & xuB(x, u) = xD(x) & xF(x). (2.22)

Применим равносильность (2.20), имея в виду, что Q₁x есть x, а Q₂x есть x. Получим

xD(x) & xF(x) xz(D(x) & F(z)). (2.23)

Рассмотрим формулу D(x) & F(z) = yA(x, y) & uB(z, u). Применив два раза равносильность (2.19), получим

yA(x, y) & uB(z, u) y(A(x, y) & uB(z, u)) yu (A(x, y) & B(z, u)). (2.24)

Учитывая (2.21), (2.22), (2.23), получим окончательно

xyA(x, y) & xuB(x, u) xzyu(A(x, y) & B(z, u)). (2.25)

В тождестве (2.25) в левой части – исходная формула, а в левой части ее нормальная формула.

Теорема 2.3. Для каждой формулы существует равносильная ей нормальная формула.

Теорема 2.3. является очевидным следствием теорем 2.1 и 2.2.

Пример 2.16.

Найти равносильную нормальную формулу для формулы: xyA(x, y)  xuB(x, u).

1. Найдем вначале приведенную формулу, равносильную данной. Избавимся от символа 

xyA(x, y)  xu(x, u)(xyA(x, y))  xuB(x, u).

Применим равносильности (2.1) и (2.2) (перенос квантора через отрицание):

(xyA(x, y)) xyA(x, y),

Следовательно,

xyA(x, y)  xuB(x, u)xyA(x, y)  xuB(x, u). (2.26)

Правая часть тождества (2.26) – приведенная формула, равносильная данной.

2. Найдем теперь нормальную формулу, равносильную приведенной формуле xyA(x, y)  xuB(x, u). Проделаем преобразование этой формулы, аналогично предыдущему примеру:

xyA(x, y)  xuB(x, u)xyA(x, y)  zuB(z, u)

xz(yA(x, y)  uB(z, u))xzyu(A(x, y)  B(z, u)). (2.27)

В правой части (2.27) – нормальная формула, равносильная исходной.