1. Нормальные формы исчисления высказываний

При разработке методов автоматического доказательства теорем необходимо все формулы, как логики высказываний, так и логики предикатов первого порядка, представить в некотором стандартном виде. В дальнейшем слова «первого порядка» будут опускаться, а логика предикатов считаться расширением логики высказываний за счет введения предикатов и кванторов общности  и кванторов существования . Простые высказывания в логике высказываний будем называть атомами, принимающими два значения: истина (И) или ложь (Л). Символы И и Л называются истинностными значениями.

Сложные высказывания (формулы) будут образовываться из простых с помо­щью логических связок  (не), & (конъюнкция),  (дизъюнкция),  (импликация),  (эквивалентность).

Любую формулу логики высказываний удобно представить в виде так называемой нормальной формы.

Атом или его отрицание будем называть литерой.

Говорят, что формула логики высказываний В представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет форму B = B₁ & B₂ & … & B_m, где каждая из B_i (i =  ) есть дизъюнкция литер. Например, В = (Х₁  Х₂) & (Х₁  Х₂  Х₃) & Х₃ представлена в КНФ.

Аналогично говорят, что формула логики высказываний В представлена в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет форму B = B₁  B₂  …  B_m, где каждая из B_i (i =  ) есть конъюнкция литер. Например, В = (Х₁ & Х₂ & Х₃)  (Х₁ & Х₂)  Х₃ представлена в ДНФ.

Любая формула исчисления высказываний может быть преобразована в нормальную форму с помощью следующего алгоритма.

Шаг 1. А  В = (А  В) & (В  А).

А  В = А  В.

Шаг 2. А = А.

законы Де-Моргана.

Шаг 3. А  (В & С) = (А  В) & (А  С) (для КНФ).

А & (В  С) = А & В  А & С (для ДНФ).

Пример 3.1. Получим КНФ для формулы (A  (B  C))  D.

(A  (B  C))  D = (A  B  C)  D = (A  B  C)  D = (A & B & C)  D = (A  D) & (B  D) & (C  D).

Пример 3.2. Получим ДНФ для формулы (A & B) & (A  B).

(A & B) & (A  B) = (A  B) & (A  B) = ((A  B) & A)  ((A  B) & B) = (A & B)  (B & A).

2. Нормальные формы исчисления предикатов

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

х₁, х₂, …, х_n, … – предметные переменные;

a₁, a₂, …a_k, … – предметные константы;

, , …, , …, , … – предикатные буквы;

, , …, , …, , … – функциональные буквы.

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

Правила конструирования термов:

1. всякая предметная переменная или предметная константа есть терм;

2. если f_i – функциональная буква и t₁, t₂, …, t_n – термы, то f_i(t₁, t₂, …, t_n) – терм;

3. других правил образования термов нет.

Например, х, у и 1 – термы, mult и plus – двухместные функциональные символы, тогда plus(y, 1) и mult(x, plus(y, 1)) – также термы.

Правила образования атомов (атомарных формул):

1. всякое переменное высказывание Х есть атом;

2. если P_i – предикатная буква, а t₁, t₂, …, t_n – термы, то P_i(t₁, t₂, …, t_n) есть атом;

3. других правил образования атомов нет.

Формулы логики предикатов конструируются по следующим правилам:

1. всякий атом есть формула;

2. если А и В – формулы и х – предметная переменная, то каждое из выражений А, А & В, А  В, А  В, А  В, хА и хА есть формула;

3. других правил образования формул нет.

Для того чтобы сократить количество скобок в формуле, используем правила силы операций:

1. связка  сильнее связок &, , , ;

2. связка & сильнее связок , , ;

3. связка  сильнее связок , ;

4. связка  сильнее связки .

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

Пример 3.3. Пусть P(x) и N(x) обозначают соответственно «х есть положительное целое число» и «х есть натуральное число». Тогда утверждение «Всякое положительное целое число есть натуральное число. Число 5 есть положительное целое число. Следовательно, 5 есть натуральное число» будет записано на языке логики предикатов следующим образом:

 х (P(x)  N(x))

