Введем на множестве M отношения следования и эквивалентности.
Формула B следует из формулы A (обозначается A 
B), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A.
Теорема 2.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула A 
B.
Доказательство. Пусть формула B следует из формулы A. Импликация A B ложна только на тех интерпретациях, на которых формула А истинна, а В ложна, что невозможно в силу условия.
Покажем обратное. Пусть A B – тождественно истинна, тогда если на некоторой интерпретации формула А истинна, то и формула В истинна на ней, что и означает A B.
Формула A эквивалентна формуле B (обозначается A º B), если они следуют друг из друга, то есть A B и B A. Легко показать, что это определение эквивалентно определению, введенному в п.1.
Теорема 2.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула A ~ B.
Доказательство аналогично доказательству теоремы 2.1.
Приведем список основных тавтологий, выражающих свойства логических операций.
1. Коммутативность:
X ÙY º Y ÙX, X ÚY º YÚX.
2. Ассоциативность:
(X ÙY)ÙZ º X Ù(YÙZ), (XÚY)ÚZ º XÚ(YÚZ).
3. Идемпотентность:
XÙX º X, XÚX º X.
4. Законы поглощения:
XÚ(X 
Y) º X, X (XÚY) º X.
5. Взаимная дистрибутивность конъюнкции и дизъюнкции:
X Ù(YÚZ) º (X ÙY)Ú(X ÙZ), XÚ (YÙZ) º (XÚY)Ù(XÚZ).
6. Свойства констант:
XÙ0 º Л, XÙ1 º X,
XÚ0 º X, XÚ1 º 1.
7. Законы де Моргана:
, 
.
8. Инволютивность:
.
9. Закон противоречия:
º 0.
10. Закон исключенного третьего:
º 1.
Эквивалентность большинства из этих формул непосредственно следует из определения операций или проверяется построением таблиц истинности.
Пусть U – некоторая формула, в которую входит переменная X или подформула А, что обозначается U (¼, X,¼) или U (¼, А,¼). Пусть В – некоторая формула. Запись U (¼, X,¼){ В // X } обозначает формулу, полученную из формулы U подстановкой формулы В вместо всех вхождений переменной X, а U (¼, А,¼){ В / А } – формулу, полученную из формулы U подстановкой формулы В вместо некоторых (в частности, вместо одного) вхождений подформулы А.
Теорема 2.3 (правило подстановки). Если U (¼, X,¼) – тавтология и В – любая формула, то U (¼, X,¼){ В // X } – тавтология.
Теорема 2.4 (правило замены). Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если U (¼, А,¼) и A º B, то U º V = U (¼, А,¼){ В / А }.
Например, так как A®B º 
, то (A®B)ÙC º ()ÙC.
Следствие. Если U~A и V~B, то:
1) U 
V º A B;
2) U 
V º A B;
3) U 
V º A B;
4) (U ~ V) º (A ~ B);
5) 
U º 
A.
Теоремы 2.3, 2.4 и ее следствие позволяют преобразовывать формулы, упрощая их, и доказывать эквивалентность формул.
Примеры.
1. Докажем 1-й из законов поглощения XÚ(X Y) º X.
.
При доказательстве использовано правило замены.
2. Упростить формулу 
.
Так как 
º X в силу подстановки 
в закон поглощения, тогда, используя правило замены получим
º 
.
Приведем еще несколько эквивалентностей, имеющих широкое применение.
11. 
.
12. 
.
13. Законы склеивания
, 
.
Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [ U ].
Определение. Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным.
Теорема 2.5. Каждый класс эквивалентности [ U ] может быть представлен приведенной формулой, т.е. для любой формулы U 
M существует приведенная формула V.
Доказательство теоремы проведём конструктивно, то есть определим порядок построения приведенной формулы.
1. Удаляются операции импликация и эквиваленция по формулам 11, 12.
2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.
3. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.
Таким образом, проверить эквивалентность формул, тождественную истинность и ложность формулы или упростить ее можно с помощью этого алгоритма.
Приведенная формула для данного класса эквивалентности не является единственной.
Задание. Упростить формулу 
.
Решение. º
º 
º 
º A.
Определение. Формула Ud называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот.
Теорема 2.6 (принцип двойственности). Пусть U (
) – приведенная формула, тогда
Ud () = U( 
).
Доказательство. Число логических операций в формуле U называется рангом формулы и обозначается r (U).Проведем доказательство индукцией по k = r (U).
10. k = 0. В этом случае U = Xi, следовательно, Ud = Xi º 
º Ø U (
).
2 0. Предположим, что теорема верна при k £ m.
3 0. Покажем, что она верна при k = m + 1.
Пусть U1 и U2 – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна.
Возможны следующие случаи
а) U = Ø U1;
б) U = U1 Ù U2;
в) U = U1 Ú U2.
Случай а) эквивалентен условию 10 и при нем теорема верна. В случаях б) и в) заменим в каждой из Ui конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): Ud = U 
Ú U 
и в): Ud = U Ù U .
В силу законов де Моргана и предположения индукции будем иметь в случае б):
Ud = U Ú U = (Ø U1 (
)) Ú (Ø U2 ()) º
º Ø (U1 () Ù U2 ()) = Ø U ().
В случае в) выкладки аналогичны. Теорема доказана.
Следствие. Если U – ТИ-формула, то Ud – ТЛ-формула.
Теорема 2.7. Если U º V, то Ud º Vd.
Доказательство. Если U º V, то (Ø U) º (Ø V). Значит, в силу теоремы 2.6, Ud (Х1, …, Хn) = Ø U () и Vd (Х1, …, Хn) = Ø V ().
Отсюда: Ud = (Ø U ()) º (Ø V ()) = Ø Vd. В силу транзитивности эквиваленции, получим Ud º Vd , что и требовалось доказать.