Логическая эквивалентность

Идеи, лежащие в основе эквиваленции, прослеживаются в античной логике. Стоики, в частности Хрисипп, различали несколько видов условной связи (импликации) и выделяли связку, соответствующую современному бикондиционалу: сложное суждение считалось истинным, если оба его компонента либо истинны, либо ложны одновременно^[5]. В средневековой схоластике принцип взаимозаменимости эквивалентных терминов salva veritate (с сохранением истинности) стал краеугольным камнем теории суппозиции и логического следования.

Г. В. Лейбниц придал принципу salva veritate строгий характер, связав эквивалентность истин с тождеством понятий и взаимозаменимостью во всех возможных контекстах. Это заложило фундамент для понимания эквиваленции не только как совпадения истинностных значений, но и как интенсионального тождества.

Дж. Буль в работах The Mathematical Analysis of Logic (1847) и Laws of Thought (1854) записывал равенство классов уравнением (например, ${\displaystyle x=y}$), что стало прообразом современного логического равенства. В булевой алгебре эквиваленция выражается как ${\displaystyle x\cdot y+(1-x)\cdot (1-y)=1}$ или ${\displaystyle x\oplus y=0}$. Г. Фреге в Begriffsschrift (1879) ввёл знак равенства содержаний (${\displaystyle \equiv }$), который изначально имел интенсиональный смысл, но позже, в рамках его концепции функции и значения, трансформировался в чисто экстенсиональную трактовку: «одно и то же истинностное значение».

Окончательное закрепление материальной эквиваленции как самостоятельной связки произошло в Principia Mathematica А. Н. Уайтхеда и Б. Рассела (1910—1913): «две пропозиции эквивалентны, когда обе истинны или обе ложны»^[6]. Ч. С. Пирс и Э. Шрёдер развили алгебру импликации и эквиваленции, а Я. Лукасевич в 1920-х годах ввёл удобную префиксную (польскую) запись ${\displaystyle \mathrm {E} pq}$.

В 1938 году Клод Шеннон в своей магистерской диссертации показал, что булева алгебра может описывать работу релейных схем. С этого момента таблица истинности эквиваленции получила физическое воплощение в виде логического элемента XNOR («исключающее ИЛИ-НЕ»), который стал стандартным компонентом в цифровой технике, компараторах и схемах контроля чётности^[7].

Пусть ${\displaystyle A}$ и ${\displaystyle B}$ — высказывания (формулы логики высказываний). Эквиваленция ${\displaystyle A\leftrightarrow B}$ задаётся таблицей истинности^[8]:

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\leftrightarrow B}$
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

Иными словами, ${\displaystyle A\leftrightarrow B}$ есть отрицание исключающего или: ${\displaystyle A\leftrightarrow B\ \equiv \ \neg (A\oplus B)}$^[7][9].

Встречаются записи ${\displaystyle A\leftrightarrow B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\equiv B}$, ${\displaystyle A\sim B}$, в польской нотации Я. Лукасевича — ${\displaystyle \mathrm {E} pq}$, в некоторых англоязычных курсах — ${\displaystyle p::q}$. Знаки ${\displaystyle \equiv }$ и ${\displaystyle \Leftrightarrow }$ чаще резервируют для отношения равносильности, а ${\displaystyle \leftrightarrow }$ — для связки в объектном языке; единообразия нет, поэтому соглашение нужно оговаривать^[1][10]. В математическом тексте обычен оборот «тогда и только тогда» (англ. if and only if, iff).

Классически эквиваленция определима, например, так^[11]:

${\displaystyle {\begin{aligned}A\leftrightarrow B&\equiv (A\to B)\land (B\to A),\\A\leftrightarrow B&\equiv (A\land B)\lor (\neg A\land \neg B),\\A\leftrightarrow B&\equiv (A\land B)\lor \neg (A\lor B).\end{aligned}}}$

