Равносильность формул ЛП

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

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

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).

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

сигнатуре s рассматриваемые формулы неравносильны. Эквивалентность двух формул 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(х)=Л. Из второго следует, что на всех элементах множества М предикат А(х) истинен. Из второго вытекает, что множестве М существуют элементы, на которых истинно отрицание предиката А(х). Следова-тельно, предположение о ложности обратной импликации также приводит к противоречию.

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