P(5)

N(5)

Отметим, что для перевода предложений с русского языка на язык логики предикатов в общем случае не существует механических правил. В каждом отдельном случае нужно сначала установить, каков смысл переводимого предложения, а затем пытаться передать тот же смысл с помощью предикатов, кванторов и термов. Для иллюстрации того, что при переводе могут возникнуть трудности, приведем довольно несложные высказывания.

Пример 3.4.

1. Все люди – животные: y (S(y)  C(y)).

2. Следовательно, голова человека является головой животного:

x (y (S(y) & V(x, y))  z (C(z) & V(x, z))).

Здесь S(x) – «х – человек»;

C(x) – «х – животное»;

V(x, y) – «х является головой у».

Если перевод первого высказывания довольно прост, то с переводом второго возникают сложности, связанные с определением его семантики.

Формулы логики высказываний и логики предикатов имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов.

Пусть дана формула логики высказываний В и Х₁, X₂, …, X_n – атомы, в ней встречающиеся. Тогда под интерпретацией формулы логики высказываний В будем понимать приписывание истинностных значений атомам Х₁, X₂, …, X_n, т.е. интерпретация – это отображение I, сопоставляющее каждому атому X_i (i =  ) некоторое истинностное значение.

Под интерпретацией в исчислении предикатов будем понимать систему, состоящую из непустого множества D, называемого областью интерпретации и какого-либо соответствия, относящего каждой предикатной букве некоторое n-местное отношение в D (т.е. Dⁿ  {И, Л}), каждой функциональное букве – некоторую n-местную функцию в D (т.е. Dⁿ  D) и каждой предметной константе a_i – некоторый элемент из D. При заданной интерпретации предметные переменные мыслятся пробегающими область D этой интерпретации, а логическим связкам , &, , ,  и кванторам придается их обычный смысл.

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

Пример 3.5. Дана формула P(f₁(x₁, x₂), a). В качестве области интерпретации берем множество всех натуральных чисел N и интерпретируем P(x, y) как х  у, f₁(x₁, x₂) – как x₁ + x₂ и а = 5. Тогда P(f₁(x₁, x₂), a) представляет отношение х₁ + х₂  а, которое верно для всех упорядоченных троек <b₁, b₂, b₃> целых положительных чисел таких, что b₁ + b₂  b₃.

Пример 3.6. Дана замкнутая формула (т.е. формула без свободных переменных) х₁ х₂ А(х₂, х₁). Пусть область интерпретации – множество натуральных чисел N и А(х, у) интерпретируем как х  у. Тогда записанное выражение оказывается истинным высказыванием, утверждающим существование наименьшего целого положительного числа.

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

Если область интерпретации D конечна, то в принципе можно выяснить истинность или ложность любой формулы, перебрав все различные элементы множества Dⁿ, где n – число различных переменных, входящих в формулу. Однако, на практике D часто настолько велика или бесконечна, что о переборе не может быть и речи. Поэтому логический вывод оказывается просто необходим.

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

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

Кроме того, будем называть формулу выполнимой, если она истинна, по крайней мере, в одной интерпретации. Аналогично, формула называется опровержимой, если она ложна, по крайней мере, в одной интерпретации. Отсюда очевидно, что формула А общезначима тогда и только тогда, когда А невыполнима, и А выполнима тогда и только тогда, когда А опровержима.

Интерпретация, при которой истинностное значение формулы есть И, называется моделью этой формулы.

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

Сначала рассмотрим некоторые равносильные формулы в исчислении предикатов. Напомним, что две формулы F и Ф равносильные, т.е. F = Ф, тогда и только тогда, когда истинностные значения этих формул совпадают при любой интерпретации F и Ф. Для подчеркивания факта, что переменная х входит в формулу F, будем писать F[x], хотя F может содержать и другие переменные.

