Эквивалентное преобразование формулы — замена её части другой формулой без изменения реализуемой булевой функции. Основной инструмент — тождество \(F'=F''\): одинаковая подстановка формул вместо переменных в обе его части снова даёт тождество, а затем одну позиционную подформулу можно заменить эквивалентной другой частью. Это принцип эквивалентной
Последовательность таких локальных шагов образует выводимость по системе тождеств τ. Если из любой пары эквивалентных формул можно перейти от одной к другой преобразованиями по τ, система τ называется
Что важно запомнить
- Тождество — равенство двух эквивалентных формул.
- Одинаковая подстановка формул в обе части тождества сохраняет
- Принцип эквивалентной замены разрешает заменить позиционную подформулу одной частью подходящей подстановки тождества на другую.
- Один локальный шаг и цепочка шагов не меняют функцию всей формулы.
- Полнота системы тождеств означает возможность связать такими шагами любые две эквивалентные формулы данного
Тождество и подстановка
Пусть формулы \(F'(x_{1},\ldots,x_n)\) и \(F''(x_{1},\ldots,x_n)\) реализуют одну и ту же ФАЛ. Тогда запись \(F'=F''\) рассматривается как тождество. Если вместо каждой \(x_i\) одновременно подставить одну и ту же формулу \(G_i\) в обе части, получим новое тождество \(F'(G_{1},\ldots,G_n)=F''(G_{1},\ldots,G_n)\). Такая операция называется подстановкой
Принцип эквивалентной замены
Если внутри большой формулы F имеется позиционная подформула, совпадающая с одной частью некоторой подстановки тождества, её можно заменить другой частью. Полученная формула F̌ эквивалентна исходной. Важно слово «позиционная»: заменяется конкретное вхождение подформулы, а не обязательно все одинаково записанные фрагменты
Именно этот принцип превращает набор известных тождеств в механизм преобразования структуры. Коммутативность, ассоциативность, дистрибутивность, законы де Моргана, поглощение и другие тождества применяются не только к отдельным переменным, но и после подстановки к произвольным подформулам.
Выводимость и полнота
Если F′ можно получить из F последовательностью эквивалентных замен на основе системы τ, пишут, что соответствующее тождество выводимо из τ. Система τ называется полной, если для любых двух эквивалентных формул рассматриваемого класса тождество между ними выводимо из τ. Таким образом, эквивалентные преобразования отвечают не за проверку равенства таблиц истинности напрямую, а за конструктивный переход от одной структурной реализации к
Пример простыми словами
Пусть в формуле встречается фрагмент ¬(A∧B). Тождество де Моргана даёт ¬(x₁∧x₂)=¬x₁∨¬x₂. Подставив вместо x₁ и x₂ формулы A и B, можно заменить именно это вхождение на ¬A∨¬B. Вся большая формула останется функционально эквивалентной исходной.
Частые ошибки
- Применять тождество только к отдельным переменным. Подстановка позволяет использовать его для произвольных формул соответствующих аргументов.
- Считать эквивалентной заменой произвольную замену похожего фрагмента. Нужна подстановка доказанного тождества.
- Путать полноту системы тождеств с функциональной полнотой базиса. Это разные свойства.
