Определение.

· Формула называется выполнимой, если на некотором наборе распределения истинностных значений переменных она принимает значение И.

· Формула называется тождественно-ложной или противоречием, если она ложна независимо от того, какие значения принимают встречающиеся в ней высказывательные переменные.

· Формула называется опровержимой, если при некотором распределении истинностных значений переменных она принимает значение Л.

Приведем утверждения, которые являются очевидными следствиями данных определений:

· A - тавтология тогда и только тогда, когда A не является опровержимой;

· A - тождественно-ложна тогда и только тогда, когда A не является выполнимой;

· A - тавтология тогда и только тогда, когда ØA - тождественно-ложна;

· A - тождественно-ложна тогда и только тогда, когда ØA - тавтология;

· A~B - тавтология тогда и только тогда, когда A и B - равносильны.

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

Перечислим наиболее важные тавтологии (A, B, C - произвольные формулы):

1. AÚØA (закон исключенного третьего или tertium nondatur);

2. AÉA;

3. AÉ(BÉA);

4. (AÉB)É((BÉC)É(AÉC)) (цепное рассуждение);

5. (AÉ(BÉC))É((AÉB)É(AÉC));

6. (A&B)ÉA; (A&B)ÉB;

7. AÉ(BÉ(A&B));

8. AÉ(AÚB); BÉ(AÉB);

9. (ØBÉØA)É((ØBÉA)ÉB);

10. ((AÉB)ÉA)ÉA (закон Пирса).

Каждую из этих тавтологий можно обосновать, например, составив таблицу и вычислив по ней значение формулы при произвольных значениях A, B и C.