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

1. Если G содержится в некотором множестве формул F и если G \-А, то F \-А. Доказательство. Пусть А имеет вывод А\,А2,..,,АП (4.1) из гипотез G. Если некоторая формула^, принадлежит G, то, очевид­ но, Ai е F . Следовательно, вывод (4.1) формулы А является выводом формулы А из гипотез F . Что и требовалось доказать. 2. G А тогда и только тогда, когда в G существует конечное подмножество Н такое, что Н \-А. Доказательство следует из определения вывода. 3. Пусть G [- Л и каждая формула В, принадлежащая G, выво­ дима из некоторого множества формул F , тогда F \-А. Доказательство. Пусть А имеет вывод AuA2,...,A „ (4.2) из гипотез G. По определению вывода некоторые А, из (4.2) могут принадлежать G , но каждая формула из G, имеет вывод из F . Заменим в (4.2) все А/, принадлежащие G, выводом А/ из F . В результате полу­ чим последовательность формул: которая уже является выводом А из F . Что и требовалось доказать. Как частный случай п.З имеем: 3'. ЕслиЛ [ - В я В \-С,тоА [-С.. 4. Если [-5 H G [-^,TO G [-5. Доказательство. Пусть В имеет вывод В\,В%...,В„ (4.3) из гипотез G иА , а формулаyi имеет вывод А],А2,--.,А„, (4.4) из гипотез G. В выводе (4.3) формулы В некоторые из Bt могут быть равны А . Заменим такие Д последовательностью (4.4). В результате получим последовательность формул сис2,...,сг, которая является выводом для В из гипотез G. Что и требовалось доказать. 148