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

Доказательство. Предположим, что А есть тавтология и ~ пропозициональные буквы, входящие в А. При каждом распределении истинностных значений для букв В],В2,...,Вк имеем, в силу леммы 4.3, В\,В\...,В'к (А ' совпадает с А, так как.,4 всегда принимает значение И). Поэтому в случае, когда 5^. принимает значе­ ние И, получим b'i,b'2,...,b\-bbk 1"^ J а когда В^ принимает значение Л, имеем: в'ьв'г,...,в\.,,лвк\а. Отсюда по теореме дедукции получим соответственно В\.В'ъ....В\.,\-Вк:=>А, (4.23) В\,В\...,В\., 1-1 (4.24) По п.ж } леммы 4.2 имеем: |- (Bf=>A)-=>((] Bt=>A)=>A'). (4-25) Теперь по MF из (4.23) и (4.25) получим В\,В'^...,В\., (4.26) Далее снова по MP из (4.26) и (4.24) следует В\,Въ....В\., [-А. Таким образом, из 5'b5'2,...,5'i [гЛ получили 5 . , 5 V-i }-А, т.е. исключили В 'к. Точно также исключим В'^.] и так далее, после к таких шагов придем к Ya, т.е. А является теоремой, что и требовалось доказать. Можно доказать и полноту в узком смысле (см., например, [7]). Примем без доказательства. Независимость аксиом. Отдельная аксиома дедуктивной тео­ рии, в том числе и исчисления высказываний, является независимой, если эту аксиому нельзя вывести в этой теории из-остальных аксиом. Система аксиом является независимой, если каждую из них нельзя вывести из остальных. 163