Математическая логика и теория алгоритмов

Т е о р е м а 4 . 6 . Каждая из схем А1, А2 и A3 независима от остальных. Доказательство. Независимость А \ . Рассмотрим следующую таблицу: При всяком распределении зна­ чений О, 1, 2 для букв, входящих в формулу А , эта таблица позволяет най­ ти соответствующее значение формулы А . Если формула А всегда принимает значение О, то она называется выделен­ ной. Правило modusponens сохраняет свойство формулы быть выделенной, так как если А и А=^В принимают значение О, т.е. выделенные, то со­ гласно таблице и В принимает значение О, следовательно, тоже выде­ ленная. Покажем, что всякая аксиома, получающаяся по схеме А2 и A 3 , тоже выделенная. Для ЛЪ имеем следующую таблицу, из которой вид­ но, что аксиома, полученная по A3, является выделенной. Аналогично можно показать выделенрюсть^2. (1 в => 1 Л) => «1 в => А) => В) 1 0 2 1 0 0 1 0 2 0 0 0 1 0 2 1 1 0 1 0 2 1 0 0 1 0 2 0 2 0 1 0 0 2 0 0 1 1 2 1 0 0 1 1 2 0 0 1 1 1 2 1 1 0 1 1 2 1 0 1 1 1 2 0 2 0 1 1 0 2 2 1 0 2 2 1 0 0 0 2 0 0 2 2 0 2 2 1 1 0 0 2 2 1 0 2 0 2 0 0 2 0 0 2 2 2 0 2 А В А=>В 0 0 1 0 1 0 1 2 2 0 0 0 0 1 2 1 1 2 2 1 0 0 2 2 1 2 0 2 2 0 164