Имеем следующие пары равносильных формул:

x F[x]  Ф = x (F[x]  Ф);

x F[x] & Ф = x (F[x] & Ф);

x F[x]  Ф = x (F[x]  Ф);

x F[x] & Ф = x (F[x] & Ф) при условии, что переменная х не входит свободно в формулу Ф. Равносильность этих формул очевидна, так как формула Ф не содержит свободно х потому не входит в область действия кванторов.

Далее имеем:

x F[x] & x Ф[x] = x (F[x] & Ф[x]),

x F[x]  x Ф[x] =  x (F[x]  Ф[x]).

Доказательство этих двух равносильностей оставляем читателю.

Однако x F[x]  x Ф[x]  x (F[x]  Ф[x]),

x F[x] & x Ф[x]   x (F[x] & Ф[x]).

Действительно, взяв область интерпретации D = {1, 2} и положив при некоторой интерпретации F[1] = И и F[2] = Л, а Ф[1] = Л и Ф[2] = И, получим в левой части первого неравенства значение Л, а в правой – И. Аналогично доказывается и второе неравенство. В последних двух случаях производим переименование связанных переменных, т.е. x F[x]  x Ф[x] = x F[x]  у Ф[у] = x у (F[x]  Ф[у]), x F[x] & x Ф[x] = x F[x] & y Ф[y] = x y (F[x] &  Ф[y]) при условии, что переменная у не появляется в F[x].

Теперь дадим определение ПНФ. Говорят, что формула F логики предикатов находится в ПНФ тогда и только тогда, когда ее можно представить в форме ₁х_{1  2}х₂ …  _rx_r M, где _ix_i, i =  , есть либо x_i, либо x_i и М – бескванторная формула. Иногда называют ₁х_{1  2}х₂ …  _rx_r префиксом, а М – матрицей формулы F.

Например, формула F₁ = x y (Q(x, y)  P(f(x))  R(x, g(y))) находится в ПНФ, а формула F₂ = x (P(x)  y Q(x, y)) – не в ПНФ.

Существует алгоритм, преобразующий произвольную заданную формулу в равносильную ей формулу, имеющую пренексный вид. Алгоритм состоит из следующих шагов.

Шаг 1. Исключение логических связок  и . Многократно (пока это возможно) делаем замены: F  Ф = (F  Ф) & (F  Ф), F  Ф = F  Ф. Результатом этого шага будет формула, равносильная исходной и не содержащая связок  и .

Шаг 2. Продвижение знака отрицания  до атома. Многократно (пока это возможно) делаем замены:

 F = F,

(F  Ф) = F &  Ф,

(F & Ф) = F   Ф,

x F[x] = x (F[x]),

x F[x] = x (F[x]).

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

Шаг 3. Переименование связанных переменных. Многократно (пока это возможно) применяется следующее правило: найти самое левое вхождение переменной такое, что это вхождение связано (некоторым квантором), но существует еще одно вхождение этой же переменной; затем сделать замену связанного вхождения на вхождение новой переменной.

Шаг 4. Вынесение кванторов. Для этого используем следующие равносильности:

x F[x]  Ф = x (F[x]  Ф),

x F[x] & Ф = x (F[x] & Ф),

x F[x] & x Ф[x] = x (F[x] & Ф[x]),

