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

4. При доказательстве независимости^! отА2 и A3 в исчисле­ нии высказываний введены выделенныеформулы (см. § 11 гл. 4). Составить программу на одном из языков программирования для выяснения, что формула исчисления высказываний, содержащая три пропозициональные буквы, является выделенной. Используя эту программу, получить, что аксиома, полученная по А 2 , является выде­ ленной. 5. При доказательстве независимости Л2 от^1 и A3 в исчисле­ нии высказываний введены гротескные формулы (см. § 11 гл. 4). Со­ ставить программу на одном из языков программирования для выяс­ нения, что формула ' исчисления высказываний, содержащая две пропозициональные буквы, является гротескной. Используя эту про­ грамму, получить, что аксиомы, полученные по А\ либо A 3 , являются гротескными. 6. Пусть в исчислении высказываний примитивными связками являются 1, &, V и =>. Формулы получены из пропозициональных букв с помощью этих примитивных связок. Каковы бы ни были формулы А, В я С, следующие формулы ~ суть аксиомы теории Li: А\: А^{В=>АУ, А2:(A=^(B=^Q)=^((A=^B)=>(A:=>C)); АЗ:А&В=^А; А4:А&В=>В', А5:А=>(В=>{А&В)); А6:A=>(AvB); А1:B=>iAvB); AS:(A=^Q=:>((B=>Q=>((A V B)=^Q); A9:(A=^B)=>i(A=>l B)=>1A); a10:11a=^a. Правилом вывода теории L; служит правило modusp o n e n s ( M P ) . Доказать для теории Lj, что: 1) формула А:=>А является теоремой; 185