Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

нельзя вывести в этой теории из остальных аксиом. Система аксиом является независимой, если каждую из них нельзя вывести из остальных. Теорема 4.6. Каждая из схем ^7, А2 ж A3 независима от остальных. Доказательство. Независимость ^7. Рассмотрим следующую таблицу. При всяком распределении значений О, 1, 2 для букв, входящих в формулу А, эта таблица позволяет найти соответствующее значение формулы А. Если формула А всегда принимают значение О, то она называется выделенной. Правило modus ponens сохраняет свойство формулы быть выделенной, так как, если^яА^ В принимают значение О, т.е. выделенные, то согласно таблице и В принимает значение О, следовательно, тоже выделенная. Покажем, что всякая аксиома, получающаяся по схеме А2 и A3, тоже выделенная. Для A3 имеем следующую таблицу. А В -А А^В 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 Г- в - А) гг- в А) В) 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 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 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 Из приведенной таблицы видно, что аксиома, полученная по A3, является выделенной. Аналогично можно показать выделенность А2. Если бы А1 была выводима в этой теории из аксиом А2 и A3, то она должна быть выделенной, так как применение MP к выделенным формулам приводит к выделенным. По А1 ш является выделенной, так как формула Ai (А2 Ai) 1 2 2 0 1 A i ^ ( А2 ^ Аi) принимает значение 2, когда ^7=1, А2=2. Таким образом, аксиома А1 не может быть выведена из аксиом А2 и A3, следовательно, она независима от них. Независимость А2. Рассмотрим следующую таблицу. 119 А В -А А^В 0 0 1 0 1 0 0 0 2 0 1 0