x F[x]  x Ф[x] = x (F[x  Ф[x]),

₁x F[x]  ₂x Ф [x] = ₁x ₂y (F[x]  Ф[y]),

₁x F[x] &  ₂x Ф [x] =  ₁x ₂y (F[x]& Ф[y]), где , ₁ и ₂ – кванторы либо , либо .

После выполнения четвертого шага формула приобретает пренексный вид:

₁х_{1  2}х₂ …  _rx_r M, где _i, {i =  }  {,}.

Пример 3.7. Пусть F = x (P(x)  x R(x))  y Q(y). Применяя алгоритм, получаем следующую последовательность формул.

Шаг 1. x [(P(x)  x R(x)) & (P(x)  x R(x))]  y Q(y), x [(P(x)  x R(x)) & (P(x)  x R(x))]  y Q(y).

Шаг 2. x {[(P(x)  x R(x)) & (P(x)  x R(x))]}  y Q(y), x {(P(x)  x R(x))  (P(x)  x R(x))}  y Q(y), x {(P(x) & x R(x))  (P(x) & x R(x))}  y Q(y), x {(P(x) & x R(x))  (P(x) & x R(x))}  y Q(y), x {(P(x) & x R(x))  (P(x) & x R(x))}  y Q(y).

Шаг 3. z {(P(z) & x R(x))  (P(z) & x R(x))}  y Q(y), z {(P(z) & w R(w))  (P(z) & x R(x))}  y Q(y).

Шаг 4. zwxy {(P(z) & R(w))  (P(z) & R(x))  Q(y)}.

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

Формула F называется ‑формулой, если она представлена в ПНФ, причем кванторная часть состоит только из кванторов общности, т.е. F = x₁x₂…x_r M, где М – бескванторная формула.

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

Пусть формула F представлена в ПНФ.

F = ₁х_{1  2}х₂ …  _rx_r M, где _j  {, }, , j =  .

Пусть _i (1  i  r) – квантор существования в префиксе ₁х_{1  2}х₂ …  _rx_r. Если i = 1, т.е. ни один квантор общности не стоит впереди квантора существования, то выбираем константу с из области определения М, отличную от констант, встречающихся в М, и заменяем х₁ на с в М. Из префикса квантор существования ₁х₁ вычеркиваем. Если перед квантором существования _i стоит _j1, _j2, …, _jm кванторов общности, то выбираем m-местный функциональный символ f, отличный от функциональных символов в М, и заменяем x_i на f(x_j1, x_j2, …, x_jm), называемую сколемовской функцией, в М. Квантор существования _iх_i вычеркиваем из префикса. Аналогично удаляются и другие кванторы существования в ПНФ. В итоге получаем ‑формулу. Опишем алгоритм последовательного исключения кванторов существования.

Алгоритм Сколема.

Шаг 1. Формулу представить в ПНФ.

Шаг 2. Найти наименьший индекс i такой, что ₁, ₂, …, _i-1 все равны , но _i = . Если i = 1, т.е. квантор  стоит на первом месте, то вместо x₁ в формулу М подставить константу с, отличную от констант, встречающихся в М, и квантор  удалить из префикса. Если такого i нет, то СТОП: формула F является -формулой.

Шаг 3. Взять новый (i – 1)-местный функциональный символ f_i, не встречающийся в F. Заменить F на формулу x₁ x₂ … x_{i‑1  i+1}x_i+1 …  _rx_r M[x₁, x₂, …, x_i‑1, f_i(x₁, x₂, …, x_i‑1), x_i+1, …, x_r].

Шаг 4. Перейти к шагу 2.

Пример 3.8. Пусть F = xyzuvw (P(x, y)  R(z, u, v) & Q(u, w)). Применяя алгоритм Сколема, получаем следующую последовательность формул:

yzuvw (P(с, y)  R(z, u, v) & Q(u, w));

yzvw (P(с, y)  R(z, f(y, z), v) & Q(f(y, z), w));

yzv (P(с, y)  R(z, f(y, z), v) & Q(f(y, z), g(y, z, v))).

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

Теорема 3.1. Пусть формула F задана в ПНФ и преобразована в -формулу. Тогда F в пренексной форме логически невыполнима тогда и только тогда, когда невыполнима -формула F.

Аналогичная теорема имеет место и для общезначимых формул. Однако следует заметить, что если имеется выполнимая формула F, то может оказаться, что -формула для F будет невыполнимой. Действительно, пусть F = x P(x) и соответствующая ей -формула есть Р(с). Тогда, задавая область интерпретации D = {1, 2} и интерпретируя Р(1) = Л и Р(2) = И и положив с = 1, получаем, что F в пренексной форме выполнима, а -формула невыполнима в этой интерпретации.

Таким образом, алгоритм Сколема, сохраняя свойство невыполнимости (противоречивости), приводит произвольную формулу, имеющую пренексный вид, к -формуле.

Рассмотрим теперь преобразование бескванторной части (матрицы) к виду так называемых дизъюнктов (clauses). Дизъюнктом называется формула вида L₁  L₂  …  L_k, где L_i (i =  ) – произвольная литера. Дизъюнкт, не имеющий литер, называется пустым дизъюнктом (). По определению он всегда ложен.

Дизъюнкты, соединенные знаком &, образуют КНФ. Существует простой алгоритм равносильного преобразования произвольной бескванторной формулы в КНФ (см. также алгоритм получения КНФ и ДНФ для логики высказываний, данный ранее). Здесь дадим его в развернутом виде.

Алгоритм приведения к КНФ.

Шаг 1. Дана формула F, составленная из литер с применением связок & и .

Предполагается, что в формуле исключены скобки между одинаковыми связками, т.е. нет выражений вида

₁  (₂  ₃), (₁  ₂)   ₃,

или ₁ & (₂ & ₃), (₁ & ₂) &  ₃.

Шаг 2. Найти первое слева вхождение двух символов ( или ) (здесь предполагается, что скобка не является скобкой атома). Если таких вхождений нет, то СТОП: формула F находится в КНФ.

Шаг 3. Пусть первым вхождением указанной пары символов является (. Тогда взять наибольшие формулы ₁, ₂, …, _r, ₁, ₂ …, _s такие, что в F входит формула F₁ = ₁  ₂  _r  (₁ & ₂ & … & _s), которая связана с вхождением (. Заменить формулу F₁ на формулу (₁  ₂  …  _r  ₁) & (₁  ₂  …  _r  ₂) & … & (₁  ₂  …  _r  _s).

Шаг 4. Пусть первым вхождением является ). Тогда взять наибольшие формулы ₁, ₂, …, _r, ₁, ₂ …, _s такие, что в F входит формула F₁ = (₁ & ₂ & … & _s)  ₁  ₂ … _r, связанная с вхождением ). Заменить F₁ на формулу (₁  ₁  ₂  … _r) & (₂  ₁  ₂  …  _r) & … & (_s  ₁  ₂  …  _r).

Шаг 5. Перейти к шагу 2.

Пример 3.9. Преобразуем формулу F = P(x)  P(a)  ((R(x, y)  Q(y)) & P(x) & (R(x, a)  (Q(y) & P(a)))) в КНФ.

F = (P(x)  P(a)  R(x, y)  Q(y)) & (P(x)  P(a)  P(x)) & (P(x)  P(a)  R(x, a)  (Q(y) & P(a))) = (P(x)  P(a)  R(x, y)  Q(y)) & (P(x)  P(a)) & (P(x)  P(a)  R(x, a)  Q(y)) & (P(x)  P(a)  R(x, a)  P(a)) = (P(x)  P(a)  R(x, y)  Q(y)) & (P(x)  P(a)) & (P(x)  P(a)  R(x, a)  Q(y)) & (P(x)  P(a)  R(x, a)).

Здесь чертой подчеркнуты вхождения (. Кроме того, в алгоритме надо предусмотреть приведение подобных членов, а также всевозможные склеивания и поглощения.

Итак, последовательным применением алгоритма приведения к ПНФ, алгоритма Сколема и алгоритма приведения к КНФ с сохранением свойства невыполнимости любая формула F может быть представлена набором дизъюнктов, объединенных кванторами общности. Такую формулу будем называть формулой, представленной в Сколемовской стандартной форме (ССФ).

В дальнейшем формулы вида x₁ x₂ … x_r [D₁ & D₂ & … & D_k], где D₁, D₂, …, D_k –дизъюнкты, а x₁, x₂, …, x_r – различные переменные, входящие в эти дизъюнкты, будет удобно представлять как множество дизъюнктов S = {D₁, D₂, …, D_k}. Например, множеству дизъюнктов S = {P(x, f(x)), P(x, y)  R(x, g(y)), Q(x)  P(x, a)} соответствует следующая формула, представленная в ССФ: x y (P(x, f(x)) & (P(x, y)  R(x, g(y))) & (Q(x)  P(x, a))). И, наконец, когда говорят, что множество дизъюнктов S = {D₁, D₂, …, D_k} невыполнимо (противоречиво), то всегда подразумевают невыполнимость формулы x₁ x₂ … x_r [D₁ & D₂ & … & D_k], где x₁, x₂, …, x_r – различные переменные, входящие в дизъюнкты.

Задачи

I. Преобразовать:

1. A&BA&CB&CC=ABC

2. (AA&B A&B)&(A A&С A&B A&B&С)=AB

3. (ABC&(AB)B&(AD))&(AC&AA&B&C)=AC

4. (A&B(A&B)&CA&C)&(AC&AB&(AC))=AC

5. (AA&BB&C&DA&D)&(BB&DB&C&(AD))=

BD

6. (ABC)&A&B&C&(ABC)&(AB&C)&(A&B

C&D)=A&B&C

7. (AA&B&CC)&A&B&C&(A&CC&DD)&

(A&CB&D)=A&B&C

8. (AA&BB&(CD))&(B&DA&B&DA&DA&B)

&B&C=B&C

9. A&CA&C&DB&C&DA&(B&C)C&D=ACD

10. A&DA&B&DA&C&D(A&B)&DB&D=BD

11. A&BA&B&CA&B&CA&C=A

12. A&C&DC&DA&CA&C&D=CD

13. (A&CA&B&CA&B&CA&C)&(C&DC&D

A&B&C)=C

14. (A&BA&CA&BA&B&C)&

(A&BB&(A&C)A&C&DA&CD)=AB

15. ((A&B)(B&C)A&C)=A&B&C

16. (A&(A&BA&B)=AB

17. ((BC)(AC)A&B)=C&AC&B

18. (AB&(AC)B&(AC))=A&B

19. ((ABC)(AC)A&B)=A&CB&C

20. ((A&CB)BB&(AC))=A&BB&C

II. Представить в ДНФ и в КНФ следующие формулы:

1. (BA&C)(AC)

2. ((BC)A)(CB)A&B&C

3. ((A&CB&C)A&B)(AB)

4. (AA&B&C)(BC)&(AB)

5. ((CB)A)B&(CA)

6. ((A&BC)(ACA&B))A&C

7. (A(BAC))((BAC)A&C)

8. (BCA)((CB)A&C)

9. (A(CAB))(ABB&C)

10. ((BC)A)((CBA)B&C)

11. ((C&BA)C)(ACC)&B

12. ((AB&C)C)(AC~B)

13. ((ABC)AC)(A&CBA&B)

14. (C(ABC))(A&CBA&B&C)

15. (A&B(AB&CB))(ACBC)

16. (A(ACB))(ACB&C)

17. ((BCA)B)((BAC)(B&CA)

18.(A&B(ACB))(ACBC)

19. (B(ACC))A&(BA&C)

20. (A&C(BCA))(BCA&B)

III. Преобразовать в ПНФ следующие формулы:

1. x (P(x)  y Q(x,y))

2. x (y P(x,y)  (z Q(z)  R(x)))

3. xy (z P(x,y,z) & ((u Q(x,u) v Q(y,v)))

IV. Найти стандартную форму для следующих формул:

1. ¬ (x P(x)  yz Q(y,z))

2. x(¬E(x,0)  (y (E(y, g(x)) &z E(z, g(x))  E(y, z))))

3. ¬ (x P(x)  y P(y))