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

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

Определение 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 * доказывать лишь любую одну из них.

Дата добавления: 2014-12-29