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

Первые понятия, скоторых начинается какая-нибудь наука, должны быть ясныиприведены ксамому меньшему числу. Тогда тольконимогут служить прочным идостаточным основанием учения. Н. Лобачевский § 7. Исчисление высказываний (теория L) В качестве первого примера формальной аксиоматической тео­ рии рассмотрим исчисление высказываний - теорию L. 1 . Сш1воламитеорииL являются: 1, =^>,), ( и буквы А, с целыми положительными числами в качестве индексов; АъАъА^,... Символы !,=> будем называть примитивными связками, &А\,А2, Аз,...- пропози­ циональными буквами. 2. ФормулытеорииL определим индуктивным образом: 1) все буквы1,^2^5,... суть формулы; 2) если А я В формулы, то ("U) и (А=>В) тоже формулы; 3) выражение теории L является формулой только тогда, когда это следует из 1) и 2). Будем считать, что: А&В служит обозначением для формулы (1(^=>(1S))), A v B служит обозначением для формулы (("U)=>S), А=В служит обозначением для формулы (]((^=>В)=>(](В=>Л)))). Из определения формул видно, что всякая формула из L есть пропозициональная форма, построенная из пропозициональных букв А],А 2... с помощью связок 1 и rz>. Будем придерживаться тех же правил опускания скобок в фор­ мулах, что и раньше для пропозициональных форм. 3. Аксиомы теории L. Каковы бы ни были формулы А, В и С теории L, следующие формулы суть аксиомытеорииL: А1:A:=>(B=^A)i А2:(А=>(В=>С))=>((А=>В)=>(А=>С)); A3: (1 S=>l^)rz>((l5i^^)rz>S). 149