Правило подстановки, совокупность общезначимых формул

Определение общезначимости дает нам автоматическую процедуру установления того, является ли какая-либо формула тождественно истинной: достаточно вычислить ее истинностную таблицу и установить, что мы всегда получаем лишь значение t. Это удачный случай, и надо без колебания пользоваться этой процедурой, если возникают сомнения.

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

Вот один простой принцип. Определяя общезначимость, мы использовали истинностную таблицу, на входах которой фигурируют атомарные составляющие, чтобы полностью использовать анализ формулы на уровне исчисления высказываний. Но чтобы установить общезначимость, нам не всегда нужно до конца разлагать формулу на ее элементарные составляющие. Если, помещая на входах таблицы все значения некоторых (не обязательно атомарных) составляющих, мы будем на выходе всегда получать t, то мы можем быть уверенными, что эта формула общезначима. Например, P&Ø PÉ P&Ø P имеет вид AÉ A. Приведенная ниже таблица (а) , на входах которой помещены значения А, дает только t, следовательно, наша формула общезначима. Действительно, при вычислении строк таблицы (b), имеющей на входе Р (как предписывается определением общезначимости), первый этап вычисления состоит в нахождении значения формулы P& Ø P, т. е. А. Оставшаяся часть вычисления состоит в нахождении значения формулы в целом, исходя из значения А (подчеркнуто в таблице (b)); но это уже было проделано в соответствующей строке таблицы (а), и в результате получилось t.

        (a)                             (b)                      (c)

A   AÉA       P        P&Ø PÉ P &ØP       P     PÉP

 t    t  t  t        t          t  f  f t  t  t  f  f  t        t      t  t  t

 f    f  t  f        f          f  f  t  f  t  f  f  t  f        f      f  t  f

Таблица (а) совпадает с таблицей (с) с точностью до обозначений: вместо того чтобы говорить о построении таблицы для AÉ A с входом А, мы можем сказать, что проверяем общезначимость формулы PÉ P, а затем подставляем А, т. е. P&Ø P, вместо Р в PÉ P. Это рассуждение дает следующую теорему, где мы пишем “ |= Е” в качестве сокращения для выражения: “Е общезначима”.

Теорема 1. (Подстановка вместо атомов.) Пусть Е — формула, в которую входят только атомы Р1,…., Рn а Е* — формула, полученная из Е одновременной подстановкой формул А1, …,Аn вместо P1, …, Рn соответственно. Если |= Е, то |= Е*.

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

 

Логика - доступно для всех