5.4 Равносильность формул лп

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

Перечислим основные, наиболее часто используемые случаи равносильности формул:

1.  х A(х)   у A( у),

2. х A(х)   у A( у),

3. x y A(х,y)   у x A(х,y),

4. х  у A(х,y)   у х A(х,y),

5.  х A(х)   x A( x),

6.  х A(х)   x A( x),

7.  х A(х)    x A( x),

8. х A(х)   x A( x),

9. х (A(х)&H)  х A(х) & H ,

10.  х (A(х) H)   х A(х)  H ,

11) х (A(х) B(x))  х A(х)  х B(x) ,

12)  х (A(х) & B(x))   х A(х) &  х B(x).

Доказательство равносильности (неравносильности) формул является частным случаем доказательства истин-ности (ложности) формул. Поскольку логическая связка ”” может быть выражена через прямую и обратную имплика-ции: (АВ)  (АВ)&(BA), то доказательство истинности операции ”” сводится к доказательству одновременной истинности прямой (АВ) и обратной (BA) импликаций.

Пример. Доказать равносильность формул х A(х)   x A( x).

Решение. Допустим, на некотором непустом множестве М и

сигнатуре  рассматриваемые формулы неравносильны. Эквивалентность двух формул F₁  F₂ ложна, когда ложна

208

хотя бы одна из импликаций F₁  F₂, F₂  F₁ . Это следует из тавтологии (ху)  ( (ху)  (ух)).

1. Допустим, ложна прямая импликация хA(х)xA(x). Из этого предположения вытекает одновременное выпол-нение двух условий: хA(х)=И, xA(x)=Л. Из первого после применения отрицания к обеим частям следует, что на всех элементах множества М предикат А(х) ложен. При этом отрицание A(x) на всех элементах множества М будет истинно. Но из второго условия следет, что существуют элементы множества М , на которых отрицание предиката А ложно. Полученное противоречие опровергает предполо-жение о ложности прямой импликации

2. Предположим, ложна обратная импликация: xA(x)  хA(х). Следовательно, одновременно выполняются два условия: xA(x)=И, хA(х)=Л. Из второго следует, что на всех элементах множества М предикат А(х) истинен. Из второго вытекает, что множестве М существуют элементы, на которых истинно отрицание предиката А(х). Следова-тельно, предположение о ложности обратной импликации также приводит к противоречию.

Поскольку прямая и обратная импликации тождест-венно истинны, то их произведение (тождественное равен-ство) также всегда истинно.

Задачи.

1. Доказать или опровергнуть равносильность формул:

а)  х A(х)   x A( x); б)  x A(х)&B   x(A( x) & B); в) B& x A(х)   x(B&A( x)); г) B x A(х)   x(B A( x)); д)  x A(х)B   x(A( x)B); е)  x A(х)B   x(A( x) B);

ж) B x A(х)   x(BA( x)); з) x A(х) B   x(A( x) B);

и)B x A(х) x(BA( x)); к)  x A(х) B   x(A(x)B); л) B x A(х)   x(B  A( x)); м)  x A(х)   xA( x) .

2. Доказать неравносильность формул xy A(х,y) и yx A(x,y).

209