Запись ${\displaystyle B\to A}$ иногда обозначают ${\displaystyle A\leftarrow B}$ и называют конверсией (обратной импликацией); это термин ряда русскоязычных учебников. Равенство ${\displaystyle (A\leftrightarrow B)\equiv (A\to B)\land (A\leftarrow B)}$ верно, но не делает эквиваленцию «видом условного суждения»: в современной логике это отдельная связка.

Материальная эквиваленция не выражает причинности. Формула «снег бел тогда и только тогда, когда ${\displaystyle 2+2=4}$» истинна просто потому, что оба члена истинны; содержательной связи между ними нет. Смешение с причинно-следственной связью — ошибка.

На уровне истинностных значений ${\displaystyle \leftrightarrow }$ коммутативна и ассоциативна^[12]:

${\displaystyle A\leftrightarrow B\equiv B\leftrightarrow A,\qquad (A\leftrightarrow B)\leftrightarrow C\equiv A\leftrightarrow (B\leftrightarrow C).}$

Цепочка ${\displaystyle A\leftrightarrow B,\ B\leftrightarrow C}$ влечёт ${\displaystyle A\leftrightarrow C}$ (правило транзитивности, «гипотетический силлогизм» для эквиваленции). Нейтральный элемент — истина: ${\displaystyle A\leftrightarrow \top \equiv A}$; ${\displaystyle A\leftrightarrow \bot \equiv \neg A}$; ${\displaystyle A\leftrightarrow A}$ — тавтология; ${\displaystyle A\leftrightarrow \neg A}$ — противоречие.

В алгебре логики эквиваленция тесно связана с операцией сложения по модулю 2 (XOR, ${\displaystyle \oplus }$). Фактически, эквиваленция является её отрицанием:

${\displaystyle A\leftrightarrow B\equiv \neg (A\oplus B).}$

Если интерпретировать истину как ${\displaystyle 1}$, а ложь как ${\displaystyle 0}$, то эквиваленцию можно выразить арифметически над полем ${\displaystyle {\text{GF}}(2)}$ как:

${\displaystyle A\leftrightarrow B=1\oplus A\oplus B.}$

Отсюда следует, что эквиваленция нескольких переменных ${\displaystyle A_{1}\leftrightarrow A_{2}\leftrightarrow \dots \leftrightarrow A_{n}}$ истинна тогда и только тогда, когда количество ложных значений среди них чётно. Это свойство активно используется в алгоритмах контроля чётности и криптографии^[7].

В классической логике эквиваленция определяется через импликацию: ${\displaystyle (A\to B)\land (B\to A)}$. Это определение сохраняется и в интуиционистской логике, однако из-за отличий в трактовке импликации некоторые классические свойства (например, связь с отрицанием исключающего или) там не выполняются.

В многозначных логиках (например, логике Лукасевича или Клини) таблица истинности для эквиваленции обобщается: значение ${\displaystyle A\leftrightarrow B}$ определяется как минимальное из значений ${\displaystyle (A\to B)}$ и ${\displaystyle (B\to A)}$ или через функцию равенства истинностных степеней: ${\displaystyle 1-|v(A)-v(B)|}$^[13].

В системах натурального вывода (естественного дедуктивного исчисления) для эквиваленции существуют два базовых правила:

1. Правило введения ${\displaystyle \leftrightarrow }$: если из допущения ${\displaystyle A}$ выводится ${\displaystyle B}$, и из допущения ${\displaystyle B}$ выводится ${\displaystyle A}$, то можно заключить ${\displaystyle A\leftrightarrow B}$.
2. Правило удаления ${\displaystyle \leftrightarrow }$: из ${\displaystyle A\leftrightarrow B}$ и ${\displaystyle A}$ следует ${\displaystyle B}$ (аналог modus ponens); из ${\displaystyle A\leftrightarrow B}$ и ${\displaystyle \neg A}$ следует ${\displaystyle \neg B}$ (modus tollens для эквиваленции)^[1][15].