3.3 Равносильные преобразования формул.

Используя равносильности, приведенные выше, можно заменить часть формулы или всю формулу равносильной ей формулой. Это преобразование называют равносильным преобразованиемданной формулы.

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

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

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

Пример. Упростить формулу .

Запишем последовательность равносильных формул

Решение логических задач методами алгебры логики.

Суть применения методов алгебры логики к решению логических задач состоит в том, что, имея конкретные условия логической задачи, стараются записать их в виде формулы алгебры логике. В дальнейшем путем равносиль­ных преобразований упрощают полученную формулу. Простейший вид формулы, как правило, приводит к от­вету на все вопросы задачи.