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

Заметим, что A l - АЗ являются схемами аксиом, т.е. указывают, как строятся аксиомы для произвольных формул А, В и С. В силу про­ извольности формул А, В н С схемы аксиом А1-А3 порождают бес­ численное множество аксиом. Легко убедиться, например, с помощью таблиц истинности, что каясдая аксиома, полученная по схемам А1-АЗ, является тавтологией. 4. Единственным правиломвыводатеорииL служит правило modusponens".В есть непосредственное следствие А и А=>В. Это пра­ вило сокращенно обозначают MP. Modusp o n e n s в переводе означает «правило отделения». Отме­ тим, что теорема 1.1 утвернодает, что если А и тавтологии, то и В тоже тавтология. Следовательно, правило modusp o n e n s из тавтологий получает тавтологию. Очевидно, правило MP означает, что А,А=рВ [-В. Таким образом, задали некоторую формальную аксиоматиче­ скую теорию, которая и называется исчислением высказываний. Рас­ смотрим некоторые доказательства в этой теории. Го, чтоначала существуют, необходгаю принять, прочее следует доказать. Аристотель § 8. Некоторые теоремы исчисления высказываний Проведем доказательство некоторых теорем исчисления выска­ зываний (теории L). Л е м м а 4 .1. j- А=>А для любой формулы А теории L, т.е., формула A:=i>A является теоремой теории L для любой формулы АmL. Доказательство. 1) (A=>{(A-=i'A)=>A))=^{{A=>(A=>Ay)=>(A^A)) - является аксио­ мой, так как получается по схеме А2, если положить В=А=>А и С-А; 150