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

Всякую формулу, принимающую согласно этой таблице всегда значение О, назовем гротескной. Правило MP сохраняет гротескность, ибо если А и А ^ В гротескны, то по приведенной таблице формула В тоже гротескна. Всякая аксиома, получаемая по схеме ^7 и A3, гротескна. В гротескности А1 можно убедиться по следующей таблице. А (В А) 0 1 0 1 0 0 0 1 1 0 1 0 2 1 2 1 0 1 0 1 2 0 1 0 1 0 0 1 0 1 2 1 2 0 1 0 2 0 0 2 0 0 1 0 2 0 1 2 0 2 0 2 Аналогичным образом доказывается гротескность A3 (проделать самостоятельно). Если А2 выводима ш А1 и ^5, то она должна быть гротескной, ибо MP, примененное к гротескным формулам, дает гротескную. Но частный случай А2 не является гротескным: (Ai (А2 Аз) =^((Ai А2) (Ai A3)), 0 1 0 2 1 2 0 0 0 1 0 2 1 ибо принимает значение 2. Следовательно, А2 независима от^7 и A3. Независимость A3. Пусть А - произвольная формула и h{A) - формула, полученная из А удалением всех вхождений знака отрицания в А. Нетрудно убедиться, что для всякой аксиомы А, полученной по схемам А1 и А2, h{A) будет тавтологией. Очевидно, что h{A^B) есть h(A)^h(B). Если h(A^B) = h{A)^h{B) и h{A) - тавтологии, то и h{B) - тавтология, следовательно, правило MP сохраняет свойство А иметь в качестве h{A) тавтологию. Таким образом, всякая формула А, выводимая из А1, А2 с помощью MP, имеет в качестве h{A) тавтологию. Но h(( —A]^—A])^(( —А]^А])^А])) = (А]^А])^(( А]^А]) = А]), и эта последняя формула не является тавтологией. Следовательно, частный случай^5 - формула ( —Aj^—Aj)^(( —Aj^Aj) = Aj), не выводима из^7 яА2 с помощью MP. Теорема доказана. Разрешимость. Дедуктивная теория, в том числе и исчисление высказываний, является разрешимой, если в этой теории понятие теоремы 0 1 2 1 1 2 2 1 0 0 2 1 1 2 0 2 2 0 120