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

Если бы А1 бьша выводима в этой теории из аксиом J 2 иJ 3 , то она должна быть выделенной, так как применение MP к выделенным формулам приводит к выделенным. Но ^1 не является выделенной, так как формула Aj=>(J2 => ^i) принимает значение 2, когда ^i = l, А2=2. Таким образом, аксиома Л не может быть выведена из аксиом А2 и A3, следова­ тельно, она независима от них. Независимость А 2 . Рассмотрим следующую таблицу. Всякую формулу, принимающую согласно этой таблице всегда значение О, назовем гротескной. Правило MP сохраняет гротескность, ибо если А и А=^В гротескны, то по приведенной таблице формула В тоже гротескна. Всякая аксиома, получаемая по схеме А1 и A 3 , гротескна. В гротескности А1 убеждаемся по следую­ щей таблице. Аналогичным образом дока­ зывается гротескность A3 (проделать само­ стоятельно). Если А2 выводима из ^ 1 и A 3 , то она должна быть гротескной, ибо MP, приме­ ненное к гротескным формулам, дает гро­ тескную. Но частный случай А2 не являет­ ся гротескным: (^1 => (а2 =>((^1 => а2) => (^5 => аз)) 0 1 0 2 1 2 0 0 0 1 0 2 1, ибо принимает значение 2. Следовательно, А2 независима от ^ 1 иA 3 . Независимость A 3 . Пусть А - произвольная формула и h ( A ) - формула, полученная из А удалением всех вхождений знака отрицания в А . Нетрудно убедиться, что для всякой аксиомы А , полученной А, => 1 2 2 0 1 А В У А^В 0 0 1 0 1 0 0 0 2 0 1 0 0 1 2 1 1 2 2 1 0 0 2 1 1 2 0 2 2 0 А (В ^ А) 0 О о о о 1 0 1 0 2 1 2 0 1 0 1 2 0 О о о 1 0 1 1 2 1 2 0 0 0 0 0 0 1 0 I 2 0 1 2 0 0 165