Основные отношения равносильности

Определение 9.7. Формулы А, В алгебры предикатов сигнатуры σ называются равносильными на алгебраической системе М(σ), если они принимают на М(σ) одинаковые значения при любом наборе значений предметных переменных, имеющих свободные вхождения переменных в А или В.

Из определения 9.7 видно, что равносильность тех или иных формул сигнатуры σ зависит от свойств алгебраической системы М(σ). Например, формулы "xA и $xA равносильны на любой одноэлементной системе, однако не равносильны в общем случае. Можно привести и менее тривиальные примеры. Изучение равносильностей, имеющих место для отдельных конкретных алгебраических систем, не отвечает целям и задачам математической логики как науки об общих закономерностях в рассуждениях. В связи с этим более ценным является следующее понятие равносильности.

Определение 9.8. Формулы алгебры предикатов сигнатуры σ называются равносильными, если они равносильны на любой алгебраической системе сигнатуры σ. Равносильность формул А, В, как и равносильность высказываний будем обозначать в виде А º В.

Отметим следующие очевидные свойства равносильности формул.

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

Если формула A¢ получена из А заменой некоторой подформулы В равносильной ей формулой В¢, то А¢ = А.

Приведем примеры равносильностей, называемых иногда основными равносильностями алгебры предикатов.

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

Так, зачастую вместо теоремы вида А ® В доказывается равносильное утверждение`А ®`В. При этом используется закон контрапозиции 13 (табл.9.1). Закон исключенного третьего 15 обычно используется при доказательствах от противного, когда для доказательства теоремы А опровергают утверждение`А и отсюда на основании равносильности`A Ú A º и делают вывод об истинности А. Правило силлогизма 17 позволяет сводить доказательства теоремы вида А ® С к доказательству цепочек более простых утверждений, например, А ® В, В ® С.

Таблица 9.1

№	Равносильности	Название
	AB º BA	Законы коммутативности
	A Ú B º B Ú A
	(AB)C º A(BC)	Законы ассоциативности
	(A Ú B) Ú C º A Ú (B Ú C)
	A(B Ú C) º AB Ú AC	Законы дистрибутивности
	A Ú BC º (A Ú B)(A Ú C)
	A(A Ú B) º A	Законы поглощения
	A Ú AB º A
	AA º A	Законы идемпотентности
	A Ú A º A
		Законы де Моргана
		Закон контрапозиции
		Закон двойного отрицания
	и	Закон исключенного третьего
	л	Закон противоречия
	(A ® B) & (B ® C) ® (A ® C) º и	Правило силлогизма
	"х"уА º "у"хА	Правила перестановки одноименных кванторов
	$х$уА º $у$хА
		Правила отрицания кванторов
	"x(A & B) º "xA & "xB	Законы дистрибутивности кванторов ", $ относительно операций & и v (соответственно)
	$x(A Ú B) º $xA Ú $xB
	ΔxA * B º δx(A * B), где δ — квантор " или $, * — операция & или v и формула В не содержит вхождений х
	δхА(х) º δуА(у), где δ — квантор " или $, А(х) — формула, не содержащая вхождений буквы у, а А(у) — формула, полученная из А(х) заменой всех свободных вхождений х на у

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

"х$уА и $у"хА (9.3)

не равносильны. Например, формула "х$у(x < y) истинна на N, а формула $х"у(x < y) ложна.

Аналогичные ошибки допускаются с использованием правила дистрибутивности кванторов $ и " относительно операций v и & соответственно. Можно показать, что формулы "х(A Ú B) и "хА Ú "xB, a также формулы $х (A & B) и $хА & $xB в общем случае не равносильны.

Заметим, что равносильность формул А, В эквивалентна истинности формулы (A ® B) & (B ® A) или двух формул A ® B, B ® A.

Однако практически зачастую бывает так, что из двух последних формул истинна только одна. Так, формулы (9.3) в общем случае не равносильны, но формула $у"хА -> "х$уА истинна на любой алгебраической системе.

Если формула А ® В истинна на системе М(σ), то при любом наборе значений предметных переменных, имеющих свободные вхождения в формулу А ® В, формула В принимает истинное значение всякий раз, когда истинным является значение А. В связи с этим говорят, что формула В является следствием формулы А.

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

Определение 9.9. Пусть А — формула алгебры предикатов, не содержащая операции «®». Формула, полученная из А заменой всех вхождений Ú на &, & на Ú, " на $, $ на ", называется двойственной к А и обозначается через А*.

Очевидно, что (А*)* = А, и потому формулы А и А* называются двойственными. Двойственными называются и взаимозаменяемые операции Ú и &, а также кванторы " и $.

Теорема 9.10. Пусть А — формула алгебры предикатов, p₁, …, p_s суть все различные элементарные формулы в А, т.е.: A = A(p₁, …, p_s). Тогда имеет место равносильность формул:

.

Доказательство. Докажем теорему индукцией по рангу r формулы А. При r = 0 ее утверждение верно. Допустим, что оно верно для любой формулы ранга r < n и пусть r(A) = n + 1. Возможны пять случаев:

A = A₁ & A₂,

A = A₁ Ú A₂,

A = "xA₁,

A = $xA₁,

.

Рассмотрим случай A = A₁ & A₂. Тогда, используя предположение индукции, закон де Моргана (см. табл.9.1 п.11) и общие свойства равносильности, получим:

В трех следующих случаях рассуждения аналогичны. Вместо равносильности 11 в них используются соответственно равносильности 12, 20, 21 (см. табл.9.1). В последнем случае утверждение теоремы следует непосредственно из предположения индукции. Теорема доказана.

Следствие 9.11. (Принцип двойственности.)

Для любых формул А, В алгебры предикатов:

A º B Û A* º B*.

Принцип двойственности позволяет вместо двух равносильностей A º B и A* º B* доказывать лишь любую одну из них.