1. Если а, (а  в) - тавтологии, то тавтологией является в.

Предположим , что В не является тавтологией. Тогда В принимает значение “ложь” при некотором наборе значений пропозиционных переменных. Но при этом же наборе значений переменных А имеет значение “истина”, так как А - тавтология (по условию). В таблице истинности такому набору значений А и В импликации (А  В) соответствует значение “ложь”. Получили противоречие с условием, что (А  В) - тавтология.

2. Если А - тавтология, содержащая пропозиционные переменные А₁, А₂ , ... , А_n , и В получается из А подстановкой формул Ф₁, Ф₂ , ... , Ф_n вместо А₁, А₂ , ... , А_n соответственно, то В есть тавтология, т.е. подстановка в тавтологию есть тавтология.

Доказательство: Обозначим А = А (А₁, А₂ , ... , А_n ), тогда В символически запишется В = А (Ф₁, Ф₂ , ... , Ф_n ). Нам нужно показать, что 1) В - формула; 2) В - тавтология. Первое следует из определения формулы и из того, что Ф₁, Ф₂ , ... , Ф_n - формулы. Пусть задан некоторый набор значений для пропозиционных переменных формулы В. Формулы Ф₁, Ф₂ , ... , Ф_n примут тогда некоторые значения х₁, х₂ , ... , х_n (каждое х_k есть И или Л). Если мы придадим значения х₁, х₂ , ... , х_n соответственно пропозиционным переменным А₁, А₂ , ... , А_n, то значение А совпадет с истинностным значением В при заданном распределении значений пропозиционных переменных, входящих в В. Так как А по условию тавтология, то В при этом наборе значений переменных примет значение “истина”. Таким образом, В всегда принимает значение И, т.е. является тавтологией.

Пример 2. Формула F=(A(BA)) является тавтологией. Действительно, если предположить ,что F принимает значение Л, то А - И, а ( В А) - Л. Но импликация (В   А) принимает значение Л только в том случае, когда В - И , а А - Л. Получили противоречие с тем, что А - И. Рассмотрим формулы Ф₁ = С& A и Ф₂ = ((С) А). Заменим в формуле F пропозиционную переменную А на Ф₁ , а В на Ф₂ , соответственно. Получим новую формулу F*= ((С& A)  (((С) А)  (С& A))), которая является тавтологией. Убедимся в этом, составив для нее таблицу истинности.

А	С	( С)	(( C)  A)	(С & A)	((( C)  A)(C& A))	F*
0	0	1	1	0	0	1
0	1	0	0	0	1	1
1	0	1	1	0	0	1
1	1	0	1	1	1	1

Если в формуле F заменить только А на Ф₁ , то получим еще одну тавтологию F** = = ((С& A)  (B  (С& A))).

А	В	С	(С& A)	(B  (С& A))	((С& A)  (B  (С& A))).
0	0	0	0	1	1
0	0	1	0	1	1
0	1	0	0	0	1
0	1	1	0	0	1
1	0	0	0	1	1
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	1	1	1

Полные системы связок. В этом разделе мы рассмотрим множество логических связок с точки зрения взаимозаменяемости его элементов. Наша задача, выбрать такое минимальное подмножество, с помощью которого можно будет определить все остальные логические связки. Такое подмножество называется полным.

Определение 3. Две формулы F и Ф ( F = Ф ) называются логически эквивалентными ( равносильными), если ( F  Ф ) - тавтология.

Из определения следует, что F равносильна Ф тогда и только тогда, когда в таблице истинности соответствующие столбцы совпадают.

Покажем, что формула (А  В) равносильна формуле ((А)  В).

А	В	А	(А  В)	((А)  В)
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

Равносильность ( В) = ((А)  В) показывает, что связку  можно исключить, заменив ее связками  и . Связку & можно исключить в силу равносильности (А & В) = ((А)  (В)). Так как (А  В) = ((А  В) & (В  А)), а связки  и & можно выразить через отрицание и дизъюнкцию, то связка  так же может быть исключена. Это показывает, что система связок {  ,  } полна.

Решение задач по теории множеств с помощью таблиц истинности. Если на выражения х  А, у  В посмотреть как на элементарные высказывания, то каждая формула теории множеств может быть заменена формулой логики высказываний. Это позволяет метод таблиц истинности применить к решению задач по теории множеств. Сведем этот способ решения задач к таблице.

Формулы теории множеств	Формулы логики
А  B А  В А \ В А  В = (А \ B) (B \ A)	А  В А  В ( A  B) ( A  B)  ( B  A)

Например, докажем равенство (А  В) = (А \ В ). Переведем это равенство в доказательство равносильности формул ((А)  В) = ( В), для чего воспользуемся таблицей истинности на предыдущей странице, показывающей их равносильность.