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

Пусть A и B - две формулы и {X₁, X₂,…, X_n} - множество всех высказывательных переменных, входящих в формулу A и/или в формулу B. Будем называть эти формулы равносильными, если при любом распределении истинностных значений для переменных {X₁, X₂,…, X_n}, они принимают одинаковые значения. Равносильность формул A и B будем обозначать AºB.

Нужно различать символы ~ и º. Так, ~ является символом формального языка, с помощью которого строятся формулы, а символ º обозначает отношение на множестве формул.

Отношение равносильности есть отношение эквивалентности. Действительно, оно рефлексивно, так как для любой формулы A AºA; симметрично, так как для любых формул A и B, если A º B, то B º A; транзитивно, так как для любых формул A, B, C, если AºB и BºC, то AºC.

Основные равносильности. Для любых формул A, B, C справедливы следующие равносильности:

A&B º B&A (коммутативность &);

A&A º A (идемпотентность &);

A&(B&C) º (A&B)&C (ассоциативность &);

AÚB º BÚA (коммутативность Ú);

AÚA º A (идемпотентностьÚ);

AÚ(BÚC) º (AÚB)ÚC (ассоциативность Ú);

AÚ(B&C) º (AÚB)&(AÚC) (дистрибутивность Ú относительно &);

A&(BÚC) º (A&B)Ú(A&C) (дистрибутивность & относительно Ú);

A&(AÚB) º A (первый закон поглощения);

AÚ(A&B) º A (второй закон поглощения);

ØØA º A (снятия двойного отрицания);

Ø(A&B) º ØAÚØB (первый закон де Моргана);

Ø(AÚB) º ØA&ØB (второй закон де Моргана);

A º (A&B)Ú(A&ØB) (первый закон расщепления);

A º (AÚB)&(AÚØB) (второй закон расщепления).

A~B º (AÉB)&(BÉA) º (A&B)Ú(ØA&ØB);

AÉB º ØAÚB º Ø(A&ØB);

AÚB º ØAÉB º Ø(ØA&ØB);

A&B º Ø(AÉØB) º Ø(ØAÚØB).

Равносильности 16-19 показывают, что одни связки могут быть выражены через другие.

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

Таблица 8

A	B	C	B&C	AÚ(B&C)	AÚB	AÚC	(AÚB)&(AÚC)
И	И	И	И	И	И	И	И
И	И	Л	Л	И	И	И	И
И	Л	И	Л	И	И	И	И
И	Л	Л	Л	И	И	И	И
Л	И	И	И	И	И	И	И
Л	И	Л	Л	Л	И	Л	Л
Л	Л	И	Л	Л	Л	И	Л
Л	Л	Л	Л	Л	Л	Л	Л

Доказательство 12 без таблицы истинности.

Пусть на некотором наборе истинностных значений переменных формула Ø(A&B) принимает значение Л. Тогда формула A&B принимает значение И, а поэтому обе формулы A и B принимают значение И. Но в этом случае, очевидно, и правая часть равносильности 12 принимает значение Л. И наоборот, пусть формула ØAÚØB принимает значение Л. Тогда формулы ØA, ØB принимают значение Л, а формулы A, B- значение И. Очевидно, что и левая часть равносильности 12 принимает значение Л.

В силу транзитивности отношения равносильности, если A₁ºA₂, A₂ºA₃,…, A_k-1ºA_k, то A₁ºA_k. В таком случае для простоты будем записывать цепочку A₁ºA₂ºA₃º…ºA_k-1ºA_k.

Приведем правило, с помощью которого можно переходить от одних равносильностей к другим.

Лемма 2.1. Пусть AºB и C - произвольная формула. Тогда ØAºØB, A&CºB&C, C&Aº C&B, AÚCºBÚC, CÚAºCÚB, AÉCºBÉC, CÉAºCÉB, A~CºB~C, C~AºC~B.

Докажем например равносильность AÉCºBÉC. Пусть на произвольном наборе высказывательных переменных формулы A и B принимают одинаковое значение (скажем, s). Пусть t - значение C на этом распределении истинностных значений. Обе части рассматриваемой равносильности принимают одно и то же значение sÉt.

Лемма 2.2. Пусть AºB и C - формула, в которой выделено одно вхождение переменной X_i. Пусть C_A получается из C заменой этого вхождения X_i на A, а C_B - из C заменой того же вхождения X_i на B. Тогда C_AºC_B.

Докажем это индукцией по числу n логических символов в C.

Базис индукции. Если n=0, то формула C должна совпадать с X_i (так как в ней имеется вхождение переменной X_i). В этом случае C_A есть A, C_B есть B, C_AºC_B - не что иное, как AºB.

Индуктивный переход. Пусть лемма доказана для числа логических символов меньше n и пусть C - формула с n логическими символами. Она имеет вид ØD, или D&E, или DÚE, или DÉE, или D~E, причем в первом случае выделенное вхождение X_i содержится в D, а в остальных случаях - либо в D, либо в E, но не в D и E сразу. Рассмотрим, например, случай, когда C имеет вид DÉE и выделенное вхождение X_i содержится в D. Заменяя X_i в этом вхождении в D на A и B, получаем соответственно формулы D_A и D_B. Ясно, что C_A есть D_AÉE, а C_B есть D_BÉE. Так как в формуле D, меньше логических символов, чем в C, то D_AºD_B. Применим теперь лемму 2.1 в случае AÉCºBÉC, где в роли A выступает D_A и в роли B - D_B, в роли C - E. В результате получаем C_AºC_B. Другие случаи рассматриваются аналогично.

Теорема 2.1. (правило равносильных преобразований). Пусть C_A - формула, содержащая A в качестве своей подформулы. Пусть C_B получается из C_A заменой A в этом вхождении на B. Тогда, если AºB, то C_AºC_B.

Рассмотрим произвольную переменную X_i и получим формулу C из C_A заменой A на X_i. Будем считать это вхождение X_i в C выделенным. Тогда C, A, B, C_A, C_B удовлетворяют условиям леммы 2.2, а значит, C_AºC_B.

Теорема 2.2 (правило устранения логических символов É и ~). Для каждой формулы можно указать равносильную ей формулу, не содержащую логических символов É и ~.

В самом деле, опираясь на правило равносильных преобразований, можно в исходной формуле каждую подформулу вида A~B заменить на (A&B)Ú(ØA&ØB), а каждую подформулу вида AÉB на ØAÚB (см. равносильности 16 и 17).

Пример 2.4. Формула (X₁É(X₂ÉX₃)) ~ Ø(X₂ÉX₁) преобразуется следующим образом: (X₁É(X₂ÉX₃)) ~ Ø(X₂ÉX₁) º (X₁É(ØX₂ÚX₃) ~ (Ø(ØX₂ÚX₁)) º (ØX₁Ú(ØX₂ÚX₃)) ~ (Ø(ØX₂ÚX₁) º

((ØX₁Ú(ØX₂ÚX₃))&&Ø(ØX₂ÚX₁))Ú(Ø(ØX₁Ú(ØX₂ÚX₃))&Ø Ø(ØX₂ÚX₁)).