Эквивалентность

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

Равно выполнимость обычно используется в контексте перевода формул, чтобы можно было определить перевод как правильный, если исходная и результирующая формулы равнозначны. Примерами переводов, включающих это понятие, являются сколемизация и некоторые переводы в конъюнктивная нормальная форма.

Перевод из логики высказываний в логику высказываний, в которой каждая бинарная дизъюнкция $a\; \vee \; b\; \{\backslash \; displaystyle\; a\; \backslash \; vee\; b\}$заменяется на $((a\; \vee \; n)\; \wedge \; (\neg \; n\; \vee \; b))\; \{\backslash \; displaystyle\; ((a\; \backslash \; vee\; n)\; \backslash \; wedge\; (\; \backslash \; neg\; n\; \backslash \; vee\; b))\}$, где $n\; \{\backslash \; displaystyle\; n\}$- новая переменная (по одной для каждой замененной дизъюнкции), - это преобразование, в котором выполнимость сохранено: исходная и полученная формулы равнозначны. Обратите внимание, что эти две формулы не эквивалентны: первая формула имеет модель, в которой $b\; \{\backslash \; displaystyle\; b\}$истинно, а $a\; \{\backslash \; displaystyle\; a\}$и $n\; \{\backslash \; displaystyle\; n\}$ложны (значение истинности модели для $n\; \{\backslash \; displaystyle\; n\}$не имеет отношения к значению истинности формулы), но это не модель второй формулы, в которой $n\; \{\backslash \; displaystyle\; n\}$должно быть истинным в этом случае.

1. ^М. Krötzsch (11 октября 2010 г.). Описание логических правил. IOS Press. ISBN 978-1-61499-342-1.