Важной задачей математической логики являются преобразования логических формул. Эквивалентными или равносильными называют формулы, представляющие одну и ту же функцию. Стандартный метод установления эквивалентности двух формул состоит в следующем:
· по каждой формуле восстанавливается таблица истинности;
· полученные таблицы сравниваются по каждому набору значений переменных;
· если на всех наборах формулы дают одинаковые истинностные значения, они эквивалентны.
Пример: доказать эквивалентность формул 
.
Воспользуемся стандартным методом, т.е. построим таблицу истинности для всех трех формул.
Таблица 2.4.
Полученные результаты говорят о том, что формулы эквивалентны.
Как видно из примера, одна и та же логическая функция может быть задана формулами, включающими различные наборы логических операций. Существуют наборы логических операций, с помощью которых можно выразить любые другие логические операции. Такие наборы называются функционально полными системами, или базисами. Примерами таких базисов логических операций являются: 
, 
.
Наиболее хорошо изученным является базис 
. Формулы, содержащие только операции конъюнкции, дизъюнкции и отрицания называются булевыми. Следующие две теоремы, приведенные без доказательств, устанавливают правила перехода от одного базиса к другому.
