Действительно, формула P\to(Q\to R) превращается в ложное высказывание, если и только если \lambda(P)=1,\lambda(Q\to R)=0. Приведем примеры выражений, не являющихся формулами. Выражение Z есть пропозициональная переменная и потому на основании п. 1 определения 2.1 является формулой. Следовательно, по определению эквивалентности вся формула всегда превращается в истинное высказывание, т.е. является тавтологией.

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

Структура первого из последних высказываний выражается формулой X\lor\lnot X, а второго — формулой \lnot(X\land\lnot X). Данные формулы дают две схемы построения всегда истинных высказываний. В частности, любая тавтология алгебры высказываний вида F\to G соответствует некоторой общей схеме логического умозаключения.

Схема логического умозаключения, описываемая данной тавтологией, часто используется в математических доказательствах. Затем доказывается, что имеется некоторое такое утверждение В, для которого истинными являются оба утверждения \lnot A\to B и \lnot A\to\lnot B. Тогда утверждаем, что истинно высказывание A. В тавтологиях, относящихся к математической логике, заключительной логической связкой является эквивалентность \leftrightarrow.

Составление таблиц истинности для формул

Последний столбец таблицы, состоящий из значений истинности данной формулы, содержит лишь единицы. Это означает, что данная формула — тавтология. Приведем следующее доказательство, рассуждая о тех значениях, которые формула может принимать. В свою очередь, \lambda(P\land Q)=1 тогда и только тогда, когда \lambda(P)=1 и \lambda(Q)=1.

Доказанное означает, что правая и левая части эквивалентности одновременно превращаются либо в истинные высказывания, либо в ложные. Докажем для примера, что первый закон де Моргана (см. формулу 3.2, ж)) является тавтологией. Пусть A и B — произвольные конкретные высказывания. Предположим, во-первых, что высказывание \lnot(A\land B) истинно. Следовательно, формула тождественно истинна. Если в формулу F вместо символа X везде, где он входит в F, вставить формулу H, то получим новую формулу.

О значении тавтологий в логике

Получающуюся формулу обозначают S_{X,Y}^{H,G}F. В частности, вместо X может быть подставлено высказывание, которое само является конкретизацией формулы H(Z_1,\ldots,Z_k) на некотором наборе конкретных высказываний.

Основные тавтологии в математической логике

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

Логическое значение составного высказывания

Оно может быть определено, исходя из логических значений исходных высказываний A_2,A_3,A_7 и той схемы, по которой из исходных высказываний построено сложное высказывание. Например, по этой схеме» из высказываний A_4,A_8,A_5 построим высказывание «Если Сократ — человек и снег — белый, то 7<4".

Итак, символическая запись (X\land Y)\to Z является своего рода формулой. Конечно, более привычны формулы типа S=\pi r^2 (формула площади круга), E=mgh (формула потенциальной энергии тела) и им подобные. Тем не менее выражение (X\land Y)\to Z также можно считать формулой — формулой схемы конструирования составных высказываний из более простых.

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

Такую последовательность всех подформул данной формулы иногда называют порождающей последовательностью для данной формулы. Наличие такой последовательности у логического выражения служит критерием того, что выражение является формулой. Это свойство отличает формулы. Ясно, что процесс построения все более сложных формул может продолжаться безгранично.

Оно было бы формулой, если бы между формулами X и Y стоял один из знаков логических связок. То, что последнее выражение не является формулой, может сначала вызвать недоумение. Но после сопоставления его с п. 2 определения 2.1 отмечаем, что в последнем выражении недостает внешних скобок для того, чтобы считать его формулой. Итак, требование внешних скобок у формулы не является излишним формализмом.

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